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

Given partitions RR and SS with the same weight and S⪯R∗S⪯R∗, the Robinson–Schensted–Knuth correspondence establishes a bijection between the class A(R,S)A(R,S) of (0,1)(0,1)-matrices with row-sum RR and column-sum SS, and pairs of Young tableaux with conjugate shape λλ and λ∗λ∗, with S⪯λ⪯R∗S⪯λ⪯R∗. We give a canonical construction for matrices in A(R,S)A(R,S) whose insertion tableau has a prescribed shape λλ, with S⪯λ⪯R∗S⪯λ⪯R∗. This algorithm generalizes some recent constructions due to R. Brualdi for the extremal cases λ=Sλ=S and λ=R∗λ=R∗ (using a Ryser-like algorithm), and due to C.M. da Fonseca and R. Mamede for particular cases of λλ.