is_valid_matrix3_decomposition
Given 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 over R, eval_matrix3_decomposition L A B equals A * B.
Statement
def is_valid_matrix3_decomposition {R : Type*} [CommSemiring R] (L : List (Matrix3Triad R)) : Prop
- Defined in
- arXiv:2610.01639, Sec. 2.1, 5.1
- Verified
- 04 Oct 2026
- Axioms
- none listed
- Built on 2
- 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…
- Used by 23
- matrix3_shorter_valid_of_shared_u_wIf a list of triads written as L₁ ++ t₁ :: L₂ ++ t₂ :: L₃ is a valid decomposition of matrix multiplication, and t₁ and t₂ have the same u…
- 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…
- matrix3_tensor_rank_le_pred_of_zero_wIf a valid decomposition has length at most r and contains a triad with zero w matrix, then the tensor rank of 3x3 matrix multiplication…
- 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_pred_of_shared_u_vIf a valid decomposition has length at most r and contains two triads sharing u and v, then the tensor rank of 3x3 matrix multiplication…
- matrix3_tensor_rank_le_int_iff_unit_checkThe tensor rank of 3x3 matrix multiplication over ℤ is at most r if and only if there exists a list of at most r triads whose computable…
- matrix3_tensor_rank_le_zmod2_iff_unit_checkFor every natural number r, 3x3 matrix multiplication over ZMod 2 has a valid decomposition with at most r triads if and only if there is…
- matrix3_valid_transpose_swapTransposing and swapping the two input factors along with transposing the output factor, (u, v, w) ↦ (vᵀ, uᵀ, wᵀ), preserves the validity…
- 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…
- matrix3_tensor_rank_le_pred_of_shared_v_wIf a valid decomposition has length at most r and contains two triads sharing v and w, then the tensor rank of 3x3 matrix multiplication…
- matrix3_shorter_valid_of_shared_u_vIf a list of triads written as L₁ ++ t₁ :: L₂ ++ t₂ :: L₃ is a valid decomposition of matrix multiplication, and t₁ and t₂ have the same u…
- matrix3_tensor_rank_le_of_surjectiveIf f : R → S is a surjective homomorphism of commutative semirings and 3x3 matrix multiplication over R has a valid triad decomposition…
- matrix3_tensor_rank_geFor a commutative semiring R and a natural number r, matrix3_tensor_rank_ge R r asserts that for every list L of elements of Matrix3Triad…
- matrix3_tensor_rank_comm_ring_le_of_intFor any commutative ring R and any natural number r, if 3x3 matrix multiplication has tensor rank at most r over the integers, then 3x3…
- matrix3_tensor_rank_le_23_of_comm_ringOver every commutative ring R, 3x3 matrix multiplication has a valid bilinear decomposition with 23 products (the classical…
- 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…
- matrix3_tensor_rank_le_pred_of_zero_uIf a valid decomposition has length at most r and contains a triad with zero u matrix, then the tensor rank of 3x3 matrix multiplication…
- matrix3_tensor_rank_le_pred_of_zero_vIf a valid decomposition has length at most r and contains a triad with zero v matrix, then the tensor rank of 3x3 matrix multiplication…
- matrix3_tensor_rank_le_monoFor any commutative semiring R and natural numbers r₁ and r₂, if 3x3 matrix multiplication over R has tensor rank at most r₁ and r₁ ≤ r₂,…
- matrix3_shorter_valid_of_shared_v_wIf a list of triads written as L₁ ++ t₁ :: L₂ ++ t₂ :: L₃ is a valid decomposition of matrix multiplication, and t₁ and t₂ have the same v…
- matrix3_tensor_rank_le_pred_of_shared_u_wIf a valid decomposition has length at most r and contains two triads sharing u and w, then the tensor rank of 3x3 matrix multiplication…
Read back from the Lean
Given a commutative semiring R and a list L of Matrix3Triad R (triads of 3×3 matrices u, v, w over R), is_valid_matrix3_decomposition L asserts that for all 3×3 matrices A and B over R, the evaluated decomposition eval_matrix3_decomposition L A B equals the matrix product A * B. Here, the evaluation on A and B sums over each triad t in L the matrix (sA * sB) • t.w, where sA is the entrywise product sum ∑ i j, t.u i j * A i j and sB is ∑ i j, t.v i j * B i j.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A triad decomposition is valid for 3x3 matrix multiplication if it computes A * B for all A and B. -/ def is_valid_matrix3_decomposition {R : Type*} [CommSemiring R] (L : List (Matrix3Triad R)) : Prop := ∀ A B : Matrix (Fin 3) (Fin 3) R, eval_matrix3_decomposition L A B = A * B