matrix3_valid_transpose_swap
Transposing and swapping the two input factors along with transposing the output factor, (u, v, w) ↦ (vᵀ, uᵀ, wᵀ), preserves the validity of a 3x3 matrix multiplication decomposition.
Statement
theorem matrix3_valid_transpose_swap {R : Type*} [CommSemiring R] (L : List (Matrix3Triad R)) (hL : is_valid_matrix3_decomposition L) : is_valid_matrix3_decomposition (L.map fun t => ⟨t.v.transpose, t.u.transpose, t.w.transpose⟩)
- Source
- step towards matrix3_tensor_rank_int_le_22
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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.
- eval_matrix3_triadGiven a commutative semiring R, a triad t of type Matrix3Triad R, and 3x3 matrices A and B over R, eval_matrix3_triad t A B is the scalar…
- 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…
The proof, explained
To prove that the transformation (u, v, w) ↦ (vᵀ, uᵀ, wᵀ) preserves the validity of the matrix multiplication decomposition, we show that evaluating the transformed decomposition on matrices A and B equals the transpose of evaluating the original decomposition on Bᵀ and Aᵀ. At the level of each triad, swapping and transposing u and v transposes the index summations against A and B, which by commutativity of the ring and summation reordering leaves the scalar product unchanged while transposing the output matrix w. Summing over all triads and pulling transposition out of the sum yields (Bᵀ Aᵀ)ᵀ. The validity hypothesis on L then gives (Bᵀ Aᵀ)ᵀ = (Aᵀ)ᵀ (Bᵀ)ᵀ = A B.
Evaluating the transformed decomposition on matrices A and B reduces to evaluating the composite mapping of transformed triads over the list.
Fix arbitrary matrices A and B. By definition of validity (`is_valid_matrix3_decomposition`), we need to show that the transformed decomposition evaluated at A and B equals A * B. Unfolding `eval_matrix3_decomposition`, this evaluation is the sum of evaluating each transformed triad on A and B. Using `List.map_map`, we fuse the triad transformation `t ↦ (t.vᵀ, t.uᵀ, t.wᵀ)` and the triad evaluation function into a single mapped composite over L.
uses
List.map_mapintro A B unfold eval_matrix3_decomposition rw [List.map_map]
For any triad t, evaluating the transformed triad (t.vᵀ, t.uᵀ, t.wᵀ) on (A, B) equals the transpose of evaluating t on (Bᵀ, Aᵀ).
We prove the triad-level identity `h_triad` pointwise for an arbitrary triad t by function extensionality (`funext`). Unfolding `eval_matrix3_triad` and matrix transposition, evaluating the transformed triad on (A, B) produces the scalar `(∑ i j, t.v j i * A i j) * (∑ i j, t.u j i * B i j)` scaling the matrix `t.wᵀ`. In contrast, transposing the evaluation of t on (Bᵀ, Aᵀ) produces `(∑ i j, t.u i j * B j i) * (∑ i j, t.v i j * A j i)` scaling `t.wᵀ`. Exchanging summation indices in each double sum via `Finset.sum_comm` and applying the commutativity of multiplication (`mul_comm`), the two scalar factors coincide.
uses
Finset.sum_comm,mul_commhave h_triad : ((fun t => eval_matrix3_triad t A B) ∘ fun t : Matrix3Triad R => (⟨t.v.transpose, t.u.transpose, t.w.transpose⟩ : Matrix3Triad R)) = (Matrix.transpose ∘ fun t => eval_matrix3_triad t B.transpose A.transpose) := by funext t dsimp [eval_matrix3_triad, Matrix.transpose] congr 1 have h1 : (∑ i : Fin 3, ∑ j : Fin 3, t.v j i * A i j) = (∑ i : Fin 3, ∑ j : Fin 3, t.v i j * A j i) := by rw [Finset.sum_comm] have h2 : (∑ i : Fin 3, ∑ j : Fin 3, t.u j i * B i j) = (∑ i : Fin 3, ∑ j : Fin 3, t.u i j * B j i) := by rw [Finset.sum_comm] rw [h1, h2, mul_comm]
The evaluation sum of the transformed decomposition equals the transpose of the original decomposition evaluated on (Bᵀ, Aᵀ).
Rewriting the sum using `h_triad` replaces the transformed triad evaluations with the transposes of evaluations on (Bᵀ, Aᵀ). We separate the mapping back into two stages using `List.map_map` and pull the transposition outside the list summation using `Matrix.transpose_list_sum`. By definition, this yields the transpose of `eval_matrix3_decomposition L Bᵀ Aᵀ`.
uses
List.map_map,Matrix.transpose_list_sumrw [h_triad] rw [← List.map_map] rw [← Matrix.transpose_list_sum] change (eval_matrix3_decomposition L B.transpose A.transpose).transpose = A * B
Evaluating the transposed decomposition on (Bᵀ, Aᵀ) yields A * B, completing the proof.
Applying the validity hypothesis `hL` to Bᵀ and Aᵀ, the original decomposition evaluates to Bᵀ * Aᵀ. We then apply `Matrix.transpose_mul` to rewrite `(Bᵀ * Aᵀ)ᵀ` as `(Aᵀ)ᵀ * (Bᵀ)ᵀ`, and eliminate the double transpositions with `Matrix.transpose_transpose` to obtain A * B.
uses
Matrix.transpose_mul,Matrix.transpose_transposerw [hL B.transpose A.transpose] rw [Matrix.transpose_mul] rw [Matrix.transpose_transpose, Matrix.transpose_transpose]
List.map_map- Mapping two functions sequentially over a list is equivalent to mapping their composite function over the list: `(l.map f).map g = l.map (g ∘ f)`.
Finset.sum_comm- The order of summation in a finite double sum can be exchanged: `∑ x ∈ s, ∑ y ∈ t, f x y = ∑ y ∈ t, ∑ x ∈ s, f x y`.
mul_comm- Multiplication in a commutative magma is commutative: `a * b = b * a`.
Matrix.transpose_list_sum- The transpose of the sum of a list of matrices equals the sum of the transposes of the matrices in the list.
Matrix.transpose_mul- The transpose of a matrix product is the product of the transposes in reverse order: `(M * N)ᵀ = Nᵀ * Mᵀ`.
Matrix.transpose_transpose- Transposing a matrix twice returns the original matrix: `(Mᵀ)ᵀ = M`.
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.
/-- Transposing and swapping the two input factors along with transposing the output factor, (u, v, w) ↦ (vᵀ, uᵀ, wᵀ), preserves the validity of a 3x3 matrix multiplication decomposition. -/theorem matrix3_valid_transpose_swap {R : Type*} [CommSemiring R] (L : List (Matrix3Triad R)) (hL : is_valid_matrix3_decomposition L) : is_valid_matrix3_decomposition (L.map fun t => ⟨t.v.transpose, t.u.transpose, t.w.transpose⟩) := by intro A B unfold eval_matrix3_decomposition rw [List.map_map] have h_triad : ((fun t => eval_matrix3_triad t A B) ∘ fun t : Matrix3Triad R => (⟨t.v.transpose, t.u.transpose, t.w.transpose⟩ : Matrix3Triad R)) = (Matrix.transpose ∘ fun t => eval_matrix3_triad t B.transpose A.transpose) := by funext t dsimp [eval_matrix3_triad, Matrix.transpose] congr 1 have h1 : (∑ i : Fin 3, ∑ j : Fin 3, t.v j i * A i j) = (∑ i : Fin 3, ∑ j : Fin 3, t.v i j * A j i) := by rw [Finset.sum_comm] have h2 : (∑ i : Fin 3, ∑ j : Fin 3, t.u j i * B i j) = (∑ i : Fin 3, ∑ j : Fin 3, t.u i j * B j i) := by rw [Finset.sum_comm] rw [h1, h2, mul_comm] rw [h_triad] rw [← List.map_map] rw [← Matrix.transpose_list_sum] change (eval_matrix3_decomposition L B.transpose A.transpose).transpose = A * B rw [hL B.transpose A.transpose] rw [Matrix.transpose_mul] rw [Matrix.transpose_transpose, Matrix.transpose_transpose]