matrix3_valid_cyclic_rotate
Cyclic rotation (u, v, w) ↦ (v, wᵀ, uᵀ) of every triad in a valid 3x3 matrix multiplication decomposition produces another valid decomposition of the same length.
Statement
theorem matrix3_valid_cyclic_rotate {R : Type*} [CommSemiring R] (L : List (Matrix3Triad R)) (hL : is_valid_matrix3_decomposition L) : is_valid_matrix3_decomposition (L.map fun t => ⟨t.v, t.w.transpose, t.u.transpose⟩)
- Source
- step towards matrix3_tensor_rank_int_le_22
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- 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…
- 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.
The proof, explained
A triad decomposition for 3x3 matrix multiplication is valid if and only if its triad matrices satisfy a trace-tensor identity. Under the cyclic rotation (u, v, w) ↦ (v, wᵀ, uᵀ), the component matrix sequences (a, b, c) are cyclically permuted to (b, c, a). The validity of the rotated decomposition follows by evaluating the original tensor identity at cyclically permuted indices and using the commutativity of scalar multiplication in R to reorder each summand.
Let n be the length of L, and define matrix families a s = (L.get s).u, b s = (L.get s).v, and c s = (L.get s).wᵀ for s : Fin n.
We extract the components of each triad in L into three sequences of 3x3 matrices indexed by s : Fin n, setting c s to be the transpose of the third component w so that (c s)ᵀ = w.
let n := L.length let a : Fin n → Matrix (Fin 3) (Fin 3) R := fun s => (L.get s).u let b : Fin n → Matrix (Fin 3) (Fin 3) R := fun s => (L.get s).v let c : Fin n → Matrix (Fin 3) (Fin 3) R := fun s => (L.get s).w.transpose
L is equal to the list of triads (a s, b s, (c s)ᵀ) over s : Fin n.
Using List.ofFn_get, L can be written as List.ofFn L.get. Applying congr_arg and function extensionality (funext s), each triad L.get s simplifies definitionally to ⟨a s, b s, (c s)ᵀ⟩ since transpose is an involution.
uses
List.ofFn_get,congr_arghave hL_eq : L = List.ofFn (fun s => (⟨a s, b s, (c s).transpose⟩ : Matrix3Triad R)) := by nth_rw 1 [← List.ofFn_get L] apply congr_arg funext s simp [a, b, c]
The matrices a, b, c satisfy the trace-tensor identity ∑ s, a s i j * b s j' k * c s k' i' = if j = j' ∧ k = k' ∧ i = i' then 1 else 0.
Since L is assumed to be a valid decomposition, rewriting L in terms of a, b, and c and applying the forward direction of matrix3_valid_iff_trace_tensor_identity establishes the tensor identity for the original triads.
uses
matrix3_valid_iff_trace_tensor_identityhave h_tensor : ∀ 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 have h_valid := hL rw [hL_eq] at h_valid exact (matrix3_valid_iff_trace_tensor_identity n a b c).mp h_valid
The rotated triad list L.map (fun t => ⟨t.v, t.wᵀ, t.uᵀ⟩) equals List.ofFn (fun s => ⟨b s, c s, (a s)ᵀ⟩).
Rewriting L as List.ofFn L.get via List.ofFn_get and pushing the map inside via List.map_ofFn leaves List.ofFn applied to the transformed triads (b s, c s, (a s)ᵀ), which matches by definition.
uses
List.ofFn_get,List.map_ofFnhave h_map_eq : (L.map fun t => ⟨t.v, t.w.transpose, t.u.transpose⟩) = List.ofFn (fun s => (⟨b s, c s, (a s).transpose⟩ : Matrix3Triad R)) := by nth_rw 1 [← List.ofFn_get L] rw [List.map_ofFn] rfl
To show the rotated list is a valid decomposition, it suffices to prove the trace-tensor identity ∑ s, b s I J * c s J' K * a s K' I' = if J = J' ∧ K = K' ∧ I = I' then 1 else 0 for all indices I, J, J', K, K', I'.
Rewriting the goal with h_map_eq puts the rotated list into the standard List.ofFn form with matrix sequences b, c, a. Applying matrix3_valid_iff_trace_tensor_identity n b c a reduces validity to checking the tensor identity on arbitrary indices I, J, J', K, K', I'.
uses
matrix3_valid_iff_trace_tensor_identityrw [h_map_eq] rw [matrix3_valid_iff_trace_tensor_identity n b c a] intro I J J' K K' I'
The required sum ∑ s, b s I J * c s J' K * a s K' I' equals the original tensor sum ∑ s, a s K' I' * b s I J * c s J' K.
Instantiating the original tensor identity at indices (K', I', I, J, J', K) produces ∑ s, a s K' I' * b s I J * c s J' K = if I' = I ∧ J = J' ∧ K' = K then 1 else 0. By symmetry of equality and commutativity of conjunction (eq_comm, and_comm, and_left_comm), the condition I' = I ∧ J = J' ∧ K' = K is equivalent to J = J' ∧ K = K' ∧ I = I', making the if-then-else conditions identical. Substituting both identities rewrites the target value to the permuted sum.
uses
eq_comm,and_comm,and_left_commhave h_orig := h_tensor K' I' I J J' K have h_eq : (if I' = I ∧ J = J' ∧ K' = K then (1 : R) else 0) = (if J = J' ∧ K = K' ∧ I = I' then (1 : R) else 0) := by congr 1 simp only [eq_comm, and_comm, and_left_comm] rw [← h_eq, ← h_orig]
The two sums are equal, completing the proof.
By Finset.sum_congr, it suffices to show equality of the summands for each s : Fin n. The identity b s I J * c s J' K * a s K' I' = a s K' I' * b s I J * c s J' K holds by the commutativity and associativity of multiplication in the commutative semiring R, which ring solves.
uses
Finset.sum_congrapply Finset.sum_congr rfl intro s _ ring
List.ofFn_get- A list l is equal to the list formed by evaluating its indexing function l.get across all indices.
congr_arg- If two inputs are equal, applying a function f to them produces equal results: a₁ = a₂ → f a₁ = f a₂.
matrix3_valid_iff_trace_tensor_identity- A decomposition given by triads (a s, b s, (c s)ᵀ) is valid if and only if ∑ s, a s i j * b s j' k * c s k' i' equals 1 when j = j', k = k', and i = i', and 0 otherwise.
List.map_ofFn- Mapping a function g over a list constructed via List.ofFn f is the same as List.ofFn (g ∘ f).
eq_comm- Equality is symmetric: a = b ↔ b = a.
and_comm- Logical conjunction is commutative: a ∧ b ↔ b ∧ a.
and_left_comm- The first two terms of an iterated conjunction can be swapped: a ∧ b ∧ c ↔ b ∧ a ∧ c.
Finset.sum_congr- Two finite sums are equal if their index domains are equal and their summands agree on every element in that domain.
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.
/-- Cyclic rotation (u, v, w) ↦ (v, wᵀ, uᵀ) of every triad in a valid 3x3 matrix multiplication decomposition produces another valid decomposition of the same length. -/theorem matrix3_valid_cyclic_rotate {R : Type*} [CommSemiring R] (L : List (Matrix3Triad R)) (hL : is_valid_matrix3_decomposition L) : is_valid_matrix3_decomposition (L.map fun t => ⟨t.v, t.w.transpose, t.u.transpose⟩) := by let n := L.length let a : Fin n → Matrix (Fin 3) (Fin 3) R := fun s => (L.get s).u let b : Fin n → Matrix (Fin 3) (Fin 3) R := fun s => (L.get s).v let c : Fin n → Matrix (Fin 3) (Fin 3) R := fun s => (L.get s).w.transpose have hL_eq : L = List.ofFn (fun s => (⟨a s, b s, (c s).transpose⟩ : Matrix3Triad R)) := by nth_rw 1 [← List.ofFn_get L] apply congr_arg funext s simp [a, b, c] have h_tensor : ∀ 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 have h_valid := hL rw [hL_eq] at h_valid exact (matrix3_valid_iff_trace_tensor_identity n a b c).mp h_valid have h_map_eq : (L.map fun t => ⟨t.v, t.w.transpose, t.u.transpose⟩) = List.ofFn (fun s => (⟨b s, c s, (a s).transpose⟩ : Matrix3Triad R)) := by nth_rw 1 [← List.ofFn_get L] rw [List.map_ofFn] rfl rw [h_map_eq] rw [matrix3_valid_iff_trace_tensor_identity n b c a] intro I J J' K K' I' have h_orig := h_tensor K' I' I J J' K have h_eq : (if I' = I ∧ J = J' ∧ K' = K then (1 : R) else 0) = (if J = J' ∧ K = K' ∧ I = I' then (1 : R) else 0) := by congr 1 simp only [eq_comm, and_comm, and_left_comm] rw [← h_eq, ← h_orig] apply Finset.sum_congr rfl intro s _ ring