matrix3_valid_of_unit_checks
If 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 decomposition: eval L A B = A * B for all 3x3 matrices A, B over R.
Statement
theorem matrix3_valid_of_unit_checks {R : Type*} [CommSemiring R] (L : List (Matrix3Triad R)) (h : ∀ i j k l : Fin 3, eval_matrix3_decomposition L (Matrix.single i j (1 : R)) (Matrix.single k l (1 : R)) = Matrix.single i j (1 : R) * Matrix.single k l (1 : R)) : is_valid_matrix3_decomposition L
- Source
- step towards matrix3_tensor_rank_zmod2_le_22
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- eval_matrix3_triad_smul_leftGiven a commutative semiring R, a triad t of type Matrix3Triad R, a scalar c : R, and matrices A and B, eval_matrix3_triad t (c • A) B…
- eval_matrix3_triad_smul_rightGiven a commutative semiring R, a triad t of type Matrix3Triad R, a scalar c : R, and matrices A and B, eval_matrix3_triad t A (c • B)…
- eval_matrix3_decomposition_sum_leftGiven a commutative semiring R, a finite set s, a list L of triads, a family of matrices F, and a matrix B, evaluating L on (∑ i ∈ s, F i)…
- eval_matrix3_decomposition_sum_rightGiven a commutative semiring R, a finite set s, a list L of triads, a matrix A, and a family of matrices G, evaluating L on A and (∑ i ∈…
- 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…
- 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…
- Used by 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…
- 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…
The proof, explained
The theorem is proved by bilinearity. Since every 3x3 matrix expands as a linear combination of the standard matrix units, both the triad decomposition evaluation and standard matrix multiplication expand into identical sums over all pairs of basis units. Applying the hypothesis that the decomposition agrees with matrix multiplication on all 81 pairs of matrix units reduces both sides to the same expression, completing the proof.
Evaluation of a decomposition is homogeneous in its first argument: eval_matrix3_decomposition L (c • A) B = c • eval_matrix3_decomposition L A B.
We proceed by induction on the list of triads L. If L is empty, both sides evaluate to zero. For the inductive step t :: L', evaluation splits as the evaluation of triad t plus that of L' via matrix3_valid_of_unit_checks_cons. The claim then follows from left-scalar linearity of a single triad (eval_matrix3_triad_smul_left), the induction hypothesis ih, and distributivity of scalar multiplication over addition (smul_add).
uses
matrix3_valid_of_unit_checks_cons,eval_matrix3_triad_smul_left,smul_addinduction L with | nil => simp [eval_matrix3_decomposition] | cons t L' ih => rw [matrix3_valid_of_unit_checks_cons, matrix3_valid_of_unit_checks_cons, eval_matrix3_triad_smul_left, ih, smul_add]
Evaluation of a decomposition is homogeneous in its second argument: eval_matrix3_decomposition L A (c • B) = c • eval_matrix3_decomposition L A B.
We proceed by induction on the list L, analogously to the left argument. The empty list evaluates to zero. For the inductive step t :: L', we split the evaluation with matrix3_valid_of_unit_checks_cons, apply right-scalar linearity for the single triad t via eval_matrix3_triad_smul_right, use the induction hypothesis ih, and distribute scalar multiplication over addition with smul_add.
uses
matrix3_valid_of_unit_checks_cons,eval_matrix3_triad_smul_right,smul_addinduction L with | nil => simp [eval_matrix3_decomposition] | cons t L' ih => rw [matrix3_valid_of_unit_checks_cons, matrix3_valid_of_unit_checks_cons, eval_matrix3_triad_smul_right, ih, smul_add]
A single-entry matrix with value c at position (i, j) equals the scalar multiple c of the unit matrix at (i, j): Matrix.single i j c = c • Matrix.single i j 1.
Rewriting by Matrix.smul_single moves the scalar inside to form the entry c • 1, which simplifies to c * 1 by smul_eq_mul and then to c by mul_one.
uses
Matrix.smul_single,smul_eq_mul,mul_onerw [Matrix.smul_single, smul_eq_mul, mul_one]Every 3x3 matrix A decomposes as a double sum of its entries scaling the standard matrix units: A = ∑ i, ∑ j, A i j • Matrix.single i j 1.
By Matrix.matrix_eq_sum_single, A is the double sum over all coordinates of single-entry matrices containing A i j. Using Finset.sum_congr to rewrite each term, we replace each single-entry matrix with A i j • Matrix.single i j 1 using matrix3_valid_of_unit_checks_single_eq_smul.
uses
Matrix.matrix_eq_sum_single,Finset.sum_congr,matrix3_valid_of_unit_checks_single_eq_smulnth_rw 1 [Matrix.matrix_eq_sum_single A] refine Finset.sum_congr rfl (fun i _ => Finset.sum_congr rfl (fun j _ => ?_)) exact matrix3_valid_of_unit_checks_single_eq_smul i j (A i j)
For any matrices A and B, eval_matrix3_decomposition L A B expands by bilinearity to the four-fold sum ∑ i, ∑ j, ∑ k, ∑ l, A i j • B k l • eval_matrix3_decomposition L (Matrix.single i j 1) (Matrix.single k l 1).
After introducing arbitrary matrices A and B, we substitute both A and B in eval_matrix3_decomposition L A B with their expansions as sums of scaled matrix units using matrix3_valid_of_unit_checks_eq_sum_smul_single. We then pull the double sums out using eval_matrix3_decomposition_sum_left and eval_matrix3_decomposition_sum_right, and pull the scalar factors out using matrix3_valid_of_unit_checks_smul_left and matrix3_valid_of_unit_checks_smul_right.
uses
matrix3_valid_of_unit_checks_eq_sum_smul_single,eval_matrix3_decomposition_sum_left,eval_matrix3_decomposition_sum_right,matrix3_valid_of_unit_checks_smul_left,matrix3_valid_of_unit_checks_smul_rightintro A B nth_rw 1 [matrix3_valid_of_unit_checks_eq_sum_smul_single A] nth_rw 1 [matrix3_valid_of_unit_checks_eq_sum_smul_single B] simp_rw [eval_matrix3_decomposition_sum_left, eval_matrix3_decomposition_sum_right, matrix3_valid_of_unit_checks_smul_left, matrix3_valid_of_unit_checks_smul_right]The four-fold sum simplifies by replacing evaluation on each pair of matrix units with their matrix product.
We rewrite the evaluation on each pair of standard matrix units using the hypothesis h, which asserts that L evaluates to the matrix product on all 81 pairs of matrix units.
simp_rw [h]
The four-fold sum equals A * B, proving that L is a valid decomposition.
On the right-hand side, we expand both A and B in A * B as double sums of scaled matrix units using matrix3_valid_of_unit_checks_eq_sum_smul_single. Distributing multiplication over both sums with Finset.sum_mul and Finset.mul_sum, and commuting scalar multiplication with matrix products via smul_mul_assoc and mul_smul_comm, equates the product of the two double sums with the four-fold sum on the left-hand side.
uses
matrix3_valid_of_unit_checks_eq_sum_smul_single,Finset.sum_mul,Finset.mul_sum,smul_mul_assoc,mul_smul_commnth_rw 2 [matrix3_valid_of_unit_checks_eq_sum_smul_single A] nth_rw 2 [matrix3_valid_of_unit_checks_eq_sum_smul_single B] simp_rw [Finset.sum_mul, Finset.mul_sum, smul_mul_assoc, mul_smul_comm]
matrix3_valid_of_unit_checks_cons- The evaluation of a list of triads prepended with a triad t is the sum of the evaluation of t and the evaluation of the remaining list.
eval_matrix3_triad_smul_left- The evaluation of a single triad is homogeneous in its first matrix argument: scaling A by a scalar c scales the output matrix by c.
smul_add- Scalar multiplication distributes over addition: c • (x + y) = c • x + c • y.
eval_matrix3_triad_smul_right- The evaluation of a single triad is homogeneous in its second matrix argument: scaling B by a scalar c scales the output matrix by c.
Matrix.smul_single- Scaling a single-entry matrix by a scalar r scales the value at that position by r.
smul_eq_mul- Scalar multiplication of a semiring on itself coincides with multiplication: a • b = a * b.
mul_one- Multiplying an element by 1 on the right leaves it unchanged: a * 1 = a.
Matrix.matrix_eq_sum_single- Any matrix is equal to the sum over all index pairs of the single-entry matrices containing its entries.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree at every index.
matrix3_valid_of_unit_checks_single_eq_smul- A single-entry matrix with value c at position (i, j) is equal to c times the standard unit matrix at (i, j).
matrix3_valid_of_unit_checks_eq_sum_smul_single- Any 3x3 matrix equals the double sum over all coordinates of its entries scaling the corresponding matrix units.
eval_matrix3_decomposition_sum_left- Evaluation of a triad decomposition distributes over finite sums in its first matrix argument.
eval_matrix3_decomposition_sum_right- Evaluation of a triad decomposition distributes over finite sums in its second matrix argument.
matrix3_valid_of_unit_checks_smul_left- Evaluation of a triad decomposition commutes with scalar multiplication on its first matrix argument.
matrix3_valid_of_unit_checks_smul_right- Evaluation of a triad decomposition commutes with scalar multiplication on its second matrix argument.
Finset.sum_mul- Multiplication on the right distributes over a finite sum: (∑ i, f i) * a = ∑ i, f i * a.
Finset.mul_sum- Multiplication on the left distributes over a finite sum: a * (∑ i, f i) = ∑ i, a * f i.
smul_mul_assoc- Associativity of scalar multiplication with matrix multiplication: (r • x) * y = r • (x * y).
mul_smul_comm- Commutation of scalar multiplication with matrix multiplication: x * (s • y) = s • (x * y).
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.
lemma matrix3_valid_of_unit_checks_cons {R : Type*} [CommSemiring R] (t : Matrix3Triad R) (L : List (Matrix3Triad R)) (A B : Matrix (Fin 3) (Fin 3) R) : eval_matrix3_decomposition (t :: L) A B = eval_matrix3_triad t A B + eval_matrix3_decomposition L A B := rfllemma matrix3_valid_of_unit_checks_smul_left {R : Type*} [CommSemiring R] (L : List (Matrix3Triad R)) (c : R) (A B : Matrix (Fin 3) (Fin 3) R) : eval_matrix3_decomposition L (c • A) B = c • eval_matrix3_decomposition L A B := by induction L with | nil => simp [eval_matrix3_decomposition] | cons t L' ih => rw [matrix3_valid_of_unit_checks_cons, matrix3_valid_of_unit_checks_cons, eval_matrix3_triad_smul_left, ih, smul_add]lemma matrix3_valid_of_unit_checks_smul_right {R : Type*} [CommSemiring R] (L : List (Matrix3Triad R)) (c : R) (A B : Matrix (Fin 3) (Fin 3) R) : eval_matrix3_decomposition L A (c • B) = c • eval_matrix3_decomposition L A B := by induction L with | nil => simp [eval_matrix3_decomposition] | cons t L' ih => rw [matrix3_valid_of_unit_checks_cons, matrix3_valid_of_unit_checks_cons, eval_matrix3_triad_smul_right, ih, smul_add]lemma matrix3_valid_of_unit_checks_single_eq_smul {R : Type*} [CommSemiring R] (i j : Fin 3) (c : R) : Matrix.single i j c = c • Matrix.single i j (1 : R) := by rw [Matrix.smul_single, smul_eq_mul, mul_one]lemma matrix3_valid_of_unit_checks_eq_sum_smul_single {R : Type*} [CommSemiring R] (A : Matrix (Fin 3) (Fin 3) R) : A = ∑ i : Fin 3, ∑ j : Fin 3, A i j • Matrix.single i j (1 : R) := by nth_rw 1 [Matrix.matrix_eq_sum_single A] refine Finset.sum_congr rfl (fun i _ => Finset.sum_congr rfl (fun j _ => ?_)) exact matrix3_valid_of_unit_checks_single_eq_smul i j (A i j)/-- Agreement with matrix multiplication on the 81 matrix-unit pairs extends to all pairs of matrices, because both sides are bilinear and every matrix is a sum of matrix units. -/theorem matrix3_valid_of_unit_checks {R : Type*} [CommSemiring R] (L : List (Matrix3Triad R)) (h : ∀ i j k l : Fin 3, eval_matrix3_decomposition L (Matrix.single i j (1 : R)) (Matrix.single k l (1 : R)) = Matrix.single i j (1 : R) * Matrix.single k l (1 : R)) : is_valid_matrix3_decomposition L := by intro A B nth_rw 1 [matrix3_valid_of_unit_checks_eq_sum_smul_single A] nth_rw 1 [matrix3_valid_of_unit_checks_eq_sum_smul_single B] simp_rw [eval_matrix3_decomposition_sum_left, eval_matrix3_decomposition_sum_right, matrix3_valid_of_unit_checks_smul_left, matrix3_valid_of_unit_checks_smul_right] simp_rw [h] nth_rw 2 [matrix3_valid_of_unit_checks_eq_sum_smul_single A] nth_rw 2 [matrix3_valid_of_unit_checks_eq_sum_smul_single B] simp_rw [Finset.sum_mul, Finset.mul_sum, smul_mul_assoc, mul_smul_comm]