tournament_exists_decycling_matrix
Every finite tournament has a symmetric decycling matrix over F₂ (so its minimum rank is attained).
Statement
theorem tournament_exists_decycling_matrix (V : Type) [Fintype V] (D : Digraph V) (h : digraph_is_tournament D) : ∃ M : Matrix V V (ZMod 2), M.IsSymm ∧ digraph_is_acyclic (digraph_flip_by_matrix D M)
- Source
- Helper for the bounds on tournament minimum rank in arXiv:2610.13798, Sec. 2.2: the minimum defining tmr(D) is over a nonempty set.
- Verified
- 13 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- tournament_min_rankThe tournament minimum rank tmr(D): the least F₂-rank of a symmetric matrix M over F₂ that decycles D, i.e. such that reversing every arc…
- digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
- digraph_is_acyclic_of_rankA digraph with a numbering of the vertices that increases along every arc is acyclic.
- digraph_is_acyclicA digraph is acyclic when it has no directed cycle: no vertex reaches itself by a nonempty directed walk. For a tournament this means it…
- digraph_flip_by_matrixGiven a digraph D and a (symmetric) matrix M over F₂ indexed by its vertices, the digraph obtained by reversing every arc uv with M_uv = 1…
- Used by 1
- tournament_min_rank_le_dijoinFor finite tournaments D₁, D₂: tmr(D₁ → D₂) ≥ max(tmr(D₁), tmr(D₂)) (hence ≥ (tmr(D₁) + tmr(D₂))/2), because the principal submatrix of a…
The proof, explained
The proof chooses an arbitrary total ordering $e : V \simeq \{0, \dots, |V|-1\}$ on the vertices and defines a symmetric matrix $M$ over $\mathbb{F}_2$ whose entries are $1$ precisely for pairs whose directed edge in the tournament points backward according to $e$. Flipping these edges reverses all backward edges and keeps all forward edges, ensuring that every edge in the resulting digraph points from a lower index to a higher index. Since the rank function $v \mapsto e(v)$ strictly increases along every directed edge, the flipped graph is acyclic.
Fix an ordering on the vertices and define the candidate decycling matrix $M$.
Using the finiteness of the vertex set $V$, we choose a bijection $e : V \simeq \{0, \dots, |V|-1\}$ to totally order the vertices. We define a matrix $M \in \operatorname{Mat}_{V \times V}(\mathbb{F}_2)$ by setting $M_{x, y} = 1$ whenever the edge between $x$ and $y$ is oriented backward relative to $e$ (that is, $(x \to y \wedge e(y) < e(x))$ or $(y \to x \wedge e(x) < e(y))$), and $M_{x, y} = 0$ otherwise.
classical let e : V ≃ Fin (Fintype.card V) := Fintype.equivFin V let M : Matrix V V (ZMod 2) := fun x y => if (D.Adj x y ∧ e y < e x) ∨ (D.Adj y x ∧ e x < e y) then 1 else 0
The matrix $M$ is symmetric: $M_{j, i} = M_{i, j}$ for all $i, j \in V$.
By `Matrix.IsSymm.ext`, symmetry reduces to showing $M_{j, i} = M_{i, j}$. The condition defining $M_{x, y} = 1$ is invariant under swapping $x$ and $y$ because swapping them merely exchanges the two disjunctive clauses. A case analysis on the truth values of the two clauses confirms that $M_{j, i} = M_{i, j}$ in all cases.
uses
Matrix.IsSymm.extrefine ⟨M, Matrix.IsSymm.ext (fun i j => ?_), ?_⟩ · by_cases h1 : D.Adj i j ∧ e j < e i <;> by_cases h2 : D.Adj j i ∧ e i < e j <;> simp [M, h1, h2]
To show the flipped graph is acyclic, it suffices to prove that every directed edge strictly increases the index $e$.
We apply `digraph_is_acyclic_of_rank` with the rank function $v \mapsto e(v) \in \mathbb{N}$. In any directed graph, the existence of a ranking function into $\mathbb{N}$ that strictly increases along every directed edge guarantees that the graph has no directed cycles.
uses
digraph_is_acyclic_of_rank· apply digraph_is_acyclic_of_rank _ (fun v => (e v : ℕ))
Any directed edge $(x, y)$ in the flipped graph has distinct endpoints $x \ne y$, so $e(x) \ne e(y)$.
Suppose $(x, y)$ is a directed edge in the flipped graph. If $x = y$, then whether the edge was flipped or preserved, $D$ would have to contain a self-loop $x \to x$, which contradicts the tournament property that $D$ is loopless. Thus $x \ne y$. Since $e$ is injective, $e(x) \ne e(y)$, so to show $e(x) < e(y)$ it will suffice to establish $e(x) \le e(y)$.
intro x y hxy have hxy' : x ≠ y := by rintro rfl rcases hxy with ⟨_, h'⟩ | ⟨_, h'⟩ <;> exact h.1 x h' have hne : e x ≠ e y := fun h' => hxy' (e.injective h') suffices hlt : e x < e y by exact hlt
If $(x, y)$ was formed by flipping an original edge, then $e(x) < e(y)$.
An edge $(x, y)$ is flipped if $M_{x, y} = 1$ and the original tournament had an edge $y \to x$. Since $M_{x, y} = 1$, the definition of $M$ implies that either ($x \to y \wedge e(y) < e(x)$) or ($y \to x \wedge e(x) < e(y)$). Because $D$ is a tournament and $y \to x$ already holds for $x \ne y$, we cannot also have $x \to y$. This eliminates the first case, leaving the second, which directly gives $e(x) < e(y)$.
rcases hxy with ⟨hM, hA⟩ | ⟨hM, hA⟩ · simp only [M] at hM split_ifs at hM with hc · rcases hc with ⟨h1, _⟩ | ⟨_, h2⟩ · exact absurd hA ((h.2 x y hxy').1 h1) · exact h2 · exact absurd hM (by decide)
If $(x, y)$ was preserved from the original tournament, then $e(x) < e(y)$.
An edge $(x, y)$ is preserved if $M_{x, y} \ne 1$ (so $M_{x, y} = 0$) and the original tournament had an edge $x \to y$. Since $M_{x, y} \ne 1$, the defining disjunction of $M_{x, y} = 1$ is false; negating it implies that $x \to y$ forces $e(x) \le e(y)$. Since $x \to y$ holds, we obtain $e(x) \le e(y)$. Combining this with $e(x) \ne e(y)$ via `lt_of_le_of_ne` yields $e(x) < e(y)$.
uses
lt_of_le_of_ne· simp only [M] at hM split_ifs at hM with hc · exact absurd rfl hM · push_neg at hc exact lt_of_le_of_ne (hc.1 hA) hne
Matrix.IsSymm.ext- A square matrix is symmetric if $A_{j, i} = A_{i, j}$ for all indices $i$ and $j$.
digraph_is_acyclic_of_rank- A directed graph is acyclic if there exists a ranking function $f : V \to \mathbb{N}$ that strictly increases along every directed edge.
lt_of_le_of_ne- In a partial order, if $a \le b$ and $a \ne b$, then $a < b$.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem tournament_exists_decycling_matrix (V : Type) [Fintype V] (D : Digraph V) (h : digraph_is_tournament D) : ∃ M : Matrix V V (ZMod 2), M.IsSymm ∧ digraph_is_acyclic (digraph_flip_by_matrix D M) := by classical let e : V ≃ Fin (Fintype.card V) := Fintype.equivFin V let M : Matrix V V (ZMod 2) := fun x y => if (D.Adj x y ∧ e y < e x) ∨ (D.Adj y x ∧ e x < e y) then 1 else 0 refine ⟨M, Matrix.IsSymm.ext (fun i j => ?_), ?_⟩ · by_cases h1 : D.Adj i j ∧ e j < e i <;> by_cases h2 : D.Adj j i ∧ e i < e j <;> simp [M, h1, h2] · apply digraph_is_acyclic_of_rank _ (fun v => (e v : ℕ)) intro x y hxy have hxy' : x ≠ y := by rintro rfl rcases hxy with ⟨_, h'⟩ | ⟨_, h'⟩ <;> exact h.1 x h' have hne : e x ≠ e y := fun h' => hxy' (e.injective h') suffices hlt : e x < e y by exact hlt rcases hxy with ⟨hM, hA⟩ | ⟨hM, hA⟩ · simp only [M] at hM split_ifs at hM with hc · rcases hc with ⟨h1, _⟩ | ⟨_, h2⟩ · exact absurd hA ((h.2 x y hxy').1 h1) · exact h2 · exact absurd hM (by decide) · simp only [M] at hM split_ifs at hM with hc · exact absurd rfl hM · push_neg at hc exact lt_of_le_of_ne (hc.1 hA) hne