ELA, Volume 12, pp. 6-16, December 2004, abstract.

A Bruhat Order for the Class of (0,1)-Matrices with
Row Sum Vector R and Column Sum Vector S

Richard A. Brualdi and Suk-Geun Hwang

Generalizing the Bruhat order for permutations 
(so for permutation matrices), a Bruhat order is 
defined for the class of m by n (0,1)-matrices
with a given row and column sum vector. An algorithm 
is given for constructing a minimal matrix (with 
respect to the Bruhat order) in such a class. This 
algorithm simplifies in the case that the row and 
column sums are all equal to a constant k. When k=2 
or k=3, all minimal matrices are determined. Examples 
are presented that suggest such a determination might 
be very difficult for k >= 4.