Page 43 - Textos de Matemática Vol. 39

THE BRUHAT SHADOW OF A PERMUTATION MATRIX 33
has 1’s in the extreme positions of B. Thus B is the Bruhat shadow of a permutation matrix if and only if B has a staircase pattern and there is a permutation matrix Q of order m such that Q ≤ B′. Suppose that B has a staircase pattern. Then since B′ is obtained from B by striking out rows and columns, B′ also has a staircase pattern.
To complete the proof it suffices to establish that if a matrix B′ with a staircase pattern satisfies that there exists a permutation matrix Q such that Q ≤ B′, then Im ≤ B′. Suppose to the contrary that the kth diagonal entry of B′ equals 0. Since B′ has a staircase pattern, either all the earlier entries of B′ in row k or all the later entries in row k are zero. A similar statement holds for column k. Suppose e.g. that all the earlier entries of B′ in row k are zero. Then the staircase pattern of B′ implies that the lower left m − k + 1 by k submatrix of B′ is a zero matrix. Since (m−k+1)+k = m+1, this contradicts the assumption that there is a permutation matrix Q with Q ≤ B′.
From Theorem 3.5 it is clear how one can check if two given sequences l1,l2,...,ln and r1,r2,...,rn are the left- and right-sequences of the Bruhat shadow of a permutation matrix. However, as indicated above, it seems hard to find an explicit characterization of such sequences. We now show that this is possible in the special case of Bruhat shadows of symmetric permutation matrices. If a permutation matrix P is symmetric, then clearly its Bruhat shadow is symmetric and therefore it suffices to look for a characterization in terms of (say) the left-sequence.
Theorem 3.6. An integral sequence l = l1, l2, . . . , ln is the left-sequence of a symmetric permutation matrix if and only if it satisfies
(i) 1≤l1 ≤l2 ≤···≤ln =n, and li ≥i (i≤n), and (ii) lk = lk−1 for all k ∈ {l1,l2,...,ln} with k ̸= 1.
Proof. Let P = [pij ] be a symmetric permutation matrix. Then condition (i) holds due to Lemma 3.3, so we need to verify (ii). By symmetry the positions of the off-diagonal ones occur in pairs (i, j) and (j, i). Assume that pij = 1 for some i < j, and that pkl = 1 for some position (k,l) with k < l and such that (k,l) lies in the Bruhat convex hull of {(i,j),(j,i)}, i.e., i < k < l < j. Then, by an L2 → I2 interchange applied to rows/columns k and l, we obtain another permutation matrix which has the same Bruhat shadow as P has. We may therefore assume (after a series of such interchanges) that all the off-diagonal ones in P are in extreme positions. In particular, the ones in the strict upper triangular part of P are in positions
where
(i1,j1),(i2,j2),...,(ik,jk)
i1 <i2 <···<ik andj1 <j2 <···<jk.