Permanents of special classes of doubly stochastic matrices

We identify the doubly stochastic matrices with at least one zero entry which are closest in the Euclidean norm to J_n, the matrix with each entry equal to 1/n, and we show that at these matrices the permanent function has a relative minimum when restricted to doubly stochastic matrices having zero entries.     

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_nin Euclidean norm, where J_nis 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.     

Transportation matrices with staircase patterns and majorization

We consider some questions concerning transportation matrices with a certain nonzero pattern. For a given staircase pattern we characterize those row sum vectors R and column sum vectors S such that the corresponding class of transportation matrices with the given row and column sums and the given pattern is nonempty. Two versions of this problem are considered. Algorithms for finding matrices in these matrix classes are introduced and, finally, a connection to the notion of majorization is discussed.     

Efficiently computing the permanent and Hafnian of some banded Toeplitz matrices

We present a new efficient method for computing the permanent and Hafnian of certain banded Toeplitz matrices. The method covers non-trivial cases for which previous known methods do not apply. The main idea is to use the elements of the first row and column, which determine the entire Toeplitz matrix, to construct a digraph in which certain paths correspond to permutations that the permanent and Hafnian count. Since counting paths can be done efficiently, the permanent and Hafnian for those matrices is easily obtainable.     

Bijective linear rank preservers for spaces of matrices over antinegative semirings

We classify the bijective linear operators on spaces of matrices over antinegative commutative semirings with no zero divisors which preserve certain rank functions such as the symmetric rank, the factor rank and the tropical rank. We also classify the bijective linear operators on spaces of matrices over the max-plus semiring which preserve the Gondran-Minoux row rank or the Gondran-Minoux column rank.     

Row Stochastic Matrices Similar to Doubly Stochastic Matrices

The problem of determining which row stochastic n-by-n matrices are similar to doubly stochastic matrices is considered. That not all are is indicated by example, and an abstract characterization as well as various explicit sufficient conditions are given. For example, if a row stochastic matrix has no entry smaller than (n+1)^-1 it is similar to a doubly stochastic matrix.

Relaxing the nonnegativity requirement, the real matrices which are similar to real matrices with row and column sums one are then characterized, and it is observed that all row stochastic matrices have this property. Some remarks are then made on the nonnegative eigenvalue problem with respect to i) a necessary trace inequality and ii) removing zeroes from the spectrum.     

Intrinsic products and factorizations of matrices

We say that the product of a row vector and a column vector is intrinsic if there is at most one nonzero product of corresponding coordinates. Analogously we speak about intrinsic product of two or more matrices, as well as about intrinsic factorizations of matrices. Since all entries of the intrinsic product are products of entries of the multiplied matrices, there is no addition. We present several examples, together with important applications. These applications include companion matrices and sign-nonsingular matrices.     

Unitary matrix digraphs and minimum semidefinite rank

For an undirected simple graph G, the minimum rank among all positive semidefinite matrices with graph G is called the minimum semidefinite rank (msr) of G. In this paper, we show that the msr of a given graph may be determined from the msr of a related bipartite graph. Finding the msr of a given bipartite graph is then shown to be equivalent to determining which digraphs encode the zero/nonzero pattern of a unitary matrix. We provide an algorithm to construct unitary matrices with a certain pattern, and use previous results to give a lower bound for the msr of certain bipartite graphs.     

Singular, nonsingular, and bounded rank completions of ACI-matrices

An affine column independent matrix is a matrix whose entries are polynomials of degree at most 1 in a number of indeterminates where no indeterminate appears with a nonzero coefficient in two different columns. A completion is a matrix obtained by giving values to each of the indeterminates. Affine column independent matrices are more general than partial matrices where each entry is either a constant or a distinct indeterminate. We determine when the rank of all completions of an affine column independent matrix is bounded by a given number, generalizing known results for partial matrices. We also characterize the square partial matrices over a field all of whose completions are nonsingular. The maximum number of free entries in such matrices of a given order is determined as well as the partial matrices with this maximum number of free entries.     

The doubly stochastic matrix equations x:aty= A and X Aty=t

For a doubly stochastic matrix A, each of the equations x:a^ty= A and X A^ty=^t is shown to have doubly stochastic solutions X and Y if and only if A lies in a subgroup of the semigroup of all doubly stochastic matrices of a given order. All elements of this semigroup which are left regular, right regular, or intra-regular are identified.     

Convolution operators on Lebesgue spaces of an n-dimensional cube

This paper is concerned with the problem of diagonally scaling a given nonnegative matrix a to one with prescribed row and column sums. The approach is to represent one of the two scaling matrices as the solution of a variational problem. This leads in a natural way to necessary and sufficient conditions on the zero pattern of a so that such a scaling exists. In addition the convergence of the successive prescribed row and column sum normalizations is established. Certain invariants under diagonal scaling are used to actually compute the desired scaled matrix, and examples are provided. Finally, at the end of the paper, a discussion of infinite systems is presented.     

A note on matrix equivalence

Let R be a principal ideal ringR_n the ring of n × n it matrices over R. It is shown that if A, B, X, Y are elements of R* such that A = XB, B = YA, then A and B are left equivalent. Some consequences are given.     

Shorted operators of partitioned matrices and application

In this paper, our main objective is to study the effect of appending/deleting a column/row on the shorted operators. It turns out that for matrices A and B for which the shorted operator S(A|B) exists, S(A₁|B₁) of the matrix A₁=[A:a] with respect to the matrix B₁=[B:b], when it exists, is obtained by appending a suitable column to S(A|B). Moreover, if S(A₁|B₁) exists, then S(A|B) exists and is obtained from S(A₁|B₁) by dropping its last column. In the process, we study the effect of appending/deleting a column/row on the space pre-order and the parallel sum of parallel summable matrices. Finally, we specialize to the case of and matrices and study the effect of bordering (by an additional column and a row) on the shorted operator. We conclude the paper with an application to Linear Models with singular dispersion structure.     

The asymptotic number of non-negative integer matrices with given row and column sums

Asymptotics are obtained for the number of m×n non-negative integer matrices subject to the following constraints: (i) each row and each column sum is specified and bounded, (ii) the entries are bounded, and (iii) a specified “sparse” set of entries must be zero. The result can be interpreted in terms of incidence matrices for labeled digraphs.     

Multidimensional Permanents and an Upper Bound on the Number of Transversals in Latin Squares

The permanent of a multidimensional matrix is the sum of products of entries over all diagonals. A nonnegative matrix whose every 1‐dimensional plane sums to 1 is called polystochastic. A latin square of order n is an array of n symbols in which each symbol occurs exactly once in each row and each column. A transversal of such a square is a set of n entries such that no two entries share the same row, column, or symbol. Let T(n) be the maximum number of transversals over all latin squares of order n. Here, we prove that over the set of multidimensional polystochastic matrices of order n the permanent has a local extremum at the uniform matrix for whose every entry is equal to . Also, we obtain an asymptotic value of the maximal permanent for a certain set of nonnegative multidimensional matrices. In particular, we get that the maximal permanent of polystochastic matrices is asymptotically equal to the permanent of the uniform matrix, whence as a corollary we have an upper bound on the number of transversals in latin squares      

Notes on D-optimal designs

The purpose of this paper is to exhibit new infinite families of D-optimal (0, 1)-matrices. We show that Hadamard designs lead to D-optimal matrices of size (j, mj) and (j − 1, mj), for certain integers j ≡ 3 (mod 4) and all positive integers m. For j a power of a prime and j ≡ 1 (mod 4), supplementary difference sets lead to D-optimal matrices of size (j, 2mj) and (j − 1, 2mj), for all positive integers m. We also show that for a given j and d sufficiently large, about half of the entries in each column of a D-optimal matrix are ones. This leads to a new relationship between D-optimality for (0, 1)-matrices and for (±1)-matrices. Known results about D-optimal (±1)-matrices are then used to obtain new D-optimal (0, 1)-matrices.     

A matrix lower bound

Four essentially different interpretations of a lower bound for linear operators are shown to be equivalent for matrices (involving inequalities, convex sets, minimax problems, and quotient spaces). Properties stated by von Neumann in a restricted case are satisfied by the lower bound. Applications are made to rank reduction, s-numbers, condition numbers, and pseudospectra. In particular, the matrix lower bound is the distance to the nearest matrix with strictly contained row or column spaces, and it occurs in a condition number formula for any consistent system of linear equations, including those that are underdetermined.     

Spectral variation under congruence

In this paper we study the possible spectra among matrices congruent to a given AεM_n(C). It is important to distinguish singular A from nonsingular and, among non-singular matrices, to distinguish where 0 lies relative to the field of values of A.     

Tests for dimensionality and interactions of mean vectors under general and reducible covariance structures

Likelihood ratio tests are derived for testing the structure of mean values in a two-way classification. The most general hypothesis considered is when the mean values are subject to row and column effects and interaction has a given complexity. The observations corresponding to a row or a column classification are assumed to have an unknown dispersion (variance covariance) matrix. Two types of dispersion matrices are considered, one with a general and another with a reducible structure. Some special cases are considered. The results of the paper provide generalizations of tests on dimensionality and interactions in a two-way array of mean values considered by Fisher, Anderson, Fujikoshi, Mandel, and Rao.     

An extremal sparsity property of the Jordan canonical form

We prove that among all the matrices that are similar to a given square complex matrix, the Jordan canonical form has the largest number of off-diagonal zero entries. We also characterize those matrices that attain this largest number.