Page 41 - Textos de Matemática Vol. 39

THE BRUHAT SHADOW OF A PERMUTATION MATRIX 31
positions of the permutation σ, an obvious contradiction. Hence rk ≤ k and similarly k ≤ lk. Hence condition (iii) is also satisfied.
Nowassumetothecontrarythatrk =sj butk̸=j.Letc=rk =sj. First suppose that k > j with c = rk = sj. Then by Remark 3.2, there is an integerp≥ksuchthatip =candthereisanintegerq≤jsuchthatiq =c. Since q ≤ j < k ≤ p, we contradict the fact that σ is a permutation. If k < j, we interchange k and j in our argument and get a contradiction again. Hence condition (iv) holds as well.
Conditions (i)–(iv) are not sufficient to guarantee that sequences l1,l2,...,ln and r1,r2,...,rn are the left- and right-sequences of a permu- tation matrix, that is, determine a Bruhat shadow. For example, let n = 7 and consider the possibility
r1122455 (3.1) σ
l6677777 with corresponding staircase matrix
⎡⎢ 1 1 1 1 1 1 0 ⎤⎥ ⎢ 1 1 1 1 1 1 0 ⎥ ⎢ 0 1 1 1 1 1 1 ⎥
(3.2) M=⎢0 1 1 1 1 1 1⎥. ⎢⎣ 0 0 0 1 1 1 1 ⎥⎦
0000111 0000111
If there is a permutation σ with left- and right-sequences as given in (3.1), then by Remark 3.2 certain elements of σ are determined:
r1122455 σ5.
l6677777
The only integer whose place in σ is not determined is the integer 3, and since 3 is not between 5 and 7, there is no such permutation σ. In terms of the corresponding staircase matrix those 1’s in boldface below are determined to be part of the permutation matrix that would correspond to σ:
⎡⎢ 1 1 1 1 1 1 0 ⎤⎥ ⎢ 1 1 1 1 1 1 0 ⎥ ⎢0 1 1 1 1 1 1⎥
M=⎢0 1 1 1 1 1 1⎥. ⎢0001111⎥ ⎣0000111⎦
0000111
6
1
7
2
4