tournament_min_rank_le_dijoin
For finite tournaments D₁, D₂: tmr(D₁ → D₂) ≥ max(tmr(D₁), tmr(D₂)) (hence ≥ (tmr(D₁) + tmr(D₂))/2), because the principal submatrix of a decycling matrix on an induced subtournament decycles it and has no larger rank.
Statement
theorem tournament_min_rank_le_dijoin (V W : Type) [Fintype V] [Fintype W] (D₁ : Digraph V) (D₂ : Digraph W) (h₁ : digraph_is_tournament D₁) (h₂ : digraph_is_tournament D₂) : max (tournament_min_rank D₁) (tournament_min_rank D₂) ≤ tournament_min_rank (digraph_dijoin D₁ D₂)
- Formalizes
- arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Observation 2.3 (stated here for the two sides of a dijoin; the average bound follows from the max).
- 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_dijoinThe dijoin D₁ → D₂: disjoint copies of D₁ and D₂ together with every arc from a vertex of D₁ to a vertex of D₂.
- tournament_exists_decycling_matrixEvery finite tournament has a symmetric decycling matrix over F₂ (so its minimum rank is attained).
- digraph_dijoin_is_tournamentThe dijoin of two tournaments is a tournament.
- 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…
- digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
The proof, explained
To show that tournament_min_rank(D₁ → D₂) ≥ max(tournament_min_rank(D₁), tournament_min_rank(D₂)), we first select an optimal symmetric decycling matrix M for the dijoin D₁ → D₂. We then establish that any induced subtournament D inherits a decycling matrix by restricting M to the corresponding principal submatrix: any directed cycle in the flipped induced subgraph would push forward to a directed cycle in the flipped dijoin, which is impossible since M decycled the dijoin. Since the rank of a principal submatrix is at most that of the full matrix, tournament_min_rank(D) is bounded by that of the dijoin; applying this to the induced subtournaments D₁ and D₂ yields the result.
There exists an optimal symmetric decycling matrix M for the dijoin D₁ → D₂, whose rank equals tournament_min_rank(D₁ → D₂).
Because the dijoin of two tournaments is a tournament (digraph_dijoin_is_tournament), it admits a symmetric decycling matrix M₀ by tournament_exists_decycling_matrix. Thus the set of ranks of symmetric decycling matrices for the dijoin is non-empty (hne). By Nat.sInf_mem, this non-empty set of natural numbers contains its infimum, providing an optimal symmetric decycling matrix M with rank equal to tournament_min_rank(D₁ → D₂).
uses
tournament_exists_decycling_matrix,digraph_dijoin_is_tournament,Nat.sInf_memobtain ⟨M0, hM0s, hM0a⟩ := tournament_exists_decycling_matrix (V ⊕ W) _ (digraph_dijoin_is_tournament D₁ D₂ h₁ h₂) have hne : Set.Nonempty {r | ∃ M : Matrix (V ⊕ W) (V ⊕ W) (ZMod 2), M.IsSymm ∧ digraph_is_acyclic (digraph_flip_by_matrix (digraph_dijoin D₁ D₂) M) ∧ M.rank = r} := ⟨_, M0, hM0s, hM0a, rfl⟩ obtain ⟨M, hMs, hMa, hMr⟩ := Nat.sInf_mem hne
For any induced subgraph D on vertex set U under an embedding f : U → V ⊕ W, edges in D flipped by the principal submatrix M[f, f] map to edges in D₁ → D₂ flipped by M.
We begin proving the general lemma lower for an arbitrary induced subgraph D. Unfolding the definition of edge-flipping by a matrix, an edge between x and y in D flipped by M[f, f] corresponds to the matrix entry (M[f, f])_{x, y} and adjacency in D. By Matrix.submatrix_apply, (M[f, f])_{x, y} = M_{f(x), f(y)}, and by the induced subgraph hypothesis hD, adjacency in D matches adjacency in the dijoin. Thus the edge condition in the flipped subgraph matches the edge condition between f(x) and f(y) in the flipped dijoin.
uses
Matrix.submatrix_applyhave lower : ∀ (U : Type) [Fintype U] (f : U → V ⊕ W) (D : Digraph U), (∀ a b, (digraph_dijoin D₁ D₂).Adj (f a) (f b) ↔ D.Adj a b) → tournament_min_rank D ≤ tournament_min_rank (digraph_dijoin D₁ D₂) := by intro U _ f D hD have step : ∀ x y, (digraph_flip_by_matrix D (M.submatrix f f)).Adj x y → (digraph_flip_by_matrix (digraph_dijoin D₁ D₂) M).Adj (f x) (f y) := by intro x y hxy simp only [digraph_flip_by_matrix, Matrix.submatrix_apply, hD] at hxy ⊢ exact hxy
The graph D flipped by the principal submatrix M[f, f] is acyclic.
Suppose for contradiction that D flipped by M[f, f] contains a directed cycle from a vertex a to itself. By induction on path length, the previous edge-mapping step shows that any directed path in the flipped subgraph maps to a directed path in the flipped dijoin. Thus f(a) would have a directed cycle to itself in the dijoin flipped by M, contradicting the fact that M decycles the dijoin (hMa).
have hac : digraph_is_acyclic (digraph_flip_by_matrix D (M.submatrix f f)) := by intro a ha apply hMa (f a) have key : ∀ x y, Relation.TransGen (digraph_flip_by_matrix D (M.submatrix f f)).Adj x y → Relation.TransGen (digraph_flip_by_matrix (digraph_dijoin D₁ D₂) M).Adj (f x) (f y) := by intro x y hxy induction hxy with | single h => exact .single (step _ _ h) | tail _ h ih => exact .tail ih (step _ _ h) exact key a a ha
Any induced subgraph D of the dijoin satisfies tournament_min_rank(D) ≤ tournament_min_rank(D₁ → D₂).
Because M is symmetric, its principal submatrix M[f, f] is symmetric, and by the previous step it decycles D. Thus the rank of M[f, f] belongs to the set of decycling ranks for D, giving tournament_min_rank(D) ≤ rank(M[f, f]) by Nat.sInf_le. Furthermore, the rank of a submatrix cannot exceed the rank of the ambient matrix (Matrix.rank_submatrix_le), which equals tournament_min_rank(D₁ → D₂).
uses
Nat.sInf_le,Matrix.rank_submatrix_lecalc tournament_min_rank D ≤ (M.submatrix f f).rank := Nat.sInf_le ⟨M.submatrix f f, hMs.submatrix f, hac, rfl⟩ _ ≤ M.rank := Matrix.rank_submatrix_le _ _ _ _ = _ := hMr
max(tournament_min_rank(D₁), tournament_min_rank(D₂)) ≤ tournament_min_rank(D₁ → D₂).
By max_le, it suffices to prove the bound for D₁ and D₂ separately. Since D₁ and D₂ are the canonically induced subgraphs of the dijoin on the left and right summands via Sum.inl and Sum.inr (both equivalences hold reflexively by Iff.rfl), applying the induced subgraph lemma lower to each case completes the proof.
uses
max_le,Sum.inl,Sum.inr,Iff.rflapply max_le · exact lower V Sum.inl D₁ (fun a b => Iff.rfl) · exact lower W Sum.inr D₂ (fun a b => Iff.rfl)
tournament_exists_decycling_matrix- Every finite tournament admits a symmetric decycling matrix over ℤ/2ℤ whose edge-flip yields an acyclic digraph.
digraph_dijoin_is_tournament- The directed join (dijoin) of two tournaments is itself a tournament.
Nat.sInf_mem- Any non-empty set of natural numbers contains its infimum (minimum).
Matrix.submatrix_apply- The entry of a submatrix at indices (i, j) is the entry of the ambient matrix at (r(i), c(j)).
Nat.sInf_le- Any member of a set of natural numbers is greater than or equal to the infimum of the set.
Matrix.rank_submatrix_le- The rank of any submatrix is at most the rank of the original matrix.
max_le- If a ≤ c and b ≤ c, then max(a, b) ≤ c.
Sum.inl- The canonical inclusion of the first component into a disjoint sum type V ⊕ W.
Sum.inr- The canonical inclusion of the second component into a disjoint sum type V ⊕ W.
Iff.rfl- Reflexivity of logical equivalence: P ↔ P for any proposition P.
- On paper, one immediately chooses a minimum-rank decycling matrix for the dijoin. In Lean, because tournament_min_rank is defined as the infimum (sInf) of ranks of symmetric decycling matrices, the proof must first demonstrate that this set of ranks is non-empty (via tournament_exists_decycling_matrix) before selecting a minimizing matrix using Nat.sInf_mem.
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_dijoin (V W : Type) [Fintype V] [Fintype W] (D₁ : Digraph V) (D₂ : Digraph W) (h₁ : digraph_is_tournament D₁) (h₂ : digraph_is_tournament D₂) : max (tournament_min_rank D₁) (tournament_min_rank D₂) ≤ tournament_min_rank (digraph_dijoin D₁ D₂) := by obtain ⟨M0, hM0s, hM0a⟩ := tournament_exists_decycling_matrix (V ⊕ W) _ (digraph_dijoin_is_tournament D₁ D₂ h₁ h₂) have hne : Set.Nonempty {r | ∃ M : Matrix (V ⊕ W) (V ⊕ W) (ZMod 2), M.IsSymm ∧ digraph_is_acyclic (digraph_flip_by_matrix (digraph_dijoin D₁ D₂) M) ∧ M.rank = r} := ⟨_, M0, hM0s, hM0a, rfl⟩ obtain ⟨M, hMs, hMa, hMr⟩ := Nat.sInf_mem hne have lower : ∀ (U : Type) [Fintype U] (f : U → V ⊕ W) (D : Digraph U), (∀ a b, (digraph_dijoin D₁ D₂).Adj (f a) (f b) ↔ D.Adj a b) → tournament_min_rank D ≤ tournament_min_rank (digraph_dijoin D₁ D₂) := by intro U _ f D hD have step : ∀ x y, (digraph_flip_by_matrix D (M.submatrix f f)).Adj x y → (digraph_flip_by_matrix (digraph_dijoin D₁ D₂) M).Adj (f x) (f y) := by intro x y hxy simp only [digraph_flip_by_matrix, Matrix.submatrix_apply, hD] at hxy ⊢ exact hxy have hac : digraph_is_acyclic (digraph_flip_by_matrix D (M.submatrix f f)) := by intro a ha apply hMa (f a) have key : ∀ x y, Relation.TransGen (digraph_flip_by_matrix D (M.submatrix f f)).Adj x y → Relation.TransGen (digraph_flip_by_matrix (digraph_dijoin D₁ D₂) M).Adj (f x) (f y) := by intro x y hxy induction hxy with | single h => exact .single (step _ _ h) | tail _ h ih => exact .tail ih (step _ _ h) exact key a a ha calc tournament_min_rank D ≤ (M.submatrix f f).rank := Nat.sInf_le ⟨M.submatrix f f, hMs.submatrix f, hac, rfl⟩ _ ≤ M.rank := Matrix.rank_submatrix_le _ _ _ _ = _ := hMr apply max_le · exact lower V Sum.inl D₁ (fun a b => Iff.rfl) · exact lower W Sum.inr D₂ (fun a b => Iff.rfl)