Page 36 - Textos de Matemática Vol. 39

26 RICHARD A. BRUALDI AND GEIR DAHL
Then an inversion-reducing interchange applied to P replaces a submatrix of order 2 equal to L2 by I2:
L2 → I2.
For permutation matrices P and Q of order n, we write P ≼B Q provided that P can be obtained from Q by a sequence of L2 → I2 interchanges. From now on we use permutation matrices of order n and permutations of {1,2,...,n} interchangeably, and use Sn to denote both the set of all permutation matrices of order n and the set of all permutations of {1,2,...,n}.
The Bruhat ideals are those nonempty subsets I of Sn such that P ∈ I and Q ≼B P imply that Q ∈ I. A principal Bruhat ideal is the ideal ⟨P⟩ generated by a permutation matrix P, that is,
⟨P⟩={Q∈Sn :Q≼B P}.
A Bruhat ideal I is the union of the principal Bruhat ideals generated by the maximal (in the Bruhat order) elements of I. If A = [aij] and B = [bij] are (0,1)-matrices of order n, their Boolean sum A +b B = [cij ] is the (0,1)-matrix satisfyingcij =1ifandonlyifaij =1orbij =1(1≤i,j≤n),thatis,cij is the Boolean sum of aij and bij. We define the Bruhat shadow of a Bruhat ideal I to be the (0,1)-matrix
S(I) = +b{Q ∈ I}.
If I is the principal Bruhat ideal generated by a permutation matrix P, then we write S(P) in place of S(I) and refer to S(P) as the Bruhat shadow of the permutation matrix P. Thus
S(P)=+b{Q∈Sn :Q≼B P}. Using this notation we have
S(I) = +b{S(P) : P maximal in I}.
The Bruhat shadow of the identity permutation matrix In is In. The Bruhat shadow of the permutation matrix corresponding to the anti-identity permuta- tion n, n − 1, . . . , 2, 1 is the matrix Jn of all 1’s. Different permutation matrices may have the same Bruhat shadow. For example, both
⎡⎢ 0 0 0 1 ⎤⎥ ⎡⎢ 0 0 0 1 ⎤⎥ ⎢⎣0 0 1 0⎥⎦and⎢⎣0 1 0 0⎥⎦
0100 0010 1000 1000
have Bruhat shadow equal to J4. We say that the Bruhat shadow of a Bruhat ideal I contains a permutation matrix Q provided that Q ≤ S(I) (entrywise). The preceding example shows that the Bruhat shadow of a principal Bruhat ideal ⟨P ⟩ may contain permutation matrices Q where Q ̸≼B P .
In this paper we characterize the Bruhat shadows of Bruhat ideals in general and of principal Bruhat ideals (permutation matrices) in particular.