Subtotally positive and Monge matrices

A real matrix is called k-subtotally positive if the determinants of all its submatrices of order at most k are positive. We show that for an m × n matrix, only mn inequalities determine such class for every k, 1 ? k ? min(m,n). Spectral properties of square k-subtotally positive matrices are studied. Finally, completion problems for 2-subtotally positive matrices and their additive counterpart, the anti-Monge matrices, are investigated. Since totally positive matrices are 2-subtotally positive as well, the presented necessary conditions for this completion problem are also necessary conditions for totally positive matrices.     

2-Adic valuations of certain ratios of products of factorials and applications

We prove the conjecture of Falikman-Friedland-Loewy on the parity of the degrees of projective varieties of n×n complex symmetric matrices of rank at most k. We also characterize the parity of the degrees of projective varieties of n×n complex skew symmetric matrices of rank at most 2p. We give recursive relations which determine the parity of the degrees of projective varieties of m×n complex matrices of rank at most k. In the case the degrees of these varieties are odd, we characterize the minimal dimensions of subspaces of n×n skew symmetric real matrices and of m×n real matrices containing a nonzero matrix of rank at most k. The parity questions studied here are also of combinatorial interest since they concern the parity of the number of plane partitions contained in a given box, on the one hand, and the parity of the number of symplectic tableaux of rectangular shape, on the other hand.     

The automorphism groups of Reed-Solomon codes

A class of maximum distance separable codes is introduced which includes Reed Solomon codes; extended Reed-Solomon codes, and other cyclic or pseudocyclie MDS codes studied recently. This class of codes, which we call “Cauchy codes” because of the special form of their generator matrices, forms a closed submanifold of dimension 2n - 4 in the k × (n - k)-dimensional algebraic manifold of all MDS codes of length n and dimension k. For every Cauchy code we determine the automorphism group and its underlying permutation group. Far doubly-extended Reed-Solomon codes over GF(q) the permutation group is the semilinear fractional group PΛL(2, q).     

Required nonzero patterns for nonsingular sign regular matrices

An n×n real matrix is called sign regular if, for each k(1?k?n), all its minors of order k have the same nonstrict sign. The zero entries which can appear in a nonsingular sign regular matrix depend on its signature because the signature can imply that certain entries are necessarily nonzero. The patterns for the required nonzero entries of nonsingular sign regular matrices are analyzed.     

The Littlewood-Offord problem and invertibility of random matrices

We prove two basic conjectures on the distribution of the smallest singular value of random n×n matrices with independent entries. Under minimal moment assumptions, we show that the smallest singular value is of order n−1/2, which is optimal for Gaussian matrices. Moreover, we give a optimal estimate on the tail probability. This comes as a consequence of a new and essentially sharp estimate in the Littlewood-Offord problem: for i.i.d. random variables Xk and real numbers ak, determine the probability p that the sum k_∑akXk lies near some number v. For arbitrary coefficients ak of the same order of magnitude, we show that they essentially lie in an arithmetic progression of length 1/p.     

The higher-order derivatives of spectral functions

We are interested in higher-order derivatives of functions of the eigenvalues of real symmetric matrices with respect to the matrix argument. We describe a formula for the k-th derivative of such functions in two general cases.The first case concerns the derivatives of the composition of an arbitrary (not necessarily symmetric) k-times differentiable function with the eigenvalues of symmetric matrices at a symmetric matrix with distinct eigenvalues.The second case describes the derivatives of the composition of a k-times differentiable separable symmetric function with the eigenvalues of symmetric matrices at an arbitrary symmetric matrix. We show that the formula significantly simplifies when the separable symmetric function is k-times continuously differentiable.As an application of the developed techniques, we re-derive the formula for the Hessian of a general spectral function at an arbitrary symmetric matrix. The new tools lead to a shorter, cleaner derivation than the original one.To make the exposition as self contained as possible, we have included the necessary background results and definitions. Proofs of the intermediate technical results are collected in the appendices.     

Nilpotent sign patterns of a given index

A sign pattern is said to be nilpotent of index k if all real matrices in its qualitative class are nilpotent and their maximum nilpotent index equals k. In this paper, we characterize sign patterns that are nilpotent of a given index k. The maximum number of nonzero entries in such sign patterns of a given order is determined as well as the sign patterns with this maximum number of nonzero entries.     

On approximately simultaneously diagonalizable matrices

A collection A₁, A₂, …, A_k of n × n matrices over the complex numbers C has the ASD property if the matrices can be perturbed by an arbitrarily small amount so that they become simultaneously diagonalizable. Such a collection must perforce be commuting. We show by a direct matrix proof that the ASD property holds for three commuting matrices when one of them is 2-regular (dimension of eigenspaces is at most 2). Corollaries include results of Gerstenhaber and Neubauer-Sethuraman on bounds for the dimension of the algebra generated by A₁, A₂, …, A_k. Even when the ASD property fails, our techniques can produce a good bound on the dimension of this subalgebra. For example, we establish for commuting matrices A₁, …, A_k when one of them is 2-regular. This bound is sharp. One offshoot of our work is the introduction of a new canonical form, the H-form, for matrices over an algebraically closed field. The H-form of a matrix is a sparse “Jordan like” upper triangular matrix which allows us to assume that any commuting matrices are also upper triangular. (The Jordan form itself does not accommodate this.)     

The centro-invertible matrix: A new type of matrix arising in pseudo-random number generation

This paper defines a new type of matrix (which will be called a centro-invertible matrix) with the property that the inverse can be found by simply rotating all the elements of the matrix through 180 degrees about the mid-point of the matrix. Centro-invertible matrices have been demonstrated in a previous paper to arise in the analysis of a particular algorithm used for the generation of uniformly-distributed pseudo-random numbers.An involutory matrix is one for which the square of the matrix is equal to the identity. It is shown that there is a one-to-one correspondence between the centro-invertible matrices and the involutory matrices. When working in modular arithmetic this result allows all possible k by k centro-invertible matrices with integer entries modulo M to be enumerated by drawing on existing theoretical results for involutory matrices.Consider the k by k matrices over the integers modulo M. If M takes any specified finite integer value greater than or equal to two then there are only a finite number of such matrices and it is valid to consider the likelihood of such a matrix arising by chance. It is possible to derive both exact expressions and order-of-magnitude estimates for the number of k by k centro-invertible matrices that exist over the integers modulo M. It is shown that order (√N) of the N=M^(k2) different k by k matrices modulo M are centro-invertible, so that the proportion of these matrices that are centro-invertible is order (1/√N).     

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.     

Real rank versus nonnegative rank

We consider the set of m×n nonnegative real matrices and define the nonnegative rank of a matrix A to be the minimum k such that A=BC where B is m×k and C is k×n. Given that the real rank of A is j for some j, we give bounds on the nonnegative rank of A and A².     

Uniqueness of analytic continuation: Necessary and sufficient conditions

Necessary and sufficient conditions for uniqueness of analytic continuation are investigated for a system of m ? 1 first-order linear homogeneous partial differential equations in one unknown, with complex-valued $\text{b}$^∞ coefficients, in some connected open subset of $\text{R}$^k, k ? 2. The type of system considered is one for which there exists a real k-dimensional, $\text{b}$^∞, connected C-R submanifold M^k of $\text{C}$ⁿ, for k, n ? 2, such that the system may be identified with the induced Cauchy-Riemann operators on M^k. The question of uniqueness of analytic continuation for a system of partial differential equations is thus transformed to the question of uniqueness of analytic continuation for C-R functions on the manifold M^k ? Cⁿ. Under the assumption that the Levi algebra of M^k has constant dimension, it is shown that if the excess dimension of this algebra is maximal at every point, then M^k has the property of uniqueness of analytic continuation for its C-R functions. Conversely, under certain mild conditions, it is shown that if M^k has the property of uniqueness of analytic continuation for all $\text{b}$^∞ C-R functions, and if the Levi algebra has constant dimension on all of M^k, then the excess dimension must be maximal at every point of M^k.     

On the representability of totally unimodular matrices on bidirected graphs

We present a polynomial time algorithm to construct a bidirected graph for any totally unimodular matrix B by finding node-edge incidence matrices Q and S such that QB=S. Seymour’s famous decomposition theorem for regular matroids states that any totally unimodular (TU) matrix can be constructed through a series of composition operations called k-sums starting from network matrices and their transposes and two compact representation matrices B₁,B₂ of a certain ten element matroid. Given that B₁,B₂ are binet matrices we examine the k-sums of network and binet matrices. It is shown that thek-sum of a network and a binet matrix is a binet matrix, but binet matrices are not closed under this operation for k=2,3. A new class of matrices is introduced, the so-called tour matrices, which generalise network, binet and totally unimodular matrices. For any such matrix there exists a bidirected graph such that the columns represent a collection of closed tours in the graph. It is shown that tour matrices are closed under k-sums, as well as under pivoting and other elementary operations on their rows and columns. Given the constructive proofs of the above results regarding the k-sum operation and existing recognition algorithms for network and binet matrices, an algorithm is presented which constructs a bidirected graph for any TU matrix.     

On Hadamard embeddability

Given any k vectors of dimension nk which are mutually orthogonal, it is well known that this matrix can be completed to an n×n orthogonal matrix. Hadamard matrices form a subclass of orthogonal matrices. By contrast it is shown that it is possible to construct Hadamard submatrices with 2t+2 rows that cannot be completed to a Hadamard matrix of order 4t for infinitely many values of t. Some familiarity with Hasse–Minkowski invariants is assumed. A large number of unsolved problems in this area are pointed out.     

Characterizations of inverse M-matrices with special zero patterns

In this paper, we provide some characterizations of inverse M-matrices with special zero patterns. In particular, we give necessary and sufficient conditions for k-diagonal matrices and symmetric k-diagonal matrices to be inverse M-matrices. In addition, results for triadic matrices, tridiagonal matrices and symmetric 5-diagonal matrices are presented as corollaries.     

Codes from incidence matrices of graphs

We examine the p-ary codes, for any prime p, from the row span over ${\mathbb {F}_p}$ of |V| × |E| incidence matrices of connected graphs Γ = (V, E), showing that certain properties of the codes can be directly derived from the parameters and properties of the graphs. Using the edge-connectivity of Γ (defined as the minimum number of edges whose removal renders Γ disconnected) we show that, subject to various conditions, the codes from such matrices for a wide range of classes of connected graphs have the property of having dimension |V| or |V| ? 1, minimum weight the minimum degree δ(Γ), and the minimum words the scalar multiples of the rows of the incidence matrix of this weight. We also show that, in the k-regular case, there is a gap in the weight enumerator between k and 2k ? 2 of the binary code, and also for the p-ary code, for any prime p, if Γ is bipartite. We examine also the implications for the binary codes from adjacency matrices of line graphs. Finally we show that the codes of many of these classes of graphs can be used for permutation decoding for full error correction with any information set.     

On the dimension of some real spaces of bounded rank matrices

Given n∈N, let X be either the set of hermitian or real n×n matrices of rank at least n-1. If n is even, we give a sharp estimate on the maximal dimension of a real vector space V⊂X∪{0}. The results are obtained, via K-theory, by studying a bundle map induced by the adjunction of matrices.     

Linear pencils on real algebraic curves

Our knowledge of linear series on real algebraic curves is still very incomplete. In this paper we restrict to pencils (complete linear series of dimension one). Let X denote a real curve of genus g with real points and let k(R) be the smallest degree of a pencil on X (the real gonality of X). Then we can find on X a base point free pencil of degree g+1 (resp. g if X is not hyperelliptic, i.e. if k(R)>2) with an assigned geometric behaviour w.r.t. the real components of X, and if we prove that which is the same bound as for the gonality of a complex curve of even genus g. Furthermore, if the complexification of X is a k-gonal curve (k≥2) one knows that k≤k(R)≤2k−2, and we show that for any two integers k≥2 and 0≤n≤k−2 there is a real curve with real points and k-gonal complexification such that its real gonality is k+n.     

Semisimilarity for matrices over a division ring

Two square matrices A and B over a ring R are semisimilar, written A$\text{?}$B, if YAX=B and XBY=A for some (possibly rectangular) matrices X, Y over R. We show that if A and B have the same dimension, and if the ring is a division ring $\text{D}$, then A$\text{?}$B if and only if A² is similar to B² and rank(A^k)=rank(B^k), k=1,2,…     

Pfaffian point process for the Gaussian real generalised eigenvalue problem

The generalised eigenvalues for a pair of N?× N matrices (X ₁, X ₂) are defined as the solutions of the equation det (X ₁ ? λX ₂)?=?0, or equivalently, for X ₂ invertible, as the eigenvalues of ${X_{2}^{-1}X_{1}}$ . We consider Gaussian real matrices X ₁, X ₂, for which the generalised eigenvalues have the rotational invariance of the half-sphere, or after a fractional linear transformation, the rotational invariance of the unit disk. In these latter variables we calculate the joint eigenvalue probability density function, the probability p _N,k of finding k real eigenvalues, the densities of real and complex eigenvalues (the latter being related to an average over characteristic polynomials), and give an explicit Pfaffian formula for the higher correlation functions ${\rho_{(k_1,k_2)}}$ . A limit theorem for p _N,k is proved, and the scaled form of ${\rho_{(k_1,k_2)}}$ is shown to be identical to the analogous limit for the correlations of the eigenvalues of real Gaussian matrices. We show that these correlations satisfy sum rules characteristic of the underlying two-component Coulomb gas.