The growth factor of a Hadamard matrix of order 16 is 16

In 1968 Cryer conjectured that the growth factor of an n × n Hadamard matrix is n. In 1988 Day and Peterson proved this only for the Hadamard–Sylvester class. In 1995 Edelman and Mascarenhas proved that the growth factor of a Hadamard matrix of order 12 is 12. In the present paper we demonstrate the pivot structures of a Hadamard matrix of order 16 and prove for the first time that its growth factor is 16. The study is divided in two parts: we calculate pivots from the beginning and pivots from the end of the pivot pattern. For the first part we develop counting techniques based on symbolic manipulation for specifying the existence or non‐existence of specific submatrices inside the first rows of a Hadamard matrix, and so we can calculate values of principal minors. For the second part we exploit sophisticated numerical techniques that facilitate the computations of all possible (n ? j) × (n ? j) minors of Hadamard matrices for various values of j. The pivot patterns are obtained by utilizing appropriately the fact that the pivots appearing after the application of Gaussian elimination on a completely pivoted matrix are given as quotients of principal minors of the matrix. Copyright © 2009 John Wiley & Sons, Ltd.     

The DJL Conjecture for CP Matrices over Special Inclines

Drew, Johnson, and Loewy conjectured that for n ≥ 4, the CP-rank of every n × n completely positive real matrix is at most [n²/4]. While this conjecture has recently been disproved for completely positive real matrices, we show that this conjecture is true for n × n completely positive matrices over certain special types of inclines. In addition, we prove an incline version of Markham's theorems which gives sufficient conditions for completely positive matrices over special inclines to have triangular factorizations.     

Efficient generation of random nonsingular matrices

We present an efficient algorithm for generating an n × n nonsingular matrix uniformly over a finite field. This algorithm is useful for several cryptographic and checking applications. Over GF[2] our algorithm runs in expected time M(n) + O(n²), where M(n) is the time needed to multiply two n × n matrices, and the expected number of random bits it uses is n² + 3. (Over other finite fields we use n² + O(1) random field elements on average.) This is more efficient than the standard method for solving this problem, both in terms of expected running time and the expected number of random bits used. The standard method is to generate random n × n matrices until we produce one with nonzero determinant. In contrast, our technique directly produces a random matrix guaranteed to have nonzero determinant. We also introduce efficient algorithms for related problems such as uniformly generating singular matrices or matrices with fixed determinant. © 1993 John Wiley & Sons, Inc.     

Minimum permanents of doubly stochastic matrices with at least one zero entry †

It is shown that the minimum value of the permanent on the n× ndoubly stochastic matrices which contain at least one zero entry is achieved at those matrices nearest to J_n in Euclidean norm, where J_n is the n× nmatrix each of whose entries is n^-1 . In case n ≠ 3 the minimum permanent is achieved only at those matrices nearest J_n ; for n= 3 it is achieved at other matrices containing one or more zero entries as well.     

Discriminant of symmetric matrices as a sum of squares and the orthogonal group

It is proved that the discriminant of n × n real symmetric matrices can be written as a sum of squares, where the number of summands equals the dimension of the space of n‐variable spherical harmonics of degree n. The representation theory of the orthogonal group is applied to express the discriminant of 3 × 3 real symmetric matrices as a sum of five squares and to show that it cannot be written as the sum of less than five squares. It is proved that the discriminant of 4 × 4 real symmetric matrices can be written as a sum of seven squares. These improve results of Kummer from 1843 and Borchardt from 1846. © 2010 Wiley Periodicals, Inc.     

The LU-factorization of totally positive matrices

An n × n real matrix A is an STP (strictly totally positive) matrix if all its minors are strictly positive. An n × n real triangular matrix A is a ΔSTP matrix if all its nontrivial minors are strictly positive. It is proved that A is an STP matrix iff A = LU where L is a lower triangular matrix, U is an upper triangular matrix, and both L and U are ΔSTP matrices. Several related results are proved. These results lead to simple proofs of many of the determinantal properties of STP matrices.     

A note on commuting pairs of matrices

We give a short proof of the Motzkin-Taussky result that the variety of commuting pairs of matrices is irreducible. An easy consequence of this is that any two generated commutative subalgebra of n×n matrices has dimension at most n. We also answer an old question of Gerstenhaber by showing that the set of commuting triples of n×n matrices is not irreducible for n≥32.     

Indecomposable matrices over a distributive lattice

In this paper, the concepts of indecomposable matrices and fully indecomposable matrices over a distributive lattice L are introduced, and some algebraic properties of them are obtained. Also, some characterizations of the set F _n (L) of all n × n fully indecomposable matrices as a subsemigroup of the semigroup H _n (L) of all n × n Hall matrices over the lattice L are given.     

The packing property

A clutter (V, E) packs if the smallest number of vertices needed to intersect all the edges (i.e. a minimum transversal) is equal to the maximum number of pairwise disjoint edges (i.e. a maximum matching). This terminology is due to Seymour 1977. A clutter is minimally nonpacking if it does not pack but all its minors pack. An m×n 0,1 matrix is minimally nonpacking if it is the edge-vertex incidence matrix of a minimally nonpacking clutter. Minimally nonpacking matrices can be viewed as the counterpart for the set covering problem of minimally imperfect matrices for the set packing problem. This paper proves several properties of minimally nonpacking clutters and matrices. Received: December 1, 1997 / Accepted: April 6, 1999?Published online October 18, 2000     

Quadratically normal and congruence-normal matrices

A matrix A ∈ C ^n×n is unitarily quasidiagonalizable if A can be brought by a unitary similarity transformation to a block diagonal form with 1 × 1 and 2 × 2 diagonal blocks. In particular, the square roots of normal matrices, i.e., the so-called quadratically normal matrices are unitarily quasidiagonalizable. A matrix A ∈ C ^n×n is congruence-normal if B = A[`(A)] B = A\overline A is a conventional normal matrix. We show that every congruence-normal matrix A can be brought by a unitary congruence transformation to a block diagonal form with 1 × 1 and 2 × 2 diagonal blocks. Our proof emphasizes andexploitsalikenessbetween theequations X <sup>2</sup> = B and X[`(X)] = B X\overline X = B for a normal matrix B. Bibliography: 13 titles.     

Matrices diagonally similar to a symmetric matrix

Let $\text{F}$ be field, and let A and B be n × n matrices with elements in $\text{F}$. Suppose that A is completely reducible and that B is symmetric. If the principal minors of A determined by the 1- and 2-circuits of the graph of B and by the chordless circuits of the graph of A are equal to the corresponding principal minors of B, then A is diagonally similar to B; and conversely.     

The rank of a 2 × 2 × 2 tensor

As computing power increases, many more problems in engineering and data analysis involve computation with tensors, or multi-way data arrays. Most applications involve computing a decomposition of a tensor into a linear combination of rank-1 tensors. Ideally, the decomposition involves a minimal number of terms, i.e. computation of the rank of the tensor. Tensor rank is not a straight-forward extension of matrix rank. A constructive proof based on an eigenvalue criterion is provided that shows when a 2?×?2?×?2 tensor over ? is rank-3 and when it is rank-2. The results are extended to show that n?×?n?×?2 tensors over ? have maximum possible rank n?+?k where k is the number of complex conjugate eigenvalue pairs of the matrices forming the two faces of the tensor cube.     

A generating function for all semi-magic squares and the volume of the Birkhoff polytope

We present a multivariate generating function for all n×n nonnegative integral matrices with all row and column sums equal to a positive integer t, the so called semi-magic squares. As a consequence we obtain formulas for all coefficients of the Ehrhart polynomial of the polytope B _n of n×n doubly-stochastic matrices, also known as the Birkhoff polytope. In particular we derive formulas for the volumes of B _n and any of its faces.     

Products of involutory matrices. I

It is shown that, for every integer ?1 and every field F, each n×n matrix over F of determinant ±1 is the product of four involutory matrices over F. Products of three ×n involutory matrices over F are characterized for the special cases where n?4 or F has prime order ?5. It is also shown for every field F that every matrix over F of determinant ±1 having no more than two nontrivial invariant factors is a product of three involutory matrices over F.     

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.     

On inverse multiplicative eigenvalue problems for matrices

Let A be an n×n complex-valued matrix, all of whose principal minors are distinct from zero. Then there exists a complex diagonal matrix D, such that the spectrum of AD is a given set σ = {λ₁,…,λ_n} in C. The number of different matrices D is at most n!.     

A problem of Westwick on k-spaces

Sets n×n matrices linear span contains only matrices of rank n?1 and 0 are investigated. To within a natural equivalence they are characterised for n ? 6. Partial results are obtained for general n.     

A fast method to block-diagonalize a Hankel matrix

In this paper, we consider an approximate block diagonalization algorithm of an n×n real Hankel matrix in which the successive transformation matrices are upper triangular Toeplitz matrices, and propose a new fast approach to compute the factorization in O(n ²) operations. This method consists on using the revised Bini method (Lin et al., Theor Comp Sci 315: 511–523, 2004). To motivate our approach, we also propose an approximate factorization variant of the customary fast method based on Schur complementation adapted to the n×n real Hankel matrix. All algorithms have been implemented in Matlab and numerical results are included to illustrate the effectiveness of our approach.     

Minimum permanents of doubly stochastic matrices with prescribed zero entries †

A study of properties of matrices with minimum permanent in a face of the polyhedron of doubly stochastic n × n matrices. The minima are determined for certain faces.     

Noncirculant Toeplitz matrices all of whose powers are Toeplitz

Let a, b and c be fixed complex numbers. Let M _n (a, b, c) be the n × n Toeplitz matrix all of whose entries above the diagonal are a, all of whose entries below the diagonal are b, and all of whose entries on the diagonal are c. For 1 ⩽ k ⩽ n, each k × k principal minor of M _n (a, b, c) has the same value. We find explicit and recursive formulae for the principal minors and the characteristic polynomial of M _n (a, b, c). We also show that all complex polynomials in M _n (a, b, c) are Toeplitz matrices. In particular, the inverse of M _n (a, b, c) is a Toeplitz matrix when it exists.