AFTD Auto-Formalizing Theoretical Domains

matrix3_valid_cyclic_rotate

theoremverified

Cyclic rotation (u, v, w) ↦ (v, wᵀ, uᵀ) of every triad in a valid 3x3 matrix multiplication decomposition produces another valid decomposition of the same length.

Statement

theorem matrix3_valid_cyclic_rotate {R : Type*} [CommSemiring R]
    (L : List (Matrix3Triad R)) (hL : is_valid_matrix3_decomposition L) :
    is_valid_matrix3_decomposition
      (L.map fun t => ⟨t.v, t.w.transpose, t.u.transpose⟩)
Source
step towards matrix3_tensor_rank_int_le_22
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 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…
  • 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.

The proof, explained

A triad decomposition for 3x3 matrix multiplication is valid if and only if its triad matrices satisfy a trace-tensor identity. Under the cyclic rotation (u, v, w) ↦ (v, wᵀ, uᵀ), the component matrix sequences (a, b, c) are cyclically permuted to (b, c, a). The validity of the rotated decomposition follows by evaluating the original tensor identity at cyclically permuted indices and using the commutativity of scalar multiplication in R to reorder each summand.

  1. Let n be the length of L, and define matrix families a s = (L.get s).u, b s = (L.get s).v, and c s = (L.get s).wᵀ for s : Fin n.

    We extract the components of each triad in L into three sequences of 3x3 matrices indexed by s : Fin n, setting c s to be the transpose of the third component w so that (c s)ᵀ = w.

    lines 6–9

      let n := L.length
      let a : Fin n → Matrix (Fin 3) (Fin 3) R := fun s => (L.get s).u
      let b : Fin n → Matrix (Fin 3) (Fin 3) R := fun s => (L.get s).v
      let c : Fin n → Matrix (Fin 3) (Fin 3) R := fun s => (L.get s).w.transpose
  2. L is equal to the list of triads (a s, b s, (c s)ᵀ) over s : Fin n.

    Using List.ofFn_get, L can be written as List.ofFn L.get. Applying congr_arg and function extensionality (funext s), each triad L.get s simplifies definitionally to ⟨a s, b s, (c s)ᵀ⟩ since transpose is an involution.

    lines 10–14

    uses List.ofFn_get, congr_arg

      have hL_eq : L = List.ofFn (fun s => (⟨a s, b s, (c s).transpose⟩ : Matrix3Triad R)) := by
        nth_rw 1 [← List.ofFn_get L]
        apply congr_arg
        funext s
        simp [a, b, c]
  3. The matrices a, b, c satisfy the trace-tensor identity ∑ s, a s i j * b s j' k * c s k' i' = if j = j' ∧ k = k' ∧ i = i' then 1 else 0.

    Since L is assumed to be a valid decomposition, rewriting L in terms of a, b, and c and applying the forward direction of matrix3_valid_iff_trace_tensor_identity establishes the tensor identity for the original triads.

    lines 15–20

    uses matrix3_valid_iff_trace_tensor_identity

      have h_tensor : ∀ i j j' k k' i' : Fin 3,
          ∑ s, a s i j * b s j' k * c s k' i' =
            if j = j' ∧ k = k' ∧ i = i' then 1 else 0 := by
        have h_valid := hL
        rw [hL_eq] at h_valid
        exact (matrix3_valid_iff_trace_tensor_identity n a b c).mp h_valid
  4. The rotated triad list L.map (fun t => ⟨t.v, t.wᵀ, t.uᵀ⟩) equals List.ofFn (fun s => ⟨b s, c s, (a s)ᵀ⟩).

    Rewriting L as List.ofFn L.get via List.ofFn_get and pushing the map inside via List.map_ofFn leaves List.ofFn applied to the transformed triads (b s, c s, (a s)ᵀ), which matches by definition.

    lines 21–25

    uses List.ofFn_get, List.map_ofFn

      have h_map_eq : (L.map fun t => ⟨t.v, t.w.transpose, t.u.transpose⟩) =
          List.ofFn (fun s => (⟨b s, c s, (a s).transpose⟩ : Matrix3Triad R)) := by
        nth_rw 1 [← List.ofFn_get L]
        rw [List.map_ofFn]
        rfl
  5. To show the rotated list is a valid decomposition, it suffices to prove the trace-tensor identity ∑ s, b s I J * c s J' K * a s K' I' = if J = J' ∧ K = K' ∧ I = I' then 1 else 0 for all indices I, J, J', K, K', I'.

    Rewriting the goal with h_map_eq puts the rotated list into the standard List.ofFn form with matrix sequences b, c, a. Applying matrix3_valid_iff_trace_tensor_identity n b c a reduces validity to checking the tensor identity on arbitrary indices I, J, J', K, K', I'.

    lines 26–28

    uses matrix3_valid_iff_trace_tensor_identity

      rw [h_map_eq]
      rw [matrix3_valid_iff_trace_tensor_identity n b c a]
      intro I J J' K K' I'
  6. The required sum ∑ s, b s I J * c s J' K * a s K' I' equals the original tensor sum ∑ s, a s K' I' * b s I J * c s J' K.

    Instantiating the original tensor identity at indices (K', I', I, J, J', K) produces ∑ s, a s K' I' * b s I J * c s J' K = if I' = I ∧ J = J' ∧ K' = K then 1 else 0. By symmetry of equality and commutativity of conjunction (eq_comm, and_comm, and_left_comm), the condition I' = I ∧ J = J' ∧ K' = K is equivalent to J = J' ∧ K = K' ∧ I = I', making the if-then-else conditions identical. Substituting both identities rewrites the target value to the permuted sum.

    lines 29–34

    uses eq_comm, and_comm, and_left_comm

      have h_orig := h_tensor K' I' I J J' K
      have h_eq : (if I' = I ∧ J = J' ∧ K' = K then (1 : R) else 0) =
                  (if J = J' ∧ K = K' ∧ I = I' then (1 : R) else 0) := by
        congr 1
        simp only [eq_comm, and_comm, and_left_comm]
      rw [← h_eq, ← h_orig]
  7. The two sums are equal, completing the proof.

    By Finset.sum_congr, it suffices to show equality of the summands for each s : Fin n. The identity b s I J * c s J' K * a s K' I' = a s K' I' * b s I J * c s J' K holds by the commutativity and associativity of multiplication in the commutative semiring R, which ring solves.

    lines 35–37

    uses Finset.sum_congr

      apply Finset.sum_congr rfl
      intro s _
      ring
List.ofFn_get
A list l is equal to the list formed by evaluating its indexing function l.get across all indices.
congr_arg
If two inputs are equal, applying a function f to them produces equal results: a₁ = a₂ → f a₁ = f a₂.
matrix3_valid_iff_trace_tensor_identity
A decomposition given by triads (a s, b s, (c s)ᵀ) is valid if and only if ∑ s, a s i j * b s j' k * c s k' i' equals 1 when j = j', k = k', and i = i', and 0 otherwise.
List.map_ofFn
Mapping a function g over a list constructed via List.ofFn f is the same as List.ofFn (g ∘ f).
eq_comm
Equality is symmetric: a = b ↔ b = a.
and_comm
Logical conjunction is commutative: a ∧ b ↔ b ∧ a.
and_left_comm
The first two terms of an iterated conjunction can be swapped: a ∧ b ∧ c ↔ b ∧ a ∧ c.
Finset.sum_congr
Two finite sums are equal if their index domains are equal and their summands agree on every element in that domain.

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

/-- Cyclic rotation (u, v, w) ↦ (v, wᵀ, uᵀ) of every triad in a valid 3x3 matrix multiplication decomposition produces another valid decomposition of the same length. -/theorem matrix3_valid_cyclic_rotate {R : Type*} [CommSemiring R]    (L : List (Matrix3Triad R)) (hL : is_valid_matrix3_decomposition L) :    is_valid_matrix3_decomposition      (L.map fun t => ⟨t.v, t.w.transpose, t.u.transpose⟩) := by  let n := L.length  let a : Fin n → Matrix (Fin 3) (Fin 3) R := fun s => (L.get s).u  let b : Fin n → Matrix (Fin 3) (Fin 3) R := fun s => (L.get s).v  let c : Fin n → Matrix (Fin 3) (Fin 3) R := fun s => (L.get s).w.transpose  have hL_eq : L = List.ofFn (fun s => (⟨a s, b s, (c s).transpose⟩ : Matrix3Triad R)) := by    nth_rw 1 [← List.ofFn_get L]    apply congr_arg    funext s    simp [a, b, c]  have h_tensor : ∀ i j j' k k' i' : Fin 3,      ∑ s, a s i j * b s j' k * c s k' i' =        if j = j' ∧ k = k' ∧ i = i' then 1 else 0 := by    have h_valid := hL    rw [hL_eq] at h_valid    exact (matrix3_valid_iff_trace_tensor_identity n a b c).mp h_valid  have h_map_eq : (L.map fun t => ⟨t.v, t.w.transpose, t.u.transpose⟩) =      List.ofFn (fun s => (⟨b s, c s, (a s).transpose⟩ : Matrix3Triad R)) := by    nth_rw 1 [← List.ofFn_get L]    rw [List.map_ofFn]    rfl  rw [h_map_eq]  rw [matrix3_valid_iff_trace_tensor_identity n b c a]  intro I J J' K K' I'  have h_orig := h_tensor K' I' I J J' K  have h_eq : (if I' = I ∧ J = J' ∧ K' = K then (1 : R) else 0) =              (if J = J' ∧ K = K' ∧ I = I' then (1 : R) else 0) := by    congr 1    simp only [eq_comm, and_comm, and_left_comm]  rw [← h_eq, ← h_orig]  apply Finset.sum_congr rfl  intro s _  ring
See it in the graphDiscuss this resultChallenge it