AFTD Auto-Formalizing Theoretical Domains

tournament_min_rank_le_inversion_number

theoremverifiedformalization

For a finite tournament D: tmr(D) ≤ inv(D).

Statement

theorem tournament_min_rank_le_inversion_number (V : Type) [Fintype V] (D : Digraph V)
    (h : digraph_is_tournament D) :
    tournament_min_rank D ≤ digraph_inversion_number D
Formalizes
arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), inequality (1.2), quoting an earlier paper (the sum of the rank-one matrices 1_X 1_Xᵀ over a decycling family is a decycling matrix of rank at most the family size).
Verified
13 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • 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_inversion_numberThe inversion number inv(D): the least number p of vertex sets X₁, …, X_p whose successive inversions turn D into an acyclic digraph (0 by…
  • tournament_exists_family_length_eq_inversion_numberFor a finite tournament D, the inversion number is attained: some decycling family of D has exactly inv(D) sets.
  • digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
  • 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…
  • digraph_invertThe inversion of a vertex set X in a digraph D: the digraph obtained by reversing every arc with both endpoints in X and keeping every…
  • 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…

The proof, explained

To show that the tournament minimum rank tmr(D) is at most the inversion number inv(D), we take an optimal sequence of vertex subsets X₀, ..., X_{k-1} of length k = inv(D) whose sequential inversion makes D acyclic. We form the V × k vertex-subset incidence matrix A over ℤ/2 and its symmetric Gram matrix M = A Aᵀ. By induction, flipping edges of D according to M is equivalent to sequentially inverting along the subsets Xᵢ, producing an acyclic tournament. Consequently, tmr(D) ≤ rank(M) ≤ rank(A) ≤ k = inv(D).

  1. Obtain an optimal sequence of vertex subsets achieving the inversion number and define the incidence and rank-one matrices.

    By tournament_exists_family_length_eq_inversion_number, there exists a list Xs of k = inv(D) vertex subsets whose successive inversion leaves D acyclic. We define the V × k incidence matrix A where A x i = 1 if x ∈ Xs i and 0 otherwise, and for any set X ⊆ V, the rank-one outer product matrix N(X) where N(X) x y = 1 if both x, y ∈ X and 0 otherwise, working over ℤ/2.

    lines 4–9

    uses tournament_exists_family_length_eq_inversion_number

      classical
      obtain ⟨Xs, hXl, hXa⟩ := tournament_exists_family_length_eq_inversion_number V D h
      let A : {n : ℕ} → (Fin n → Set V) → Matrix V (Fin n) (ZMod 2) :=
        fun X x i => if x ∈ X i then 1 else 0
      let N : Set V → Matrix V V (ZMod 2) :=
        fun X x y => (if x ∈ X then 1 else 0) * (if y ∈ X then 1 else 0)
  2. Flipping a digraph by a symmetric matrix P and then by a matrix M is equivalent to flipping by P + M.

    After noting basic arithmetic in ℤ/2 (1 + 1 = 0, 0 ≠ 1, and every element is 0 or 1), we compare the adjacency conditions. Flipping by P swaps an edge (x, y) if P x y = 1, and flipping again by M swaps it if M x y = 1. Using the symmetry of P (P y x = P x y) and checking all four possible value pairs for (P x y, M x y) in {0, 1}², the composed flip agrees with flipping whenever (P + M) x y = 1.

    lines 10–20

    uses Matrix.add_apply

      have h11 : (1 : ZMod 2) + 1 = 0 := rfl
      have h01 : (0 : ZMod 2) ≠ 1 := by decide
      have two : ∀ a : ZMod 2, a = 0 ∨ a = 1 := by decide
      have flip_add : ∀ (E : Digraph V) (P M : Matrix V V (ZMod 2)), (∀ x y, P y x = P x y) →
          digraph_flip_by_matrix (digraph_flip_by_matrix E P) M =
            digraph_flip_by_matrix E (P + M) := by
        intro E P M hP
        ext x y
        simp only [digraph_flip_by_matrix, Matrix.add_apply, hP x y]
        rcases two (P x y) with ha | ha <;> rcases two (M x y) with hb | hb <;>
          simp [ha, hb, h11]
  3. Inverting a digraph along a subset X is equivalent to flipping edges by the matrix N(X).

    Inverting along X reverses an edge (x, y) if and only if both x ∈ X and y ∈ X. Since N(X) x y = 1 precisely when x, y ∈ X, this coincides with flipping edges by N(X), verified by a case analysis on whether x ∈ X and y ∈ X.

    lines 21–25

      have hN : ∀ (E : Digraph V) (X : Set V), digraph_invert E X = digraph_flip_by_matrix E (N X) := by
        intro E X
        ext x y
        simp only [digraph_flip_by_matrix, digraph_invert, N]
        by_cases hx : x ∈ X <;> by_cases hy : y ∈ X <;> simp [hx, hy]
  4. Flipping by the Gram matrix A(X) * A(X)ᵀ is equivalent to sequentially inverting the family of subsets X.

    By induction on the length n of the sequence X. For n = 0, A(X) * A(X)ᵀ is the zero matrix, which flips no edges, matching the empty sequence of inversions. For n + 1, the matrix product decomposes via Fin.sum_univ_succ into N(X 0) + A(X') * A(X')ᵀ, where X' is the tail of the sequence. Because N(X 0) is symmetric, flip_add shows that flipping by this sum equals flipping by N(X 0) followed by A(X') * A(X')ᵀ. By the induction hypothesis and hN, this matches inverting X 0 followed by inverting the remaining subsets.

    lines 26–43

    uses List.ofFn_succ, List.foldl_cons, Matrix.mul_apply, Matrix.add_apply, Matrix.transpose_apply, Fin.sum_univ_succ

      have key : ∀ (n : ℕ) (X : Fin n → Set V) (E : Digraph V),
          digraph_flip_by_matrix E (A X * (A X).transpose) = (List.ofFn X).foldl digraph_invert E := by
        intro n
        induction n with
        | zero =>
          intro X E
          ext x y
          simp [digraph_flip_by_matrix, Matrix.mul_apply]
        | succ n ih =>
          intro X E
          rw [List.ofFn_succ, List.foldl_cons, ← ih (fun i => X i.succ), hN, flip_add]
          · congr 1
            ext x y
            simp only [Matrix.mul_apply, Matrix.add_apply, Matrix.transpose_apply, Fin.sum_univ_succ]
            rfl
          · intro x y
            simp only [N]
            ring
  5. The Gram matrix M = A(Xs) * A(Xs)ᵀ is symmetric.

    By Matrix.IsSymm.ext, it suffices to show M j i = M i j. Using Matrix.mul_apply and Matrix.transpose_apply, the entry M i j is ∑ k, A i k * A j k. By commutativity of multiplication (mul_comm and Finset.sum_congr), this equals ∑ k, A j k * A i k = M j i.

    lines 44–48

    uses Matrix.IsSymm.ext, Matrix.mul_apply, Matrix.transpose_apply, Finset.sum_congr, mul_comm

      have hsymm : (A Xs.get * (A Xs.get).transpose).IsSymm := by
        apply Matrix.IsSymm.ext
        intro i j
        simp only [Matrix.mul_apply, Matrix.transpose_apply]
        exact Finset.sum_congr rfl (fun k _ => mul_comm _ _)
  6. Flipping D by M = A(Xs) * A(Xs)ᵀ produces an acyclic tournament.

    Using key to rewrite the matrix flip as sequential inversion and List.ofFn_get to identify the indexing function with the list Xs, flipping D by M yields the tournament obtained by sequentially inverting Xs. This digraph is acyclic by the choice of Xs (hypothesis hXa).

    lines 49–51

    uses List.ofFn_get

      have hac : digraph_is_acyclic (digraph_flip_by_matrix D (A Xs.get * (A Xs.get).transpose)) := by
        rw [key, List.ofFn_get]
        exact hXa
  7. The tournament minimum rank of D is at most its inversion number.

    Since M = A(Xs) * A(Xs)ᵀ is a symmetric matrix over ℤ/2 that flips D to an acyclic tournament, its rank is an upper bound for tournament_min_rank(D) by Nat.sInf_le. The rank of A * Aᵀ is at most the rank of A by Matrix.rank_mul_le_left, which in turn is bounded by the number of columns |Xs| by Matrix.rank_le_card_width. Because |Xs| = inv(D), we conclude tournament_min_rank(D) ≤ inv(D).

    lines 52–56

    uses Nat.sInf_le, Matrix.rank_mul_le_left, Matrix.rank_le_card_width

      calc tournament_min_rank D ≤ (A Xs.get * (A Xs.get).transpose).rank :=
            Nat.sInf_le ⟨_, hsymm, hac, rfl⟩
        _ ≤ (A Xs.get).rank := Matrix.rank_mul_le_left _ _
        _ ≤ Fintype.card (Fin Xs.length) := Matrix.rank_le_card_width _
        _ = digraph_inversion_number D := by simp [hXl]
tournament_exists_family_length_eq_inversion_number
Every finite tournament has a list of vertex subsets of length equal to its inversion number whose sequential inversion yields an acyclic tournament.
Matrix.add_apply
The (i, j)-th entry of the sum of two matrices is the sum of their (i, j)-th entries.
List.ofFn_succ
Converting a function on Fin (n + 1) to a list yields the value at 0 prepended to the list of the remaining values.
List.foldl_cons
Folding a function over a non-empty list a :: l applies the function to the accumulator and the head a, then folds over the tail l.
Matrix.mul_apply
The (i, k)-th entry of a matrix product M * N is the sum over j of M i j * N j k.
Matrix.transpose_apply
The (i, j)-th entry of the transpose of a matrix M is M j i.
Fin.sum_univ_succ
A sum over Fin (n + 1) splits into the term at index 0 plus the sum over the remaining n indices.
Matrix.IsSymm.ext
A square matrix is symmetric if A j i = A i j for all indices i and j.
Finset.sum_congr
Two sums over finite sets are equal if the sets are equal and the summands agree at each point.
mul_comm
Multiplication in a commutative magma is commutative: a * b = b * a.
List.ofFn_get
Reconstructing a list from its indexing function yields the original list.
Nat.sInf_le
The infimum of a set of natural numbers is less than or equal to any element in the set.
Matrix.rank_mul_le_left
The rank of a matrix product A * B is at most the rank of the left factor A.
Matrix.rank_le_card_width
The rank of an m × n matrix is at most its number of columns n.

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_le_inversion_number (V : Type) [Fintype V] (D : Digraph V)    (h : digraph_is_tournament D) :    tournament_min_rank D ≤ digraph_inversion_number D := by  classical  obtain ⟨Xs, hXl, hXa⟩ := tournament_exists_family_length_eq_inversion_number V D h  let A : {n : ℕ} → (Fin n → Set V) → Matrix V (Fin n) (ZMod 2) :=    fun X x i => if x ∈ X i then 1 else 0  let N : Set V → Matrix V V (ZMod 2) :=    fun X x y => (if x ∈ X then 1 else 0) * (if y ∈ X then 1 else 0)  have h11 : (1 : ZMod 2) + 1 = 0 := rfl  have h01 : (0 : ZMod 2) ≠ 1 := by decide  have two : ∀ a : ZMod 2, a = 0 ∨ a = 1 := by decide  have flip_add : ∀ (E : Digraph V) (P M : Matrix V V (ZMod 2)), (∀ x y, P y x = P x y) →      digraph_flip_by_matrix (digraph_flip_by_matrix E P) M =        digraph_flip_by_matrix E (P + M) := by    intro E P M hP    ext x y    simp only [digraph_flip_by_matrix, Matrix.add_apply, hP x y]    rcases two (P x y) with ha | ha <;> rcases two (M x y) with hb | hb <;>      simp [ha, hb, h11]  have hN : ∀ (E : Digraph V) (X : Set V), digraph_invert E X = digraph_flip_by_matrix E (N X) := by    intro E X    ext x y    simp only [digraph_flip_by_matrix, digraph_invert, N]    by_cases hx : x ∈ X <;> by_cases hy : y ∈ X <;> simp [hx, hy]  have key : ∀ (n : ℕ) (X : Fin n → Set V) (E : Digraph V),      digraph_flip_by_matrix E (A X * (A X).transpose) = (List.ofFn X).foldl digraph_invert E := by    intro n    induction n with    | zero =>      intro X E      ext x y      simp [digraph_flip_by_matrix, Matrix.mul_apply]    | succ n ih =>      intro X E      rw [List.ofFn_succ, List.foldl_cons, ← ih (fun i => X i.succ), hN, flip_add]      · congr 1        ext x y        simp only [Matrix.mul_apply, Matrix.add_apply, Matrix.transpose_apply, Fin.sum_univ_succ]        rfl      · intro x y        simp only [N]        ring  have hsymm : (A Xs.get * (A Xs.get).transpose).IsSymm := by    apply Matrix.IsSymm.ext    intro i j    simp only [Matrix.mul_apply, Matrix.transpose_apply]    exact Finset.sum_congr rfl (fun k _ => mul_comm _ _)  have hac : digraph_is_acyclic (digraph_flip_by_matrix D (A Xs.get * (A Xs.get).transpose)) := by    rw [key, List.ofFn_get]    exact hXa  calc tournament_min_rank D ≤ (A Xs.get * (A Xs.get).transpose).rank :=        Nat.sInf_le ⟨_, hsymm, hac, rfl⟩    _ ≤ (A Xs.get).rank := Matrix.rank_mul_le_left _ _    _ ≤ Fintype.card (Fin Xs.length) := Matrix.rank_le_card_width _    _ = digraph_inversion_number D := by simp [hXl]
See it in the graphDiscuss this resultChallenge it