AFTD Auto-Formalizing Theoretical Domains

tournament_min_rank_dijoin_le_of_symm_inv

theoremverifiedformalization

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.

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

    lines 6–7

    uses Matrix.transpose_nonsing_inv

      have two : ∀ a : ZMod 2, a = 0 ∨ a = 1 := by decide
      have hBinvT : (B⁻¹).transpose = B⁻¹ := by rw [Matrix.transpose_nonsing_inv, hB.eq]
  2. 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.

    lines 9–18

    uses congrFun, Matrix.transpose_apply

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

    lines 19–47

    uses digraph_is_acyclic_of_rank, Sum.elim_inl, not_le, Sum.elim_inr

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

    lines 49–68

    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_fin

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

    lines 69–76

    uses Matrix.transpose_mul, Matrix.transpose_transpose, Matrix.mul_assoc, Matrix.IsSymm.fromBlocks, le_trans, Nat.sInf_le

      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 _)
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

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