Remark. Note that solving an assignment problem for A = (aij ) ∈ Tn×n is
equivalent to deciding whether the permanent of the matrix B = (bij ) is positive
where B is defined by bij = 1 if aij = 0 and bij = 0 otherwise. Therefore the
statements in Section 3 solve in special cases the question: Given A ∈ {0, 1}n×n ,
and k ≤ n, is there a k ×k principal submatrix of A whose permanent is positive?
4 JRP for special matrices over R
Recall that a matrix A ∈ Rn×n is called irreducible if D(A) is strongly con-
nected or n = 1. If A, B are square matrices and A can be obtained from B
by simultaneous permutations of the rows and columns then we say that A and
B are equivalent, notation A ~ B. Clearly, ~ is an equivalence relation, and
δk (A) = δk (B) if A ~ B. It is known [18] that every matrix A can be trans-
formed in linear time to an equivalent matrix B in the Frobenius normal form,
that is
B=
B B11 B12
B 22
-∞
Bpp
in which all diagonal blocks are irreducible.
In this section we study JRP for matrices over R. First we present some
solvable special cases and then we show that JRP(A) for A ∈ Rn×n can be
solved in polynomial time if this is true for every diagonal block of the Frobenius
normal form of A.
4.1 Pyramidal matrices
If A = (aij) ∈ Rn×n and k ∈ N then the principal submatrix A(1,..., k) is called
a main principal submatrix of A, notation A[k]. If for all i, j, r, s ∈ N
max(i, j) < max(r, s) =⇒ aij ≥ ars ,
(1)
then A is called pyramidal.
Theorem 13. If A = (aij) ∈ Rn×n is pyramidal then δk(A) = m(A[k]).
Proof. Let A(l1, . . . lk) be an arbitrary principal submatrix, where 1 ≤ l1 <
11