Structural properties and recognition of restricted and strongly unimodular matrices

A (0, ±1) matrix A is restricted unimodular if every matrix obtained from A by setting to zero any subset of its entries is totally unimodular. Restricted unimodular matrices are also known as matrices without odd cycles. They have been studied by Commoner and recently Yannakakis has given a polynomial algorithm to recognize when a matrix belongs to this class. A matrix A is strongly unimodular if any matrix obtained from A by setting at most one of its entries to zero is totally unimodular. Crama et al. have shown that (0,1) matrix A is strongly unimodular if and only if any basis of (A, 1) is triangular, whereI is an identity matrix of suitable dimensions. In this paper we give a very simple algorithm to test whether a matrix is restricted unimodular and we show that all strongly unimodular matrices can be obtained by composing restricted unimodular matrices with a simple operation. Partially supported by a New York University Research Challenge Fund Grant.     

On minimal forbidden subgraph characterizations of balanced graphs

A {0, 1}-matrix is balanced if it contains no square submatrix of odd order with exactly two 1's per row and per column. Balanced matrices lead to ideal formulations for both set packing and set covering problems. Balanced graphs are those graphs whose clique-vertex incidence matrix is balanced.While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to some graph classes which also lead to polynomial time or even linear time recognition algorithms within the corresponding subclasses.     

A structure theorem for the consecutive 1's property

A (0, 1)-matrix M has the consecutive 1's property for columns if the rows of M can be permuted so that the 1's in each column appear consecutively. A graph-theoretic approach is used to characterize matrices with this property in terms of forbidden submatrices. Graphs whose adjacency matrix has this property are also characterized.     

On linear forbidden submatrices

In this paper we study the extremal problem of finding how many 1 entries an n by n 0-1 matrix can have if it does not contain certain forbidden patterns as submatrices. We call the number of 1 entries of a 0-1 matrix its weight. The extremal function of a pattern is the maximum weight of an n by n 0-1 matrix that does not contain this pattern as a submatrix. We call a pattern (a 0-1 matrix) linear if its extremal function is O(n). Our main results are modest steps towards the elusive goal of characterizing linear patterns. We find novel ways to generate new linear patterns from known ones and use this to prove the linearity of some patterns. We also find the first minimal non-linear pattern of weight above 4. We also propose an infinite sequence of patterns that we conjecture to be minimal non-linear but have Ω(nlogn) as their extremal function. We prove a weaker statement only, namely that there are infinitely many minimal not quasi-linear patterns among the submatrices of these matrices. For the definition of these terms see below.     

On the gibson barrier for the pólya problem

We study lower bounds on the number of nonzero entries in (0, 1) matrices such that the permanent is always convertible to the determinant by placing?±?signs on matrix entries.     

Perfect zero–one matrices

A zero–one matrix is called perfect if the polytope of the associated set packing problem has integral vertices only. By this definition, all totally unimodular zero–one matrices are perfect. In this paper we give a characterization of perfect zero–one matrices in terms offorbidden submatrices. Perfect zero–one matrices are closely related to perfect graphs and constitute a generalization of balanced matrices as introduced by C. Berge. Furthermore, the results obtained here bear on an unsolved problem in graph theory, the strong perfect graph conjecture, also due to C. Berge.     

Hermitian positive semidefinite matrices whose entries are 0 or 1 in Modulus

We show that a matrix is a Hermitian positive semidefinite matrix whose nonzero entries have modulus 1 if and only if it is similar to a direct sum of all I's matrices and a 0 matrix via a unitary monomial similarity. In particular, the only such nonsingular matrix is the identity matrix and the only such irreducible matrix is similar to an all l's matrix by means of a unitary diagonal similarity. Our results extend earlier results of Jain and Snyder for the case in which the nonzero entries (actually) equal 1. Our methods of proof, which reiy on the so called principal submatrix rank property, differ from the approach used by Jain and Snyder.     

Balanced 0, ±1-matrices,bicoloring and total dual integrality

A 0, ±1-matrixA is balanced if, in every submatrix with two nonzero entries per row and column, the sum of the entries is a multiple of four. This definition was introduced by Truemper (1978) and generalizes the notion of a balanced 0, 1-matrix introduced by Berge (1970). In this paper, we extend a bicoloring theorem of Berge (1970) and total dual integrality results of Fulkerson, Hoffman and Oppenheim (1974) to balanced 0, ±1-matrices.This work was supported in part by NSF grants DDM-8800281, ECS-8901495 and DDM-9001705.     

Pólya convertibility problem for symmetric matrices

We investigate symmetric (0, 1) matrices on which the permanent is convertible to the determinant by assigning ± signs to their entries. In particular, we obtain several quantitative bounds for the number of nonzero elements of such matrices, including the analog of Gibson’s theorem for symmetric matrices.     

Mixed dominating matrices

We characterize the class of matrices for which the set of supports of nonnegative vectors in the null space can be determined by the signs of the entries of the matrix. This characterization is in terms of mixed dominating matrices, which are defined by the nonexistence of square submatrices that have nonzeros of opposite sign in each row. The class of mixed dominating matrices is contained in the class of L-matrices from the theory of sign-solvability, and generalizes the class of S-matrices. We give a polynomial-time algorithm to decide if a matrix is mixed dominating. We derive combinatorial conditions on the face lattice of a Gale transform of a matrix in this class.     

Computing the inertia from sign patterns

A symmetric matrix A is said to be sign-nonsingular if every symmetric matrix with the same sign pattern as A is nonsingular. Hall, Li and Wang showed that the inertia of a sign-nonsingular symmetric matrix is determined uniquely by its sign pattern. The purpose of this paper is to present an efficient algorithm for computing the inertia of such symmetric matrices. The algorithm runs in time for a symmetric matrix of order n with m nonzero entries. In addition, it is shown to be NP-complete to decide whether the inertia of a given symmetric matrix is not determined by its sign pattern.     

Permanent Semigroups

A permanent semigroup is a semigroup of n × n matrices on which the permanent function is multiplicative. If the underlying ring is an infinite integral domain with characteristic p > n or characteristic 0 we prove that any permanent semigroup consists of matrices with at most one nonzero diagonal. The same result holds if the ring is a finite field with characteristic p > n and at least n²+n elements. We also consider the Kronecker product of permanent semigroups and show that the Kronecker product of permanent semigroups is a permanent semigroup if and only if the pennanental analogue of the formula for the determinant of a Kronecker product of two matrices holds. This latter result holds even when the matrix entries are from a commutative ring with unity.     

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.     

On Balanced Graphs

Berge defined a hypergraph to be balanced if its incidence matrix is balanced. We consider this concept applied to graphs, and call a graph to be balanced when its clique matrix is balanced. Characterizations of balanced graphs by forbidden subgraphs and by clique subgraphs are proved in this work. Using properties of domination we define four subclasses of balanced graphs. Two of them are characterized by 0–1 matrices and can be recognized in polynomial time. Furthermore, we propose polynomial time combinatorial algorithms for the problems of stable set, clique-independent set and clique-transversal for one of these subclasses of balanced graphs. Finally, we analyse the behavior of balanced graphs and these four subclasses under the clique graph operator. Received: April, 2004     

Enumeration of symmetry classes of alternating sign matrices and characters of classical groups

An alternating sign matrix is a square matrix with entries 1, 0 and −1 such that the sum of the entries in each row and each column is equal to 1 and the nonzero entries alternate in sign along each row and each column. To some of the symmetry classes of alternating sign matrices and their variations, G. Kuperberg associate square ice models with appropriate boundary conditions, and give determinant and Pfaffian formulae for the partition functions. In this paper, we utilize several determinant and Pfaffian identities to evaluate Kuperberg's determinants and Pfaffians, and express the round partition functions in terms of irreducible characters of classical groups. In particular, we settle a conjecture on the number of vertically and horizontally symmetric alternating sign matrices (VHSASMs). Dedicated to the memory of David Robbins.     

Small Forbidden Configurations

In the present paper we continue the work begun by Sauer, Perles, Shelah and Anstee on forbidden configurations of 0–1 matrices. We give asymptotically exact bounds for all possible 2 × l forbidden submatrices and almost all 3 × l ones. These bounds are improvements of the general bounds, or else new constructions show that the general bound is best possible. It is interesting to note that up to the present state of our knowledge every forbidden configuration results in polynomial asymptotic.     

Required nonzero patterns for nonsingular sign regular matrices

An n×n real matrix is called sign regular if, for each k(1?k?n), all its minors of order k have the same nonstrict sign. The zero entries which can appear in a nonsingular sign regular matrix depend on its signature because the signature can imply that certain entries are necessarily nonzero. The patterns for the required nonzero entries of nonsingular sign regular matrices are analyzed.