AFTD Auto-Formalizing Theoretical Domains

matrix3_valid_iff_trace_tensor_identity

theoremverified

For a finite indexed family of triads over any commutative semiring, validity of the decomposition whose output weights are the transposes of c is equivalent to the coefficient identities of the cyclic trace tensor. This identifies the bilinear map convention with the tensor convention used in arXiv:2610.11823.

Statement

theorem matrix3_valid_iff_trace_tensor_identity {R : Type*} [CommSemiring R]
    (n : ℕ) (a b c : Fin n → Matrix (Fin 3) (Fin 3) R) :
    is_valid_matrix3_decomposition
      (List.ofFn fun s => (⟨a s, b s, (c s)ᵀ⟩ : Matrix3Triad 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
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 5
  • matrix3_valid_of_unit_checksIf a list L of triads over a commutative semiring R evaluates to matrix multiplication on all 81 pairs of matrix units, then L is a valid…
  • eval_matrix3_decomposition_applyEntry (i, j) of the evaluation of a list of 3x3 triads on A and B is the sum, over the triads, of (sum of u_kl A_kl) times (sum of v_kl…
  • 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.
  • eval_matrix3_decompositionGiven a commutative semiring R, a list L of Matrix3Triad R, and 3x3 matrices A and B over R, eval_matrix3_decomposition L A B is the sum…
  • 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…
Used by 3

The proof, explained

The equivalence between decomposition validity and the cyclic trace tensor identity is proved by reducing validity on all matrices to validity on standard basis matrices. Two helper lemmas compute the entrywise evaluation of the decomposition on basis matrices and the product of basis matrices, respectively. Both directions of the equivalence then follow by specializing or verifying the identity on the standard basis.

  1. Evaluating the triad decomposition on basis matrices $E_{i, j}$ and $E_{k, l}$ at entry $(p, q)$ equals $\sum_s a_s(i, j) b_s(k, l) c_s(q, p)$.

    Unfold the evaluation formula at entry $(p, q)$ with `eval_matrix3_decomposition_apply`, then simplify using list mapping/summing lemmas, the basis matrix entry formula `Matrix.single_apply`, and the transpose formula `Matrix.transpose_apply`.

    lines 7–8

    uses eval_matrix3_decomposition_apply, List.map_ofFn, List.sum_ofFn, Matrix.single_apply, Matrix.transpose_apply, ite_and

      rw [eval_matrix3_decomposition_apply]
      simp [List.map_ofFn, List.sum_ofFn, Matrix.single_apply, Matrix.transpose_apply, ite_and]
  2. The product of basis matrices $E_{i, j}$ and $E_{j', k}$ at entry $(i', k')$ equals $1$ if $j = j'$, $k = k'$, and $i = i'$, and $0$ otherwise. automation

    Expand the matrix product formula using `Matrix.mul_apply` and `Matrix.single_apply`, then perform case analysis on the index equalities using `split_ifs` and simplify each case.

    lines 14–15

    uses Matrix.mul_apply, Matrix.single_apply, ite_and

      simp [Matrix.mul_apply, Matrix.single_apply, ite_and]
      split_ifs <;> simp_all
  3. Validity of the decomposition implies the trace tensor identity for all indices.

    Split the equivalence into two implications. In the forward direction, assume the decomposition is valid. Given indices $i, j, j', k, k', i'$, evaluate the validity assumption on basis matrices $E_{i, j}$ and $E_{j', k}$ and take the $(i', k')$-entry using `congrArg`. Rewriting the LHS and RHS with the helper lemmas `matrix3_trace_eval_units` and `matrix3_trace_product_units` yields the desired cyclic trace tensor identity.

    lines 24–29

    uses congrArg, matrix3_trace_eval_units, matrix3_trace_product_units

      constructor
      · intro h i j j' k k' i'
        have he := congrArg (fun M : Matrix (Fin 3) (Fin 3) R => M i' k')
          (h (Matrix.single i j 1) (Matrix.single j' k 1))
        rw [matrix3_trace_eval_units, matrix3_trace_product_units] at he
        exact he
  4. The trace tensor identity implies validity of the decomposition.

    In the reverse direction, assume the trace tensor identity holds. By `matrix3_valid_of_unit_checks`, it suffices to verify validity on pairs of basis matrices $E_{i, j}$ and $E_{j', k}$. By extensionality, we compare the matrices entrywise at $(i', k')$. Rewriting both sides with `matrix3_trace_eval_units` and `matrix3_trace_product_units` reproduces the tensor identity, which matches the assumption.

    lines 30–35

    uses matrix3_valid_of_unit_checks, matrix3_trace_eval_units, matrix3_trace_product_units

      · intro h
        apply matrix3_valid_of_unit_checks
        intro i j j' k
        ext i' k'
        rw [matrix3_trace_eval_units, matrix3_trace_product_units]
        exact h i j j' k k' i'
Matrix.mul_apply
Matrix multiplication is given by the standard row-column sum: $(M N)_{i, k} = \sum_j M_{i, j} N_{j, k}$.
Matrix.single_apply
The entries of a single-entry matrix $c E_{i, j}$ are $c$ at $(i, j)$ and $0$ elsewhere.
Matrix.transpose_apply
The $(i, j)$-entry of the transpose $M^T$ is $M_{j, i}$.
List.map_ofFn
Mapping over a list constructed from a function on $\mathrm{Fin}\ n$ corresponds to composing the functions.
List.sum_ofFn
The sum of a list formed from a function on $\mathrm{Fin}\ n$ is the sum over $\mathrm{Fin}\ n$.
ite_and
An `if` expression with a conjunction $P \wedge Q$ can be split into nested `if` expressions for $P$ and $Q$.
congrArg
Applying a function preserves equality: if $a_1 = a_2$, then $f(a_1) = f(a_2)$.
eval_matrix3_decomposition_apply
Unfolds the definition of matrix decomposition evaluation at an entry $(i, j)$ as the sum of inner products of basis elements times the output triad matrix.
matrix3_trace_eval_units
Evaluating the triad decomposition with transposed output weights on standard basis matrices $E_{i, j}$ and $E_{k, l}$ at entry $(p, q)$ equals $\sum_s a_s(i, j) b_s(k, l) c_s(q, p)$.
matrix3_trace_product_units
The $(i', k')$-entry of the product of basis matrices $E_{i, j} E_{j', k}$ equals $1$ if $j = j'$, $k = k'$, and $i = i'$, and $0$ otherwise.
matrix3_valid_of_unit_checks
A matrix decomposition is valid for all matrices if it correctly evaluates products of standard basis matrices.

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 Matrixprivate theorem matrix3_trace_eval_units {R : Type*} [CommSemiring R] (n : ℕ)    (a b c : Fin n → Matrix (Fin 3) (Fin 3) R) (i j k l p q : Fin 3) :    eval_matrix3_decomposition (List.ofFn fun s => (⟨a s, b s, (c s)ᵀ⟩ : Matrix3Triad R))      (Matrix.single i j 1) (Matrix.single k l 1) p q =        ∑ s, a s i j * b s k l * c s q p := by  rw [eval_matrix3_decomposition_apply]  simp [List.map_ofFn, List.sum_ofFn, Matrix.single_apply, Matrix.transpose_apply, ite_and]private theorem matrix3_trace_product_units {R : Type*} [CommSemiring R]    (i j j' k k' i' : Fin 3) :    (Matrix.single i j (1 : R) * Matrix.single j' k 1 : Matrix (Fin 3) (Fin 3) R) i' k' =      if j = j' ∧ k = k' ∧ i = i' then 1 else 0 := by  simp [Matrix.mul_apply, Matrix.single_apply, ite_and]  split_ifs <;> simp_alltheorem matrix3_valid_iff_trace_tensor_identity {R : Type*} [CommSemiring R]    (n : ℕ) (a b c : Fin n → Matrix (Fin 3) (Fin 3) R) :    is_valid_matrix3_decomposition      (List.ofFn fun s => (⟨a s, b s, (c s)ᵀ⟩ : Matrix3Triad 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 := by  constructor  · intro h i j j' k k' i'    have he := congrArg (fun M : Matrix (Fin 3) (Fin 3) R => M i' k')      (h (Matrix.single i j 1) (Matrix.single j' k 1))    rw [matrix3_trace_eval_units, matrix3_trace_product_units] at he    exact he  · intro h    apply matrix3_valid_of_unit_checks    intro i j j' k    ext i' k'    rw [matrix3_trace_eval_units, matrix3_trace_product_units]    exact h i j j' k k' i'
See it in the graphDiscuss this resultChallenge it