Page 47 - Textos de Matemática Vol. 39

P = ⎢
THE BRUHAT SHADOW OF A PERMUTATION MATRIX 37
As an example let n = 13 and consider the matrix
⎡⎢
⎢ ⎢ ⎢ ⎢ ⎢
0001∗∗∗∗∗∗∗∗∗⎤⎥ 000001∗∗∗∗∗∗∗⎥ 000010∗∗∗∗∗∗∗⎥ 001000∗∗∗∗∗∗∗⎥ 0000001∗∗∗∗∗∗⎥ 0100000∗∗∗∗∗∗⎥ 00000000001∗∗⎥. 0000000000001⎥ 0000000000010⎥ 0 0 0 0 0 0 0 0 0 1 0 0 0 ⎥
⎢
⎢
⎢ ⎢0000000010000⎥
⎣0000000100000⎦ 1000000000000
Here the stars indicate the full staircase pattern (so l1 = 4, l2 = 6 etc.). We have p = 5 and calculate (the terms corresponds to r = 1,2,...,5) βA =3+9+3+4+15=34.P isconstructedbyAlgorithm1anditsatisfies inv(P ) = inv∗A = 34.
The next result concerns the range of the inversion numbers of permuta- tion matrices P ≤ A in a full staircase pattern.
Corollary 4.3. For each integer 0 ≤ k ≤ βA there is a permutation matrix P ≤ A with inv(P) = k.
Proof. Let P be the matrix obtained by Algorithm 1, so inv(P) = βA. Con- sider the 1 in the last row, say that it lies in column j. Then, for s = j + 1,j + 2,...,n we use an L2 → I2 interchange involving the 1 in the last row and the 1 in column s; this is feasible due to the staircase pattern. Each such interchange reduces the number of inversions by one, and after these interchanges we have a new permutation matrix P1 with a 1 in position (n, n). Then we repeat this process for the 1 in row n − 1 (neglecting the last row) and proceed row by row until we eventually have the identity matrix (having no inversions). In this process we have constructed permutation matrices with corresponding inversion numbers βA, βA − 1, . . . , 1, 0 as desired.
5. Open questions We conclude with a number of open questions.
(1) Let M be a (0,1)-matrix of order n such that M has total support and has a staircase pattern with In ≤ M. Then by Theorem 2.4, M is the Bruhat shadow of a Bruhat ideal I of Sn. Find algorithms to determine a permutation matrix P with P ≤ M such that (i) P is a