AFTD Auto-Formalizing Theoretical Domains

matrix3_trace_rank_sum_ge_27

theoremverifiedformalization

For a finite family of 3x3 matrices over a field satisfying the cyclic trace identities of matrix multiplication, the sum of the matrix ranks of the first factors is at least 27.

Statement

theorem matrix3_trace_rank_sum_ge_27 {K : Type*} [Field K] {r : ℕ} (a b c : Fin r → Matrix (Fin 3) (Fin 3) K)
    (h : ∀ i j j' k k' i' : Fin 3,
      ∑ s, a s i j * b s j' k * c s k' i' =
        if j = j' ∧ k = k' ∧ i = i' then 1 else 0) :
    27 ≤ ∑ s, (a s).rank
Formalizes
arXiv:2610.11823v3, Lemma 4.1 (split flattening). The proof here uses a surjective linear map from the product of the first-factor column ranges and applies over every field; the paper states the two-element-field case.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

The proof establishes the lower bound 27 ≤ ∑ s, rank(a s) by constructing a surjective linear map from the product of the column spaces of the matrices a s to the space of 3x3x3 tensors K^(3×3×3). The cyclic trace identities ensure that an explicit right inverse can be formed from the matrices c s, proving surjectivity. Since the map is surjective, the dimension of the tensor space (27) cannot exceed the dimension of the domain (the sum of the ranks of the matrices a s).

  1. Define the factor space as the direct product of the column spaces of the matrices a s.

    For each index s, (a s).mulVecLin is the linear map corresponding to the 3x3 matrix a s, and its range is the column space in K³. The factor space is the product of these ranges over all s.

    lines 1–7

    uses LinearMap.range

    open Matrix Finset
    noncomputable section
    variable {K : Type*} [Field K] {r : ℕ}
    
    private abbrev matrix3_factor_space (a : Fin r → Matrix (Fin 3) (Fin 3) K) :=
      ∀ s, LinearMap.range (a s).mulVecLin
    
  2. Define a linear map from the factor space to the space of 3-tensors.

    The map sends a tuple of vectors (x s) to the tensor p ↦ ∑ s, (x s)_{p.1} * (b s)_{p.2.1, p.2.2}. Linearity is verified by distributivity and associativity of multiplication and summation.

    lines 8–17

    uses add_mul, Finset.sum_add_distrib, Finset.mul_sum, mul_assoc

    private def matrix3_factor_map (a b : Fin r → Matrix (Fin 3) (Fin 3) K) :
        matrix3_factor_space a →ₗ[K] (Fin 3 × Fin 3 × Fin 3 → K) where
      toFun x p := ∑ s, (x s).val p.1 * b s p.2.1 p.2.2
      map_add' x y := by
        ext p
        simp [add_mul, Finset.sum_add_distrib]
      map_smul' c x := by
        ext p
        simp [Finset.mul_sum, mul_assoc]
    
  3. Construct a preimage in the factor space for every 3-tensor.

    For a tensor z, the s-th component is defined as the image under a s of the vector j ↦ ∑ k i, (c s)_{k, i} * z(i, j, k), which belongs to the column space of a s by construction.

    lines 18–22

    private def matrix3_factor_preimage (a c : Fin r → Matrix (Fin 3) (Fin 3) K)
        (z : Fin 3 × Fin 3 × Fin 3 → K) : matrix3_factor_space a :=
      fun s => ⟨(a s).mulVecLin (fun j => ∑ k, ∑ i, c s k i * z (i,j,k)),
        ⟨_, rfl⟩⟩
    
  4. The preimage construction provides an exact right inverse to the factor map.

    Evaluating the factor map on the preimage yields z by applying the cyclic trace identity via matrix3_trace_split_reconstruction.

    lines 23–31

    uses matrix3_trace_split_reconstruction

    private theorem matrix3_factor_reconstruction (a b c : Fin r → Matrix (Fin 3) (Fin 3) K)
        (h : ∀ i j j' k k' i' : Fin 3,
          ∑ s, a s i j * b s j' k * c s k' i' =
            if j = j' ∧ k = k' ∧ i = i' then 1 else 0)
        (z : Fin 3 × Fin 3 × Fin 3 → K) :
        matrix3_factor_map a b (matrix3_factor_preimage a c z) = z := by
      ext p
      exact matrix3_trace_split_reconstruction a b c h z p
    
  5. The factor map is surjective.

    Every tensor z is in the range of the factor map because matrix3_factor_preimage produces a preimage whose image is z by matrix3_factor_reconstruction.

    lines 32–38

    uses matrix3_factor_reconstruction

    theorem matrix3_trace_rank_sum_ge_27 {K : Type*} [Field K] {r : ℕ} (a b c : Fin r → Matrix (Fin 3) (Fin 3) K)
        (h : ∀ i j j' k k' i' : Fin 3,
          ∑ s, a s i j * b s j' k * c s k' i' =
            if j = j' ∧ k = k' ∧ i = i' then 1 else 0) :
        27 ≤ ∑ s, (a s).rank := by
      have hs : Function.Surjective (matrix3_factor_map a b) := fun z =>
        ⟨matrix3_factor_preimage a c z, matrix3_factor_reconstruction a b c h z⟩
  6. The dimension of the tensor space is at most the dimension of the factor space.

    A surjective linear map between finite-dimensional spaces has codomain dimension bounded by domain dimension.

    line 39

    uses LinearMap.finrank_le_finrank_of_surjective

      have hd := LinearMap.finrank_le_finrank_of_surjective hs
  7. 27 ≤ ∑ s, (a s).rank automation

    The dimension of the codomain K^(3×3×3) is 3³ = 27, and the dimension of the domain ∏ s im(a s) is the sum of the ranks of the matrices a s. Linear arithmetic completes the proof.

    line 40

    uses Matrix.rank, Module.finrank_pi, Module.finrank_pi_fintype

      simpa [matrix3_factor_space, Matrix.rank, Module.finrank_pi, Module.finrank_pi_fintype] using hd
LinearMap.range
The range (column space) of a linear map as a submodule of its codomain.
add_mul
Right distributivity of multiplication over addition: (a + b) * c = a * c + b * c.
Finset.sum_add_distrib
The sum over a finite set of a pointwise sum of functions equals the sum of the individual sums.
Finset.mul_sum
Left distributivity of multiplication across a finite sum: a * ∑ i, f i = ∑ i, a * f i.
mul_assoc
Associativity of multiplication: (a * b) * c = a * (b * c).
matrix3_trace_split_reconstruction
The cyclic trace identity reconstructs any 3-tensor z from its contractions with the matrix families.
matrix3_factor_reconstruction
The statement that a preimage constructor provides a valid right inverse for the factor map.
LinearMap.finrank_le_finrank_of_surjective
If a linear map between vector spaces is surjective, the dimension of the codomain is at most the dimension of the domain.
Matrix.rank
The rank of a matrix is the dimension of the image of its associated linear map.
Module.finrank_pi
The dimension of the space of functions from a finite set ι to the base ring R is the cardinality of ι.
Module.finrank_pi_fintype
The dimension of a product of finitely many vector spaces is the sum of their individual dimensions.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

open Matrix Finsetnoncomputable sectionvariable {K : Type*} [Field K] {r : ℕ}private abbrev matrix3_factor_space (a : Fin r → Matrix (Fin 3) (Fin 3) K) :=  ∀ s, LinearMap.range (a s).mulVecLinprivate def matrix3_factor_map (a b : Fin r → Matrix (Fin 3) (Fin 3) K) :    matrix3_factor_space a →ₗ[K] (Fin 3 × Fin 3 × Fin 3 → K) where  toFun x p := ∑ s, (x s).val p.1 * b s p.2.1 p.2.2  map_add' x y := by    ext p    simp [add_mul, Finset.sum_add_distrib]  map_smul' c x := by    ext p    simp [Finset.mul_sum, mul_assoc]private def matrix3_factor_preimage (a c : Fin r → Matrix (Fin 3) (Fin 3) K)    (z : Fin 3 × Fin 3 × Fin 3 → K) : matrix3_factor_space a :=  fun s => ⟨(a s).mulVecLin (fun j => ∑ k, ∑ i, c s k i * z (i,j,k)),    ⟨_, rfl⟩⟩private theorem matrix3_factor_reconstruction (a b c : Fin r → Matrix (Fin 3) (Fin 3) K)    (h : ∀ i j j' k k' i' : Fin 3,      ∑ s, a s i j * b s j' k * c s k' i' =        if j = j' ∧ k = k' ∧ i = i' then 1 else 0)    (z : Fin 3 × Fin 3 × Fin 3 → K) :    matrix3_factor_map a b (matrix3_factor_preimage a c z) = z := by  ext p  exact matrix3_trace_split_reconstruction a b c h z ptheorem matrix3_trace_rank_sum_ge_27 {K : Type*} [Field K] {r : ℕ} (a b c : Fin r → Matrix (Fin 3) (Fin 3) K)    (h : ∀ i j j' k k' i' : Fin 3,      ∑ s, a s i j * b s j' k * c s k' i' =        if j = j' ∧ k = k' ∧ i = i' then 1 else 0) :    27 ≤ ∑ s, (a s).rank := by  have hs : Function.Surjective (matrix3_factor_map a b) := fun z =>    ⟨matrix3_factor_preimage a c z, matrix3_factor_reconstruction a b c h z⟩  have hd := LinearMap.finrank_le_finrank_of_surjective hs  simpa [matrix3_factor_space, Matrix.rank, Module.finrank_pi, Module.finrank_pi_fintype] using hd
See it in the graphDiscuss this resultChallenge it