On the job rotation problem

Let σ be the cyclic permutation i 1 → i2 → ∙ ∙ ∙ → ip → i 1 of arbitrary length
p such that w(A, σ) 6= -∞.

As w(A, σ) 6= -∞, then ai_j i_j+1 6= -∞ for all j. So ij and ij+1 must be of
different parities for all j . This means elements in the sequence i1 , i2 , . . . , ip , i1
alternate between even and odd. Thus p must be an even number, i.e. there are
no cyclic permutations σ of odd length of finite weight. Hence the result. □

If A is symmetric, then together with Corollary 4, this gives us:

Theorem 17. If A = (aij) ∈ Rn×n is a symmetric matrix such that aij = -∞
if i + j is even, then δk(A) 6= -∞ for all even k ≤ kmax, and δk (A) = -∞ for
all odd k.

A certain type of Hankel matrix satisfies Theorem 17. Rewriting it for this
type of matrix gives:

Theorem 18. If {g_r ∈ R; r = 1,..., 2n — 1} is the sequence generating Hankel
matrix H and gr = -∞ for all odd r, then δk(H) 6= -∞ for all even k ≤ kmax
and δ_k(H) = -∞ for all odd k.

Combining Theorem 15 and Theorem 18 enables us to decide whether δ_k(H)
is finite or not for any Hankel matrix H .

Theorem 19. If {g_r ∈ R; r = 1,..., 2n — 1} is the sequence generating Hankel
matrix H then

1. δ_k (H) = -∞ for all even k ≤ k_max,

2. δ_k(H) = -∞ for all odd k if g_r = -∞ for all odd r, and

3. δ_k(H) = -∞ for all odd k ≤ k_max if g_r = -∞ for some odd r.

4.3 Block diagonal matrices

A = blockdiag(A1, A2, . . . , Ap) =

∖-∞

D(Ai) is a subgraph of D(A) for every i = 1, . . . , p. Every D(Ai) is disjoint
from any D(Aj ), j 6= i. So any cycle in D(A) has nodes entirely within one

14

<<   11   12   13   14   15   16   17   >>

More intriguing information