An extension of Brualdi's algorithm for the construction of (0,1)-matrices with prescribed row and column sum vectors

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

Given partitions R and S with the same weight and S ¹ R¤, 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 with conjugate shape \lambda and \lambda^* with S\preceq \lambda \preceq R^*. We give a canonical construction for matrices in A(R; S) whose insertion tableau has a prescribed shape \lambda with S\preceq \lambda \preceq R^*. This algorithm generalizes some recent constructions due to R. Brualdi for the extremal cases \lambda = S and \lambda = R^* (using a Ryser-like algorithm), and due to C.M. da Fonseca and R. Mamede for particular cases of \lambda..
Original languageUnknown
Pages (from-to)2365-2379
JournalDiscrete Mathematics
Volume313
Issue number20
DOIs
Publication statusPublished - 1 Jan 2013

Cite this