AFTD Auto-Formalizing Theoretical Domains

tournament_min_rank_eq_zero_of_is_acyclic

theoremverified

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.

  1. 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.

    lines 3–4

    uses Nat.sInf_eq_zero.mpr

      apply Nat.sInf_eq_zero.mpr
      left
  2. 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.

    line 5

    uses Matrix.isSymm_zero, digraph_flip_by_matrix_zero, Matrix.rank_zero

      exact ⟨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

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⟩
See it in the graphDiscuss this resultChallenge it