Page 45 - Textos de Matemática Vol. 39

THE BRUHAT SHADOW OF A PERMUTATION MATRIX 35 Letnownr =ir+1−ir (1≤r≤p)whereip+1 =n+1,anddefinethenumber
p r=1
Lemma 4.1. Let P be a permutation matrix with P ≤ A. Then inv(P) ≤ βA.
Proof. Let P be a permutation matrix P with P ≤ A. Since inv(P) equals the number of 2 × 2 submatrices of P equal to L2,
(4.2) inv(P)=N1 +N2 +···+Nn
where Ni is the number of L2-submatrices of P whose first row is a subvector ofrowiofP (hereNn =0).
We now claim that for 1 ≤ r ≤ p,
Nir +Nir+1 +···+Nir+1−1 ≤nr(nr −1)/2+nr(lir −ir+1 +1).
Let I = {ir,ir +1,...,ir+1 −1}. Due to the staircase pattern the 1’s in rows i ∈ I of P must be in the first lir columns. However, these first lir columns also contain ir − 1 ones in the first ir − 1 rows (again due to the staircase pattern). Thus, the rows in I contain nr = ir+1 − ir ones, and the rows below these contain at most lir −(ir −1+nr) = lir −ir+1 +1 ones in the first li columns. The maximum number of inversions is obtained if all these ones are placed in columns whose numbers decrease with i (i.e., τi > τs when i < s). It follows that Nir +Nir+1 +···+Nir+1−1 is at most nr(nr −1)/2+nr(lir −ir+1 +1) which proves the claim.
Finally, by adding up the bounds in the claim for 1 ≤ r ≤ p and using (4.2) we obtain the desired inequality and the proof is complete.
Consider the following simple algorithm for constructing a permutation matrix P with P ≤ A.
Algorithm 1.
1. Initialize P to be the zero matrix of order n. 2. For i = 1, 2, . . . , n do
let j be largest possible with j ≤ li such that P has no 1 in column j, and set pij = 1.
The following theorem shows that this algorithm finds a permutation ma- trix with the largest possible number of inversions. The idea in the proof is to establish that the number of inversions of the constructed matrix equals the upper bound βA found in Lemma 4.1.
βA =
[(nr(nr − 1)/2 + nr(lir − ir+1 + 1)].