44 
CHAPTER 2. THEORY 
mial y is computed for each irreducible submatrix Aj,..., A, using single 
indeterminates. According to Proposition 2.2.11 the resulting polynomials 
can be written in a sum which contains equivalent information to the poly¬ 
nomial y(x....,.). Compared to an implementation of the polynomial 
% in n indeterminates this technique reduces the computational complexity 
and size of the suggested polynomial expression and determines the number 
of k-dicycles. 
2.2.2 Critical Arcs in Tournaments 
So far we have established a general algebraic decomposition which breaks 
down a digraph (tournament) into subdigraphs (subtournaments) on the ba¬ 
sis of its dicycles. To take this approach a step further, it appears promising 
to explore which arcs are particularly responsible or critical for dicycles. This 
question leads to a fundamental optimization problem. The following discus¬ 
sion is mostly restricted to tournaments. 
The following proposition suggests how to perform simple matrix opera¬ 
tions on an adjacency matrix to find the number of 3-dicycles intersecting in 
each arc. 
Proposition 2.2.12 Let A E M be the adjacency matrix of a directed graph 
be the matrix 
without loops. Let R = r 
RJ = A?AT 
where * denotes the Hadamard product. Then each entry in Ry records the 
number of times arc a;; belongs to a directed cycle of length 3. 
Proof. The Hadamard product is defined as A*B = a,b for (1 i,j 
n). A2 records all directed walks of length 2 from a; to a;. The transposed 
matrix of the Hadamard product between A2 and A', has entry r; » 0 if 
there is an arc a; — a; completing r:; directed 3-cycles. Consequently, arc 
D 
a; belongs to r;; different 3-dicycles. 
Note that this result does not hold for multigraphs where 2-dicycles and loops 
are allowed. However, the matrix 
RT =A-1 AT 
(2.10) 
for 3 % k § 5 identifies k-dicycles in a tournament and R+ = A*A can be 
used to determine preference reversals between pair comparisons.