On the job rotation problem

nodes.

Proof. Let {σ1, . . . , σt} be a collection of PND cycles in D(A) covering l nodes
with σi having odd length for i = 1, . . . , r and even length otherwise. By
splitting the cycles σ_i for i = r+ 1, . . . , t if needed, we may assume that all these
cycles are 2-cycles. By splitting one by one the cycles σi - vi for vi ∈ V (σi)
and i = 1, . . . , r, we get that δl-i = 0 for i = 1, . . . , r. After these splittings,
all remaining cycles are 2-cycles and removing them one by one proves the
result.                                                                           □

Corollary 4. Let A ∈ T^n×n be a symmetric matrix. For all even k ≤ kmax ,
δk (A) = 0, and if δk (A) = 0 for some odd k ∈ N then δk-1 (A) = 0.

If A has at least one zero on the main diagonal, (or equivalently, if the
digraph D(A) has at least one loop), then we can derive a number of properties:

Theorem 5. If A ∈ T^n×n is a symmetric matrix, and there exists a collection
of PND cycles in D(A) covering l nodes, at least one of which is a loop, then
δk (A) = 0 for all k ≤ l.

Proof. Let {σ₁ , . . . , σ_t} be a collection of PND cycles in D(A) covering k_max
nodes with σi having odd length for i = 1, . . . , r and even length otherwise.
Assume σr is a loop. By splitting the cycles σi for i = r + 1, . . . , t if needed, we
may assume that all these cycles are 2-cycles. By splitting one by one the cycles
σ_i -v_i for v_i ∈ V (σ_i) and i = 1, . . . , r- 1, we get that δ_l-i = 0 for i = 1, . . . , r- 1.
After these splittings, all remaining cycles except σr are 2-cycles. Removing the
2-cycles one by one gives us δl-i = 0 for odd i ∈ {r + 1, . . . , l - 1}. Removing
σ_r and the 2-cycles one by one gives us δ_l-i = 0 for even i ∈ {r,... ,l}.       □

If l ∈ {kmax, kmax - 1} in Theorem 5, then we can completely solve the
(non-weighted) JRP for this type of matrix:

Theorem 6. If A ∈ T^n×n is a symmetric matrix, l ∈ {k_max, k_max - 1} and
there exists a collection of PND cycles in D(A) covering l nodes, at least one of
which is a loop, then δk (A) = 0 for all k ≤ kmax .

Proof. The statement immediately follows from Theorem 5 and the fact that
δkmaχ (A)=0.                                                      □

Theorem 7. If A = (aij) ∈ T^n×n is a symmetric matrix and D(A) contains a
loop, then δ_k (A) = 0 for all k ≤ k_max .

<<   5   6   7   8   9   10   11   >>

More intriguing information