Problems involving diagonal products in nonnegative matrices
Richard Sinkhorn, Paul J. Knopp · Transactions of the American Mathematical Society · 1969
Introduction and definitions.A conjecture of B. L. van der Waerden states that the minimal value of the permanent of the n x n doubly stochastic matrices is n\jnn and is uniquely achieved at the matrix /" in which every element is l/n.In view of this problem and the fact that the permanent of a matrix is the sum of the diagonal products, this paper investigates the question of just how well the diagonal products of a matrix characterize that matrix.The results are stated for nonnegative matrices, but many of the theorems hold in a more general setting.The main result is the following.If A is an n x n nonnegative fully indecomposable matrix whose positive diagonal products are equal, there exists a unique matrix B of rank one which is positive and is such that ow=aw when aw>0.As a consequence of this it is shown that no two doubly stochastic matrices have corresponding diagonal products equal.Two of the main tools used in obtaining these results are well known.Proofs may be found in [3, pp.97-98].Frobenius-König Theorem.Every diagonal of annxn matrix A contains a zero element if and only if A has an sxt zero submatrix with s + t = n+l.Birkhoff's Theorem.The set of all nxn doubly stochastic matrices forms a convex polyhedron with the permutation matrices as vertices.We shall make use of the following notions and definitions.A (0, l)-matrix is a matrix in which every element is either 0 or 1.A diagonal of a square matrix is a collection of entries from the matrix, one from each row and one from each column.If a is a permutation of {1, 2,..., n} then the diagonal associated with cr is aiaa), a2a^,..., ana(n).Every diagonal corresponds to a permutation.A positive diagonal is a diagonal in which every aia(i)>0.A diagonal product is the product of the elements on a diagonal.A nonnegative square matrix A has doubly stochastic pattern if there is a doubly stochastic matrix B such that ai; = 0 if and only if bit=0.A consequence of Birkhoff's theorem is that a square matrix A has doubly stochastic pattern if and only if each positive entry lies on a positive diagonal.