Lower bounds on the spectra of symmetric matrices with nonnegative entries

If we normalize a symmetric n × n matrix with nonnegative entriesso that its largest entry is 1, then its spectrum is bounded below by $\text{?n}\text{2}$. The lower bound is achieved in all even dimensions for (and only for) adjacency matrices of complete bipartite graphs with equal parts.     

On the optimal computation of a set of symmetric and persymmetric bilinear forms

A special class $\text{T}$ⁿ of n×n matrices is described, which has tensor rank n over the real field. A tensor base for general symmetric, persymmetric, both symmetric and persymmetric matrices and Toeplitz symmetric matrices can be defined in terms of the tensor bases of $\text{T}$^l for some different values of l. It is proved that both symmetric and persymmetric n×n matrices and Toeplitz symmetric n×n matrices have tensor rank $\text{[}\text{(n+1)}{}^2\text{4}\text{]}$ and 2n?2, respectively, in the real field.     

Hermitian matrices with a bounded number of eigenvalues

Conjugation covariants of matrices are applied to study the real algebraic variety consisting of complex Hermitian matrices with a bounded number of distinct eigenvalues. A minimal generating system of the vanishing ideal of degenerate three by three Hermitian matrices is given, and the structure of the corresponding coordinate ring as a module over the special unitary group is determined. The method applies also for degenerate real symmetric three by three matrices. For arbitrary n   partial information on the minimal degree component of the vanishing ideal of the variety of n×n$n\times n$ Hermitian matrices with a bounded number of eigenvalues is obtained, and some known results on sum of squares presentations of subdiscriminants of real symmetric matrices are extended to the case of complex Hermitian matrices.     

Retarded equations on the sphere induced by linear equations

Using a Poincaré compactification, the linear homogeneous system of delay equations {x = Ax(t ? 1) (A is an n × n real matrix) induces a delay system π(A) on the sphere Sⁿ. The points at infinity belong to an invariant submanifold S^{n ? 1} of Sⁿ. For an open and dense set of 2 × 2 matrices A with distinct eigenvalues, the system π(A) has only hyperbolic critical points (including the critical points at infinity). For an open and dense set of 2 × 2matrices $\text{A}$ with complex eigenvalues, the nonwandering set at infinity is the union of an odd number of hyperbolic periodic orbits; if $\text{(}\text{det}\text{A}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{<}\text{3π}\text{2}$, the restriction of $\text{π(}\text{A}\text{)}$ to S¹ is Morse-Smale. For n = 1 there exist periodic orbits of period 4 provided that $\text{?A >}\text{π}\text{2}$ and Hopf bifurcation of a center occurs for ?A near $\text{(}\text{π}\text{2}\text{) + 2kπ, k ? Z}$.     

Complex eigenvalues of a non-negative matrix with a specified graph

Let A be a non-negative matrix of order n with Perron eigenvalue ? and associated directed graph G. Let m be the length of the longest circuit of G. Theorem: If m=2, all eigenvalues of A are real. If 2<m?n, and if λ=μ+iv is an eigenvalue of A, then $\text{μ+|v|tan(}\text{Π}\text{m}\text{) ? ρ}$.     

On the existence of matrices with constrained elements,rows and columns

Let the following be given: two n × m real matrices, E and F, such that F ? E, three real n-rows, p, a and b, such that b ? a, and three real m-columns, t, c and d, such that d ? c. We give inequalities relating the given matrices and vectors, equivalent to the consistency of the system

$\text{F ? X ? E}$

,

$\text{d ? Xt ? c}$

,

$\text{b ? pX ?a}$

, where X is an n × m unknown real matrix.     

Nonnegative rank-preserving operators

Analogues of characterizations of rank-preserving operators on field-valued matrices are determined for matrices witheentries in certain structures $\text{S}$ contained in the nonnegative reals. For example, if $\text{S}$ is the set of nonnegative members of a real unique factorization domain (e.g. the nonnegative reals or the nonnegative integers), M is the set of m×n matrices with entries in $\text{S}$, and min(m,n)?4, then a “linear” operator on M preserves the “rank” of each matrix in M if and only if it preserves the ranks of those matrices in M of ranks 1, 2, and 4. Notions of rank and linearity are defined analogously to the field-valued concepts. Other characterizations of rank-preserving operators for matrices over these and other structures $\text{S}$ are also given.     

Matrices with prescribed Ritz values

On the way to establishing a commutative analog to the Gelfand-Kirillov theorem in Lie theory, Kostant and Wallach produced a decomposition of M(n) which we will describe in the language of linear algebra. The “Ritz values” of a matrix are the eigenvalues of its leading principal submatrices of order m=1,2,…,n. There is a unique unit upper Hessenberg matrix H with those eigenvalues. For real symmetric matrices with interlacing Ritz values, we extend their analysis to allow eigenvalues at successive levels to be equal. We also decide whether given Ritz values can come from a tridiagonal matrix.     

Spaces of matrices of equal rank

Let M_m,n(F) denote the space of all mXn matrices over the algebraically closed field F. A subspace of M_m,n(F), all of whose nonzero elements have rank k, is said to be essentially decomposable if there exist nonsingular mXn matrices U and V respectively such that for any element A, UAV has the form

$\text{UAV=}\text{A}{}_1\text{A}{}_2\text{A}{}_3\text{0}$

where A₁ is iX(k–i) for some i?k. Theorem: If $\text{K}$ is a space of rank k matrices, then either $\text{K}$ is essentially decomposable or dim $\text{K}$?k+1. An example shows that the above bound on non-essentially-decomposable spaces of rank k matrices is sharp whenever n?2k–1.     

A property of matrices with positive determinants

Let $\text{P}$ be the set of all n × n real matrices which have a positive determinant. We show here that at least 2^{n ? 1} matrices are needed to “see” each matrix in $\text{P}$. Also, any finite subset of $\text{P}$ can be “seen” from a class of at most 2^{n ? 1} matrices in $\text{P}$.     

Nonnegative factorization of completely positive matrices

Let A be a real symmetric n × n matrix of rank k, and suppose that A = BB′ for some real n × m matrix B with nonnegative entries (for some m). (Such an A is called completely positive.) It is shown that such a B exists with $\text{m?}\text{1}\text{2}\text{k(k+1)?N}$, where 2N is the maximal number of (off-diagonal) entries which equal zero in a nonsingular principal submatrix of A. An example is given where the least m which works is $\text{(k+1)}{}^2\text{4}$ (k odd),$\text{k(k+2)}\text{4}$ (k even).     

The 1-width of (0,1)-matrices having constant row sum 3

In this note we establish upper bounds for the 1-width of an m × n matrix of 0's and 1's having three 1's in every row and having a constant number, c, of 1's in every column. When c = 3, this upper bound is $\text{n}\text{2}$ and when c = 4 this estimate is $\text{5n}\text{9}$. In these cases the upper bound is best possible, in the sense that for every possible size there exist matrices with this maximal 1-width. The technique of proof is also used to improve the known bound for the 1-width of (0, 1)-matrices with constant line sum 4.     

A family of quadratic forms associated to quadratic mappings of spheres

The general form of a real quadratic mapping of spheres can be determined by studying the diagonalization of each form in an associated family of quadratic forms. In particular, the eigenvalues provide a means for detecting maps which are of the Hopf type. When the eigenvalues are nonzero for every form in the family, the forms associated to $\text{?:}\text{S}{}^{\mathrm{n}}\text{→}\text{S}{}^{\mathrm{m}}$ give rise to a quadratic form on the tangent bundle of the unit sphere Sⁿ. If ? is of the Hopf type, nondegeneracy of each form occurs only when n=1,3,7,15.     

General forbidden configuration theorems

Results in this paper gives bounds on the number of columns in a matrix when certain submatrices are forbidden. Let F be a k by l (0, 1)-matrix with no repeated columns, column sums at least s. Let A be a m by n (0, 1)-matrix with no repeated column, column sums at least s and no submatrix F nor any row and column permutation of F. Then $\text{n?(}\text{m}\text{k?1}\text{) + (}\text{m}\text{k?2}\text{) + ? + (}\text{m}\text{s}\text{)}$. This bound is best possible for numerous F. The bound, with s = 0, is an easy corollary to a bound of Sauer and Perles and Shelah. The bounds can be extended to any F and to any F where we do not allow row and column permutations. The results follow from a configuration theorem that says, in essence, that matrices without a configuration are determined by row intersections of sets of rows of various sizes. A linear independence argument yields the bound. Results of Ryser, Frankl and Pach, Quinn and the author are obtained.     

Universal bounds for global solutions of a forced porous medium equation

We show that in a smooth bounded domain $\text{Ω⊂}\text{R}{}^{\mathrm{n}}$, n⩾2, all global nonnegative solutions of u_t−Δu^m=u^p with zero boundary data are uniformly bounded in $\text{Ω×(τ,∞)}$ by a constant depending on $\text{Ω,p}$ and τ but not on u₀, provided that 1<m<p<[(n+1)/(n−1)]m. Furthermore, we prove an a priori bound in $\text{L}{}^{\mathrm{\infty }}\text{(Ω×(0,∞))}$ depending on $\text{||u}{}_0\text{||}{}_{\mathrm{L\infty (\Omega )}}$ under the optimal condition 1<m<p<[(n+2)/(n−2)]m.     

Convex sets of some doubly stochastic matrices

Let Ω denote the set of all n by n doubly stochastic matrices. Let t be a real number such that $\text{1}\text{t}\text{?}\text{1}\text{n}$ and let m be a real number such that $\text{1}\text{m}\text{? 1 ?}\text{1}\text{t}$. The set $\text{Ω}{}_{\mathrm{s}}\text{= {A ? Ω :}\text{1}\text{m}\text{? a}{}_{\mathrm{ij}}\text{?}\text{1}\text{t}\text{, 1 ? i, j ? n}}$ is the convex hull of the matrices in $\text{Ω}{}_{\mathrm{s}}$ having as many largest entries, namely, $\text{1}\text{t}$, as possible in each row and column while filling out the remaining entries with the value $\text{1}\text{m}$ and if necessary at most one entry in each row and column which has a value between $\text{1}\text{m}$ and $\text{1}\text{t}$.     

On the separation power and the completion of partial latin squares

Let n and m be natural numbers, n ? m. The separation power of order n and degree m is the largest integer k = k(n, m) such that for every (0, 1)-matrix A of order n with constant linesums equal to m and any set of k 1's in A there exist (disjoint) permutation matrices P₁,…, P_m such that A = P₁ + … + P_m and each of the k 1's lies in a different P_i. Almost immediately we have 1 ? k(n, m) ? m ? 1, yet in all cases where the value of k(n, m) is actually known it equals m ? 1 (except under the somewhat trivial circumstances of k(n, m) = 1). This leads to a conjecture about the separation power, namely that k(n, m) = m ? 1 if $\text{m ? [}\text{n}\text{2}\text{] + 1}$. We obtain the bound $\text{k(n, m) ? m ? [}\text{n}\text{2}\text{] + 2}$, so that this conjecture holds for n ? 7. We then move on to latin squares, describing several equivalent formulations of the concept. After establishing a sufficient condition for the completion of a partial latin square in terms of the separation power, we can show that the Evans conjecture follows from this conjecture about the separation power. Finally the lower bound on k(n, m) allows us to show, after some calculations, that the Evans conjecture is true for orders n ? 11.     

Universal caterpillars

For a class $\text{C}$ of graphs, denote by u($\text{C}$) the least value of m so that for some graph U on m vertices, every G ? $\text{C}$ occurs as a subgraph of U. In this note we obtain rather sharp bounds on u($\text{C}$) when $\text{C}$ is the class of caterpillars on n vertices, i.e., tree with property that the vertices of degree exceeding one induce a path.     

On the rational spectra of graphs with abelian singer groups

Let G be a finite abelian group. We investigate those graphs $\text{G}$ admitting G as a sharply 1-transitive automorphism group and all of whose eigenvalues are rational. The study is made via the rational algebra $\text{P}$(G) of rational matrices with rational eigenvalues commuting with the regular matrix representation of G. In comparing the spectra obtainable for graphs in $\text{P}$(G) for various G's, we relate subschemes of a related association scheme, subalgebras of $\text{P}$(G), and the lattice of subgroups of G. One conclusion is that if the order of G is fifth-power-free, any graph with rational eigenvalues admitting G has a cospectral mate admitting the abelian group of the same order with prime-order elementary divisors.     

Group-invariant analogues of Hadamard's inequality

A wide class of inequalities for the determinant and other real-valued functions of an n × n complex Hermitian (or real symmetric) matrix H≡(h_jk) may be obtained by generalizing Marshall and Olkin's proof of Hadamard's inequality

$\text{det}\text{H?}\text{∏}\text{j=1}\text{n}\text{h}{}_{\mathrm{jj}}$

for positive definite (pd) H. We shall see that each subgroup G of the group U_n of n x n unitary matrices not only determines an analogue of (1) for det H, but also provides inequalities for a large family of unitarily invariant functions of H (not necessarily pd).