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 Tn×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 Tn×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 1 , . . . , σt} be a collection of PND cycles in D(A) covering kmax
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 -vi for vi 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 Tn×n is a symmetric matrix, l {kmax, kmax - 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) Tn×n is a symmetric matrix and D(A) contains a
loop, then
δk (A) = 0 for all k ≤ kmax .



More intriguing information

1. The name is absent
2. The name is absent
3. Strategic monetary policy in a monetary union with non-atomistic wage setters
4. The name is absent
5. Short Term Memory May Be the Depletion of the Readily Releasable Pool of Presynaptic Neurotransmitter Vesicles
6. Proceedings from the ECFIN Workshop "The budgetary implications of structural reforms" - Brussels, 2 December 2005
7. The name is absent
8. The name is absent
9. Tourism in Rural Areas and Regional Development Planning
10. NEW DEVELOPMENTS IN FARM PRICE AND INCOME POLICY PROGRAMS: PART I. SITUATION AND PROBLEM
11. Target Acquisition in Multiscale Electronic Worlds
12. The name is absent
13. Bird’s Eye View to Indonesian Mass Conflict Revisiting the Fact of Self-Organized Criticality
14. The name is absent
15. The name is absent
16. Automatic Dream Sentiment Analysis
17. The name is absent
18. The Shepherd Sinfonia
19. THE DIGITAL DIVIDE: COMPUTER USE, BASIC SKILLS AND EMPLOYMENT
20. Disturbing the fiscal theory of the price level: Can it fit the eu-15?