Page 37 - Textos de Matemática Vol. 39

THE BRUHAT SHADOW OF A PERMUTATION MATRIX 27
We show that given the Bruhat shadow S(P) of a permutation matrix P, there is a unique permutation matrix Q such that S(Q) = S(P) and ⟨Q⟩ is the set of all permutation matrices contained in S(P). The permutation matrix Q is the unique permutation matrix contained in S(P) with the smallest number of inversions. Moreover, we give a result on the maximum number of inversions of a permutation matrix where the ones can lie in a certain type of staircase pattern.
2. Bruhat Shadow
Let A be a nonzero (0, 1)-matrix of order n. Recall that A has total support provided that each 1 of A is on a permutation matrix Q with Q ≤ A. The matrix A is fully indecomposable provided it has total support and there do not exist permutation matrices U and V such that U AV is the direct sum of two matrices of smaller order. The (0, 1)-matrix A has a staircase pattern provided the 1’s in each row and in each column occur consecutively (a property sometimes referred to as doubly convex) and the leftmost (resp., rightmost) 1 in a row occurs above or to the left of the leftmost (resp., rightmost) 1 in the next row.
Let P = [pij ] be a permutation matrix of order n corresponding to a per- mutation σ = i1,i2,...,in of {1,2,...,n}. We define two sequences l(σ) = l1,l2,...,ln, the left-sequence of σ, and r(σ) = r1,r2,...,rn, the right- sequence of σ, where rk is the smallest integer in the set {ik,ik+1,...,in} of integers weakly to the right of ik in σ and lk is the largest integer in the set {i1,i2,...,ik} of integers weakly to the left of ik in σ (k = 1,2,...,n). It fol- lowsthatrk ≤k≤lk andrk ≤ik ≤lk fork=1,2,...,n;seeLemma3.3. We depict the right- and left-sequences as shown below for the permutation 3,4,1,5,2, with the right-sequence on top, the left-sequence on the bottom, and the permutation in the middle:
r11122 σ2.
l34455
The following lemma contains an interpretation of left- and right-sequen-
ces in connection with L2 → I2 interchanges.
Lemma 2.1. Consider a permutation matrix P of order n and its correspond- ingleft-andright-sequencesl1,l2,...,ln andr1,r2,...,rn.Thenrk equalsthe smallest index of a column and lk equals the largest index of a column to which the 1 in row k can be moved by a L2 → I2 interchange or no interchange.
Proof. Let σ = i1,i2,...,in be the permutation corresponding to the per- mutation matrix P. Let k be an integer with 1 ≤ k ≤ n. If no interchange is done on P, then the 1 in row k remains in column ik. Consider an L2 → I2 interchange involving row k and some other row t. We may assume that t > k; otherwise the 1 in row k is moved to a column j > ik. But then the possible
3
4
1
5