On the job rotation problem

Remark. Note that solving an assignment problem for A = (aij ) ∈ T^n×n is
equivalent to deciding whether the permanent of the matrix B = (bij ) is positive
where B is defined by bij = 1 if aij = 0 and bij = 0 otherwise. Therefore the
statements in Section 3 solve in special cases the question: Given A ∈ {0, 1}^n×n ,
and k ≤ n, is there a k ×k principal submatrix of A whose permanent is positive?

4 JRP for special matrices over R

Recall that a matrix A ∈ Rn×n is called irreducible if D(A) is strongly con-
nected or n = 1. If A, B are square matrices and A can be obtained from B
by simultaneous permutations of the rows and columns then we say that A and
B are equivalent, notation A ~ B. Clearly, ~ is an equivalence relation, and
δ_k (A) = δ_k (B) if A ~ B. It is known [18] that every matrix A can be trans-
formed in linear time to an equivalent matrix B in the Frobenius normal form,
that is

-∞

in which all diagonal blocks are irreducible.

In this section we study JRP for matrices over R. First we present some
solvable special cases and then we show that JRP(A) for A ∈ Rn×n can be
solved in polynomial time if this is true for every diagonal block of the Frobenius
normal form of A.

4.1 Pyramidal matrices

If A = (aij) ∈ Rⁿ×n and k ∈ N then the principal submatrix A(1,..., k) is called
a main principal submatrix of A, notation A[k]. If for all i, j, r, s ∈ N

max(i, j) < max(r, s) =⇒ aij ≥ ars ,

then A is called pyramidal.

Theorem 13. If A = (aij) ∈ Rn×n is pyramidal then δ_k(A) = m(A[k]).

Proof. Let A(l1, . . . lk) be an arbitrary principal submatrix, where 1 ≤ l1 <

11

<<   8   9   10   11   12   13   14   >>

More intriguing information