2.2. DECOMPOSITION INTO STRONG COMPONENTS 
45 
Lemma 2.2.13 Let A be the adjacency matrix of a tournament. Then the 
following two statements are equivalent. 
A is acyclic 
(1) 
(ii) (42) +A=0 
Note that in this context an acyclic tournament is equivalent to a transitive 
tournament without directed cycles. 
Proof. That (i) implies (ii) is clear. Now assume that A has no 3-dicycles 
but contains an n-dicycle. If a; — a; — a is a directed walk within the n- 
dicycle then there is an arc a;— — a because A represents a tournament, 
hence there is a directed cycle of length n - 1. By induction a 3-dicycle 
remains and a contradiction is reached. Consequently, (ii) implies (i). 
This result does not ensure that a tournament is acyclic or without in¬ 
consistent choices if arcs from 3-dicycles in a tournament are successively 
removed until no 3-dicycle remains. This is illustrated in Figure 2.2. If the 3- 
dicycles in Tournament A are eliminated by removing arcs 1 — 3 and 2 — 4 
from Tournament A then the subdigraph is acyclic. If the same arcs are re¬ 
moved from Tournament B then the 4-dicycle 1 — 4 — 3 — 2 — 1 remains. 
In this case the removal of arc 3 — 2 which belongs to both 3-dicycles and 
B. 
A. 
25 
24 
Figure 2.2: Tournament A differs from B by a single arc. 
the 4-dicycle in Tournament B results in acyclic digraphs. 
It is conjectured that an iterative algorithm which takes into account the 
number of intersecting k-dicycles for each arc of a digraph eventually leads to 
an acyclic digraph with a minimal set of removed arcs. For example, consider