tournament_min_rank_le_inversion_number
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).
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.
uses
tournament_exists_family_length_eq_inversion_numberclassical 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)
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.
uses
Matrix.add_applyhave 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]
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.
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]
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.
uses
List.ofFn_succ,List.foldl_cons,Matrix.mul_apply,Matrix.add_apply,Matrix.transpose_apply,Fin.sum_univ_succhave 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
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.
uses
Matrix.IsSymm.ext,Matrix.mul_apply,Matrix.transpose_apply,Finset.sum_congr,mul_commhave 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 _ _)
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).
uses
List.ofFn_gethave hac : digraph_is_acyclic (digraph_flip_by_matrix D (A Xs.get * (A Xs.get).transpose)) := by rw [key, List.ofFn_get] exact hXa
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).
uses
Nat.sInf_le,Matrix.rank_mul_le_left,Matrix.rank_le_card_widthcalc 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.
- In Lean, the equivalence between inverting along a family of subsets and flipping edges according to the Gram matrix A Aᵀ over ℤ/2 is established by induction on the length of the list, decomposing A Aᵀ into the sum of outer products of the column indicator vectors.
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_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]