AFTD Auto-Formalizing Theoretical Domains

matrix3_valid_of_unit_checks

theoremverified

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

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.

  1. 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).

    lines 8–12

    uses matrix3_valid_of_unit_checks_cons, eval_matrix3_triad_smul_left, smul_add

      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]
  2. 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.

    lines 17–21

    uses matrix3_valid_of_unit_checks_cons, eval_matrix3_triad_smul_right, smul_add

      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]
  3. 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.

    line 25

    uses Matrix.smul_single, smul_eq_mul, mul_one

      rw [Matrix.smul_single, smul_eq_mul, mul_one]
  4. 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.

    lines 29–31

    uses Matrix.matrix_eq_sum_single, Finset.sum_congr, matrix3_valid_of_unit_checks_single_eq_smul

      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)
  5. 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.

    lines 39–43

    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_right

      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]
  6. 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.

    line 44

      simp_rw [h]
  7. 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.

    lines 45–47

    uses matrix3_valid_of_unit_checks_eq_sum_smul_single, Finset.sum_mul, Finset.mul_sum, smul_mul_assoc, mul_smul_comm

      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]
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

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]
See it in the graphDiscuss this resultChallenge it