Algorithms for constructing \((0,1)\)-matrices with prescribed row and column sum vectors (Q856850)

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.