tournament_min_rank_dijoin_le_of_symm_inv
Let B be an invertible symmetric n × n matrix over F₂, L the lower triangular all-ones matrix, and A = L B⁻¹ Lᵀ. Then the tournaments D₁ = T(A) and D₂ = T(B) satisfy tmr(D₁ → D₂) ≤ n.
Statement
theorem tournament_min_rank_dijoin_le_of_symm_inv (n : ℕ) (B : Matrix (Fin n) (Fin n) (ZMod 2))
(hB : B.IsSymm) (hdet : IsUnit B.det) :
tournament_min_rank (digraph_dijoin
(tournament_of_symm_matrix (lower_ones_matrix n * B⁻¹ * (lower_ones_matrix n).transpose))
(tournament_of_symm_matrix B)) ≤ n- Formalizes
- arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Proposition 3.1. Stated here is the bound tmr(T(A) → T(B)) ≤ n; the proposition's remark that A is again invertible symmetric is not part of the statement (its symmetry is proved inside the proof).
- 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_of_symm_matrixThe tournament T(G) of a symmetric n × n matrix G over F₂, on vertices 1, …, n: for i < j the arc goes i → j if G_ij = 0 and j → i if G_ij…
- lower_ones_matrixThe n × n lower triangular matrix L over F₂ with all entries on and below the diagonal equal to 1: L_ij = 1 iff j ≤ i.
- 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_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…
The proof, explained
To bound the tournament minimum rank of the dijoin T(A) → T(B) by n, we construct a 2n × 2n symmetric block matrix M over 𝔽₂ whose blocks are A = L B⁻¹ Lᵀ, L, Lᵀ, and B. We show that flipping the dijoin along M yields an acyclic tournament using an explicit potential function that assigns odd values 2i + 1 to vertices in T(A) and even values 2j to vertices in T(B). Finally, factoring M as P B Pᵀ for a 2n × n matrix P bounds the rank of M by n, which upper bounds the minimum rank.
The field 𝔽₂ has only two elements (0 and 1), and the inverse matrix B⁻¹ is symmetric.
Every element of ℤ/2ℤ is decided to be either 0 or 1. Since B is symmetric and invertible, its inverse B⁻¹ is also symmetric because transposition commutes with matrix inversion for invertible matrices.
uses
Matrix.transpose_nonsing_invhave two : ∀ a : ZMod 2, a = 0 ∨ a = 1 := by decide have hBinvT : (B⁻¹).transpose = B⁻¹ := by rw [Matrix.transpose_nonsing_inv, hB.eq]
For any symmetric matrix G, flipping the tournament T(G) by G directs all edges towards larger indices: any arc i → j in the flipped graph satisfies i < j.
By symmetry, G j i = G i j. By definition, T(G) has an arc i → j if either i < j with G i j = 0, or j < i with G j i = 1. Flipping T(G) by G keeps or reverses each edge depending on whether G i j = 1 or G i j ≠ 1. In both cases (G i j = 0 and G i j = 1), the condition simplifies directly to i < j.
uses
congrFun,Matrix.transpose_applyhave diag : ∀ G : Matrix (Fin n) (Fin n) (ZMod 2), G.IsSymm → ∀ i j : Fin n, (G i j = 1 ∧ (tournament_of_symm_matrix G).Adj j i) ∨ (G i j ≠ 1 ∧ (tournament_of_symm_matrix G).Adj i j) → (i : ℕ) < j := by intro G hG i j h have hs : G j i = G i j := by have := congrFun (congrFun hG.eq i) j simpa [Matrix.transpose_apply] using this simp only [tournament_of_symm_matrix, hs] at h rcases two (G i j) with h0 | h0 <;> simp [h0] at h <;> exact h
For any symmetric matrix A, flipping the dijoin tournament T(A) → T(B) by the block matrix M = [A, L; Lᵀ, B] produces an acyclic directed graph.
We show acyclicity by exhibiting a ranking function f strictly increasing along every edge of the flipped graph, mapping inl i to 2i + 1 and inr j to 2j. We analyze an edge x → y in the flipped graph by cases on where x and y lie: 1. Both in T(A): the edge is in the flipped T(A), so i < j by the diagonal block property, which implies 2i + 1 < 2j + 1. 2. x in T(A) and y in T(B): the dijoin contains no reverse edges from inr to inl, so this edge must be an unflipped forward edge with matrix entry L i j ≠ 1. By definition of L, this requires ¬(j ≤ i), so i < j, which yields 2i + 1 < 2j. 3. x in T(B) and y in T(A): the dijoin has no edges from inr to inl, so this edge must arise from flipping an existing forward dijoin edge from inl to inr with matrix entry Lᵀ i j = L j i = 1. By definition of L, this requires i ≤ j, which gives 2i < 2j + 1. 4. Both in T(B): the edge is in the flipped T(B), so i < j by the diagonal block property, which implies 2i < 2j. In every case, f(x) < f(y), so the flipped graph is acyclic.
uses
digraph_is_acyclic_of_rank,Sum.elim_inl,not_le,Sum.elim_inrhave hdec : ∀ A : Matrix (Fin n) (Fin n) (ZMod 2), A.IsSymm → digraph_is_acyclic (digraph_flip_by_matrix (digraph_dijoin (tournament_of_symm_matrix A) (tournament_of_symm_matrix B)) (Matrix.fromBlocks A (lower_ones_matrix n) (lower_ones_matrix n).transpose B)) := by intro A hA apply digraph_is_acyclic_of_rank _ (Sum.elim (fun i : Fin n => 2 * (i : ℕ) + 1) (fun j : Fin n => 2 * (j : ℕ))) intro x y hxy rcases x with i | i <;> rcases y with j | j · have := diag A hA i j hxy simp only [Sum.elim_inl] omega · rcases hxy with ⟨_, h⟩ | ⟨h, _⟩ · exact h.elim · have hji : ¬ j ≤ i := fun hji => h (by simp [Matrix.fromBlocks, lower_ones_matrix, hji]) have hij : (i : ℕ) < j := by rw [not_le] at hji; exact hji simp only [Sum.elim_inl, Sum.elim_inr] omega · rcases hxy with ⟨h, _⟩ | ⟨_, h⟩ · have hij : i ≤ j := by by_contra hc simp [Matrix.fromBlocks, lower_ones_matrix, hc] at h have hij' : (i : ℕ) ≤ j := hij simp only [Sum.elim_inl, Sum.elim_inr] omega · exact h.elim · have := diag B hB i j hxy simp only [Sum.elim_inr] omega
For any matrix L, the block matrix [L B⁻¹ Lᵀ, L; Lᵀ, B] has rank at most n.
The block matrix factors as P * B * Pᵀ, where P = [L B⁻¹; I] is the 2n × n matrix obtained by stacking L B⁻¹ above the identity matrix I. Expanding the block multiplication and using B⁻¹ * B = I, B * B⁻¹ = I, and (B⁻¹)ᵀ = B⁻¹ verifies that the four blocks match. The rank of P * B * Pᵀ is bounded by the rank of P, and since P has width n, its rank is at most n.
uses
Matrix.fromRows_mul,Matrix.transpose_fromRows,Matrix.fromRows_mul_fromCols,Matrix.mul_assoc,Matrix.nonsing_inv_mul,Matrix.mul_one,Matrix.transpose_mul,Matrix.transpose_one,Matrix.one_mul,Matrix.mul_nonsing_inv,Matrix.rank_mul_le_left,Matrix.rank_le_card_width,Fintype.card_finhave hrank : ∀ L : Matrix (Fin n) (Fin n) (ZMod 2), (Matrix.fromBlocks (L * B⁻¹ * L.transpose) L L.transpose B).rank ≤ n := by intro L have hMP : Matrix.fromBlocks (L * B⁻¹ * L.transpose) L L.transpose B = Matrix.fromRows (L * B⁻¹) 1 * B * (Matrix.fromRows (L * B⁻¹) 1).transpose := by rw [Matrix.fromRows_mul, Matrix.transpose_fromRows, Matrix.fromRows_mul_fromCols] congr 1 · rw [Matrix.mul_assoc L B⁻¹ B, Matrix.nonsing_inv_mul B hdet, Matrix.mul_one, Matrix.transpose_mul, hBinvT, Matrix.mul_assoc] · rw [Matrix.transpose_one, Matrix.mul_one, Matrix.mul_assoc, Matrix.nonsing_inv_mul B hdet, Matrix.mul_one] · rw [Matrix.one_mul, Matrix.transpose_mul, hBinvT, ← Matrix.mul_assoc, Matrix.mul_nonsing_inv B hdet, Matrix.one_mul] · rw [Matrix.one_mul, Matrix.transpose_one, Matrix.mul_one] rw [hMP] calc _ ≤ (Matrix.fromRows (L * B⁻¹) 1 * B).rank := Matrix.rank_mul_le_left _ _ _ ≤ (Matrix.fromRows (L * B⁻¹) (1 : Matrix (Fin n) (Fin n) (ZMod 2))).rank := Matrix.rank_mul_le_left _ _ _ ≤ Fintype.card (Fin n) := Matrix.rank_le_card_width _ _ = n := Fintype.card_fin n
The block matrix M = [L B⁻¹ Lᵀ, L; Lᵀ, B] is symmetric, certifying that the tournament minimum rank of the dijoin is at most n.
The matrix A = L B⁻¹ Lᵀ is symmetric because Aᵀ = (Lᵀ)ᵀ (B⁻¹)ᵀ Lᵀ = L B⁻¹ Lᵀ = A. Therefore, the block matrix M is symmetric because its diagonal blocks A and B are symmetric and its off-diagonal blocks are mutual transposes. Since M is symmetric and flips the dijoin tournament into an acyclic graph, its rank belongs to the set whose infimum defines the tournament minimum rank. Because the rank of M is at most n, the infimum is at most n as well.
uses
Matrix.transpose_mul,Matrix.transpose_transpose,Matrix.mul_assoc,Matrix.IsSymm.fromBlocks,le_trans,Nat.sInf_lehave hAs : (lower_ones_matrix n * B⁻¹ * (lower_ones_matrix n).transpose).IsSymm := by unfold Matrix.IsSymm rw [Matrix.transpose_mul, Matrix.transpose_mul, Matrix.transpose_transpose, hBinvT, Matrix.mul_assoc] have hMs : (Matrix.fromBlocks (lower_ones_matrix n * B⁻¹ * (lower_ones_matrix n).transpose) (lower_ones_matrix n) (lower_ones_matrix n).transpose B).IsSymm := Matrix.IsSymm.fromBlocks hAs rfl hB exact le_trans (Nat.sInf_le ⟨_, hMs, hdec _ hAs, rfl⟩) (hrank _)
Fintype.card_fin- The number of elements in Fin n is n.
Matrix.IsSymm.fromBlocks- A 2 × 2 block matrix is symmetric if its diagonal blocks are symmetric and each off-diagonal block is the transpose of the other.
Matrix.fromRows_mul_fromCols- Multiplying a column of two blocks by a row of two blocks results in the corresponding 2 × 2 block matrix of products.
Matrix.fromRows_mul- Multiplying a two-row block matrix by a matrix on the right distributes to each block row.
Matrix.mul_assoc- Matrix multiplication is associative: (L * M) * N = L * (M * N).
Matrix.mul_nonsing_inv- Multiplying an invertible matrix on the right by its inverse gives the identity matrix.
Matrix.mul_one- Multiplying any matrix on the right by the identity matrix leaves it unchanged.
Matrix.nonsing_inv_mul- Multiplying an invertible matrix on the left by its inverse gives the identity matrix.
Matrix.one_mul- Multiplying any matrix on the left by the identity matrix leaves it unchanged.
Matrix.rank_le_card_width- The rank of a matrix is at most the number of its columns.
Matrix.rank_mul_le_left- The rank of a matrix product A * B is at most the rank of the left factor A.
Matrix.transpose_apply- The (i, j)-entry of the transpose of a matrix M is the (j, i)-entry of M.
Matrix.transpose_fromRows- The transpose of a matrix formed by stacking two block rows is formed by stacking the transposes of the blocks as columns.
Matrix.transpose_mul- The transpose of a matrix product is the product of the transposes in reverse order: (M * N)ᵀ = Nᵀ * Mᵀ.
Matrix.transpose_nonsing_inv- For any invertible matrix, the transpose of its inverse is the inverse of its transpose.
Matrix.transpose_one- The transpose of the identity matrix is the identity matrix.
Matrix.transpose_transpose- Taking the transpose of a matrix twice yields the original matrix: (Mᵀ)ᵀ = M.
Nat.sInf_le- The infimum of a set of natural numbers is at most any element of that set.
Sum.elim_inl- Applying a function defined on a disjoint union by cases to a left-injected element yields the value of the left case function.
Sum.elim_inr- Applying a function defined on a disjoint union by cases to a right-injected element yields the value of the right case function.
congrFun- If two functions are equal, then their evaluations at any given argument are equal.
digraph_is_acyclic_of_rank- A directed graph is acyclic if there exists a ranking function into the natural numbers that strictly increases along every directed edge.
le_trans- The less-than-or-equal relation is transitive: if a ≤ b and b ≤ c, then a ≤ c.
not_le- For elements of a linear order, a is not less than or equal to b if and only if b < a.
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_dijoin_le_of_symm_inv (n : ℕ) (B : Matrix (Fin n) (Fin n) (ZMod 2)) (hB : B.IsSymm) (hdet : IsUnit B.det) : tournament_min_rank (digraph_dijoin (tournament_of_symm_matrix (lower_ones_matrix n * B⁻¹ * (lower_ones_matrix n).transpose)) (tournament_of_symm_matrix B)) ≤ n := by have two : ∀ a : ZMod 2, a = 0 ∨ a = 1 := by decide have hBinvT : (B⁻¹).transpose = B⁻¹ := by rw [Matrix.transpose_nonsing_inv, hB.eq] -- the diagonal blocks reverse exactly the arcs of `T(G)` that go downwards have diag : ∀ G : Matrix (Fin n) (Fin n) (ZMod 2), G.IsSymm → ∀ i j : Fin n, (G i j = 1 ∧ (tournament_of_symm_matrix G).Adj j i) ∨ (G i j ≠ 1 ∧ (tournament_of_symm_matrix G).Adj i j) → (i : ℕ) < j := by intro G hG i j h have hs : G j i = G i j := by have := congrFun (congrFun hG.eq i) j simpa [Matrix.transpose_apply] using this simp only [tournament_of_symm_matrix, hs] at h rcases two (G i j) with h0 | h0 <;> simp [h0] at h <;> exact h have hdec : ∀ A : Matrix (Fin n) (Fin n) (ZMod 2), A.IsSymm → digraph_is_acyclic (digraph_flip_by_matrix (digraph_dijoin (tournament_of_symm_matrix A) (tournament_of_symm_matrix B)) (Matrix.fromBlocks A (lower_ones_matrix n) (lower_ones_matrix n).transpose B)) := by intro A hA apply digraph_is_acyclic_of_rank _ (Sum.elim (fun i : Fin n => 2 * (i : ℕ) + 1) (fun j : Fin n => 2 * (j : ℕ))) intro x y hxy rcases x with i | i <;> rcases y with j | j · have := diag A hA i j hxy simp only [Sum.elim_inl] omega · rcases hxy with ⟨_, h⟩ | ⟨h, _⟩ · exact h.elim · have hji : ¬ j ≤ i := fun hji => h (by simp [Matrix.fromBlocks, lower_ones_matrix, hji]) have hij : (i : ℕ) < j := by rw [not_le] at hji; exact hji simp only [Sum.elim_inl, Sum.elim_inr] omega · rcases hxy with ⟨h, _⟩ | ⟨_, h⟩ · have hij : i ≤ j := by by_contra hc simp [Matrix.fromBlocks, lower_ones_matrix, hc] at h have hij' : (i : ℕ) ≤ j := hij simp only [Sum.elim_inl, Sum.elim_inr] omega · exact h.elim · have := diag B hB i j hxy simp only [Sum.elim_inr] omega -- the rank is at most `n`: the block matrix is `P B Pᵀ` with `P` of width `n` have hrank : ∀ L : Matrix (Fin n) (Fin n) (ZMod 2), (Matrix.fromBlocks (L * B⁻¹ * L.transpose) L L.transpose B).rank ≤ n := by intro L have hMP : Matrix.fromBlocks (L * B⁻¹ * L.transpose) L L.transpose B = Matrix.fromRows (L * B⁻¹) 1 * B * (Matrix.fromRows (L * B⁻¹) 1).transpose := by rw [Matrix.fromRows_mul, Matrix.transpose_fromRows, Matrix.fromRows_mul_fromCols] congr 1 · rw [Matrix.mul_assoc L B⁻¹ B, Matrix.nonsing_inv_mul B hdet, Matrix.mul_one, Matrix.transpose_mul, hBinvT, Matrix.mul_assoc] · rw [Matrix.transpose_one, Matrix.mul_one, Matrix.mul_assoc, Matrix.nonsing_inv_mul B hdet, Matrix.mul_one] · rw [Matrix.one_mul, Matrix.transpose_mul, hBinvT, ← Matrix.mul_assoc, Matrix.mul_nonsing_inv B hdet, Matrix.one_mul] · rw [Matrix.one_mul, Matrix.transpose_one, Matrix.mul_one] rw [hMP] calc _ ≤ (Matrix.fromRows (L * B⁻¹) 1 * B).rank := Matrix.rank_mul_le_left _ _ _ ≤ (Matrix.fromRows (L * B⁻¹) (1 : Matrix (Fin n) (Fin n) (ZMod 2))).rank := Matrix.rank_mul_le_left _ _ _ ≤ Fintype.card (Fin n) := Matrix.rank_le_card_width _ _ = n := Fintype.card_fin n have hAs : (lower_ones_matrix n * B⁻¹ * (lower_ones_matrix n).transpose).IsSymm := by unfold Matrix.IsSymm rw [Matrix.transpose_mul, Matrix.transpose_mul, Matrix.transpose_transpose, hBinvT, Matrix.mul_assoc] have hMs : (Matrix.fromBlocks (lower_ones_matrix n * B⁻¹ * (lower_ones_matrix n).transpose) (lower_ones_matrix n) (lower_ones_matrix n).transpose B).IsSymm := Matrix.IsSymm.fromBlocks hAs rfl hB exact le_trans (Nat.sInf_le ⟨_, hMs, hdec _ hAs, rfl⟩) (hrank _)