More on the Bruhat order for (0, 1)-matrices Original Research Article

Let image denote the class of all (0, 1)-matrices with row sum vector R and column sum vector S. Continuing an earlier investigation of the Bruhat order and secondary Bruhat order (both of which extend the classical Bruhat order on permutations of {1, 2, … , n}) on image, we provide a counterexample to a conjecture of Brualdi and Hwang which shows that these two orders are not in general the same. We characterize the cover relation for the secondary Bruhat order. We also study in more detail certain classes image where R = S = (k, k, … , k), a constant vector. We show that for k = 2 the Bruhat order and secondary Bruhat order are the same, but this is not always so when k = 3.