Page 38 - Textos de Matemática Vol. 39

28 RICHARD A. BRUALDI AND GEIR DAHL
new column positions for the 1 in row k are among ik+1, ik+2, . . . , in and the smallest number among these and ik is precisely rk, as desired. The property of lk in the lemma is proved in a similar way.
Let A(P ) = [akj ]be the (0,1)-matrix such that
akj = 1 ifrk ≤j≤lk (1≤k,j≤n).
0 otherwise
The matrix A(P ) has a staircase-pattern with In ≤ A and P ≤ A. For example,
if σ = 5,7,1,3,2,6,4, we have
⎡⎢ 1 1 1 1 1 0 0 ⎤⎥ ⎢1 1 1 1 1 1 1⎥ ⎢ 1 1 1 1 1 1 1 ⎥
(2.1) A(P)=⎢0 1 1 1 1 1 1⎥, ⎢0111111⎥ ⎣0001111⎦
0001111
where the 1’s of the permutation matrix corresponding to σ are in boldface. If a permutation begins with n and ends with 1, then its right-sequence is 1, 1, . . . , 1 and its left-sequence is n,n,...,n, and hence A(P) = Jn.
We now show that the Bruhat shadow of a permutation matrix P equals A(P ).
Theorem 2.2. Let P be a permutation matrix of order n. Then S(P) = A(P).
In particular, the matrix A(P) has total support.
Proof. Because of the staircase-pattern of A(P ) it follows easily that if Q is a permutation matrix having a 1 in a position where A(P ) has a 0, then Q ̸≼B P . This is because a permutation matrix Q with Q ≼B P can be obtained from P by a sequence of L2 → I2 interchanges and each 0 in A(P) either does not have a 1 to its right or does not have a 1 to its left; see Lemma 2.1.
We now prove by induction that for each position where A(P) has a 1, there is a permutation matrix Q ≼B P which also has a 1 in that position. We have P ≤ S(A). Using the 1’s of P below the positions of A(P) with a 1 in row 1 (columns 1, 2, . . . , l1), we can by one L2 → I2 interchange obtain a permutation matrix Q ≼B P which has a 1 in any prescribed position 1,2,...,l1 of row 1. Similarly, we can obtain a permutation matrix Q ≼B P which contains a 1 in any prescribed position in column 1 where A(P) has a 1.
Now let U be the permutation matrix obtained from P by doing the L2 → I2 interchange involving the two 1’s of P in row 1 and column 1. (Note that if P has a 1 in position (1, 1), then no such interchange is necessary.) Let U ′ be the permutation matrix of order n − 1 obtained from U by deleting row