On the job rotation problem

Remark. Matrices that are not pyramidal, may become such after simultane-
ously permuting rows and columns. It follows from (1) that the diagonal entries
of the matrix must be in descending order for (1) to be satisfied. Once rows and
columns have been simultaneously permuted in this way, additional simultane-
ous row and column permutations may be needed between rows and columns
which have a diagonal entry equal to another diagonal entry.

4.2 Monge and Hankel matrices

A matrix A will be called diagonally dominant if id ∈ ap(A). (Note that through-
out the paper id stands for the identity permutation.) A matrix A = (aij ) ∈
R is called Monge if aij + a_rs ≥ ai_s + a_rj for all i, j, r, s ∈ N, i ≤ r, j ≤ s.
It is well known [6] that every Monge matrix A is diagonally dominant. It is
also easily seen that a principal submatrix of a Monge matrix is also Monge.
Hence JRP (A, k) for Monge matrices is readily solved by finding the k biggest
diagonal entries of A.

For a given sequence {g_r ∈ R; r = 1,..., 2n — 1}, the Hankel matrix is the
matrix H = (h_ij) ∈ Rn×ⁿ where hij = g_i+j_-1. Hankel matrices generated by
convex sequences are Monge [9]. Therefore, for these matrices, JRP is readily
solved. However, no efficient method seems to exist for Hankel matrices in
general.

In this subsection we show that finiteness of δk (H) can be easily decided for
any Hankel matrix H. Since Hankel matrices are symmetric, we can use some
of the results of Section 3.

Theorem 15. If {g_r ∈ R; r = 1,..., 2n — 1} is the sequence generating Hankel
matrix H = (hij) ∈ Rn×ⁿ and g_r = -∞ for some odd r, then δ_k(H) = -∞ for

Proof. Let C = (cij) be defined by cj = 0 if hij = -∞ and cj = -∞ otherwise.
Assume g_r = -∞ for some odd r. So (∃i) cii = -∞, i.e. (∃i) cii = 0. We now
use Theorem 7 to give us δk (C) = 0 for all k ≤ kmax . Then as δk (C) = 0 if and
only if δ_k(H) = -∞, the theorem follows.                                 □

Theorem 16. If a matrix A = (aij) ∈ Rn×ⁿ is any matrix such that aij = -∞
if i + j is even, then δ_k (A) = -∞ for all odd k.

Proof. Assume A = (aij) is a matrix such that aij = -∞ if i + j is even. If aij
is finite then i + j is odd. So i and j must be of different parities.

13

<<   10   11   12   13   14   15   16   >>

More intriguing information