AFTD Auto-Formalizing Theoretical Domains

tournament_exists_decycling_matrix

theoremverified

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.

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

    lines 4–7

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

    lines 8–10

    uses Matrix.IsSymm.ext

      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]
  3. 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.

    line 11

    uses digraph_is_acyclic_of_rank

      · apply digraph_is_acyclic_of_rank _ (fun v => (e v : ℕ))
  4. 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)$.

    lines 12–17

        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
  5. 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)$.

    lines 18–24

        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)
  6. 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)$.

    lines 25–29

    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

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