On the job rotation problem

• • • <l_k ≤ n. Note that

i ≤ li , for all i ≤ k.

Therefore

max(i, j) ≤ max(li, lj), for i, j ≤ k.

If equality does not hold for some i and j, then by (1) we have,

aij ≥ ali,lj.

If equality does hold for some i and j, then let lt = max(li, lj ). Note that
i < j ⇔ li < lj . So we have t = max(i, j) and therefore lt = t. Hence

l_t_-₁ = t - 1, . . . , l₁ = 1. In this case

aij = ali,lj.

Either way, aij ≥ al_i ,l_j holds. Therefore

m(A(l1, . . . lk)) ≤ m(A(1, . . . k))

= m(A[k])

= δk(A),

as A(l1 , . . . lk) was arbitrary. Hence the result.

Example 14. Consider the matrix

The indicated lines help to check that A is pyramidal. Hence by Theorem 13
we find:

δ1(A) = m(A[1]) = 9

δ2 (A) = m(A[2]) = 16

δ3 (A) = m(A[3]) = 20

δ4(A) = m(A[4]) = m(A) = 22.