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.     

A minimal completion of (0, 1)-matrices without total support

In this paper, we provide a method to complete a (0, 1)-matrix without total support via the minimal doubly stochastic completion of doubly substochastic matrices and show that the size of the completion is determined by the maximum diagonal sum or the term rank of the given (0, 1)-matrix.     

(0, 1)-matrices with minimal permanents

It is shown that the permanent of a totally indecomposable (0,1)-matrix is equal to its largest row sum if and only if all its other row sums are 2. This research was supported by the U.S. Air Force Office of Scientific Research under Grant AFOSR-72-2164.     

A characterization of convertible (0, 1)-matrices

We characterize those (0, 1)-matrices M whose elements can be given plus or minus signs so as to yield a matrix M′ for which det M′ = perm M.     

Monotone subsequences in (0, 1)-matrices

A (0, 1)-matrix contains anS ₀(k) if it has 0-cells (i, j ₁), (i + 1,j ₂),..., (i + k – 1,j _k) for somei andj ₁ < ... < j_k, and it contains anS ₁(k) if it has 1-cells (i ₁,j), (i ₂,j + 1),...,(i _k ,j + k – 1) for somej andi ₁ < ... <i _k . We prove that ifM is anm × n rectangular (0, 1)-matrix with 1 m n whose largestk for anS ₀(k) isk ₀ m, thenM must have anS ₁(k) withk m/(k ₀ + 1). Similarly, ifM is anm × m lower-triangular matrix whose largestk for anS ₀(k) (in the cells on or below the main diagonal) isk ₀ m, thenM has anS ₁(k) withk m/(k ₀ + 1). Moreover, these results are best-possible.     

Representing (0, 1)-matrices by boolean circuits

A boolean circuit represents an n by n(0,1)-matrix A if it correctly computes the linear transformation over GF(2) on all n unit vectors. If we only allow linear boolean functions as gates, then some matrices cannot be represented using fewer than Ω(n²/lnn) wires. We first show that using non-linear gates one can save a lot of wires: any matrix can be represented by a depth-2 circuit with O(nlnn) wires using multilinear polynomials over GF(2) of relatively small degree as gates. We then show that this cannot be substantially improved: If any two columns of an n by n(0,1)-matrix differ in at least d rows, then the matrix requires Ω(dlnn/lnlnn) wires in any depth-2 circuit, even if arbitrary boolean functions are allowed as gates.     

关于逆N0-矩阵的若干性质

1989年Meyer为计算马尔可夫链的平稳分布向量构造了一个算法,首次提出非负不可约矩阵的Perron补的概念.在非负不可约矩阵的广义Perron补若干性质的基础上,给出逆N0-矩阵的几个性质.     

On (0, 1)-matrices with prescribed row and column sum vectors

Given partitions R and S with the same weight, the Robinson-Schensted-Knuth correspondence establishes a bijection between the class A(R,S) of (0, 1)-matrices with row sum R and column sum S and pairs of Young tableaux of conjugate shapes λ and λ^∗, with S?λ?R^∗. An algorithm for constructing a matrix in A(R,S) whose insertion tableau has a prescribed shape λ, with S?λ?R^∗, is provided. We generalize some recent constructions due to R. Brualdi for the extremal cases λ=S and λ=R^∗.     

An upper bound for theα-height of (0, 1)-matrices

We obtain an upper bound for theα-height of an arbitrary matrix of zeros and ones. We apply the result to a number of known combinatorial problems.     

On permanents of (1, − 1)-matrices

A preliminary study on permanents of (1, ? 1)-matrices is given. Some inequalities are derived and a few unsolved problems, believed to be new, are mentioned.     

Upper bounds for permanents of (1, − 1)-matrices

Let Ω _n denote the set of alln×n (1, ? 1)-matrices. In 1974 E. T. H. Wang posed the following problems: Is there a decent upper bound for |perA| whenAσΩ _n is nonsingular? We recently conjectured that the best possible bound is the permanent of the matrix with exactlyn?1 negative entries in the main diagonal, and affirmed that conjecture by the study of a large class of matrices in Ω _n . Here we prove that this conjecture also holds for another large class of (1, ?1)-matrices which are all nonsingular. We also give an upper bound for the permanents of a class of matrices in Ω _n which are not all regular.     

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.     

Some properties of the permanent of (1, -1)-matrices

Some convergence properties for the Campbell-Baker-Hausdorff series for the logarithm of a product of exponentials are established.     

The numerical range of certain 0,1-matrices

Let A be a 0, 1-matrix with at most one 1 in each row and column. The authors prove that the numerical range of A is the convex hull of a polygon and a circular disk, both centered at the origin and contained in the unit disk. The proof uses a permutation similarity to reduce A to a direct sum of matrices whose numerical ranges can be determined. A computer program, developed by the authors, which plots the boundary of the numerical range of an arbitrary complex matrix is also discussed.     

On some questions concerning permanents of (1,−1)-matrices

Let Ω _n denote the set of alln×n-(1,?1)-matrices. E.T.H. Wang has posed the following problem: For eachn≧4, can one always find nonsingularA∈Ω _n such that |perA|=|detA| (*)? We present a solution forn≦6 and, more generally, we show that (*) does not hold ifn=2 ^k ?1,k≧2, even for singularA∈Ω _n . Moreover, we prove that perA≠0 ifA∈Ω _n ,n=2 ^k ?1, and we derive new results concerning the divisibility of the permanent in Ω _n by powers of 2.     

The class A(R,S) of (0, 1)-matrices

Let R and S be two vectors whose components are m and n non-negative integers, respectively. Let $\text{A}$(R, S) be the class consisting of all (0, 1)-matrices of size m by n with row sum vector R and column sum vector S. In this paper we derive a lower bound to the cardinality of the class $\text{A}$(R, S), which can be computed readily.     

A note on the proportion of singular (0, 1)-matrices in a class associated with fractional 2n factorial designs

Let the set T = {(x₁, x₂,…, x_n): x_i = 0, 1}. Since the elements of T can be seen as binary representations of integers, we order them with their corresponding integer values. Let $\text{Γ}{}^1$ be the set of (n + 1) × (n + 1) matrices of the form [1 … D], where the n + 1 rows of D are distinct ordered elements of T. We show that the proportion of singular matrices in $\text{Γ}{}^1$ approaches 0 as n → ∞.