tournament_min_rank_eq_zero_of_is_acyclic
An acyclic digraph has tournament minimum rank 0 (the zero matrix decycles it).
Statement
theorem tournament_min_rank_eq_zero_of_is_acyclic {V : Type*} [Fintype V] (D : Digraph V) (h : digraph_is_acyclic D) : tournament_min_rank D = 0
- Source
- Sanity lemma for tournament_min_rank (arXiv:2610.13798, Sec. 2.2).
- Verified
- 13 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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_flip_by_matrix_zeroFlipping by the zero matrix changes nothing.
- 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…
The proof, explained
The tournament minimum rank of a digraph D is defined as the infimum of the ranks of symmetric matrices over ℤ/2ℤ whose flip decycles D. Since D is already acyclic, flipping by the zero matrix leaves D unchanged. The zero matrix is symmetric and has rank 0, which witnesses that 0 belongs to the set of ranks, so the infimum is 0.
It suffices to show that 0 belongs to the set of ranks of symmetric decycling matrices for D.
The tournament minimum rank of D is defined as the infimum in ℕ of the ranks of symmetric matrices over ℤ/2ℤ that make D acyclic after flipping. By Nat.sInf_eq_zero.mpr, this infimum is 0 if 0 is an element of the set (or if the set is empty). Choosing the left alternative reduces the goal to showing that 0 is achievable.
uses
Nat.sInf_eq_zero.mprapply Nat.sInf_eq_zero.mpr left
0 belongs to the set of ranks, as witnessed by the zero matrix.
We provide the zero matrix M = 0 as the witness. It is symmetric by Matrix.isSymm_zero and has rank 0 by Matrix.rank_zero. Flipping D by the zero matrix leaves D unchanged by digraph_flip_by_matrix_zero, and D is already acyclic by the hypothesis h.
uses
Matrix.isSymm_zero,digraph_flip_by_matrix_zero,Matrix.rank_zeroexact ⟨0, Matrix.isSymm_zero, by rwa [digraph_flip_by_matrix_zero], Matrix.rank_zero⟩
Nat.sInf_eq_zero.mpr- For any set of natural numbers, if 0 belongs to the set or the set is empty, its infimum is 0.
Matrix.isSymm_zero- The zero matrix is symmetric.
digraph_flip_by_matrix_zero- Flipping a directed graph by the zero matrix leaves the graph unchanged.
Matrix.rank_zero- The rank of the zero matrix is 0.
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_min_rank_eq_zero_of_is_acyclic {V : Type*} [Fintype V] (D : Digraph V) (h : digraph_is_acyclic D) : tournament_min_rank D = 0 := by apply Nat.sInf_eq_zero.mpr left exact ⟨0, Matrix.isSymm_zero, by rwa [digraph_flip_by_matrix_zero], Matrix.rank_zero⟩