Algorithms for constructing \((0,1)\)-matrices with prescribed row and column sum vectors
type: Item
instance of: scholarly article
title: Algorithms for constructing \((0,1)\)-matrices with prescribed row and column sum vectors
zbMATH Open document ID: 1110.05102
author: Richard A. Brualdi
published in: Discrete Mathematics
publication date: 2006-12-14T00:00:00Z
review text: Let \(R=(r_1\geq r_2 \geq r_3 \geq \cdots\geq r_m)\) and \(S=(s_1\geq s_2 \geq s_3 \geq \cdots \geq s_n)\) be positive integer vectors satisfying \(\sum r_i=\sum s_i,\) and let \({\mathcal A}(R,S)\) be the family of \(m\times n\) \((0,1)\)-matrices with row sum vector \(R\) and column sum vector \(S.\) Let \(\preceq\) be the majorization order and \(R^*\) the conjugate to \(R.\) The well-known Gale-Ryser theorem says that \({\mathcal A}(R,S)\neq \emptyset\) if and only if \(S\preceq R^*.\) The Ryser algorithm starts from the unique matrix in \({\mathcal A}(R,R^*)\) to actually construct an element in \({\mathcal A}(R,S).\) A \((0,1)\)-matrix \(A=(a_{ij})\) defines a unique generalized permutation \(\{(i,j): a_{ij}=1\}\) which in turn stands via the Knuth-Schensted correspondence [see \textit{C. Greene}, Adv. Math. 14, 254--265 (1974; Zbl 0303.05006) and \textit{D. E. Knuth}, Pac. J. Math. 34, 709--727 (1970; Zbl 0199.31901)] in a bijective relation with a pair of Young tableaux. If \(A\in {\mathcal A}(R,S),\) one of these tableaux, the insertion tableau, has shape \(\lambda\) satisfying \(S\preceq \lambda \preceq R^*.\) The author says that, given \(\lambda\) with \(S\preceq \lambda \preceq R^*,\) it may not be easy to construct in algorithmic manner a matrix whose associated insertion tableau has shape \(\lambda,\) but he succeeds to give Ryser like algorithms for the cases \(\lambda=S\) and \(\lambda=R^*.\) In passing also given is the relation of \(| {\mathcal A}(R,S)| \) with the Kostka numbers.
reviewed by: Alexander Kovačec
Mathematics Subject Classification ID: 05E10
zbMATH DE Number: 5080049
zbMATH Keywords: Young tableaux
zbMATH Keywords: row and columns sum vectors
zbMATH Keywords: algorithms
zbMATH Keywords: Gale-Ryser theorem
zbMATH Keywords: Knuth-Schensted correspondence
zbMATH Keywords: Kostka numbers
zbMATH Keywords: Ryser algorithm
MaRDI profile type: Publication
full work available at URL: j.disc.2004.10.028
OpenAlex ID: W1995751254
cites work: Matrices of zeros and ones with fixed row and column sum vectors
cites work: Q5484517
cites work: Q3129746
cites work: An extension of Schensted's theorem
cites work: Permutations, matrices, and generalized Young tableaux
DOI: 10.1016/J.DISC.2004.10.028
Recommended article: On (0, 1)-matrices with prescribed row and column sum vectors
Recommended article: An extension of Brualdi's algorithm for the construction of \((0,1)\)-matrices with prescribed row and column sum vectors
Recommended article: Schröder Partitions and Schröder Tableaux
Recommended article: Permutations, matrices, and generalized Young tableaux
Recommended article: Finding the permutations corresponding to a given Young tableau
Recommended article: Shifted tableaux, Schur q-functions, and a conjecture of R. Stanley
Recommended article: The computer-aided discovery of a theorem about Young tableaux
Recommended article: Q5502235
Recommended article: Ascending subsequences of permutations and the shapes of tableaux
Recommended article: Insertion and the multiplication of rational Schur functions
description: scientific article; zbMATH DE number 5080049