Simple existence conditions for zero-one matrices with at most one structural zero in each row and column

We give simple necessary and sufficient conditions for the existence of a zero-one matrix with given row and column sums and at most one structural zero in each row and column.     

On some methods for entropy maximization and matrix scaling

We describe and survey in this paper iterative algorithms for solving the discrete maximum entropy problem with linear equality constraints. This problem has applications e.g. in image reconstruction from projections, transportation planning, and matrix scaling. In particular we study local convergence and asymptotic rate of convergence as a function of the iteration parameter. For the trip distribution problem in transportation planning and the equivalent problem of scaling a positive matrix to achieve a priori given row and column sums, it is shown how the iteration parameters can be chosen in an optimal way. We also consider the related problem of finding a matrix X, diagonally similar to a given matrix, such that corresponding row and column norms in X are all equal. Reports of some numerical tests are given.     

Decomposition of infinite matrices

We consider the problem of decomposing a matrix of integers according to constraints on the row and column sums, in the case when the original matrix is infinite. Some necessary conditions and some sufficient conditions are found for the existence of such a decomposition, generalizing results of Ball for the finite case. Connections with the Transversal Problem for infinite sets are pointed out.     

Matrices with prescribed row and column sums

This is a survey of the recent progress and open questions on the structure of the sets of 0–1 and non-negative integer matrices with prescribed row and column sums. We discuss cardinality estimates, the structure of a random matrix from the set, discrete versions of the Brunn–Minkowski inequality and the statistical dependence between row and column sums.     

Reconstructing Convex Matrices by Integer Programming Approaches

We consider the problem of reconstructing two-dimensional convex binary matrices from their row and column sums with adjacent ones. Instead of requiring the ones to occur consecutively in each row and column, we maximize the number of adjacent ones. We reformulate the problem by using integer programming and we develop approximate solutions based on linearization and convexification techniques.     

Biproportional scaling of matrices and the iterative proportional fitting procedure

A short proof is given of the necessary and sufficient conditions for the convergence of the Iterative Proportional Fitting procedure. The input consists of a nonnegative matrix and of positive target marginals for row sums and for column sums. The output is a sequence of scaled matrices to approximate the biproportional fit, that is, the scaling of the input matrix by means of row and column divisors in order to fit row and column sums to target marginals. Generally it is shown that certain structural properties of a biproportional scaling do not depend on the particular sequence used to approximate it. Specifically, the sequence that emerges from the Iterative Proportional Fitting procedure is analyzed by means of the L ₁-error that measures how current row and column sums compare to their target marginals. As a new result a formula for the limiting L ₁-error is obtained. The formula is in terms of partial sums of the target marginals, and easily yields the other well-known convergence characterizations.     

Random dense bipartite graphs and directed graphs with specified degrees

Let s and t be vectors of positive integers with the same sum. We study the uniform distribution on the space of simple bipartite graphs with degree sequence s in one part and t in the other; equivalently, binary matrices with row sums s and column sums t . In particular, we find precise formulae for the probabilities that a given bipartite graph is edge‐disjoint from, a subgraph of, or an induced subgraph of a random graph in the class. We also give similar formulae for the uniform distribution on the set of simple directed graphs with out‐degrees s and in‐degrees t . In each case, the graphs or digraphs are required to be sufficiently dense, with the degrees varying within certain limits, and the subgraphs are required to be sufficiently sparse. Previous results were restricted to spaces of sparse graphs. Our theorems are based on an enumeration of bipartite graphs avoiding a given set of edges, proved by multidimensional complex integration. As a sample application, we determine the expected permanent of a random binary matrix with row sums s and column sums t . © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Constructing integral matrices with given line sums

D. Gale, in 1957 and H.J. Ryser, in 1963, independently proved the famous Gale–Ryser theorem on the existence of (0, 1)–matrices with prescribed row and column sums. Around the same time, in 1968, Mirsky solved the more general problem of finding conditions for the existence of a nonnegative integral matrix with entries less than or equal to p and prescribed row and column sums. Using the results of Mirsky, Brualdi shows that a modified version of the domination condition of Gale–Ryser is still necessary and sufficient for the existence of a matrix under the same constraints. In this article we prove another extension of Gale–Ryser’s domination condition. Furthermore we present a method to build nonnegative integral matrices with entries less than or equal to p and prescribed row and column sums.     

Vector Optimization Problems with Generalized Functional Constraints in Variable Ordering Structure Setting

This paper connects discrete optimal transport to a certain class of multi-objective optimization problems. In both settings, the decision variables can be organized into a matrix. In the multi-objective problem, the notion of Pareto efficiency is defined in terms of the objectives together with nonnegativity constraints and with equality constraints that are specified in terms of column sums. A second set of equality constraints, defined in terms of row sums, is used to single out particular points in the Pareto-efficient set which are referred to as “balanced solutions.” Examples from several fields are shown in which this solution concept appears naturally. Balanced solutions are shown to be in one-to-one correspondence with solutions of optimal transport problems. As an example of the use of alternative interpretations, the computation of solutions via regularization is discussed.     

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.     

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.     

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.     

Sufficient conditions for permutation equivalence to a WHS-matrix

Square matrices with positive leading principal minors, called WHS-matrices (weak Hawkins–Simon), are considered in economics. Some sufficient conditions for a matrix to be a WHS-matrix after suitable row and/or column permutations have recently appeared in the literature. New and unified proofs and generalizations of some results to rectangular matrices are given. In particular, it is shown that if left multiplication of a rectangular matrix A by some nonnegative matrix is upper triangular with positive diagonal, then some row pemutation of A is a WHS-matrix. For a nonsingular A with either the first nonzero entry of each of its rows positive or the last nonzero entry of each column of A ^?1 positive, again some row permutation of A is a WHS-matrix. In addition, any rectangular full rank semipositive matrix is shown to be permutation equivalent to a WHS-matrix.     

On Integer Solutions to Linear Equations

A magic square is an n × n matrix with non-negative integer entries, such that the sum of the entries in each row and column is the same. We study the enumeration and P-recursivity of these in the case in which the sum along each row and column is fixed, with the size n of the matrix as the variable. A method is developed that nicely proves some known results about the case when the row and column sum is 2, and we prove new results for the case when the sum is 3. Received December 23, 2005     

NEW RESULTS ON ESTIMATES FOR SINGULAR VALUES

1　ＩｎｔｒｏｄｕｃｔｉｏｎＴｈｅｒｅｈａｖｅｂｅｅｎＧｅｒｓｃｈｇｏｒｉｎ’ｓｄｉｓｋｔｈｅｏｒｅｍ ,Ｂｒａｕｅｒ’ｓｔｈｅｏｒｅｍ ,Ｏｓｔｒｏｗｓｋｉ’ｓｔｈｅｏｒｅｍａｎｄＢｒｕａｌｄｉ’ｓｔｈｅｏｒｅｍｅｔｃ .ｂｙｗｈｉｃｈｗｅｃａｎｅｓｔｉｍａｔｅｔｈｅｉｎｃｌｕｓｉｏｎｒｅｇｉｏｎｓｏｆｅｉｇｅｎｖａｌｕｅｓｏｆａｍａｔｒｉｘｉｎｔｅｒｍｓｏｆｉｔｓｅｎｔｒｉｅｓ.(Ｓｅｅ [2 ,Ｃｈａｐｔｅｒ 6 ]) .ＳｉｎｃｅｔｈｅｓｑｕａｒｅｓｏｆｔｈｅｓｉｎｇｕｌａｒｖａｌｕｅｓｏｆｍａｔｒｉｘＡａ…     

四元数矩阵方程AXB+CXD=E的广义延拓解

本文在四元数体上讨论矩阵方程AXB+CXD=E的广义行（列）共轭延拓解问题.利用四元数矩阵的复与实分解,以及广义共轭延拓矩阵的结构特点,借助矩阵Kronecker积,把约束四元数矩阵方程转化为实数域上无约束方程,从而得到该方程具有广义行（列）共轭延拓解的充要条件及其通解表达式.最后通过数值算例说明所给算法的可行性.     

Break minimization

A break in a {0, 1}-matrix is defined as a 0 with at least one 1 to its left and at least one 1 to its right in the same row. This paper is concerned with {0, 1}-matrices with given column sums and an upper limit for the row sums. In addition, there are limits on the distance from the first to the last 1 in a row. The problem that is considered is to find a {0, 1}-matrix satisfying the conditions such that the total number of breaks is minimum. An algorithm for solving this problem is presented. Computational results illustrate the effectiveness of the algorithm. The investigation originated in a problem of crew rostering.     

Improved bounds for sampling contingency tables

We study the problem of sampling contingency tables (nonnegative integer matrices with specified row and column sums) uniformly at random. We give an algorithm which runs in polynomial time provided that the row sums r_i and the column sums c_j satisfy r_i = Ω(n^3/2m log m), and c_j = Ω(m^3/2n log n). This algorithm is based on a reduction to continuous sampling from a convex set. The same approach was taken by Dyer, Kannan, and Mount in previous work. However, the algorithm we present is simpler and has weaker requirements on the row and column sums. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 135–146, 2002     

On graphs with exactly one anti-adjacency eigenvalue and beyond

The anti-adjacency matrix of a graph is constructed from the distance matrix of a graph by keeping each row and each column only the largest distances. This matrix can be interpreted as the opposite of the adjacency matrix, which is instead constructed from the distance matrix of a graph by keeping in each row and each column only the distances equal to 1. The (anti-)adjacency eigenvalues of a graph are those of its (anti-)adjacency matrix. Employing a novel technique introduced by Haemers (2019) [9], we characterize all connected graphs with exactly one positive anti-adjacency eigenvalue, which is an analog of Smith's classical result that a connected graph has exactly one positive adjacency eigenvalue iff it is a complete multipartite graph. On this basis, we identify the connected graphs with all but at most two anti-adjacency eigenvalues equal to ?2 and 0. Moreover, for the anti-adjacency matrix we determine the HL-index of graphs with exactly one positive anti-adjacency eigenvalue, where the HL-index measures how large in absolute value may be the median eigenvalues of a graph. We finally propose some problems for further study.     

A combinatorial problem associated with nonograms

Associated with an m × n matrix with entries 0 or 1 are the m-vector of row sums and n-vector of column sums. In this article we study the set of all pairs of these row and column sums for fixed m and n. In particular, we give an algorithm for finding all such pairs for a given m and n.