AFTD Auto-Formalizing Theoretical Domains

matrix3_tensor_rank_le_pred_of_zero_v

theoremverified

If a valid decomposition has length at most r and contains a triad with zero v matrix, then the tensor rank of 3x3 matrix multiplication over R is at most r - 1.

Statement

theorem matrix3_tensor_rank_le_pred_of_zero_v {R : Type*} [CommSemiring R]
    (r : ℕ) (L₁ L₂ : List (Matrix3Triad R)) (t : Matrix3Triad R)
    (hv : t.v = 0)
    (hlen : (L₁ ++ t :: L₂).length ≤ r)
    (hval : is_valid_matrix3_decomposition (L₁ ++ t :: L₂)) :
    matrix3_tensor_rank_le R (r - 1)
Source
step towards matrix3_tensor_rank_int_le_22
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • 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.
  • matrix3_eval_triad_zero_vEvaluating any triad whose v component is zero yields the zero matrix for all input matrices A and B.
  • 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…
  • 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_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…
  • 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…

The proof, explained

To show that the tensor rank of 3x3 matrix multiplication is at most r - 1, we drop the triad t from the decomposition L₁ ++ t :: L₂ to obtain L₁ ++ L₂. Because the v component of t is zero, t evaluates to the zero matrix on any input pair and contributes nothing to the sum. Removing t therefore decreases the length of the decomposition by one while preserving the evaluated product A * B.

  1. It suffices to show that the concatenated list L₁ ++ L₂ has length at most r - 1 and forms a valid decomposition of 3x3 matrix multiplication.

    By definition of matrix3_tensor_rank_le, the tensor rank is at most r - 1 if there exists a valid decomposition of length at most r - 1. We propose the list L₁ ++ L₂, obtained by dropping the triad t from the original decomposition, as the witness.

    line 8

      refine ⟨L₁ ++ L₂, ?_, ?_⟩
  2. The length of L₁ ++ L₂ is at most r - 1.

    Rewriting with List.length_append and List.length_cons expands the original length bound |L₁ ++ t :: L₂| ≤ r to |L₁| + (|L₂| + 1) ≤ r. Linear integer arithmetic (omega) then proves that |L₁ ++ L₂| = |L₁| + |L₂| ≤ r - 1.

    lines 9–10

    uses List.length_append, List.length_cons

      · simp only [List.length_append, List.length_cons] at hlen ⊢
        omega
  3. For arbitrary matrices A and B, the validity of the shortened decomposition reduces to showing that the sum of triad evaluations over L₁ plus that over L₂ equals A * B.

    We introduce arbitrary matrices A and B and specialize the validity of the original decomposition hval to them. Unfolding eval_matrix3_decomposition and distributing list mapping and summation across append and cons (via List.map_append, List.map_cons, List.sum_cons, and List.sum_append), the evaluation of L₁ ++ t :: L₂ is expressed as the sum over L₁ plus eval_matrix3_triad t A B plus the sum over L₂.

    lines 11–14

    uses List.map_append, List.map_cons, List.sum_cons, List.sum_append

      · intro A B
        have h := hval A B
        simp only [eval_matrix3_decomposition, List.map_append,
          List.map_cons, List.sum_cons, List.sum_append] at h ⊢
  4. The triad t evaluates to the zero matrix on A and B.

    Decomposing t into its components ⟨u, v, w⟩, the hypothesis hv becomes v = 0. Substituting v = 0, the lemma matrix3_eval_triad_zero_v shows that any triad with zero middle matrix evaluates to zero on any inputs A and B.

    lines 15–20

    uses matrix3_eval_triad_zero_v

        have hzero : eval_matrix3_triad t A B = 0 := by
          cases t with
          | mk u v w =>
            simp only at hv
            subst v
            exact matrix3_eval_triad_zero_v u w A B
  5. The candidate decomposition L₁ ++ L₂ is valid, completing the proof.

    Substituting eval_matrix3_triad t A B = 0 into the evaluated original decomposition replaces t's contribution with zero. Simplifying 0 + sum(L₂) to sum(L₂) shows that the shortened decomposition evaluates to A * B, as required.

    lines 21–22

        rw [hzero] at h
        simpa using h
List.length_append
The length of the concatenation of two lists is the sum of their lengths.
List.length_cons
Prepending an element to a list increases its length by one.
List.map_append
Mapping a function over the concatenation of two lists equals the concatenation of the mapped lists.
List.map_cons
Mapping a function over a list with a prepended element applies the function to the head and prepends it to the mapped tail.
List.sum_append
The sum of elements in the concatenation of two lists is the sum of the elements of the first list plus the sum of the elements of the second list.
List.sum_cons
The sum of a list with head a and tail l is a plus the sum of l.
matrix3_eval_triad_zero_v
Evaluating a 3x3 matrix multiplication triad whose second matrix component v is zero on any two matrices yields the zero matrix.

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

/-- If a valid decomposition has length at most r and contains a triad with zero v matrix, then the tensor rank of 3x3 matrix multiplication over R is at most r - 1. -/theorem matrix3_tensor_rank_le_pred_of_zero_v {R : Type*} [CommSemiring R]    (r : ℕ) (L₁ L₂ : List (Matrix3Triad R)) (t : Matrix3Triad R)    (hv : t.v = 0)    (hlen : (L₁ ++ t :: L₂).length ≤ r)    (hval : is_valid_matrix3_decomposition (L₁ ++ t :: L₂)) :    matrix3_tensor_rank_le R (r - 1) := by  refine ⟨L₁ ++ L₂, ?_, ?_⟩  · simp only [List.length_append, List.length_cons] at hlen ⊢    omega  · intro A B    have h := hval A B    simp only [eval_matrix3_decomposition, List.map_append,      List.map_cons, List.sum_cons, List.sum_append] at h ⊢    have hzero : eval_matrix3_triad t A B = 0 := by      cases t with      | mk u v w =>        simp only at hv        subst v        exact matrix3_eval_triad_zero_v u w A B    rw [hzero] at h    simpa using h
See it in the graphDiscuss this resultChallenge it