Algorithm JRPBLOCKDIAG
Input: A = blockdiag(A 1, A2,..., Ap) ∈ Rn×n.
Output: For k = 1, . . . , n, δk (A), and if δk (A) is finite, then also k independent
entries of a k × k principal submatrix of A whose total is δk (A).
1. Set M0 = {(0,0, 0)}
2. For j = 1 to p :
(a) For r = 1 to n(j ) :
i. Find δr(Aj).
ii. Find Bjr ∈ (Aj )r and πjr ∈ ap(Bj r) such that w(Bjr, πjr) =
δr(Aj).
(b) Set Mj = Mj-1
(c) For each element (S, w, l) ∈ Mj-1 :
j
For each r = 1 to min( n(t) - l, n(j)) with δr (Aj ) finite :
t=1
i. If @(S0, w0, l + r) ∈ Mj, then add (S ∪ {(j, r)}, w + δr (Aj), l + r)
to Mj .
ii. If ∃(S0, w0, l + r) ∈ Mj and w0 < w + δr (Aj ), then remove
(S0, w0, l + r) from Mj and add (S ∪ {(j, r)}, w + δr (Aj), l + r) to
Mj.
3. For k = 1 to n :
If ∃(S, w, k) ∈ Mp, then return δk (A) = w, and for i = 1, . . . , r and all
(j, r) ∈ S, return the element of A that corresponds to the (i, πjr (i)) entry
of Bjr. Else return δk (A) = -∞.
Figure 2: An algorithm for solving JRP for block diagonal matrices.
Lemma 20.
1. If (S, w, k) ∈ Mj in Step 3 of the algorithm, then
(a) S ⊆ {1, . . . , p} × {1, . . . , n},
(b) P δs(Ai) = w,
(i,s)∈S
(c) P s = k,
(i,s)∈S
(d) If (S0 , w0 , k) ∈ Mj , then S0 = S and w0 = w,
(e) If S0 ⊆ {1,...,p} × {1,...,n}, w0 = P δs(Ai) and P s = k
(i,s)∈S0 (i,s)∈S0
then w0 ≤ w.
16