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.     

Orbits of Nilpotent Matrices

The action under conjugation of invertible lower triangular n×n matrices (over an infinite field) on lower triangular nilpotent matrices, N_n, divides N_n into orbits. We show that for n?6 the number of orbits is infinite.     

Invertible and nilpotent matrices over antirings

In this paper, we characterize invertible matrices over an arbitrary commutative antiring S with 1 and find the structure of GL_n(S). We find the number of nilpotent matrices over an entire commutative finite antiring. We prove that every nilpotent n×n matrix over an entire antiring can be written as a sum of ⌈log₂n⌉ square-zero matrices and also find the necessary number of square-zero summands for an arbitrary trace-zero matrix to be expressible as their sum.     

On orthostochastic, unistochastic and qustochastic matrices

We introduce qustochastic matrices as the bistochastic matrices arising from quaternionic unitary matrices by replacing each entry with the square of its norm. This is the quaternionic analogue of the unistochastic matrices studied by physicists. We also introduce quaternionic Hadamard matrices and quaternionic mutually unbiased bases (MUB). In particular we show that the number of MUB in an n-dimensional quaternionic Hilbert space is at most 2n+1. The bound is attained for n=2. We also determine all quaternionic Hadamard matrices of size n?4.     

Generalized inverses of matrices over fields of characteristic two

For F a field of characteristic two, the problem of determining which m×n matrices of rank r have normalized generalized inverses and which have pseudoinverses is solved. For F_q a finite field of characteristic two, both the number of m×n matrices of rank r over F which have normalized generalized inverses and the number of m×n matrices of rank r over F_q which have pseudoinverses are determined.     

Linear relations of refined enumerations of alternating sign matrices

In recent papers we have studied refined enumerations of alternating sign matrices with respect to a fixed set of top and bottom rows. The present paper is a first step towards extending these considerations to alternating sign matrices where in addition some left and right columns are fixed. The main result is a simple linear relation between the number of n×n alternating sign matrices where the top row as well as the left and the right column is fixed and the number of n×n alternating sign matrices where the two top rows and the bottom row are fixed. This may be seen as a first indication for the fact that the refined enumerations of alternating sign matrices with respect to a fixed set of top and bottom rows as well as left and right columns can possibly be reduced to the refined enumerations where only some top and bottom rows are fixed. For the latter numbers we provide a system of linear equations that conjecturally determines them uniquely.     

A problem on conjugacy of matrices

Let F be an infinite field and n?12. Then the number of conjugacy classes of the upper triangular nilpotent matrices in M_n(F) under action by the subgroup of GL_n(F) consisting of all the upper triangular matrices is infinite.     

Finiteness of circulant weighing matrices of fixed weight

Let n be a fixed positive integer. Every circulant weighing matrix of weight n arises from what we call an irreducible orthogonal family of weight n. We show that the number of irreducible orthogonal families of weight n is finite and thus obtain a finite algorithm for classifying all circulant weighing matrices of weight n. We also show that, for every odd prime power q, there are at most finitely many proper circulant weighing matrices of weight q.     

Minimal condition number for positive definite Hankel matrices using semidefinite programming

We present a semidefinite programming approach for computing optimally conditioned positive definite Hankel matrices of order n. Unlike previous approaches, our method is guaranteed to find an optimally conditioned positive definite Hankel matrix within any desired tolerance. Since the condition number of such matrices grows exponentially with n, this is a very good test problem for checking the numerical accuracy of semidefinite programming solvers. Our tests show that semidefinite programming solvers using fixed double precision arithmetic are not able to solve problems with n>30. Moreover, the accuracy of the results for 24?n?30 is questionable. In order to accurately compute minimal condition number positive definite Hankel matrices of higher order, we use a Mathematica 6.0 implementation of the SDPHA solver that performs the numerical calculations in arbitrary precision arithmetic. By using this code, we have validated the results obtained by standard codes for n?24, and we have found optimally conditioned positive definite Hankel matrices up to n=100.     

Information about group matrices

Each ordering for the elements of a finite group G of order n defines a corresponding class of group matrices for G. First, this paper proves that the number of distinct classes of group matrices for G equals (n ? 1)!/m, where m is the number of automorphisms of G. Then, a study is made of a block-diagonal reduction for the group matrices of any particular class.     

A new proof of the refined alternating sign matrix theorem

In the early 1980s, Mills, Robbins and Rumsey conjectured, and in 1996 Zeilberger proved a simple product formula for the number of n×n alternating sign matrices with a 1 at the top of the ith column. We give an alternative proof of this formula using our operator formula for the number of monotone triangles with prescribed bottom row. In addition, we provide the enumeration of certain 0-1-(−1) matrices generalizing alternating sign matrices.     

The group-theoretic complexity of subsemigroups of boolean matrices

We find the group-theoretic complexity of many subsemigroups of the semigroup B_n of n × n Boolean matrices, including Hall matrices, reflexive matrices, fully indecomposable matrices, upper triangular matrices, row-rank-n matrices, and others.     

Determinants of matrices over commutative finite principal ideal rings

In this paper, the determinants of $n\times n$ matrices over commutative finite chain rings and over commutative finite principal ideal rings are studied. The number of $n\times n$ matrices over a commutative finite chain ring R of a fixed determinant a is determined for all $a\in R$ and positive integers n. Using the fact that every commutative finite principal ideal ring is a product of commutative finite chain rings, the number of $n\times n$ matrices of a fixed determinant over a commutative finite principal ideal ring is shown to be multiplicative, and hence, it can be determined. These results generalize the case of matrices over the ring of integers modulo m.     

On the accuracy of the Gerschgorin circle theorem for bounding the spread of a real symmetric matrix

The spread of a matrix with real eigenvalues is the difference between its largest and smallest eigenvalues. The Gerschgorin circle theorem can be used to bound the extreme eigenvalues of the matrix and hence its spread. For nonsymmetric matrices the Gerschgorin bound on the spread may be larger by an arbitrary factor than the actual spread even if the matrix is symmetrizable. This is not true for real symmetric matrices. It is shown that for real symmetric matrices (or complex Hermitian matrices) the ratio between the bound and the spread is bounded by $\text{p+1}$, where p is the maximum number of off diagonal nonzeros in any row of the matrix. For full matrices this is just $\text{n}$. This bound is not quite sharp for n greater than 2, but examples with ratios of $\text{n?1}$ for all n are given. For banded matrices with m nonzero bands the maximum ratio is bounded by $\text{m}$ independent of the size of n. This bound is sharp provided only that n is at least 2m. For sparse matrices, p may be quite small and the Gerschgorin bound may be surprisingly accurate.     

The bilinear complexity and practical algorithms for matrix multiplication

A method for deriving bilinear algorithms for matrix multiplication is proposed. New estimates for the bilinear complexity of a number of problems of the exact and approximate multiplication of rectangular matrices are obtained. In particular, the estimate for the boundary rank of multiplying 3 × 3 matrices is improved and a practical algorithm for the exact multiplication of square n × n matrices is proposed. The asymptotic arithmetic complexity of this algorithm is O(n ^2.7743).     

Stopping criteria for the Ando-Li-Mathias and Bini-Meini-Poloni geometric means

We provide an upper bound for the number of iterations necessary to achieve a desired level of accuracy for the Ando-Li-Mathias [Linear Algebra Appl. 385 (2004) 305-334] and Bini-Meini-Poloni [Math. Comput. 79 (2010) 437-452] symmetrization procedures for computing the geometric mean of n positive definite matrices, where accuracy is measured by the spectral norm and the Thompson metric on the convex cone of positive definite matrices. It is shown that the upper bound for the number of iterations depends only on the diameter of the set of n matrices and the desired convergence tolerance. A striking result is that the upper bound decreases as n increases on any bounded region of positive definite matrices.     

Involutory matrices over finite commutative rings

An n × n matrix A is called involutory iff A²=I_n, where I_n is the n × n identity matrix. This paper is concerned with involutory matrices over an arbitrary finite commutative ring R with identity and with the similarity relation among such matrices. In particular the authors seek a canonical set $\text{C}$ with respect to similarity for the n × n involutory matrices over R—i.e., a set $\text{C}$ of n × n involutory matrices over R with the property that each n × n involutory matrix over R is similar to exactly on matrix in $\text{C}$. Because of the structure of finite commutative rings and because of previous research, they are able to restrict their attention to finite local rings of characteristic a power of 2, and although their main result does not completely specify a canonical set $\text{C}$ for such a ring, it does solve the problem for a special class of rings and shows that a solution to the general case necessarily contains a solution to the classically unsolved problem of simultaneously bringing a sequence A₁,…,A_v of (not necessarily involutory) matrices over a finite field of characteristic 2 to canonical form (using the same similarity transformation on each A_i). (More generally, the authors observe that a theory of similarity fot matrices over an arbitrary local ring, such as the well-known rational canonical theory for matrices over a field, necessarily implies a solution to the simultaneous canonical form problem for matrices over a field.) In a final section they apply their results to find a canonical set for the involutory matrices over the ring of integers modulo 2^m and using this canonical set they are able to obtain a formula for the number of n × n involutory matrices over this ring.     

On the weighted enumeration of alternating sign matrices and descending plane partitions

We prove a conjecture of Mills, Robbins and Rumsey [Alternating sign matrices and descending plane partitions, J. Combin. Theory Ser. A 34 (3) (1983) 340-359] that, for any n, k, m and p, the number of n×n alternating sign matrices (ASMs) for which the 1 of the first row is in column k+1 and there are exactly m −1?s and m+p inversions is equal to the number of descending plane partitions (DPPs) for which each part is at most n and there are exactly k parts equal to n, m special parts and p nonspecial parts. The proof involves expressing the associated generating functions for ASMs and DPPs with fixed n as determinants of n×n matrices, and using elementary transformations to show that these determinants are equal. The determinants themselves are obtained by standard methods: for ASMs this involves using the Izergin-Korepin formula for the partition function of the six-vertex model with domain-wall boundary conditions, together with a bijection between ASMs and configurations of this model, and for DPPs it involves using the Lindström-Gessel-Viennot theorem, together with a bijection between DPPs and certain sets of nonintersecting lattice paths.