matrix3_valid_iff_trace_tensor_identity
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
- matrix3_valid_cyclic_rotateCyclic rotation (u, v, w) ↦ (v, wᵀ, uᵀ) of every triad in a valid 3x3 matrix multiplication decomposition produces another valid…
- matrix3_tensor_rank_le_iff_trace_familyThe tensor rank of 3x3 matrix multiplication over a commutative semiring R is at most r if and only if there exists a cyclic trace family…
- matrix3_tensor_rank_ge_iff_trace_tensor_boundA lower bound r for the lengths of all valid 3x3 matrix multiplication triad lists is equivalent to the same lower bound for every finite…
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.
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`.
uses
eval_matrix3_decomposition_apply,List.map_ofFn,List.sum_ofFn,Matrix.single_apply,Matrix.transpose_apply,ite_andrw [eval_matrix3_decomposition_apply] simp [List.map_ofFn, List.sum_ofFn, Matrix.single_apply, Matrix.transpose_apply, ite_and]
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.
uses
Matrix.mul_apply,Matrix.single_apply,ite_andsimp [Matrix.mul_apply, Matrix.single_apply, ite_and] split_ifs <;> simp_all
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.
uses
congrArg,matrix3_trace_eval_units,matrix3_trace_product_unitsconstructor · 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
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.
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
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.
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'