Page 42 - Textos de Matemática Vol. 39

32 RICHARD A. BRUALDI AND GEIR DAHL
Obviously there is no way to complete the collection of the 1’s in boldface to a permutation matrix P with P ≤ M. It is easy to check that the matrix (3.2) is the Bruhat shadow of the Bruhat ideal with the two maximal elements 6, 1, 3, 2, 4, 7, 5 and 1, 2, 7, 3, 4, 6, 5 with 7 and 5 inversions, respectively.
Now consider the possibility
r1123 (3.3) σ .
s2344
If there is a permutation σ with left- and right-sequences as given in (3.3), then
certain entries of σ are determined:
r1123 σ3. s2344
This gives several contradictions: 2 and 3 occur twice and positions 2 and 3 each have two different required entries. In terms of the corresponding staircase matrix, the 1’s in boldface are determined to be part of the permutation matrix that would correspond to σ:
2
1,3
2,4
⎡⎢ 1 1 0 0 ⎤⎥ M=⎢⎣1 1 1 0⎥⎦,
but rows 2 and 3 and columns 2 and 3 each contain two boldface 1’s. Thus M is not the Bruhat shadow of a principal ideal. It is however the Bruhat shadow of the ideal with two maximal elements, namely the permutation 2, 1, 4, 3 with two inversions and the permutation 1, 3, 2, 4 with one inversion.
The following straightforward result is a discrete and simplified version of the Krein-Milman theorem in convexity. (Our convex sets are (0, 1)-matrices with staircase patterns.)
Lemma 3.4. Let B be a square (0, 1)-matrix with a staircase pattern. Then B is the Bruhat convex hull of its extreme positions.
In the next theorem we characterize Bruhat shadows of permutation ma- trices.
Theorem 3.5. Let B be a (0,1)-matrix of order n. Then B is the Bruhat shadow of a permutation matrix if and only if B has a staircase pattern and the matrix B′ obtained from B by striking out the rows and columns of its extreme positions satisfies Im ≤ B′ where B′ has order m.
Proof. By Theorem 2.2 the Bruhat shadow B of a permutation matrix has a staircase pattern. Moreover, any permutation matrix P such that S(P) = B
0111 0011