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

作者：Fernandes Rosario^*; da Cruz Henrique F

来源：Discrete Mathematics, 2013, 313(20): 2365-2379.

DOI：10.1016/j.disc.2013.06.016

• (0,1)-matrices
• Row and column vectors
• Young tableaux
• RSK algorithm

Given partitions Rand 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 <= lambda <= R*. We give a canonical construction for matrices in A(R, S) whose insertion tableau has a prescribed shape lambda, with S <= lambda <= 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.

• 出版日期2013-10-28