matrix3_tensor_rank_le_iff_trace_family
The 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 of length at most r satisfying the matrix multiplication tensor coefficient identities.
Statement
theorem matrix3_tensor_rank_le_iff_trace_family {R : Type*} [CommSemiring R] (r : ℕ) : matrix3_tensor_rank_le R r ↔ ∃ (n : ℕ) (_ : n ≤ r) (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
- Source
- step towards matrix3_tensor_rank_int_le_22
- Verified
- 09 Nov 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_leFor a commutative semiring R and a natural number r, matrix3_tensor_rank_le R r asserts that there exists a list L of elements of…
- 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 established in both directions using the bridge lemma `matrix3_valid_iff_trace_tensor_identity`, which equates the validity of a decomposition list of triads $(a_s, b_s, c_s^T)$ with the cyclic trace tensor identity. In the forward direction, given a valid decomposition list $L$ of length at most $r$, setting $a_s = L_s.u$, $b_s = L_s.v$, and $c_s = (L_s.w)^T$ recovers $L$ because transposition is an involution, so the validity of $L$ implies the tensor identity. In the reverse direction, given matrix families satisfying the tensor identity, constructing the list of triads $(a_s, b_s, c_s^T)$ yields a valid decomposition of length at most $r$.
To prove the forward direction, given a valid decomposition list $L$ of length at most $r$, it suffices to show that the matrix families $a_s = L_s.u$, $b_s = L_s.v$, and $c_s = (L_s.w)^T$ satisfy the cyclic trace tensor identity.
We split the bi-implication into the forward and reverse directions. For the forward direction, assuming the tensor rank is at most $r$, there exists a list $L$ of matrix triads of length at most $r$ that forms a valid matrix multiplication decomposition. We instantiate the existential witnesses with $n = |L|$ (which satisfies $n \le r$), and the matrix families $a_s = L_s.u$, $b_s = L_s.v$, and $c_s = (L_s.w)^T$ for each index $s$, leaving the tensor identity to be shown.
constructor · rintro ⟨L, hlen, hvalid⟩ refine ⟨L.length, hlen, fun s => (L.get s).u, fun s => (L.get s).v, fun s => (L.get s).w.transpose, ?_⟩
Reconstructing the list of triads from components $a_s, b_s, c_s^T$ recovers the original list $L$.
For each index $s$, the triad with components $L_s.u$, $L_s.v$, and $(L_s.w^T)^T$ is identical to $L_s$ because matrix transposition is an involution and record components determine the triad (`simp`). By function extensionality, this function is equal to $L\text{.get}$. Applying `List.ofFn_get` then shows that converting this indexing function back into a list recovers $L$.
uses
List.ofFn_gethave heq : (List.ofFn fun s => ({ u := (L.get s).u, v := (L.get s).v, w := (L.get s).w.transpose.transpose } : Matrix3Triad R)) = L := by have : (fun s => ({ u := (L.get s).u, v := (L.get s).v, w := (L.get s).w.transpose.transpose } : Matrix3Triad R)) = L.get := by funext s simp rw [this, List.ofFn_get]
The matrix families $a, b, c$ satisfy the cyclic trace tensor identity, completing the forward direction.
By `matrix3_valid_iff_trace_tensor_identity`, the required summation identity is equivalent to the list formed by triads $(a_s, b_s, c_s^T)$ being a valid matrix multiplication decomposition. By the equality established in the previous step, that reconstructed list is simply $L$, which is valid by assumption.
uses
matrix3_valid_iff_trace_tensor_identityrw [← matrix3_valid_iff_trace_tensor_identity] rwa [heq]
In the reverse direction, given families $a, b, c$ of length $n \le r$ satisfying the identity, the corresponding list of triads has length at most $r$.
We assume there exist $n \le r$ and matrix families $a, b, c$ satisfying the cyclic trace tensor identity. We propose as candidate decomposition the list $L = \text{List.ofFn}(s \mapsto \{u := a_s, v := b_s, w := c_s^T\})$. By `List.length_ofFn`, the length of $L$ is $n$, which is bounded by $r$.
uses
List.length_ofFn· rintro ⟨n, hlen, a, b, c, hid⟩ refine ⟨List.ofFn fun s => { u := a s, v := b s, w := (c s).transpose }, ?_, ?_⟩ · rw [List.length_ofFn] exact hlenThe constructed list is a valid decomposition of $3 \times 3$ matrix multiplication, concluding the equivalence.
Applying the reverse direction of `matrix3_valid_iff_trace_tensor_identity` to the assumed identity shows that the constructed list is indeed a valid decomposition, proving that the tensor rank is at most $r$.
uses
matrix3_valid_iff_trace_tensor_identity· exact (matrix3_valid_iff_trace_tensor_identity n a b c).mpr hid
List.ofFn_get- Reconstructing a list from its indexing function via `List.ofFn` yields the original list.
List.length_ofFn- The length of a list created by `List.ofFn` from a function on `Fin n` is $n$.
matrix3_valid_iff_trace_tensor_identity- A list of triads $(a_s, b_s, c_s^T)_{s < n}$ is a valid matrix multiplication decomposition if and only if the matrix families $a, b, c$ satisfy the cyclic trace tensor identity $\sum_s a_s(i, j) b_s(j', k) c_s(k', i') = [j = j' \wedge k = k' \wedge i = i']$.
- In line 14, `simp` automatically handles both the involution $(w^T)^T = w$ on matrices and the constructor eta-expansion of `Matrix3Triad`.
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.
/-- The 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 of length at most r satisfying the tensor coefficient identities. -/theorem matrix3_tensor_rank_le_iff_trace_family {R : Type*} [CommSemiring R] (r : ℕ) : matrix3_tensor_rank_le R r ↔ ∃ (n : ℕ) (_ : n ≤ r) (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 := by constructor · rintro ⟨L, hlen, hvalid⟩ refine ⟨L.length, hlen, fun s => (L.get s).u, fun s => (L.get s).v, fun s => (L.get s).w.transpose, ?_⟩ have heq : (List.ofFn fun s => ({ u := (L.get s).u, v := (L.get s).v, w := (L.get s).w.transpose.transpose } : Matrix3Triad R)) = L := by have : (fun s => ({ u := (L.get s).u, v := (L.get s).v, w := (L.get s).w.transpose.transpose } : Matrix3Triad R)) = L.get := by funext s simp rw [this, List.ofFn_get] rw [← matrix3_valid_iff_trace_tensor_identity] rwa [heq] · rintro ⟨n, hlen, a, b, c, hid⟩ refine ⟨List.ofFn fun s => { u := a s, v := b s, w := (c s).transpose }, ?_, ?_⟩ · rw [List.length_ofFn] exact hlen · exact (matrix3_valid_iff_trace_tensor_identity n a b c).mpr hid