Page 39 - Textos de Matemática Vol. 39

THE BRUHAT SHADOW OF A PERMUTATION MATRIX 29
and column 1. Then the matrix of order n − 1 obtained from A(P ) by deleting row and column 1 equals S(U′). Hence the theorem follows by induction.
There is yet another way of viewing the Bruhat shadow of a permutation matrix. Define a partial order on the set V = {1,2,...,n} × {1,2,...,n} of positions in a n × n matrix by (i,j) ≤ (i′,j′) whenever i ≥ i′ and j ≤ j′, i.e. (i′, j′) is “northeast of” (i, j). For (i, j), (i′, j′) ∈ V we have the corresponding interval Ii,j;i′ ,j′ = {(i∗, j∗) : (i, j) ≤ (i∗, j∗) ≤ (i′, j′)} in this partially ordered set consisting of those positions (if any) that lie between (i,j) and (i′,j′). Geometrically, such an interval corresponds to a rectangle of positions in a matrix of order n with (i,j) and (i′,j′) its southwest and northeast corners, respectively. Now let P = [pkl] be a permutation matrix of order n, and let S be the union of all intervals Ii,j;i′ ,j′ for which pij = pi′ j′ = 1. The (0, 1)-matrix of order n with support S (i.e. ones in positions in S and zeros elsewhere) is denoted by Bconv(P) and we call it the Bruhat convex hull of P.
The next result says that the Bruhat shadow and the Bruhat convex hull of a permutation matrix coincide.
Theorem 2.3. Consider a permutation matrix P of order n. Then B(P ) = Bconv(P ).
Proof. In fact, the left- and right-sequences give the left and right boundary of the support S of Bconv(P).
Theorem 2.4. A (0, 1)-matrix M of order n is the Bruhat shadow of a Bruhat ideal of Sn if and only if M is a matrix of total support with a staircase pattern satisfying In ≤ M.
Proof. Since the Bruhat shadow of a Boolean ideal I is the Boolean sum of permutation matrices, it follows that the Bruhat shadow M of a Boolean ideal is a matrix of total support; since In is the unique minimal permutation matrix in the Bruhat order on Sn, In ∈ I and hence In ≤ M. By Theorem 2.2 for each permutation matrix P , S(P ) = A(P ), a matrix with a staircase pattern. Since M is the Boolean sum of matrices with a staircase pattern, M has also has a staircase pattern.
Now let M be a (0,1)-matrix with total support satisfying In ≤ M. Let Q be any permutation matrix with Q ≤ M; at least one such Q exists since In ≤ M. Since M has a staircase pattern, S(Q) ≤ M (entrywise). Since M has total support, each 1 of M is on a permutation matrix P with P ≤ M. Hence M is a Bruhat shadow of a Bruhat ideal.
The problem of identification of Bruhat shadows of principal ideals is taken up in the next section.