Page 44 - Textos de Matemática Vol. 39

34 RICHARD A. BRUALDI AND GEIR DAHL
Moreover, all the k numbers i1,i2,...,ik and j1,j2,...,jk must be distinct, as P is a symmetric permutation matrix. This implies that lk = lk−1 for indices k that occur in the given sequence l, so condition (ii) holds.
Conversely, if an integral sequence l1, l2, . . . , ln satisfies conditions (i) and (ii), then we may put ones in the corresponding extreme positions. These ones are not in conflict due to (ii), and we get a symmetric subpermutation ma- trix. By adding ones in suitable positions on the diagonal we get a symmetric permutation matrix with left-sequence equal to l1, l2, . . . , ln as desired.
As an example, let n = 6 and consider the potential left-sequence given by l = 3,3,5,5,5,6. Then, for k = l1 = 3 we have lk > lk−1, so condition (ii) in the theorem is violated. Therefore l is not the left-sequence of a symmetric permutation matrix. Here the problem is that l forces ones to be placed in positions (1, 3), (3, 1) (by symmetry) and also in position (3, 5).
4. Inversions
Consider a full staircase pattern given by a (0,1)-matrix A satisfying aij =1(1≤j≤li,i=1,2,...,n)wherel1 ≤l2 ≤···≤ln,andaij =0 otherwise. It is assumed throughout this section that
(4.1) li ≥ i (i = 1,2,...,n).
We consider the problem of finding a permutation matrix P ≤ A with the largest number of inversions. The number of inversions of a permutation ma- trix P, denoted inv(P), is the number of inversions of the corresponding per- mutation τ = τ1,τ2,...,τn and this equals the number of submatrices of P equal to L2. The condition (4.1) is necessary and sufficient for the existence of a permutation matrix P ≤ A; this follows from K¨onig’s theorem, see [3]. Let
inv∗A =max{inv(P):P ≤A, P ∈Sn}
be the maximum number of inversions of a permutation matrix P ≤ A. Clearly a matrix P with inv(P ) = inv∗A must be inversion-maximal in the sense that no I2 → L2 interchange is possible within the given full staircase pattern. However, for general patterns, there are examples where an inversion-maximal matrix P does not have the maximum number of inversions. Therefore we would like to find an upper bound on inv∗A which may be used in testing the optimality of a given permutation matrix (optimal means that the number of inversions equals inv∗A ).
Since the l-sequence is nondecreasing there are indices 1=i1<i2<· · ·<ip≤n such that
li1 =li1+1=···=li2−1<li2 =li2+1=···=li3−1<···<lip =lip+1=···=ln.