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.     

Unbounded solutions of quasi-linear difference equations

We study positive increasing solutions of the nonlinear difference equation $\text{δ(a}{}_{\mathrm{n}}\text{φ}{}_{\mathrm{p}}\text{(δχ}{}_{\mathrm{n}}\text{))=b}{}_{\mathrm{n}}\text{f(χ}{}_{\mathrm{n+1}}\text{,}\text{φ}{}_{\mathrm{p}}\text{(u)=|u|}{}^{\mathrm{p-2}}\text{u,}\text{p>1}$ where {a_n}, {b_n} are positive real sequences for n ≥ 1, fR → R is continuous with uf(u) > 0 for u ≠ 0. A full characterization of limit behavior of all these solutions in terms of a_n, b_n is established. Examples, showing the essential role of used hypotheses, are also included. The tools used are the Schauder fixed-point theorem and a comparison method based on the reciprocity principle.     

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.     

Determination of a general economic location constant by monte carlo simulation

The problem of estimating the number of markets (or plants) to serve a set of sources in a given geographical area was considered. Markets were located so as to minimize total assembly cost which was considered a linear function of the weighted Euclidean distances between sources and markets. The following predictive function C_m was proposed for estimating the minimum total assembly cost for a given number of markets: $\text{C}{}_{\mathrm{m}}\text{= C}{}_1\text{?(}\text{m?1}\text{m}\text{)}{}^{\mathrm{k}}\text{(}\text{M}\text{M ? 1}\text{)}{}^{\mathrm{k}}\text{(C}{}_1\text{? C}{}_{\mathrm{M}}\text{),m = 1, 2, 3, …, M}$ where m = number of markets being located. M = maximum number of potential market sites. C₁ = minimum assembly cost when only one market is located. C_M = minimum assembly cost when all M markets are located. k = an undetermined constant which specifies the shape of the function.The validity of the C_m function and the range of the k constant were determined by computer Monte Carlo experimentation. The constant k, to a sufficient degree of approximation and ordinary use, was found independent of the number of sources and their distribution. A general economic location co     

Improved M-matrix condition for the existence of positive-real weighting

It is proved that, for a given stable transfer matrix G(s), there exists a constant diagonal matrix W which makes WG(s) positive-real if Re g_ii(jω) ≥ 0 and I?? is an M-matrix where ? = (?_jk) is defined by ?_ii = 0 and $\text{?}{}_{\mathrm{jk}}\text{=}\text{sup}{}_{\mathrm{\omega }}\text{|g}{}_{\mathrm{ik}}\text{(gω) |/(}\text{Re}\text{[g}{}_{\mathrm{ii}}\text{(jω)]·}\text{Re}\text{[g}{}_{\mathrm{kk}}\text{(jω])}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$.     

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.     

Some results on addition/subtraction chains

Let ?(n) (respectively $\text{?}$(n)) be the length of the shortest addition chain respectively addition/subtraction chain for n. We shall present several results on $\text{?}$(n). In particular, we determine $\text{?}$(n) for all n satisfying $\text{s}\text{(}\text{n}\text{) ? 3}$ and show $\text{?}\text{log n}\text{? + 2 ?}\text{?}\text{(}\text{n}\text{)}$ for all n satisfying $\text{s}\text{(}\text{n}\text{) ? 3}$, where $\text{s}\text{(}\text{n}\text{)}$ is the extended sum of digits of n. These results are based on analogous results for ?(n) and on the following two inequalities: |n| ? 2^d?1F_f+3 < 2^k?b and $\text{f + b}\text{?}\text{log}\text{s}\text{(n)}$ for a chain of length k = d + f + b with d doublings, f short steps, and b back steps for n. Moreover, we show that the difference $\text{?(}\text{n}\text{)?}\text{?}\text{(}\text{n}\text{)}$ (respectively $\text{?}\text{(}\text{n}\text{)??}\text{log n}\text{?}$) can be made arbbitrarily large. In addition, we prove that $\text{?}\text{(}\text{m}\text{) ?}\text{?}\text{(?}\text{m}\text{) ?}\text{?}\text{(}\text{m}\text{) + 1}\text{for m}\text{> 0}$ and characterize the case $\text{?}\text{(?}\text{m}\text{) =}\text{?}\text{(}\text{m}\text{)}$. Finally, we determine $\text{?}{}_{\mathrm{<mtext>k</mtext>}}\text{(}\text{n}{}_1\text{,…,}\text{n}{}_{\mathrm{k}}\text{)}$, the k-dimensional generalization of $\text{?}$, with the help of $\text{?}\text{(}\text{n}{}_1\text{,…,}\text{n}{}_{\mathrm{k}}\text{)}$, the k-element generalization of $\text{?}$.     

Averaging shifted histograms

A method which consists in shifting different histograms of the same spectrum and then taking their average is presented in order to smooth the data and to increase the localization accuracy and separation of the peaks. The statistical properties of this method are investigated. The average of two histograms with shifted bin limits is studied. It is shown that for histograms with random bin limits, distributed according to

$\text{F}{}_{\mathrm{i}}\text{(x)=}\text{∫}\text{?∞}\text{x}\text{?}{}_{\mathrm{i}}\text{(ξ, μ}{}_{\mathrm{i}}\text{, σ)}\text{d}\text{ξ}$

; where the standard deviation σ is very small compared to the difference of the means (μ_i+1 ? μ_i) for ll i the zero order approximation to the variance of this histogram is given by:

$\text{var}\text{∽}\text{(H)=}\text{∑}\text{i=0}\text{m}\text{(A}{}_{\mathrm{i+1}}\text{?a}{}_{\mathrm{i}}\text{)}{}^2\text{F}{}_{\mathrm{i+1}}\text{(x)(1?F}{}_{\mathrm{i+1}}\text{(x))}$

, where

$\text{a}{}_{\mathrm{i}}\text{=}\text{1}\text{x}{}_{\mathrm{i=1}}\text{?x}{}_{\mathrm{i}}\text{∫}\text{x}{}_{\mathrm{i}}\text{x}{}_{\mathrm{i+1}}\text{g(ξ)}\text{d}\text{ξ}$

and g is an unknown function fitted by the histogram. Formula (1) gives also the relation:

$\text{v}\text{a}\text{?}\text{r}\text{(}\text{(H}{}_1\text{+ H}{}_2\text{)}\text{2}\text{) =}\text{1}\text{4}\text{(}\text{v}\text{a}\text{?}\text{r}\text{(H}{}_1\text{(x)) +}\text{v}\text{a}\text{?}\text{r}\text{(H}{}_2\text{(x))}$

, when H₁ and H₂ have stochastically independent bin limits.When the histogram H is considered as a spline function S of order one it is shown that for the minimization criterion with respect to the coefficient of the spline:

$\text{M}{}_1\text{=}\text{min}\text{∫}\text{x}{}_1\text{x}{}_{\mathrm{m+1}}\text{(g(x) ? S}{}_1\text{(x))}{}^2\text{d}\text{x}$

, the following result holds: $\text{M}{}_{\mathrm{a}}\text{?}{}^1{}_2\text{(M}{}_1\text{+ M}{}_2\text{)}$, where $\text{S}{}_{\mathrm{a}}\text{(x) =}{}^1{}_2\text{(S}{}_1\text{(x) + S}{}_2\text{(x))}$. If the number of shifted histograms tends to infinity, then

$\text{S}{}_{\mathrm{\infty }}\text{(x) = [Γ(x + h) + Γ(x ? h) ? 2Γ(x)]/h}{}^2$

, where $\text{Γ(x) =}\text{∫}\text{?∞}\text{x}\text{∫}\text{?∞}\text{η}\text{g(ξ)}\text{d}\text{ξ}\text{d}\text{η}$, and h is a constant bin size. Then

$\text{M}{}_{\mathrm{\infty }}\text{≈}\text{h}{}^4\text{144}\text{∫}\text{x}{}_1\text{x}{}_{\mathrm{m+1}}\text{g″}{}^2\text{(x)}\text{D}\text{x}$

. Extensions to two-dimensional histograms and to higher order (empirical distributions) are presented.     

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.     

Improving loops and vanishing variables in long transportation problems

In this paper the following two results are presented: (1)A method which determines the optimal values of certain variables during the iterative solution process. The closer the current primal feasible solution is to the optimal solution, the greater the number of variables which may be determined. (2) For each current feasible solution (X_ij) of the given m × n transportation problem A, a feasible solution ($\text{X}\text{?}{}_{\mathrm{ij}}$) of an auxiliary m × m(m ?1) transportation problem $\text{A}\text{?}$ is constructed. Problem $\text{A}\text{?}$ is shown to be equivalent to an m(m ? 1) × m(m ? 1) assignment problem with two admissible cells per column. The optimally of (X_ij) is shown to imply the optimality of ($\text{X}\text{?}{}_{\mathrm{ij}}$) and conversely. The best “improving loops” (including the improving loops used in MODI) of $\text{A}\text{?}$ are shown to be the best “improving loops” of A as well.     

On n-Dimensional Sequences. I

Let R be a commutative ring and let n ≥ 1. We study Γ(s), the generating function and Ann(s), the ideal of characteristic polynomials of s, an n-dimensional sequence over R .We express f(X₁,…,X_n) · Γ(s)(X^-1₁,…,X^-1_n) as a partitioned sum. That is, we give (i) a 2ⁿ-fold "border" partition (ii) an explicit expression for the product as a 2ⁿ-fold sum; the support of each summand is contained in precisely one member of the partition. A key summand is βo(f, s), the "border polynomial" of f and s, which is divisible by X₁ … X_n.We say that s is eventually rectilinear if the elimination ideals Ann(s)∩R[X_i] contain an f_i (X_i) for 1 ≤ i ≤ n. In this case, we show that Ann(s) is the ideal quotient ($\text{∑}{}^{\mathrm{n}}{}_{\mathrm{i}}\text{=1(fi) : βo(f, s)/(X}{}_1\text{… X}{}_{\mathrm{n}}\text{)}$).When R and R[[X₁, X₂ ,…, X_n]] are factorial domains (e.g. R a principal ideal domain or F [X₁,…, X_n]), we compute the monic generator γ_i of Ann(s) ∩ R[X_i] from known f_i ϵ Ann(s) ∩ R[X_i] or from a finite number of 1-dimensional linear recurring sequences over R. Over a field F this gives an O($\text{∏}{}_{\mathrm{n}}{}^{\mathrm{i}}\text{=1 δγ}{}^3{}_{\mathrm{i}}$) algorithm to compute an F-basis for Ann(s).     

An iterative method for determining the current-potential curves of a spherical probe in a slightly ionized continuum plasma with 5 ⩽ ρp ⩽ 50, yp < 7

A desk analogue computer has been used to draw normalized curves for positive and negative particle concentrations $\text{(n}{}_{\mathrm{+}}\text{,n}{}_{\mathrm{?}}\text{)}$ and potential $\text{(y)}$ vs the distance from a spherical probe surface for a slightly ionized continuum plasma. The governing equations are three simultaneous differential equations leading to a two-point boundary condition problem. An iterative analogue method has been developed which enables the positive and negative particle currents $\text{(J}{}_{\mathrm{+}}\text{,J}{}_{\mathrm{?}}\text{)}$ to the probe, for particular $\text{y}{}_{\mathrm{p}}\text{< 7}$ and $\text{ρ}{}_{\mathrm{p}}\text{< 50}$, to be found to a numerical accuracy of about 1 digit in the second decimal place.