2.2. DECOMPOSITION INTO STRONG COMPONENTS 
43 
— 
where A, + X, and An- + X»- are square matrices of order r and n 
r, 
respectively. The union of their diagonal elements is sæ1,x2,...,xn). 
It 
follows thaty can be written as a partition of two nonconstant polynomials 
in Zsæj xn). 
Now assume that the matrix A = a; is irreducible. Suppose that y has 
a partition 
V = p+9 
(2.9) 
into two nonconstant polynomials in Zaj,...,. Without loss of generality 
let p be a polynomial in the indeterminates x1,...,x. and q a polynomial 
in the indeterminates (.+1...,n). 
Consider the digraph D associated with the adjacency matrix A. By ap¬ 
plying Lemma 2.2.2 we know that A is irreducible if and only if the associated 
digraph D is strongly connected. It follows that there is at least one dicy¬ 
cle whose support has at least one vertex in x1,...,x. and at least one 
in ,1...,. Consequently, y cannot be expressed as the sum of two 
polynomials in distinct sets of indeterminates, which renders a contradiction. 
O 
Hence, y has no partition in its indeterminates. 
The partition ofy in its indeterminates is uniquely determined. The de¬ 
velopment of an algorithm for the computation of the polynomial and its 
partition is limited by the complexity of the digraph. Explicit considerations 
on the computational complexity are beyond the scope of this thesis and 
have been omitted. However, counting all dicycles in a polynomial is not an 
efficient technique although complexity can be reduced by the partition of 
the polynomial expression. A slightly better way to assess all directed cycles 
in a digraph was implemented in the Prolog program listed in Appendix C.1 
which employs a depth-first strategy. Directed cycles in digraphs have been 
subject to extensive research in connection with the linear ordering problem 
and the corresponding acyclic subgraph problem' (see for example Fishburn, 
1992; Jünger, 1985; Reinelt, 1985). These problems among many others are 
known to be NP-complete which means that if there exists an algorithm 
which solves one of them in polynomial time, there would exist a polynomial 
time algorithm for solving them all. Garey and Johnson (1979) provide a 
comprehensive treatment of the theory of NP-completeness and a compila¬ 
tion of all contemporary NP-complete problems.? 
In a straightforward application of results the adjacency matrix A of a 
tournament is first brought into Frobenius normal form. Then the polyno¬ 
There is an occasional survey on recent developments in the field by Johnson in Journal of Algorithms.