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.     

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.     

Unbiased invariant minimum norm estimation in generalized growth curve model

This paper considers the generalized growth curve model subject to R(X_m)⊆R(X_m-1)⊆?⊆R(X₁), where B_i are the matrices of unknown regression coefficients, X_i,Z_i and U are known covariate matrices, i=1,2,…,m, and E splits into a number of independently and identically distributed subvectors with mean zero and unknown covariance matrix Σ. An unbiased invariant minimum norm quadratic estimator (MINQE(U,I)) of tr(CΣ) is derived and the conditions for its optimality under the minimum variance criterion are investigated. The necessary and sufficient conditions for MINQE(U,I) of tr(CΣ) to be a uniformly minimum variance invariant quadratic unbiased estimator (UMVIQUE) are obtained. An unbiased invariant minimum norm quadratic plus linear estimator (MINQLE(U,I)) of is also given. To compare with the existing maximum likelihood estimator (MLE) of tr(CΣ), we conduct some simulation studies which show that our proposed estimator performs very well.     

An approximation algorithm for counting contingency tables

We present a randomized approximation algorithm for counting contingency tables, m × n non‐negative integer matrices with given row sums R = (r₁,…,r_m) and column sums C = (c₁,…,c_n). We define smooth margins (R,C) in terms of the typical table and prove that for such margins the algorithm has quasi‐polynomial N^{O(ln N)} complexity, where N = r₁ + … + r_m = c₁ + … + c_n. Various classes of margins are smooth, e.g., when m = O(n), n = O(m) and the ratios between the largest and the smallest row sums as well as between the largest and the smallest column sums are strictly smaller than the golden ratio (1 + )/2 ≈? 1.618. The algorithm builds on Monte Carlo integration and sampling algorithms for log‐concave densities, the matrix scaling algorithm, the permanent approximation algorithm, and an integral representation for the number of contingency tables. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

On the bounds for the norms of r-circulant matrices with the Fibonacci and Lucas numbers

In this paper, we have found upper and lower bounds for the spectral norms of r-circulant matrices in the forms A = C_r(F₀, F₁, …, F_n−1), B = C_r(L₀, L₁, …, L_n−1), and we have obtained some bounds for the spectral norms of Kronecker and Hadamard products of A and B matrices.     

Noncommutative convexity arises from linear matrix inequalities

This paper concerns polynomials in g noncommutative variables x=(x₁,…,xg), inverses of such polynomials, and more generally noncommutative “rational expressions” with real coefficients which are formally symmetric and “analytic near 0.” The focus is on rational expressions r=r(x) which are “matrix convex” near 0; i.e., those rational expressions r for which there is an ?>0 such that if X=(X₁,…,Xg) is a g-tuple of n×n symmetric matrices satisfying

     

Matrices of zeros and ones with fixed row and column sum vectors

Let m and n be positive integers, and let R=(r₁,…,r_m) and S=(s₁,…,s_n) be nonnegative integral vectors. We survey the combinational properties of the set of all m × n matrices of 0's and 1's having r_i1's in row i ands_i 1's in column j. A number of new results are proved. The results can be also be formulated in terms of a set of bipartite graps with bipartition into m and n vertices having degree sequence R and S, respectively. They can also be formulated in terms of the set of hypergraphs with m vertices having degree sequence R and n edges whose cardinalities are given by S.     

Conley's spectral sequence via the sweeping algorithm

In this article we consider a spectral sequence (Er,dr) associated to a filtered Morse-Conley chain complex (C,Δ), where Δ is a connection matrix. The underlying motivation is to understand connection matrices under continuation. We show how the spectral sequence is completely determined by a family of connection matrices. This family is obtained by a sweeping algorithm for Δ over fields F as well as over Z. This algorithm constructs a sequence of similar matrices Δ⁰=Δ,Δ¹,… , where each matrix is related to the others via a change-of-basis matrix. Each matrix Δr over F (resp., over Z) determines the vector space (resp., Z-module) Er and the differential dr. We also prove the integrality of the final matrix ΔR produced by the sweeping algorithm over Z which is quite surprising, mainly because the intermediate matrices in the process may not have this property. Several other properties of the change-of-basis matrices as well as the intermediate matrices Δr 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.     

The relationship between the class %plane1D;518;2(R,S) of (0,1,2)-matrices and the collection of constellation matrices

Let %plane1D;518;₂(R,S) be the class of all (0, 1, 2)-matrices with a prescribed row sum vector R and column sum vector S. A (0, 1,2)-matrix in %plane1D;518;₂(R,S) is defined to be parsimonious provided no (0, 1, 2)-matrix with the same row and column sum vectors has fewer positive entries. In a parsimonious (0, 1, 2)-matrix A there are severe restrictions on the (0, 1)-matrix A⁽¹⁾ which records the positions of the 1's in A. Brualdi and Michael obtained some necessary arithmetic conditions for a set of matrices to serve simultaneously as the 1-pattern matrices for parsimonious matrices in a given class. In this paper, we provide a direct construction that proves that these conditions are also sufficient.     

New upper bounds on the spectral radius of unicyclic graphs

Let G=(V(G),E(G)) be a unicyclic simple undirected graph with largest vertex degree Δ. Let C_r be the unique cycle of G. The graph G-E(C_r) is a forest of r rooted trees T₁,T₂,…,T_r with root vertices v₁,v₂,…,v_r, respectively. Let

     

Generalized doubly stochastic and permutation matrices over a ring

Let R be a ring with unity. A combinatorial argument is used to show that the R-module Δ_n(R) of all n × n matrices over R with constant row and column sums has a basis consisting of permutation matrices. This is used to characterize orthogonal matrices which are linear combinations of permutation matrices. It is shown that all bases of Δ_n(R) consisting of permutation matrices have the same cardinality, and other properties of bases of Δ_n(R) are investigated.     

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.     

On the Heegaard Floer homology of a surface times a circle

We make a detailed study of the Heegaard Floer homology of the product of a closed surface Σg of genus g with S¹. We determine HF⁺(Σg×S¹,s;C) completely in the case c₁(s)=0, which for g?3 was previously unknown. We show that in this case HF^∞ is closely related to the cohomology of the total space of a certain circle bundle over the Jacobian torus of Σg, and furthermore that HF⁺(Σg×S¹,s;Z) contains nontrivial 2-torsion whenever g?3 and c₁(s)=0. This is the first example known to the authors of torsion in Z-coefficient Heegaard Floer homology. Our methods also give new information on the action of H₁(Σg×S¹) on HF⁺(Σg×S¹,s) when c₁(s) is nonzero.     

Prime interchange graphs of classes of matrices of zeros and ones

Let R = (r₁,…, r_m) and S = (s₁,…, s_n) be nonnegative integral vectors, and let $\text{U}$(R, S) denote the class of all m × n matrices of 0's and 1's having row sum vector R and column sum vector S. An invariant position of $\text{U}$(R, S) is a position whose entry is the same for all matrices in $\text{U}$(R, S). The interchange graph G(R, S) is the graph where the vertices are the matrices in $\text{U}$(R, S) and where two matrices are joined by an edge provided they differ by an interchange. We prove that when 1 ≤ r_i ≤ n ? 1 (i = 1,…, m) and 1 ≤ s_j ≤ m ? 1 (j = 1,…, n), G(R, S) is prime if and only if $\text{U}$(R, S) has no invariant positions.     

Asymptotic enumeration of sparse 0-1 matrices with irregular row and column sums

Let s=(s₁,…,s_m) and t=(t₁,…,t_n) be vectors of non-negative integer-valued functions with equal sum . Let N(s,t) be the number of m×n matrices with entries from {0,1} such that the ith row has row sum s_i and the jth column has column sum t_j. Equivalently, N(s,t) is the number of labelled bipartite graphs with degrees of the vertices in one side of the bipartition given by s and the degrees of the vertices in the other side given by t. We give an asymptotic formula for N(s,t) which holds when S→∞ with 1?st=o(S^2/3), where and . This extends a result of McKay and Wang [Linear Algebra Appl. 373 (2003) 273-288] for the semiregular case (when s_i=s for 1?i?m and t_j=t for 1?j?n). The previously strongest result for the non-semiregular case required 1?max{s,t}=o(S^1/4), due to McKay [Enumeration and Design, Academic Press, Canada, 1984, pp. 225-238].     

Boolean invertible matrices identified from two permutations and their corresponding Haar-type matrices

We construct a class R_m of m×m boolean invertible matrices whose elements satisfy the following property: when we perform the Hadamard product operation R_i⊙R_j on the set of row vectors {R₁,…,R_m} of an element R∈R_m we produce either the row R_max{i,j} or the zero row. In this paper, we prove that every matrix R∈R_m is uniquely determined by a pair of permutations of the set {1,…,m}. As a by-product of this result we identify Haar-type matrices from a pair of permutations as well, because these matrices emerge from the Gram-Schmidt orthonormalization process of the set of row vectors of R matrices belonging in a certain subclass R₀⊂R_m.     

A note on traversing specified vertices in graphs embedded with large representativity

A graph G is said to have property P(2,k) if given any k+2 distinct vertices a,b,v₁,…,v_k, there is a path P in G joining a and b and passing through all of v₁,…,v_k. A graph G is said to have property C(k) if given any k distinct vertices v₁,…,v_k, there is a cycle C in G containing all of v₁,…,v_k. It is shown that if a 4-connected graph G is embedded in an orientable surface Σ (other than the sphere) of Euler genus eg(G,Σ), with sufficiently large representativity (as a function of both eg(G,Σ) and k), then G possesses both properties P(2,k) and C(k).     

Random generation of 2×n contingency tables

Let r=(r₁, r₂) and c=(c₁,…,c_n) be positive integer partitions of N. Let Σ_rc denote the set of all 2×n arrays of nonnegative integers whose ith row sums to r_i and jth column sums to c_j. We consider the problem of randomly generating an element from the uniform distribution over Σ_rc. This problem arises in statistics where random samples are used to decide whether two attributes are independent. In this paper, we present a Markov chain Monte Carlo algorithm for this problem and give the first general polynomial bounds on its running time. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 71–79, 1998     

A generalized Cayley-Hamilton theorem for polynomials with matrix coefficients

A family F of square matrices of the same order is called a quasi-commuting family if (AB-BA)C=C(AB-BA) for all A,B,C∈F where A,B,C need not be distinct. Let f_k(x₁,x₂,…,x_p),(k=1,2,…,r), be polynomials in the indeterminates x₁,x₂,…,x_p with coefficients in the complex field C, and let M₁,M₂,…,M_r be n×n matrices over C which are not necessarily distinct. Let and let δ_F(x₁,x₂,…,x_p)=detF(x₁,x₂,…,x_p). In this paper, we prove that, for n×n matrices A₁,A₂,…,A_p over C, if {A₁,A₂,…,A_p,M₁,M₂,…,M_r} is a quasi-commuting family, then F(A₁,A₂,…,A_p)=O implies that δ_F(A₁,A₂,…,A_p)=O.