Let us denote for k = 1, . . . , n
δk (A) = max m(B),
k B∈Pk(A)
where Pk(A) is the set of all principal submatrices of A of order k. For sim-
plicity we often write just δk instead of δk (A). Clearly, δn = m(A) and δ1 =
max(a11, a22, . . . , ann). Note that δk = -∞ if m(B) = -∞ for all B ∈ Pk (A).
Thus JRP(A, k) (k = 1, ..., n) is the problem of finding a matrix B ∈ Pk (A)
such that
δk(A) = m(B).
Example 1. Let
A=
-∞
-∞
-∞
1 -∞ 0
54
-∞
-∞ 6
-∞ -∞
Then it is easily seen that δ1
-∞, δ2 = 8, δ3 = 13, and δ4 = -∞.
If A = (aij) ∈ Rn×n then we denote by D(A) the digraph whose set of
nodes is N and arc set is {(i, j); aij > -∞}. For a path τ = (i1 , i2, . . . , ip), let
V (τ) = {i1 , i2, . . . , ip}. For a digraph D, we say paths τ1, τ2, . . . , τs in D are
pairwise node disjoint (PND) if V(τi) ∩ V(Tj) = 0 for i, j = 1,..., s,i = j.
For A ∈ Rn×n, we define kmax(A) or just kmax as
max{k ∈ N; δk(A) > -∞}.
Since every permutation is a product of cyclic permutations, kmax (A) is the
biggest number of nodes in D(A) that can be covered by PND cycles in D(A).
Note that we are not using the word ”elementary” in connection with cycles as
all cycles in this paper are elementary.
Let A ∈ Rn×n be a symmetric matrix and σ be an arbitrary cycle of length
p in D(A). By symmetry, for each arc (i, j) in D(A), (j, i) is also an arc
(”counterarc”). If p is even, we define the operation of splitting σ as removing
alternate arcs from σ, and adding counterarcs (j, i) for each (i, j) that remains
from σ, resulting in a collection of 2 PND cycles in D(A) that cover all p nodes
from V (σ). If σ is a loop, we define the operation of splitting σ as removing
the arc. If p ≥ 3 is odd, we define the operation of splitting σ - v as removing