time. The whole of Step 2 is carried out for j = 1, . . . , p. It is easily seen that
Step 3 can be done in O(n2) time. So algorithm JRPBLOCKDIAG runs in time
Pp =1 O(n(j))t + Pp=ι O(n)O(n(j)) + O(n2) = O(n(n + t)). □
Corollary 22. If in Theorem 21, t is polynomial in n, that is, if JRP (Ai, k0)
can be solved in polynomial time, for all i = 1, . . . , p and k0 = 1, . . . , k, then for
a block diagonal matrix A, JRP(A) can be solved in polynomial time.
Any matrix that can be obtained by permuting the rows and/or columns of
the matrix containing zeros on the main diagonal and -∞ elsewhere, will be
called a permutation matrix. Any matrix that can be obtained by permuting the
rows and/or columns of a matrix containing finite entries on the main diagonal
and -∞ elsewhere, will be called a generalized permutation matrix. It is known
[8] that JRP (A) can be solved in O(n2 ) time, for a permutation matrix A.
With the same time complexity, this is also true for generalized permutation
matrices:
Corollary 23. For any generalized permutation matrix A ∈ Rn×n, JRP(A)
can be solved in O(n2 ) time.
Proof. Generalized permutation matrices are a special type of block diagonal
matrix. Each block contains only one cycle, therefore we can solve JRP for each
block in linear time, and hence use Theorem 21 to give the result. □
Any element of a matrix that does not lie on a finite cycle may be set to -∞
without affecting δk for any k ∈ N . Hence if B is in Frobenius normal form,
then we may set all elements of off-diagonal blocks in B to -∞. Therefore if
we define Ci = Bii, for i = 1, . . . , p, i.e.
C = blockdiag(C1, C2,..., Cp),
then we have δk (C) = δk (A) for all k ∈ N . We have derived the following:
Theorem 24. For any A ∈ Rn×n, if we can solve JRP for all diagonal blocks of
the Frobenius normal form of A in polynomial time, then we can solve JRP(A)
in polynomial time (by converting it to a block diagonal matrix and using the
JRPBLOCKDIAG algorithm of Figure 2).
18
More intriguing information
1. The name is absent2. The name is absent
3. Recognizability of Individual Creative Style Within and Across Domains: Preliminary Studies
4. Backpropagation Artificial Neural Network To Detect Hyperthermic Seizures In Rats
5. Industrial districts, innovation and I-district effect: territory or industrial specialization?
6. Quelles politiques de développement durable au Mali et à Madagascar ?
7. The name is absent
8. Large Scale Studies in den deutschen Sozialwissenschaften:Stand und Perspektiven. Bericht über einen Workshop der Deutschen Forschungsgemeinschaft
9. The name is absent
10. The role of statin drugs in combating cardiovascular diseases