Some angularity and inertia theorems related to normal matrices

Motivated by the definition of the inertia, introduced by Ostrowski and Schneider, a notion of angularity of a matrix is defined. The angularity characterizes the distribution of arguments of eigenvalues of a matrix. It is proved that if B and C are nonsingular matrices, then B¹AB and C¹AC have the same angularity provided they are diagonal. Some well-known inertia theorems (e.g. Sylvester's law) have been deduced as corollaries of this result. The case when C is permitted to be singular is discussed next. Finally, we prove that (a) any linear transformation T, on the set of n by n complex matrices, mapping Hermitian matrices into themselves and preserving the inertia of each Hermitian matrix is of the form T(A)=C¹AC or T(A)=C^1LA′C where C is some nonsingular matrix, and (b) any linear transformation T mapping normal matrices into normal matrices and preserving the angularity of each normal matrix is also of one of the above forms, but with C=kU where k≠0 and U is unitary.     

Fast solution of toeplitz systems of equations and computation of Padé approximants

We present two new algorithms, ADT and MDT, for solving order-n Toeplitz systems of linear equations Tz = b in time O(n log²n) and space O(n). The fastest algorithms previously known, such as Trench's algorithm, require time $\text{Ω(n}{}^2\text{)}$ and require that all principal submatrices of T be nonsingular. Our algorithm ADT requires only that T be nonsingular. Both our algorithms for Toeplitz systems are derived from algorithms for computing entries in the Padé table for a given power series. We prove that entries in the Padé table can be computed by the Extended Euclidean Algorithm. We describe an algorithm EMGCD (Extended Middle Greatest Common Divisor) which is faster than the algorithm HGCD of Aho, Hopcroft and Ullman, although both require time O(n log²n), and we generalize EMGCD to produce PRSDC (Polynomial Remainder Sequence Divide and Conquer) which produces any iterate in the PRS, not just the middle term, in time O(n log²n). Applying PRSDC to the polynomials U₀(x) = x²ⁿ⁺¹ and U₁(x) = a₀ + a₁x + … + a_2nx²ⁿ gives algorithm AD (Anti-Diagonal), which computes any (m, p) entry along the antidiagonal m + p = 2n of the Padé table for U₁ in time O(n log²n). Our other algorithm, MD (Main-Diagonal), computes any diagonal entry (n, n) in the Padé table for a normal power series, also in time O(n log²n). MD is related to Schönhage's fast continued fraction algorithm. A Toeplitz matrix T is naturally associated with U₁, and the (n, n) Padé approximation to U₁ gives the first column of T^?1. We show how a formula due to Trench can be used to compute the solution z of Tz = b in time O(n log n) from the first row and column of T^?1. Thus, the Padé table algorithms AD and MD give O(n log²n) Toeplitz algorithms ADT and MDT. Trench's formula breaks down in certain degenerate cases, but in such cases a companion formula, the discrete analog of the Christoffel-Darboux formula, is valid and may be used to compute z in time O(n log²n) via the fast computation (by algorithm AD) of at most four Padé approximants. We also apply our results to obtain new complexity bounds for the solution of banded Toeplitz systems and for BCH decoding via Berlekamp's algorithm.     

Linear transformations on matrices: the invariance of sets of ranks

Let R_E denote the set of all m × n matrices over an algebraically closed field F whose ranks lie in the set E, where E is a subset of {1,2,…,m}. Let T be a linear transformation which maps R_E into itself. Under some restrictions on E, or when T is nonsingular, there are nonsingular matrices U and V such that T(A) = UAV for every m × n matrix A.     

Linear preservers of matrices of rank-2

Let T be a linear operator on the space of all m×n matrices over any field. we prove that if T maps rank-2 matrices to rank-2 matrices then there exist nonsingular matrices U and V such that either T(X)=UXV for all matrices X, or m=n and T(X)=UX^tV for all matrices X where X^t denotes the transpose of X.     

Commutativity-preserving operators on symmetric matrices

If φ is a nonsingular linear operator on n × n symmetric matrices over a formally real field, n ? 3, and if φ preserves commutativity, then φ(A) = cU^-1AU + f(A)I, where U^tU and c are scalar and ? is a linear functional. This is an extension of a result of Chan and Lim.     

A theorem in combinatorial matrix theory

Let Z be a matrix of order n, and suppose that the elements of Z consist of only two elements x and y, which are elements of a field F. We call Z an (x,y)-matrix over F. In this paper we study the matrix equation ZEZ^T = D+λJ, where Z is a nonsingular (x,y)-matrix over F, Z^T is the transpose of Z, D and E are nonsingular diagonal matrices, J is the matrix of 1's and λ is an element of F. Our main theorem shows that the column sums of Z are severely restricted. This result generalizes a number of earlier investigations that deal with symmetric block designs and related configurations. The problems that emerge are of interest from both a combinatorial and a matrix theoretic point of view.     

Linear maps that preserve matrices annihilated by a polynomial

Let M_n be the algebra of n×n matrices over an algebraically closed field of characteristic zero. Let f(x) be a polynomial over $\text{F}$ with at least two distinct roots. Then all nonsingular linear maps L:M_n→M_n that map matrix roots of F(x)=0 into matrix roots of f(x}=0 are found.     

Tournament matrices and their generalizations,I.

If M is any complex matrix with rank (M + M ^* + I) = 1, we show that any eigenvalue of M that is not geometrically simple has 1/2 for its real part. This generalizes a recent finding of de Caen and Hoffman: the rank of any n × n tournament matrix is at least n ? 1. We extend several spectral properties of tournament matrices to this and related types of matrices. For example, we characterize the singular real matrices M with 0 diagonal for which rank (M + M^T + I) = 1 and we characterize the vectors that can be in the kernels of such matrices. We show that singular, irreducible n × n tournament matrices exist if and only n? {2,3,4,5} and exhibit many infinite families of such matrices. Connections with signed digraphs are explored and several open problems are presented.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.     

Theory of cones

This survey deals with the aspects of archimedian partially ordered finite-dimensional real vector spaces and order preserving linear maps which do not involve spectral theory. The first section sketches some of the background of entrywise nonnegative matrices and of systems of inequalities which motivate much of the current investigations. The study of inequalities resulted in the definition of a polyhedral cone K and its face lattice F(K). In Section II.A the face lattice of a not necessarily polyhedral cone K in a vector space V is investigated. In particular the interplay between the lattice properties of $\text{F}$(K) and geometric properties of K is emphasized. Section II.B turns to the cones Π(K) in the space of linear maps on V. Recall that Π(K) is the cone of all order preserving linear maps. Of particular interest are the algebraic structure of Π(K) as a semiring and the nature of the group Aut(K) of nonsingular elements A?Π(K) for which A^-1?Π(K) as well. In a short final section the cone P_n of n×n positive semidefinite matrices is discussed. A characterization of the set of completely positive linear maps is stated. The proofs will appear in a forthcoming paper.     

Linear transformations which preserve fixed rank

Let M_{m, n}(F) denote the set of all m×n matrices over the algebraically closed field F. Let T denote a linear transformation, T:M_{m, n}(F)→M_{m, n}(F). Theorem: If max(m, n)?2k?2, k?1, and T preserves rank k matrices [i.e.?(A)=k implies ?(T(A))=k], then there exist nonsingular m×m and n×n matrices U and V respectively such that either (i) T:A→UAV for all A?M_{m, n}(F), or (ii) m=n and T:A→UA^tV for all A?M_n(F), where A^t denotes the transpose of A.     

Classes of general H-matrices

Let M(A) denote the comparison matrix of a square H-matrix A, that is, M(A) is an M-matrix. H-matrices such that their comparison matrices are nonsingular are well studied in the literature. In this paper, we study characterizations of H-matrices with either singular or nonsingular comparison matrices. The spectral radius of the Jacobi matrix of M(A) and the generalized diagonal dominance property are used in the characterizations. Finally, a classification of the set of general H-matrices is obtained.     

On algebraic Riccati equations associated with M-matrices

We consider the algebraic Riccati equation for which the four coefficient matrices form an M-matrix K. When K is a nonsingular M-matrix or an irreducible singular M-matrix, the Riccati equation is known to have a minimal nonnegative solution and several efficient methods are available to find this solution. In this paper we are mainly interested in the case where K is a reducible singular M-matrix. Under a regularity assumption on the M-matrix K, we show that the Riccati equation still has a minimal nonnegative solution. We also study the properties of this particular solution and explain how the solution can be found by existing methods.     

Simultaneous block diagonalization of two real symmetric matrices

The simultaneous diagonalization of two real symmetric (r.s.) matrices has long been of interest. This subject is generalized here to the following problem (this question was raised by Dr. Olga Taussky-Todd, my thesis advisor at the California Institute of Technology): What is the first simultaneous block diagonal structure of a nonsingular pair of r.s. matrices ? For example, given a nonsingular pair of r.s. matrices S and T, which simultaneous block diagonalizations X′SX = diag(A₁, , A_k), X′TX = diag(B₁,, B_k) with dim A_i = dim B_i and X nonsingular are possible for 1 ? k ? n; and how well defined is a simultaneous block diagonalization for which k, the number of blocks, is maximal? Here a pair of r.s. matrices S and T is called nonsingular if S is nonsingular.If the number of blocks k is maximal, then one can speak of the finest simultaneous block diagonalization of S and T, since then the sizes of the blocks A_i are uniquely determined (up to permutations) by any set of generators of the pencil P(S, T) = {aS + bT|a, tb ε R} via the real Jordan normal form of S^?1T. The proof uses the canonical pair form theorem for nonsingular pairs of r.s. matrices. The maximal number k and the block sizes dim A_i are also determined by the factorization over C of ? (λ, μ) = det(λS + μT) for λ, μ ε R.     

Nonlinear Lie derivations on upper triangular matrices

Let M _n (𝔸) and T _n (𝔸) be the algebra of all n?×?n matrices and the algebra of all n?×?n upper triangular matrices over a commutative unital algebra 𝔸, respectively. In this note we prove that every nonlinear Lie derivation from T _n (𝔸) into M _n (𝔸) is of the form A?→?AT???TA?+?A _??+?ξ(A)I _n , where T?∈?M _n (𝔸), ??:?𝔸?→?𝔸 is an additive derivation, ξ?:?T _n (𝔸)?→?𝔸 is a nonlinear map with ξ(AB???BA)?=?0 for all A,?B?∈?T _n (𝔸) and A _? is the image of A under???applied entrywise.     

Essentially doubly stochastic matrices II. Canonical forms for row equivalence,equivalence, and a special case of congruence

In this paper we obtain canonical forms for row equivalence, equivalence, and a special case of congruence in the algebra of essentially doubly stochastic (e.d.s.) matrices of order n over a field F, char(F) [nmid] n. These forms are analogues of familiar forms in ordinary matrix algebra. The canonical form for equivalence is used in showing, in a subsequent paper, that every e.d.s. matrix of rank r and order n over F, char(F) = 0 or char(F) > n, is a product of elementary e.d.s. matrices, n – r of which are singular.     

To what extent is a large space of matrices not closed under product?

Let (K) be a field. Given an arbitrary linear subspace V of M_n(K) of codimension less than n-1, a classical result states that V generates the (K)-algebra M_n(K). Here, we strengthen this statement in three ways: we show that M_n(K) is spanned by the products of the form AB with (A,B)∈V²; we prove that every matrix in M_n(K) can be decomposed into a product of matrices of V; finally, when V is a linear perplane of M_n(K) and n>2, we show that every matrix in M_n(K) is a product of two elements of V.     

Regular orientable imbeddings of complete graphs

This paper classifies the regular imbeddings of the complete graphs K_n in orientable surfaces. Biggs showed that these exist if and only if n is a prime power p^e, his examples being Cayley maps based on the finite field F = GF(n). We show that these are the only examples, and that there are $\text{φ(n ? 1)}\text{e}$ isomorphism classes of such maps (where φ is Euler's function), each corresponding to a conjugacy class of primitive elements of F, or equivalently to an irreducible factor of the cyclotomic polynomial Φ_{n ? 1}(z) over GF(p). We show that these maps are all equivalent under Wilson's map-operations H_i, and we determined for which n they are reflexible or self-dual.     

The singular linear preservers of non-singular matrices

Given an arbitrary field K, we reduce the determination of the singular endomorphisms f of M_n(K) such that f(GL_n(K))⊂GL_n(K) to the classification of n-dimensional division algebras over K. Our method, which is based upon Dieudonné’s theorem on singular subspaces of M_n(K), also yields a proof for the classical non-singular case.     

A note on factorizations of singular M-matrices

Supposing that M is a singular M-matrix, we show that there exists a permutation matrix P such that PMP^T = LU, where L is a lower triangular M-matrix and U is an upper triangular singular M-matrix. An example is given to illustrate that the above result is the best possible one.