The inverse M-matrix problem

One aspect of the inverse M-matrix problem can be posed as follows. Given a positive n × n matrix A=(a_ij) which has been scaled to have unit diagonal elements and off-diagonal elements which satisfy 0 < y ? a_ij ? x < 1, what additional element conditions will guarantee that the inverse of A exists and is an M-matrix? That is, if A^?1=B=(b_ij), then b_ii> 0 and b_ij ? 0 for i≠_j. If n=2 or x=y no further conditions are needed, but if n ? 3 and y < x, then the following is a tight sufficient condition. Define an interpolation parameter s via x²=sy+(1?s)y²; then B is an M-matrix if s^?1 ? n?2. Moreover, if all off-diagonal elements of A have the value y except for a_ij=a_jj=x when i=n?1, n and 1 ? _j ? n?2, then the condition on both necessary and sufficient for B to be an M-matrix.     

Monochromatic Vs multicolored paths

Letl andk be positive integers, and letX={0,1,...,l ^k?1}. Is it true that for every coloring δ:X×X→{0,1,...} there either exist elementsx ₀<x ₁<...<x _l ofX with δ(x ₀,x ₁)=δ(x ₁,x ₂)=...=δ(x _l?1,x _l), or else there exist elementsy ₀<y ₁<...<y _k ofX with δ(y _i?1,y _i) ∈ δ(y _j?1,y _j) for all 1<-i<j≤k? We prove here that this is the case if eitherl≤2, ork≤4, orl≥(3k)^2k . The general question remains open.     

Problem 25 : Posed by C.D. Godsil

Let x and y be two letters and m a fixed integer; a ‘bayonet’ is a word of the type xⁱyxⁱ, i + j?m ? 1. We compute the number t_n of all the words obtained by the concatenation of n bayonets. A consequence for the ‘triangle conjecture’ is deduced from the result.     

A new inequality for symmetric functions

Let x_i ≥ 0, y_i ≥ 0 for i = 1,…, n; and let a_j(x) be the elementary symmetric function of n variables given by a_j(x) = ∑_{1 ≤ ii < … <ij ≤ n}x_ii … x_ij. Define the partical ordering x <y if a_j(x) ≤ a_j(y), j = 1,… n. We show that $\text{x}\text{\$}\text{?}\text{y ? x}{}^{\mathrm{\alpha }}\text{\$}\text{?}\text{y}{}^{\mathrm{\alpha }}\text{, 0}\text{\$}\text{?}\text{α ≤ 1}$, where {x^α}_i = x^α_i. We also give a necessary and sufficient condition on a function f(t) such that x <y ? f(x) <f(y). Both results depend crucially on the following: If x <y there exists a piecewise differentiable path z(t), with z_i(t) ≥ 0, such that z(0) = x, z(1) = y, and z(s) <z(t) if 0 ≤ s ≤ t ≤ 1.     

Solution of a system of functional-differential equations arising from an optimization problem

In connection with an optimization problem, all functions ?: Iⁿ → $\text{R}$ with continuous nonzero partial derivatives and satisfying

$\text{??}\text{?x,}{}_{\mathrm{i}}\text{??}\text{?x}{}_{\mathrm{j}}$

for all x_i, x_j ≠ I, i, j = 1,2,…, n (n > 2) are determined (I is an interval of positive real numbers).     

Arithmetic in generalized Artin-Schreier extensions of k(x)

If k is a perfect field of characteristic p ≠ 0 and k(x) is the rational function field over k, it is possible to construct cyclic extensions K_n over k(x) such that [K : k(x)] = pⁿ using the concept of Witt vectors. This is accomplished in the following way; if [β₁, β₂,…, β_n] is a Witt vector over k(x) = K₀, then the Witt equation $\text{y}{}^{\mathrm{p}}\text{?}\text{y}\text{= β}$ generates a tower of extensions through $\text{K}{}_{\mathrm{i}}\text{= K}{}_{\mathrm{i?1}}\text{(}\text{y}{}_{\mathrm{i}}\text{)}$ where $\text{y}\text{= [}\text{y}{}_1\text{,}\text{y}{}_2\text{,…,}\text{y}{}_{\mathrm{n}}\text{]}$. In this paper, it is shown that there exists an alternate method of generating this tower which lends itself better for further constructions in K_n. This alternate generation has the form K_i = K_i?1(y_i); y_i^p ? y_i = B_i, where, as a divisor in K_i?1, B_i has the form . In this form q is prime to Πp_j^λ_j and each λ_j is positive and prime to p. As an application of this, the alternate generation is used to construct a lower-triangular form of the Hasse-Witt matrix of such a field K_n over an algebraically closed field of constants.     

Normal Forms for Nonautonomous Differential Equations

We extend Henry Poincarés normal form theory for autonomous differential equations x=f(x) to nonautonomous differential equations x=f(t, x). Poincarés nonresonance condition λ_j−∑ⁿ_i=1 ?_iλ_i≠0 for eigenvalues is generalized to the new nonresonance condition λ_j∩∑ⁿ_i=1 ?_iλ_i=∅ for spectral intervals.     

A new approach to the dynamic maintenance of maximal points in a plane

A pointp _i=(x _i, y_i) in thex–y plane ismaximal if there is no pointp _j=(x _j, y_j) such thatx _j>x_i andy _j>y_i. We present a simple data structure, a dynamic contour search tree, which contains all the points in the plane and maintains an embedded linked list of maximal points so thatm maximal points are accessible inO(m) time. Our data structure dynamically maintains the set of points so that insertions takeO(logn) time, a speedup ofO(logn) over previous results, and deletions takeO((logn)²) time.The research of the first author was partially supported by the National Science Foundation under Grant No. DCR-8320214 and by the Office of Naval Research on Contract No. N 00014-86-K-0689. The research of the second author was partially supported by the Office of Naval Research on Contract No. N 00014-86-K-0689.     

On the rational approximation ofe −x on [0, ∞)

In recent years the problem of uniform approximation ofe ^?x on [0, ∞) by rational functions has found wide interest. In this paper we present a method for the construction of rational approximations toe ^?x that seem to come arbitrarily near to the asymptotically best one. We start with a generalization of the integral form of the Padé approximant by introducing certain real parametersa _j ,b _i ,k and?. The corresponding error function has again an integral representation and is estimated for everyx∈[0,∞) by the Laplace method. This leads to the consideration of a finite number of new error functionsφ _i·j whose maxima are determined by a set of nonlinear equations and, under some restrictions on thea _j ,b _i ,k, and?, are also unique. Variation of these parameters according to a special algorithm and computation of the corresponding maxima of the functionsφ _i·j shows that forn→∞ the order of rational approximation ofe ^?x on [0, ∞) is at least 9.03^?n .     

The Sperner Capacity of Linear and Nonlinear Codes for the Cyclic Triangle

Shannon introduced the concept of zero-error capacity of a discrete memoryless channel. The channel determines an undirected graph on the symbol alphabet, where adjacency means that symbols cannot be confused at the receiver. The zero-error or Shannon capacity is an invariant of this graph. Gargano, Körner, and Vaccaro have recently extended the concept of Shannon capacity to directed graphs. Their generalization of Shannon capacity is called Sperner capacity. We resolve a problem posed by these authors by giving the first example (the two orientations of the triangle) of a graph where the Sperner capacity depends on the orientations of the edges. Sperner capacity seems to be achieved by nonlinear codes, whereas Shannon capacity seems to be attainable by linear codes. In particular, linear codes do not achieve Sperner capacity for the cyclic triangle. We use Fourier analysis or linear programming to obtain the best upper bounds for linear codes. The bounds for unrestricted codes are obtained from rank arguments, eigenvalue interlacing inequalities and polynomial algebra. The statement of the cyclic q-gon problem is very simple: what is the maximum size N _q(n) of a subset S _n of {0, 1, \(\ldots\) , q?1} ⁿ with the property that for every pair of distinct vectors x = (x _i), y = (y _i) \(\in \) S _n, we have x _j ?y _j ≡ 1(mod q) for some j? For q = 3 (the cyclic triangle), we show N ₃(n)?2 ⁿ . If however S _n is a subgroup, then we give a simple proof that \(\left| {S_n } \right| \leqslant \sqrt 3 ^n \) .     

On a metric generalization of ramsey’s theorem

An increasing sequence of realsx=〈x _i :i<ω〉 is simple if all “gaps”x _i +1−x _i are different. Two simple sequencesx andy are distance similar ifx _i +1−x _i <x _j +1−x _j if and only ify _i +1−y _i <y _j +1−y _j for alli andj. Given any bounded simple sequencex and any coloring of the pairs of rational numbers by a finite number of colors, we prove that there is a sequencey distance similar tox all of whose pairs are of the same color. We also consider many related problems and generalizations. Partially supported by OTKA-4269. Partially supported by NSF grant STC-91-19999. Partially supported by OTKA-T-020914, NSF grant CCR-9424398 and PSC-CUNY Research Award 663472.     

Point estimation for multi-spectral distributed random matrices

In this communication, we consider a p×n random matrix which is normally distributed with mean matrix M and covariance matrix Σ, where the multivariate observation x_i=y_i+?_i with p dimensions on an object consists of two components, the signal y_i with mean vector μ and covariance matrix Σ_s and noise with mean vector zero and covariance matrix Σ_?, then the covariance matrix of x_i and x_j is given by Σ=Cov(x_i,x_j)=Γ⊗(B_|i-j|Σ_s+C_|i-j|Σ_?), where Γ is a correlation matrix; B_|i-j| and C_|i-j| are diagonal constant matrices. The statistical objective is to consider the maximum likelihood estimate of the mean matrix M and various components of the covariance matrix Σ as well as their statistical properties, that is the point estimates of Σ_s,Σ_? and Γ. More importantly, some properties of these estimators are investigated in slightly more general models.     

On bounds for eigenvalues of real symmetric matrices

Let A=(a_ij) be a real symmetric matrix of order n. We characterize all nonnegative vectors x=(x₁,...,x_n) and y=(y₁,...,y_n) such that any real symmetric matrix B=(b_ij), with b_ij=a_ij, i≠jhas its eigenvalues in the union of the intervals [b_ij?y_i, b_ij+ x_i]. Moreover, given such a set of intervals, we derive better bounds for the eigenvalues of B using the 2n quantities {b_ii?y, b_ii+x_i}, i=1,..., n.     

An upper bound on the number of high-dimensional permutations

What is the higher-dimensional analog of a permutation? If we think of a permutation as given by a permutation matrix, then the following definition suggests itself: A d-dimensional permutation of order n is an n×n×...×n=[n] ^d+1 array of zeros and ones in which every line contains a unique 1 entry. A line here is a set of entries of the form {(x ₁,...,x _i?1,y,x _i+1,...,x _d+1)|n≥y≥1} for some index d+1≥i≥1 and some choice of x _j ∈ [n] for all j ≠ i. It is easy to observe that a one-dimensional permutation is simply a permutation matrix and that a two-dimensional permutation is synonymous with an order-n Latin square. We seek an estimate for the number of d-dimensional permutations. Our main result is the following upper bound on their number $$\left( {(1 + o(1))\frac{n} {{e^d }}} \right)^{n^d } .$$ We tend to believe that this is actually the correct number, but the problem of proving the complementary lower bound remains open. Our main tool is an adaptation of Brégman’s [1] proof of the Minc conjecture on permanents. More concretely, our approach is very close in spirit to Schrijver’s [11] and Radhakrishnan’s [10] proofs of Brégman’s theorem.     

Bernstein type operators having 1 and x j as fixed points

For certain generalized Bernstein operators {L _n } we show that there exist no i, j ∈ {1, 2, 3,…}, i < j, such that the functions e _i (x) = x ⁱ and e _j (x) = x ^j are preserved by L _n for each n = 1, 2,… But there exist infinitely many e _i such that e ₀(x) = 1 and e _j (x) = x _j are its fixed points.     

A Katona-type proof of an Erd?s-Ko-Rado-type theorem

Let p?1/2 and let μ_p be the product measure on {0,1}ⁿ, where μ_p(x)=p^∑x_i(1-p)^n-∑x_i. Let A⊂{0,1}ⁿ be an intersecting family, i.e. for every x,y∈A there exists 1?i?n such that x_i=y_i=1. Then μ_p(A)?p. Our proof uses a probabilistic trick first applied by Katona to prove the Erd?s-Ko-Rado theorem.     

Optimal interval lengths for nonlocal boundary value problems associated with third order Lipschitz equations

For the third order differential equation, y^?=f(x,y,y^′,y^″), where f(x,y₁,y₂,y₃) is Lipschitz continuous in terms of yi, i=1,2,3, we obtain optimal bounds on the length of intervals on which there exist unique solutions of certain nonlocal three and four point boundary value problems. These bounds are obtained through an application of the Pontryagin Maximum Principle from the theory of optimal control.