Properties of (0, 1)-matrices with no triangles

We study (0, 1)-matrices which contain no triangles (submatrices of order 3 with row and column sums 2) previously studied by Ryser. Let the row intersection of row i and row j of some matrix, when regarded as a vector, have a 1 in a given column if both row i and row j do and a zero otherwise. For matrices with no triangles, columns sums ?2, we find that the number of linearly independent row intersections is equal to the number of distinct columns. We then study the extremal (0, 1)-matrices with no triangles, column sums ?2, distinct columns, i.e., those of size mx(^m₂). The number of columns of column sum l is m ? l + 1 and they form a (l ? 1)-tree. The ((^m₂)) columns have a unique SDR of pairs of rows with 1's. Also, these matrices have a fascinating inductive buildup. We finish with an algorithm for constructing these matrices.     

On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries

We consider the set Σ(R,C) of all m×n matrices having 0-1 entries and prescribed row sums R=(r₁,…,rm) and column sums C=(c₁,…,cn). We prove an asymptotic estimate for the cardinality |Σ(R,C)| via the solution to a convex optimization problem. We show that if Σ(R,C) is sufficiently large, then a random matrix D∈Σ(R,C) sampled from the uniform probability measure in Σ(R,C) with high probability is close to a particular matrix Z=Z(R,C) that maximizes the sum of entropies of entries among all matrices with row sums R, column sums C and entries between 0 and 1. Similar results are obtained for 0-1 matrices with prescribed row and column sums and assigned zeros in some positions.     

Properties of (0, 1)-matrices without certain configurations

We generalize results of Ryser on (0, 1)-matrices without triangles, 3 × 3 submatrices with row and column sums 2. The extremal case of matrices without triangles was previously studied by the author. Let the row intersection of row i and row j (i ≠ j) of some matrix, when regarded as a vector, have a 1 in a given column if both row i and row j do not 0 otherwise. For matrices satisfying some conditions on forbidden configurations and column sums ? 2, we find that the number of linearly independent row intersections is equal to the number of distinct columns. The extremal matrices with m rows and $\text{(}\text{m}\text{2}\text{)}$ distinct columns have a unique SDR of pairs of rows with 1's. A triangle bordered with a column of 0's and its (0, 1)-complement are also considered as forbidden configurations. Similar results are obtained and the extremal matrices are closely related to the extremal matrices without triangles.     

Asymptotic Estimates for the Number of Contingency Tables, Integer Flows, and Volumes of Transportation Polytopes

We prove an asymptotic estimate for the number of m x n non-negativeinteger matrices (contingency tables) with prescribed row andcolumn sums and, more generally, for the number of integer-feasibleflows in a network. Similarly, we estimate the volume of thepolytope of m x n non-negative real matrices with prescribedrow and column sums. Our estimates are solutions of convex optimizationproblems, and hence can be computed efficiently. As a corollary,we show that if row sums R = (r₁, ..., r_m) and column sums C= (c₁, ..., c_n) with r₁ + + r_m = c₁ + + c_n = Nare sufficientlyfar from constant vectors, then, asymptotically, in the uniformprobability space of the m x nnon-negative integer matriceswith the total sum N of entries, the event consisting of thematrices with row sums R and the event consisting of the matriceswith column sums C are positively correlated.     

A general upper bound for 1-widths

Let A be an m × n(0, 1)-matrix having row sums ? r and column sums ? c. An upper bound for the 1-width of A is obtained in terms of m, n, r, c.     

On Euclidean distance matrices

If A is a real symmetric matrix and P is an orthogonal projection onto a hyperplane, then we derive a formula for the Moore-Penrose inverse of PAP. As an application, we obtain a formula for the Moore-Penrose inverse of an Euclidean distance matrix (EDM) which generalizes formulae for the inverse of a EDM in the literature. To an invertible spherical EDM, we associate a Laplacian matrix (which we define as a positive semidefinite n × n matrix of rank n − 1 and with zero row sums) and prove some properties. Known results for distance matrices of trees are derived as special cases. In particular, we obtain a formula due to Graham and Lovász for the inverse of the distance matrix of a tree. It is shown that if D is a nonsingular EDM and L is the associated Laplacian, then D⁻¹ − L is nonsingular and has a nonnegative inverse. Finally, infinitely divisible matrices are constructed using EDMs.     

Completion of a partial integral matrix to a unimodular matrix

We first characterize submatrices of a unimodular integral matrix. We then prove that if n entries of an n × n partial integral matrix are prescribed and these n entries do not constitute a row or a column, then this matrix can be completed to a unimodular matrix. Consequently an n × n partial integral matrix with n − 1 prescribed entries can always be completed to a unimodular matrix.     

General forbidden configuration theorems

Results in this paper gives bounds on the number of columns in a matrix when certain submatrices are forbidden. Let F be a k by l (0, 1)-matrix with no repeated columns, column sums at least s. Let A be a m by n (0, 1)-matrix with no repeated column, column sums at least s and no submatrix F nor any row and column permutation of F. Then $\text{n?(}\text{m}\text{k?1}\text{) + (}\text{m}\text{k?2}\text{) + ? + (}\text{m}\text{s}\text{)}$. This bound is best possible for numerous F. The bound, with s = 0, is an easy corollary to a bound of Sauer and Perles and Shelah. The bounds can be extended to any F and to any F where we do not allow row and column permutations. The results follow from a configuration theorem that says, in essence, that matrices without a configuration are determined by row intersections of sets of rows of various sizes. A linear independence argument yields the bound. Results of Ryser, Frankl and Pach, Quinn and the author are obtained.     

Rectangular arrays

In this paper we studied m×n arrays with row sums $\text{nr}\text{(n,m)}$ and column sums $\text{mr}\text{(n,m)}$ where (n,m) denotes the greatest common divisor of m and n. We were able to show that the function H_m,n(r), which enumerates m×n arrays with row sums and column sums $\text{nr}\text{(m,n)}$ and $\text{mr}\text{(n,m)}$ respectively, is a polynomial in r of degree (m?1)(n?1). We found simple formulas to evaluate these polynomials for negative values, ?r, and we show that certain small negative integers are roots of these polynomials. When we considered the generating function G_m,n(y) = Σ_r?0H_m,n(r)y^r, it was found to be rational of degree less than zero. The denominator of G_m,n(y) is of the form (1?y)^(m?1)(n?1)+3, and the coefficients of the numerator are non-negative integers which enjoy a certain symmetric relation.     

Recursive algorithm for the reliability of a connected-(1, 2)-or-(2, 1)-out-of-(m, n):F lattice system

The connected-(1, 2)-or-(2, 1)-out-of-(m, n):F lattice system is included by the connected-X-out-of-(m, n):F lattice system defined by Boehme et al. [Boehme, T.K., Kossow, A., Preuss, W., 1992. A generalization of consecutive-k-out-of-n:F system. IEEE Transactions on Reliability 41, 451–457]. This system fails if and only if at least one subset of connected failed components occurs which includes at least a (1, 2)-matrix (that is, a row and two columns) or a (2, 1)-matrix(that is, two rows and a column) of failed components. This system is applied to two-dimensional network problems with adjacent constraints, and various systems, for example, a supervision system, etc.     

Sampling contingency tables

We give polynomial time algorithms for random sampling from a set of contingency tables, which is the set of m×n matrices with given row and column sums, provided the row and column sums are sufficiently large with respect to m, n. We use this to approximately count the number of such matrices. These problems are of interest in Statistics and Combinatorics. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10 , 487–506, 1997     

Asymptotic enumeration of dense 0-1 matrices with specified line sums

Let s=(s₁,s₂,…,sm) and t=(t₁,t₂,…,tn) be vectors of non-negative integers with . Let B(s,t) be the number of m×n matrices over {0,1} with jth row sum equal to sj for 1?j?m and kth column sum equal to tk for 1?k?n. Equivalently, B(s,t) is the number of bipartite graphs with m vertices in one part with degrees given by s, and n vertices in the other part with degrees given by t. Most research on the asymptotics of B(s,t) has focused on the sparse case, where the best result is that of Greenhill, McKay and Wang (2006). In the case of dense matrices, the only precise result is for the case of equal row sums and equal column sums (Canfield and McKay, 2005). This paper extends the analytic methods used by the latter paper to the case where the row and column sums can vary within certain limits. Interestingly, the result can be expressed by the same formula which holds in the sparse case.     

On the completion of a partial integral matrix to a unimodular matrix

We prove that if a partial integral matrix has a free diagonal then this matrix can be completed to a unimodular matrix. Such a condition is necessary in a general sense. Consequently if an n × n (n ? 2) partial integral matrix has 2n − 3 prescribed entries and any n entries of these do not constitute a row or a column then it can be completed to a unimodular matrix. This improves a recent result of Zhan.     

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     

Bipanconnectivity of faulty hypercubes with minimum degree

In this paper, we consider the conditionally faulty hypercube Q_n with n ? 2 where each vertex of Q_n is incident with at least m fault-free edges, 2 ? m ? n − 1. We shall generalize the limitation m ? 2 in all previous results of edge-bipancyclicity. We also propose a new edge-fault-tolerant bipanconnectivity called k-edge-fault-tolerant bipanconnectivity. A bipartite graph is k-edge-fault-tolerant bipanconnected if G − F remains bipanconnected for any F ⊂ E(G) with ∣F∣ ? k. For every integer m, under the same hypothesis, we show that Q_n is (n − 2)-edge-fault-tolerant edge-bipancyclic and bipanconnected, and the results are optimal with respect to the number of edge faults tolerated. This not only improves some known results on edge-bipancyclicity and bipanconnectivity of hypercubes, but also simplifies the proof.     

Defining Sets and Critical Sets in (0,1)‐Matrices

If D is a partially filled‐in (0, 1)‐matrix with a unique completion to a (0, 1)‐matrix M (with prescribed row and column sums), we say that D is a defining set for M. If the removal of any entry of D destroys this property (i.e. at least two completions become possible), we say that D is a critical set for M. In this note, we show that the complement of a critical set for a (0, 1)‐matrix M is a defining set for M. We also study the possible sizes (number of filled‐in cells) of defining sets for square matrices M with uniform row and column sums, which are also frequency squares. In particular, we show that when the matrix is of even order 2m and the row and column sums are all equal to m, the smallest possible size of a critical set is precisely m². We give the exact structure of critical sets with this property. © 2012 Wiley Periodicals, Inc. J. Combin. Designs 21: 253–266, 2013     

Reliability of a consecutive (r, s)-out-of-(m, n):F lattice system with conditions on the number of failed components in the system

A consecutive(r, s)-out-of-(m, n):F lattice system which is defined as a two-dimensional version of a consecutive k-out-of-n:F system is used as a reliability evaluation model for a sensor system, an X-ray diagnostic system, a pattern search system, etc. This system consists of m × n components arranged like an (m, n) matrix and fails iff the system has an (r, s) submatrix that contains all failed components. In this paper we deal a combined model of a k-out-of-mn:F and a consecutive (r, s)-out-of-(m, n):F lattice system. Namely, the system has one more condition of system down, that is the total number of failed components, in addition to that of a consecutive (r, s)-out-of-(m, n):F lattice system. We present a method to obtain reliability of the system. The proposed method obtains the reliability by using a combinatorial equation that does not depend on the system size. Some numerical examples are presented to show the relationship between component reliability and system reliability.     

Matrix semigroup homomorphisms into higher dimensions

We study non-degenerate irreducible homomorphisms from the multiplicative semigroup of all n-by-n matrices over an algebraically closed field of characteristic zero to the semigroup of m-by-m matrices over the same field. We prove that every non-degenerate homomorphism from the multiplicative semigroup of all n-by-n matrices to the semigroup of (n + 1)-by-(n + 1) matrices when n ? 3 is reducible and that every non-degenerate homomorphism from the multiplicative semigroup of all 3-by-3 matrices to the semigroup of 5-by-5 matrices is reducible.     

A generalization of Descartes’ rule of signs and fundamental theorem of algebra

Descartes’ rule of signs yields an upper bound for the number of positive and negative real roots of a given polynomial. The fundamental theorem of algebra implies a similar property; every real polynomial of degree n ? 1 has at most n real zeroes. In this paper, we describe axiomatically function families possessing one or another of these properties. The resulting families include, at least, all polynomial functions and sums of exponential functions. As an application of our approach, we consider, among other things, a method for identifying certain type of bases for the Euclidean space.     

The domination numbers of cylindrical grid graphs

Let γ(P_m □ C_n) denote the domination number of the cylindrical grid graph formed by the Cartesian product of the graphs P_m, the path of length m, m ? 2 and the graph C_n, the cycle of length n, n ? 3. In this paper, methods to find the domination numbers of graphs of the form P_m □ C_n with n ? 3 and m = 2, 3 and 4 are proposed. Moreover, bounds on domination numbers of the graphs P₅ □ C_n, n ? 3 are found. The methods that are used to prove that results readily lead to algorithms for finding minimum dominating sets of the above mentioned graphs.