AFTD Auto-Formalizing Theoretical Domains

matrix3_valid_transpose_swap

theoremverified

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.

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

    lines 6–8

    uses List.map_map

      intro A B
      unfold eval_matrix3_decomposition
      rw [List.map_map]
  2. 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.

    lines 9–19

    uses Finset.sum_comm, mul_comm

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

    lines 20–23

    uses List.map_map, Matrix.transpose_list_sum

      rw [h_triad]
      rw [← List.map_map]
      rw [← Matrix.transpose_list_sum]
      change (eval_matrix3_decomposition L B.transpose A.transpose).transpose = A * B
  4. 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.

    lines 24–26

    uses Matrix.transpose_mul, Matrix.transpose_transpose

      rw [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

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