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

DOI10.1016/0024-3795(80)90105-6zbMath0448.05047OpenAlexW2072502638WikidataQ56288392 ScholiaQ56288392MaRDI QIDQ1146695

Richard A. Brualdi

Publication date: 1980

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0024-3795(80)90105-6

zbMATH Keywords

rankhypergraphsbipartite graphsbinary matrix

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (05C99) Matrices of integers (15B36) Research exposition (monographs, survey articles) pertaining to linear algebra (15-02)

Related Items (88)

On the properties of interchange operations in classes of \((0,1)\)- matrices ⋮ The structure matrix of (0,1)-matrices: Its rank, trace, and eigenvalues. An application to econometric models ⋮ Hamiltonicity of a type of interchange graphs ⋮ The structure matrix of the class of \(r\)-multigraphs with a prescribed degree sequence ⋮ On realization graphs of degree sequences ⋮ On asymmetric \((0,1)\)-matrices with given row and column sum vectors ⋮ On the eigenvalues of the structure matrix of matrices of zeros and ones ⋮ The connectivity of the interchange graph of class \({\mathfrak A}(R,S)\) of (0,1)-matrices ⋮ The structure matrix and a generalization of Ryser's maximum term rank formula ⋮ On assignment functions ⋮ Chains and Antichains in the Bruhat Order for Classes of (0, 1)-Matrices ⋮ Algorithms for constructing \((0,1)\)-matrices with prescribed row and column sum vectors ⋮ A generalization of Ryser's theorem on term rank ⋮ Binary vectors partially determined by linear equation systems ⋮ Singular (0,1) matrices with constant row and column sums ⋮ Balanced home-away assignments ⋮ On joint realization of (0,1) matrices ⋮ Matrices with prescribed row, column and block sums ⋮ More on the Bruhat order for (0, 1)-matrices ⋮ Constructing (0,1)-matrices with large minimal defining sets ⋮ Discrete tomography determination of bounded lattice sets from four X-rays ⋮ New summary measures and datasets for the multi-project scheduling problem ⋮ An extension of Brualdi's algorithm for the construction of \((0,1)\)-matrices with prescribed row and column sum vectors ⋮ Unnamed Item ⋮ Realizing disjoint degree sequences of span at most two: a tractable discrete tomography problem ⋮ Detecting arrays for effects of single factors ⋮ Switching checkerboards in \((0,1)\)-matrices ⋮ A classification and new benchmark instances for the multi-skilled resource-constrained project scheduling problem ⋮ Some properties for a class of interchange graphs ⋮ Alternating signed bipartite graphs and difference-1 colourings ⋮ On polyatomic tomography over abelian groups: some remarks on consistency, tree packings and complexity ⋮ Inversion of Band-Limited Discrete Fourier Transforms of Binary Images: Uniqueness and Algorithms ⋮ Block-regularized repeated learning-testing for estimating generalization error ⋮ On the enumeration of rectangular (0, 1)-matrices ⋮ Extremal problems under dimension constraints. ⋮ Sampling contingency tables ⋮ On maximum chains in the Bruhat order of \(\mathcal A(n,2)\) ⋮ Triangular (0,1)-matrices with prescribed row and column sums ⋮ The maximal length of a chain in the Bruhat order for a class of binary matrices ⋮ Graphs and degree sequences. I ⋮ Rejection sampling of bipartite graphs with given degree sequence ⋮ Constrained \((0,1)\)-matrix completion with a staircase of fixed zeros ⋮ Product action. ⋮ Uniform sampling ofk-hypertournaments ⋮ Joint realization of (0, 1) matrices revisited ⋮ Integral matrices with given row and column sums ⋮ Antichains of \((0, 1)\)-matrices through inversions ⋮ Matrices of zeros and ones with given line sums and a zero block ⋮ Majorization permutahedra and (0,1)-matrices ⋮ An algorithm for finding the number of (0, 1, 2,…, l)-matrices with prefixed row sum and column sum vectors ⋮ Defining Sets and Critical Sets in (0,1)‐Matrices ⋮ Minimal matrices in the Bruhat order for symmetric (0,1)-matrices ⋮ Addition of sets via symmetric polynomials - a polynomial method ⋮ Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms ⋮ Matrices of zeros and ones with given line sums and a zero block ⋮ A note on majorization transforms and Ryser's algorithm ⋮ On \(\mathfrak A(R,S)\) all of whose members are indecomposable ⋮ Reconstruction of 8-connected but not 4-connected \(hv\)-convex discrete sets ⋮ On the computational complexity of reconstructing three-dimensional lattice sets from their two-dimensional \(X\)-rays ⋮ A Legendre pair of length 77 using complementary binary matrices with fixed marginals ⋮ Approximating hv-Convex Binary Matrices and Images from Discrete Projections ⋮ On (0, 1)-matrices with prescribed row and column sum vectors ⋮ Some properties of a class of interchange graphs ⋮ Small diameter interchange graphs of classes of matrices of zeros and ones ⋮ Sampling \(k\)-partite graphs with a given degree sequence ⋮ Further steps on the reconstruction of convex polyominoes from orthogonal projections ⋮ On the upper bound of the diameter of interchange graphs ⋮ Prime interchange graphs of classes of matrices of zeros and ones ⋮ The relationship between the class \({\mathfrak A}_2(R,S)\) of (0, 1, 2)-matrices and the collection of constellation matrices ⋮ The realization graph of a degree sequence with majorization gap 1 is Hamiltonian ⋮ The network flows approach for matrices with given row and column sums ⋮ Cliques in realization graphs ⋮ Chromatic number of classes of matrices of zeros and ones ⋮ Disjoint cycles in Eulerian digraphs and the diameter of interchange graphs ⋮ An introduction to periodical discrete sets from a tomographical perspective ⋮ A new look at the optimal assignment problem ⋮ On normal matrices of zeros and ones with fixed row sum ⋮ Matrices of zeros and ones with the maximum jump number ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ A sufficient condition for non-uniqueness in binary tomography with absorption ⋮ Reconstruction of convex polyominoes from orthogonal projections of their contours ⋮ Minimal matrices and discrete tomography ⋮ Reconstruction of Discrete Sets from Four Projections: Strong Decomposability ⋮ Reconstruction of convex 2D discrete sets in polynomial time ⋮ Latin Squares and their Bruhat Order ⋮ On the minimum rank of regular classes of matrices of zeros and ones ⋮ Reconstructing \(hv\)-convex polyominoes from orthogonal projections ⋮ Invariant sets of arcs in network flow problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A theorem on flows in networks
• Zero-one matrices with zero trace
• Term rank of \(0,1\) matrices
• On Ryser's maximum term rank formula
• On Haber's minimum term rank formula
• Matrices of 0's and 1's with total support
• A general upper bound for 1-widths
• Convex polyhedra of doubly stochastic matrices. I: Applications of the permanent function
• A short proof of Minc's conjecture
• Non-singular 0-1 matrices with constant row and column sums
• Parallel concepts in graph theory
• (0,1)-matrices with minimal permanents
• Transversal theory. An account of some aspects of combinatorial mathematics
• The 1-width of (0,1)-matrices having constant row sum 3
• Two combinatorial covering theorems
• Cyclic and diagonal products on a matrix
• Term ranks and permanents of nonnegative matrices
• A lower bound for the permanent on \(U_ n(k,k)\)
• Systems of distinct representatives. II
• The diagonal equivalence of a nonnegative matrix to a stochastic matrix
• Combinatorial Properties of Matrices of Zeros and Ones
• The Term Rank of a Matrix
• A Graph Theoretic Method for the Complete Reduction of a Matrix with a View Toward Finding its Eigenvalues
• Matrices of zeros and ones
• Widths and Heights of (0,1) -Matrices
• Multiplicities and Minimal Widths for (0, 1)-Matrices
• Minimal Term Rank of a Class of (0, 1)-Matrices
• Invariant Sets for Classes of Matrices of Zeros and Ones
• A Canonical Form For Fully Indecomposable (0,1)-Matrices
• Matrices permutation equivalent to irreducible matrices and applications
• A Lower Bound on the Permanent of a (0, 1)-Matrix
• An Upper Bound for the Permanent of a Fully Indecomposable Matrix
• Local Restrictions for Various Classes of Directed Graphs
• Minimal Interchanges of (0, 1)-Matrices and Disjoint Circuits in a Graph
• Convex Sets of Non-Negative Matrices
• Note on the Transfinite Case of Hall's Theorem on Representatives
• A lower bound for permanents of (0,1)-matrices
• Permanents
• Combinatorial theorems and integral matrices
• Problems Involving Diagonal Products in Nonnegative Matrices
• On Lower Bounds for Permanents of (0, 1) Matrices
• Existence theorem for infinite integral matrices
• MAXIMAL DEPTH OF A CLASS OF $ (0,1)$-MATRICES
• A Lower Bound for the Permanent of a (0, 1)-Matrix
• On the Permanent of a Certain Class of (0, 1)-Matrices
• Traces of Matrices of Zeros and Ones
• Width Sequences for Special Classes of (0, 1)-Matrices
• Upper bounds for permanents of $\left( {0,\,1} \right)$-matrices
• The Factorization of Linear Graphs
• Distinct representatives of subsets
• Matrix factorizations of determinants and permanents

This page was built for publication: Matrices of zeros and ones with fixed row and column sum vectors