AFTD Auto-Formalizing Theoretical Domains

matrix3_tensor_rank_ge_iff_trace_tensor_bound

theoremverified

A lower bound r for the lengths of all valid 3x3 matrix multiplication triad lists is equivalent to the same lower bound for every finite indexed family satisfying the cyclic trace tensor coefficient identities. The third tensor factor is the transpose of the triad output weight.

Statement

theorem matrix3_tensor_rank_ge_iff_trace_tensor_bound {R : Type*} [CommSemiring R]
    (r : ℕ) :
    matrix3_tensor_rank_ge R r ↔
    ∀ (n : ℕ) (a b c : Fin n → Matrix (Fin 3) (Fin 3) R),
      (∀ 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) → r ≤ n
Source
Adapter for OP-2 / matrix3_tensor_rank_zmod2_le_22; cyclic trace coefficient convention in arXiv:2610.11823v3, Section 2 and its companion RootSound/Tensor.lean. Proof written here using the existing unit-check extension theorem; no external proof is assumed.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • matrix3_valid_iff_trace_tensor_identityFor a finite indexed family of triads over any commutative semiring, validity of the decomposition whose output weights are the transposes…
  • matrix3_tensor_rank_geFor a commutative semiring R and a natural number r, matrix3_tensor_rank_ge R r asserts that for every list L of elements of Matrix3Triad…
  • Matrix3TriadGiven a type R, a Matrix3Triad R is a structure consisting of three 3-by-3 matrices with entries in R, labeled u, v, and w.
  • is_valid_matrix3_decompositionGiven a commutative semiring R and a list L of Matrix3Triad R, is_valid_matrix3_decomposition L asserts that for all 3x3 matrices A and B…

The proof, explained

The equivalence is proved in both directions using `matrix3_valid_iff_trace_tensor_identity`, which establishes that a triad list is a valid $3 \times 3$ matrix multiplication decomposition if and only if its factors $(a_s, b_s, c_s)$ satisfy the cyclic trace tensor coefficient identity, with the third factor transposed. In the forward direction, any family satisfying the trace identity defines a valid triad list of length $n$, yielding $r \le n$ from the rank lower bound. In the reverse direction, any valid triad decomposition list $L$ is re-indexed into components with $c_s = w_s^\top$ via double transposition, so the assumed trace tensor bound implies $r \le |L|$.

  1. If every valid triad decomposition has length at least $r$, then any family $(a, b, c)$ of size $n$ satisfying the cyclic trace tensor identity satisfies $r \le n$.

    We split the if-and-only-if statement into both directions. In the forward direction, we assume that all valid matrix multiplication decompositions have length at least $r$, and consider families $a, b, c : \mathrm{Fin}\ n \to M_3(R)$ satisfying the trace tensor identity. By `matrix3_valid_iff_trace_tensor_identity`, the list formed by triads with components $a(s)$, $b(s)$, and $c(s)^\top$ is a valid decomposition of $3 \times 3$ matrix multiplication. The hypothesis then gives that $r$ is bounded by the length of this list, which simplifies to $n$ via `List.length_ofFn`.

    lines 10–13

    uses matrix3_valid_iff_trace_tensor_identity, List.length_ofFn

      constructor
      · intro h n a b c hc
        have hv := (matrix3_valid_iff_trace_tensor_identity n a b c).mpr hc
        simpa only [List.length_ofFn] using h _ hv
  2. Any valid triad decomposition $L$ can be expressed as a list generated by index-wise extraction of its components, with the third factor double-transposed.

    For the reverse implication, we assume that any family satisfying the trace tensor identities has size at least $r$, and consider an arbitrary valid decomposition list $L$. We reconstruct $L$ via `List.ofFn` using the elements $\langle (L.\mathrm{get}\ s).u, (L.\mathrm{get}\ s).v, ((L.\mathrm{get}\ s).w^\top)^\top \rangle$. Simplifying the double transpose using `Matrix.transpose_transpose` and applying `List.ofFn_get`, this list equals $L$, so it is also a valid matrix multiplication decomposition.

    lines 14–19

    uses Matrix.transpose_transpose, List.ofFn_get

      · intro h L hL
        have hget : (List.ofFn fun s : Fin L.length =>
            (⟨(L.get s).u, (L.get s).v, ((L.get s).wᵀ)ᵀ⟩ : Matrix3Triad R)) = L := by
          simp only [Matrix.transpose_transpose]
          exact List.ofFn_get L
        have hv := hget.symm ▸ hL
  3. Every valid triad decomposition $L$ satisfies $r \le |L|$, completing the equivalence.

    Applying `matrix3_valid_iff_trace_tensor_identity` to the indexed representation of $L$, the validity of the decomposition implies that the components $a(s) = (L.\mathrm{get}\ s).u$, $b(s) = (L.\mathrm{get}\ s).v$, and $c(s) = (L.\mathrm{get}\ s).w^\top$ satisfy the cyclic trace tensor coefficient identities. Invoking the reverse hypothesis for this family of length $|L|$ immediately concludes that $r \le |L|$.

    lines 20–22

    uses matrix3_valid_iff_trace_tensor_identity

        exact h L.length (fun s => (L.get s).u) (fun s => (L.get s).v)
          (fun s => (L.get s).wᵀ)
          ((matrix3_valid_iff_trace_tensor_identity L.length _ _ _).mp hv)
matrix3_valid_iff_trace_tensor_identity
A list of triads formed by $(a_s, b_s, c_s^\top)$ is a valid matrix multiplication decomposition if and only if the sum of triple products $\sum_s a_s(i, j) b_s(j', k) c_s(k', i')$ equals $1$ when $j = j', k = k', i = i'$ and $0$ otherwise.
List.length_ofFn
The length of a list created by `List.ofFn f` from a function with domain `Fin n` is $n$.
Matrix.transpose_transpose
Transposing a matrix twice returns the original matrix: $(M^\top)^\top = M$.
List.ofFn_get
Reconstructing a list from its indexing function via `List.ofFn` recovers the original list.

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

open Matrixtheorem matrix3_tensor_rank_ge_iff_trace_tensor_bound {R : Type*} [CommSemiring R]    (r : ℕ) :    matrix3_tensor_rank_ge R r ↔    ∀ (n : ℕ) (a b c : Fin n → Matrix (Fin 3) (Fin 3) R),      (∀ 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) → r ≤ n := by  constructor  · intro h n a b c hc    have hv := (matrix3_valid_iff_trace_tensor_identity n a b c).mpr hc    simpa only [List.length_ofFn] using h _ hv  · intro h L hL    have hget : (List.ofFn fun s : Fin L.length =>        (⟨(L.get s).u, (L.get s).v, ((L.get s).wᵀ)ᵀ⟩ : Matrix3Triad R)) = L := by      simp only [Matrix.transpose_transpose]      exact List.ofFn_get L    have hv := hget.symm ▸ hL    exact h L.length (fun s => (L.get s).u) (fun s => (L.get s).v)      (fun s => (L.get s).wᵀ)      ((matrix3_valid_iff_trace_tensor_identity L.length _ _ _).mp hv)
See it in the graphDiscuss this resultChallenge it