48 
CHAPTER 2. THEORY 
The characteristic polynomial is computed by 
%(x) = det(xI - A) = 2x" + 212-1 +... + 2n-12 + 2n 
(2.11) 
where x is indeterminate in Z and I is the identity matrix. The coefficients zi 
of the characteristic polynomial correspond to certain collections of dicycles 
within the matrix. The characteristic polynomial o(x) of matrix A has the 
form 
9(x) = g12-72°- 112°- 10x' + 5a“ + 242' + 30r' + 20a' +722+r (2.12) 
The factorization of the polynomial (x) results in three irreducible poly¬ 
nomials." The disadvantages of the characteristic polynomial are twofold: 
First, the coefficients of the characteristic polynomial detect dicycles of any 
given length together with collections of disjoint dicycles which add up to the 
same given length. Consequently, if there are disjoint dicycles within strong 
components then the coefficients (before and after factorization) do not equal 
the number of dicycles. Second, the factorization of %(x) does not necessarily 
correspond to the strong components of a tournament. 
To overcome both problems the polynomial y(x1,...,x») is used instead. 
It counts only directed cycles and has a partition in its indeterminates. The 
partitioned polynomial corresponds to the strong components of any digraph 
including tournaments. For computational reasons the polynomials y in sin¬ 
gle indeterminates are computed for the irreducible submatrices of the Frobe¬ 
nius normal form. According to Theorem 2.2.11 the resulting polynomials 
can be written as a sum. 
The Hasse-like diagram in Figure 2.3 illustrates the preferences of matrix A 
in a special way. The alternatives are arranged in descending order according 
to their preference scores. As in a Hasse diagram preference decreases from 
top to bottom along the solid lines without arrow-heads. In the example of 
Figure 2.3 Lottery 11 is preferred over any other lottery, followed by Lotter¬ 
ies 3, 10, 6, 9, 7, 4 and 1. The arc pointing from Lottery 1 to 3 indicates a 
preference which violates the top-down order and creates many intransitivi¬ 
ties among the seven lotteries in this strong component. However, all these 
lotteries are preferred to Lottery 8. Finally, Lottery 8 is preferred over Lot¬ 
tery 5, followed by Lottery 2, and 12. Here the arc pointing from Lottery 12 
In this special case the three factors correspond to the decomposition of the tournament A into three 
strong components Aj, A», and Ag. Moreover, the coefficients of the three irreducible polynomials equal the 
number of directed cycles within the strong components. But we know from Theorem 2.2.5 and Proposi¬ 
tion 2.2.6 that both results do not hold for arbitrary tournaments.