Page 46 - Textos de Matemática Vol. 39

36 RICHARD A. BRUALDI AND GEIR DAHL
Theorem 4.2. Consider a full staircase pattern given by A as above. Then the maximum number of inversions of a permutation matrix P ≤ A equals βA, i.e.
i n v ∗A = β A .
Moreover, such an optimal matrix P is found by Algorithm 1.
Proof. Observe first that Algorithm 1 corresponds to recursively doing the following operation: (i) put a 1 in position (1,l1), (ii) strike out the first row and column l1 and update the staircase pattern accordingly (the li’s).
We shall prove, by induction, that Algorithm 1 produces a matrix P with the following properties
(A1) P is a permutation matrix,
(A2) for 1 ≤ r ≤ p the submatrix of P induced by rows ir,ir +1,...n
and columns 1, 2, . . . , li contains lir −ir+1 + 1 ones, and these ones occur decreasingly, i.e., the mentioned submatrix contains no I2 submatrix.
Note first that (A1)-(A2) are trivial for n = 1. Assume that Algorithm 1 finds a matrix satisfying (A1)-(A2) for all full staircase patterns of order n − 1. Consider a full staircase pattern of order n. Algorithm 1 starts with the zero matrix of order n and puts a 1 in position (1,l1); this is possible as l1 ≥ 1. Then we strike out row 1 and column l1. This operation gives a full staircase pattern of order n − 1 which also satisfies the condition (4.1) (because the new li is equal to the old li+1 −1 which is at least i+1−1 = i). The induction assumption assures that Algorithm 1 constructs a permutation matrix of order n−1 for this pattern, and together with the one placed in position (1, li) we get a permutation matrix of order n. Thus (A1) holds by induction. Furthermore, since we put the 1 in the first row in the rightmost position l1 it is easy to check that property (A2) also holds.
Finally, the constructed permutation matrix P satisfies (A1)-(A2), and therefore it also satisfies inv(P) = βA. In fact, from (A2) we see that
Nir +Nir+1 +···+Nir+1−1 =nr(nr −1)/2+nr(lir −ir+1 +1)
for 1 ≤ r ≤ p, confer the notation used in connection with the claim in the proof of Lemma 4.1. This proves the theorem.