Matrix equations over rings

The main purpose of this work is to establish necessary conditions and sufficient conditions for the existence of a solution of matrix equations whose coefficient matrices have elements belonging to the ring $\text{R=}\text{C}\text{[z}{}_1\text{,z}{}_2\text{,…z}{}_{\mathrm{n}}\text{]}$ of polynomials in n variables with complex coefficients and the ring $\text{R=}\text{R}\text{[z}{}_1\text{,z}{}_2\text{,…z}{}_{\mathrm{n}}\text{]}{}^{\mathrm{n}}$ of rational functions a(z₁,z₂,…z_n)b(z₁,z₂,…,z_n)^?1 with real coefficients and b(z₁,z₂,…,z_n)≠0 for all (z₁,z₂,…,z_n) in Rⁿ. Results obtained are useful in multidimensional systems theory and elsewhere.     

An optimal triangulation for second-order elliptic problems

Let Ω be a polygonal domain in $\text{R}{}^{\mathrm{n}}$, τ_h an associated triangulation and u_h the finite element solution of a well-posed second-order elliptic problem on (Ω, τ_h). Let M = {M_i}^{p + q}_{i = 1} be the set of nodes which defines the vertices of the triangulation τ_h: for each i,$\text{M}{}_{\mathrm{i}}\text{= {x}{}_{\mathrm{i}}{}^{\mathrm{l}}\text{¦1 ? l ?n}}$ in Rⁿ. The object of this paper is to provide a computational tool to approximate the best set of positions M? of the nodes and hence the best triangulation $\text{}\text{?}\text{gt}{}_{\mathrm{h}}$ which minimizes the solution error in the natural norm associated with the problem.The main result of this paper are theorems which provide explicit expressions for the partial derivatives of the associated energy functional with respect to the coordinates x_i^l, 1 ? l ? n, of each of the variable nodes M_i, i = 1,…, p.     

Mathematical foundations of Bézier's technique

Bezier's method is one of the most famous in computational geometry. In his book Numerical control Bezier gives excellent expositions of the mathematical foundations of this method. In this paper a new expression of the functions {f_n,i(u)}

$\text{f}{}_{\mathrm{n,i}}\text{(u)=1?}\text{Σ}\text{p=0}\text{i?1}\text{C}{}^{\mathrm{p}}{}_{\mathrm{n}}\text{u}{}^{\mathrm{p}}\text{(1?u)}{}^{\mathrm{n?p}}\text{(i=1,2,…,n)}$

is obtained.Using this formula, we have not only derived some properties of the functions {f_n,i(u)} (for instance $\text{f}{}_{\mathrm{n,n}}\text{(u) < f}{}_{\mathrm{n,n?1}}\text{(u)<...<f}{}_{\mathrm{n,1}}\text{(u)}\text{u}\text{? [0, 1]}$ and functions {f_n,i(u)} increase strictly at [0, 1] etc) but also simplified systematically all the mathematical discussions about Bezier's method.Finally we have proved the plotting theorem completely by matrix calculation.     

Normal forms for nonautonomous difference equations

We extend Henry Poincaré's normal form theory for autonomous difference equations χ_{k + 1} = f(χ_k) to nonautonomous difference equations χ_{k + 1} = f_k(χ_k). Poincaré's nonresonance condition $\text{α}{}_{\mathrm{j}}\text{-П}{}^{\mathrm{n}}{}_{\mathrm{i=1}}\text{=1α}{}^{\mathrm{qi}}{}_{\mathrm{i}}\text{≠0}$ for eigenvalues is generalized to the new nonresonance condition λ_j∪$\text{α}{}_{\mathrm{j}}\text{⊔П}{}^{\mathrm{n}}{}_{\mathrm{i=1}}\text{α}{}^{\mathrm{qi}}{}_{\mathrm{i}}\text{≠0}$ for spectral intervals.     

Crosscorrelation between linearly and nonlinearly distorted versions of a given signal

A given deterministic signal x(.) is distorted by passing it through a linear time-invariant filter and also by subjecting it to the action of an instantaneous nonlinearity. The resulting time crosscorrelation of the two distorted versions of the original signal is expressed by the function

$\text{R}{}_2\text{(s)?∫}{}_{\mathrm{?\infty }}{}^{\mathrm{\infty }}\text{?∫}{}_{\mathrm{?\infty }}{}^{\mathrm{\infty }}\text{g[x(t)]k(t?t′)x(t?s)dt dt′}$

, where x(.) is the given signal, k(.) is the nonnegative definite impulse response of the linear filter, and g(.) is the output-input characteristic of the zero-memory nonlinear device. The problem considered is that of determining conditions on the pair (x,g) such that R₂(s) ? R₂(0) for all s and any choice of nonnegative definite filter function k; the principal result is the formulation of a necessary and sufficient condition for R₂ to have a global maximum at the origin. In particular, the peak value occurs at the origin if and only if $\text{G}{}_{\mathrm{x}}{}^1\text{(ω)X(ω)}$ is real and nonnegative for all ω ? 0, where G_x(.) and X(.) are the Fourier transforms of g[x(.)] and x(.), respectively. An equivalent condition is that the correlation function

$\text{R}{}_2\text{(s)?∫}{}_{\mathrm{?\infty }}{}^{\mathrm{\infty }}\text{g[x(t)]x(t?s)dt}$

, previously studied by Richardson, be nonnegative definite.Several examples are given, and it is shown that, unlike the case for R₁(.), monotonicity of g(.) is not a sufficient condition for R₂(.) to have a global maximum at s = 0 independently of the choice of filter characteristic k. Certain extensions of these results are given for the case when x(.) is a Gaussian random input.     

Membership problems for data dependencies in relational expressions

In relational databases, a query can be formulated in terms of a relational algebra expression using projection, selection, restriction, cross product and union. In this paper, we consider a problem, called the membership problem, of determining whether a given dependency d is valid in a given relational expression E over a given database scheme R that is, whether every instance of the view scheme defined by E satisfies d (assuming that the underlying constraints in R are always satisfied).Consider the case where each relation scheme in R is associated with functional dependencies (FDs) as constraints, and d is an FD. Then the complement of the membership problem is NP-complete. However, if E contains no union, then the membership problem can be solved in polynomial time. Furthermore, if E contains neither a union nor a projection, then we can construct in polynomial time a cover for valid FDs in E, that is, a set of FDs which implies every valid FD in E.Consider the case where each relation scheme in R is associated with multivalued dependencies (MVDs) as well as FDs, and d is an FD or an MVD. Even if E consists of selections and cross products only, the membership problem is NP-hard. However, if E contains no union, and each relation scheme name in R occurs in E at most once, then the membership problem can be solved in polynomial time. As a corollary of this result, it can be determined in polynomial time whether a given FD or MVD is valid in $\text{R}{}_1\text{???R}{}_{\mathrm{s}}$, where R₁,…,R_s are relation schemes with FDs and MVDs, and $\text{R}{}_{\mathrm{i}}\text{?R}{}_{\mathrm{j}}$ is the natural join of R_i and R_j.     

On the time-space tradeoff for sorting with linear queries

Extending a result of Borodin et al. [1], we show that any branching program using linear queries “∑_iλ_ix_i:c” to sort n numbers x₁, x₂,…,x_n must satisfy the time-space tradeoff relation $\text{TS = Ω(n}{}^2\text{)}$. The same relation is also shown to be true for branching programs that uses queries “min R = ?” where R is any subset of {x₁, x₂,…,x_n}.     

Some polynomials that are hard to compute

Using the result of Heintz and Sieveking [1], we show that the polynomials $\text{Σ}{}_{\mathrm{1?j?d}}\text{b}{}^{\mathrm{<mtext>1</mtext><mtext>i</mtext>}}\text{X}{}^{\mathrm{j}}$ with b positive real different from one, and Σ_1?j?dj^rX^j with r rational not integer, are hard to compute.     

Uniform computational complexity of the derivatives of C∞-functions

We discuss the uniform computational complexity of the derivatives of C^∞-functions in the model of Ko and Friedman (Ko, Complexity Theory of Real Functions, Birkhäuser, Basel, 1991; Ko, Friedman, Theor. Comput. Sci. 20 (1982) 323–352). We construct a polynomial time computable real function g∈C^∞[−1,1] such that the sequence $\text{{|g}{}^{\mathrm{(n)}}\text{(0)|}}{}_{\mathrm{<mtext>n\in </mtext><mtext>N</mtext>}}$ is not bounded by any recursive function. On the other hand, we show that if f∈C^∞[−1,1] is polynomial time computable and the sequence of the derivatives of f is uniformly polynomially bounded, i.e., |f⁽ⁿ⁾(x)| is bounded by 2^p(n) for all x∈[−1,1] for some polynomial p, then the sequence $\text{{f}{}^{\mathrm{(n)}}\text{}}{}_{\mathrm{<mtext>n\in </mtext><mtext>N</mtext>}}$ is uniformly polynomial time computable.     

computer aided intuition in abstract algebra

Two examples are given in which the computer was used to supplement intuition in abstract algebra. In the first example, the computer was used to search Cayley tables of 4 element groupoids to find those which are 5-associative but not 4-associative. (n-associative means that the product of any n elements is independent of the way the factors are grouped by parentheses.) The computer generated examples suggested the existence of n element groupoids which are (2^n?2+1)-associative but not (2^n-2)-associative, for each integer n≧4.In the second example, the computer counted the numbers g₂(m) of invertible 2×2 matrices with entries chosen from the ring Z_mof integers, for m = 2, 3, 4,…, 18. The insight gained from these results led to a proof that there are

invertible n×n matrices over Z_m.Some applications to graduate and undergraduate instruction are indicated.     

A general approach to classification problems

In the classification problem the value of the discrete random variable I must be estimated from that of a random variable X given a random sample (I₁, X₁),(I₂, X₂),…,(I_n, X_n). A classification rule giving such an estimate can be based on most nonparametric density estimators which are based on delta sequences. The rate at which the nonerror rate for this rule converges to the optimal is calculated. It is found to be $\text{O(n}{}^{\mathrm{<mtext>?1</mtext><mtext>(2d\; +\; 2)</mtext>}}\text{log}{}^{\mathrm{d}}\text{n}$, where d is the dimension of the variable X under mild assumptions on the densities. A procedure for choosing an associated parameter for small samples is given.     

Three symmetric solutions of lidstone boundary value problems for difference and partial difference equations

We consider the boundary value problem $\text{δ}{}^{\mathrm{2m}}\text{y(k-m)=f(y(k),δ}{}^2\text{y(k-1),…,δ}{}^{\mathrm{2i}}\text{y(k-1),…,δ}{}^{\mathrm{2(m-1)}}\text{y(k-(m-1)))}\text{kϵ{a+1,…,b+1},}\text{δ}{}^{\mathrm{2i}}\text{y(a+1-m)=δ}{}^{\mathrm{2i}}\text{y(b+1+m-2i)=0,}\text{0≤i≤m-1,}$ where m ≥ 1 and (−1)^m f R^m → [0, ∞) is continuous. By using Amann and Leggett-Williams' fixed-point theorems, we develop growth conditions on f so that the boundary value problem has triple positive symmetric solutions. The results obtained are then applied in the investigation of radial solutions for certain partial difference equation subject to Lidstone type conditions.     

Some remarks on a conjecture in parameter adaptive control

A.S. Morse has raised the following question: Do there exist differentiable functions

$\text{f:R}{}^2\text{→ R}\text{and}\text{g:R}{}^2\text{→ R}$

with the property that for every nonzero real number λ and every (x₀, y₀) ∈ $\text{R}$² the solution (x(t),y(t)) of

$\text{x}\text{?}\text{(t) = x(t) + λf(x(t),y(t))}$

,

$\text{y}\text{?}\text{(t) = g(x(t),y(t))}$

,

$\text{x(0) = x}{}_0\text{, y(0) = y}{}_0$

, is defined for all t ? 0 and satisfies

$\text{lim}\text{t → + ∞}$

and y(t) is bounded on [0,∞)? We prove that the answer is yes, and we give explicit real analytic functions f and g which work. However, we prove that if f and g are restricted to be rational functions, the answer is no.     

A distribution-free geometric upper bound for the probability of error of a minimum distance classifier

An upperbound to the probability of error per class in a multivariate pattern classification is derived. The bound, given by

$\text{P(E|class w}{}_{\mathrm{i}}\text{)≤}\text{N}\text{R}{}^2{}_{\mathrm{i}}$

is derived with minimal assumptions; specifically the mean vectors exist and are distinct and the covariance matrices exist and are non-singular. No other assumptions are made about the nature of the distributions of the classes. In equation (i) N is the number of features in the feature (vector) space and R_i is a measure of the “radial neighbourhood” of a class. An expression for R_i is developed. A comparison to the multivariate Gaussian hypothesis is presented.