Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

CLRS Chapter 4, §4.1: Eight-Way Recursive Matrix Multiplication — Correctness and Cubic Counted Work

Proved
CLRS.Chapter4Publication.MatrixRecursive.correctness_and_running_time

by Chutong · Oct 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

algo2leanalgo2lean-clrs-chapter4-fd33cf9algorithmsclrslinear-algebrarunning-timetextbook

Reusable divide-and-conquer multiplication

Dividing matrix multiplication into smaller multiplications changes the execution structure without changing its mathematical result. The eight-way recursive algorithm in CLRS, fourth edition, Chapter 4 provides a concrete setting for relating a recursive cost recurrence to actual source calls. The formal result supplies matrix correctness, termination, preservation, fresh result rows, and a uniform cubic bound in one execution.

Matrices, valid sizes, and measured operations

The inputs are nested matrices, Seq[Seq[Int]], represented in an arbitrary heap hhh by references a,ba,ba,b and mathematical values A,BA,BA,B. The predicate MatrixHeap.Stored requires a valid outer array and valid row references at every integer outer index. Rows may alias within or between inputs. The finite problem occupies [0,n)×[0,n)[0,n)\times[0,n)[0,n)×[0,n); no zero-padding condition is imposed outside it, but those entries must also satisfy the heap representation premise.

The entry point is matrix_recursive(a, b, n), with dimension n=2kn=2^kn=2k for a natural depth k≥0k\ge0k≥0. Thus n≥1n\ge1n≥1. It allocates a zero result matrix and uses matrix_block to accumulate products into its disjoint fresh rows. Row, column, and inner-coordinate offsets select submatrices of the original inputs rather than creating copies of every quadrant.

Let MMM be the increment of multiplications and NNN the increment of calls. The first counts scalar products at leaves; the second counts invocations of matrix_block, including scalar leaves. Counted work is T=M+NT=M+NT=M+N, with unit weight on each clock.

Formalization targets

For every valid heap and input pair, establish a terminating compiled call returning a fresh RRR and a final heap h′h'h′ with

Rij=∑t=0n−1AitBtj(0≤i,j<n),Rij=0outside the square.R_{ij}=\sum_{t=0}^{n-1}A_{it}B_{tj}\quad(0\le i,j<n), \qquad R_{ij}=0\quad\text{outside the square}.Rij​=t=0∑n−1​Ait​Btj​(0≤i,j<n),Rij​=0outside the square.

All previously allocated caller rows, arrays, and objects remain unchanged; the finite output rows are fresh and pairwise distinct. The stable cost target quantifies its upper constant before every depth, heap, and input:

∃C∈N>0  ∀ valid inputs of size n=2k,n3≤T≤Cn3.\exists C\in\mathbb N_{>0}\;\forall\text{ valid inputs of size }n=2^k, \qquad n^3\le T\le C n^3.∃C∈N>0​∀ valid inputs of size n=2k,n3≤T≤Cn3.

The supporting exact specification is

M=8k=n3,N=C8(k),C8(0)=1,C8(k+1)=1+8C8(k).M=8^k=n^3,\qquad N=C_8(k),\qquad C_8(0)=1,\quad C_8(k+1)=1+8C_8(k).M=8k=n3,N=C8​(k),C8​(0)=1,C8​(k+1)=1+8C8​(k).

Lean proves 7C8(k)+1=8k+17C_8(k)+1=8^{k+1}7C8​(k)+1=8k+1 and 8k≤C8(k)≤2⋅8k8^k\le C_8(k)\le2\cdot8^k8k≤C8​(k)≤2⋅8k. Consequently 2n3≤T≤3n32n^3\le T\le3n^32n3≤T≤3n3 for every permitted size, strengthening the headline's lower bound. The upper witness C=3C=3C=3 is uniform; every unnamed clock has zero increment. Initial clock values are arbitrary and do not change the bound on increments.

What the formal result supplies

CLRS.Chapter4Publication.MatrixRecursive.correctness_and_running_time combines the actual returning call, mathematical product, preserved caller storage, fresh output allocation, exact clock increments, and uniform runtime bound. All these conclusions concern the same final heap.

The source execution summary identifies the actual final heap and counters of eight-way recursion. Its value and allocation theorems establish ordinary matrix multiplication in independently writable result rows. A caller reuses these properties together without reconstructing the recursive execution proof.

Where the specification needs care

Eight recursive products update overlapping output quadrants by accumulation. The full product claim must therefore account for previous contributions, coordinate offsets, and separation between writable result rows and input rows. A recurrence detached from these updates would establish neither the returned product nor its connection to the charged source execution.

Formalization scope and algorithm source

The verified entry point creates its own correctly separated output; callers need no separation between input matrices. A direct call to the lower-level matrix_block needs its separate writable-output contract. Dimension zero, non-power-of-two dimensions, automatic padding, and rectangular matrices are outside the main result. The code does not validate these size assumptions.

The exact standalone source is examples/matrix_recursive.algo, with proof examples/analysis/matrix_recursive.lean. The work model excludes row allocation, uncharged source operations, generated transition counts, elapsed time, and integer bit complexity. Alternative proofs must quantify over every valid represented input and establish actual compiled termination; assuming a returning call is insufficient. Compiler provenance is development commit fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41 from chutongyang98/Lean_formalization, branch codex/clrs-chapter-4, with Lean 4.26.0. This is not public v0.1.4. The proofs are handwritten analysis of generated definitions; exact generation alone does not prove the compiler correct. Algo2Lean was created by Lunjia Hu; Chutong Yang is a contributor, and both are software citation authors.

Selected references

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, fourth edition, MIT Press, 2022, Chapter 4, §4.1. Publisher.
  • Algo2Lean Chapter 4 development, commit fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41, 2026. Scope and theorem guide.

Formalization Note. The submitted headline is CLRS.Chapter4Publication.MatrixRecursive.correctness_and_running_time, from the combined contracts. It places the positive natural runtime constant before all input heaps, references, values, and dimensions. The actual returning call, mathematical product, storage preservation, fresh outer array, distinct fresh finite rows, exact clock increments, and runtime inequalities are conjuncts about the same final heap. The source repository pins Lean 4.26.0; this upload is checked in the separate Lean 4.33.1, Mathlib 0df444a360eaa60ab8c11dca51a86af692955474 environment. The compiler is the development snapshot fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41, not public Algo2Lean v0.1.4.

Platform namespace. The imported Chapter 4 source declarations live under CLRS in this upload to avoid collisions with independently published compiler versions. The immutable source reference retains the original declaration names.

Preamble
import Definitions.Def_CLRS_Chapter4_Algo2Lean
import Definitions.Def_CLRS_Chapter4_Algo2LeanExamples_MatrixMultiply
import Definitions.Def_CLRS_Chapter4_Algo2LeanExamples_MatrixMultiplyGenerated
import Definitions.Def_CLRS_Chapter4_Algo2LeanExamples_MatrixMultiplyPoints
import Definitions.Def_CLRS_Chapter4_Algo2LeanExamples_MatrixRecursive
import Definitions.Def_CLRS_Chapter4_Algo2LeanExamples_MatrixRecursiveGenerated
import Definitions.Def_CLRS_Chapter4_Algo2LeanExamples_MatrixStrassen
import Definitions.Def_CLRS_Chapter4_Algo2LeanExamples_MatrixStrassenGenerated
import Definitions.Def_CLRS_Chapter4_Algo2LeanExamples_MatrixStrassenPoints
import Definitions.Def_CLRS_Chapter4_Algo2LeanLib_CallCost
import Definitions.Def_CLRS_Chapter4_Algo2LeanLib_MatrixHeap
import Definitions.Def_CLRS_Chapter4_Publication_MatrixContracts
import Std

set_option autoImplicit false
set_option backward.isDefEq.respectTransparency false
set_option backward.defeqAttrib.useBackward true

namespace CLRS
end CLRS
open CLRS
open Algo2LeanCore Algo2LeanGenerated Algo2LeanCore.MatrixHeap
namespace CLRS.Chapter4Publication
end CLRS.Chapter4Publication
open CLRS.Chapter4Publication
namespace CLRS.Chapter4Publication.MatrixRecursive
end CLRS.Chapter4Publication.MatrixRecursive
open CLRS.Chapter4Publication CLRS.Chapter4Publication.MatrixRecursive

Formal statement
theorem CLRS.Chapter4Publication.MatrixRecursive.correctness_and_running_time :
    ∃ C : Nat, 0 < C ∧
      ∀ (heap : Heap) (a b : CollectionRef) (av bv : Values) (depth : Nat),
        Stored heap a av → Stored heap b bv →
        ∃ after result,
          MatrixRecursiveLibrary.matrix_recursive.Call heap (a, b, ((2^depth : Nat) : Int)) after result ∧
          Stored after result (product (2^depth) av bv) ∧ Extends heap after ∧
          heap.nextCollection ≤ result ∧ result < after.nextCollection ∧
          FreshRows heap after result (2^depth) ∧
          heap.Increments after (MatrixRecursiveAnalysis.costs depth) ∧
          ((2^depth : Nat)^3) ≤ runtime (heap.cost after) ∧
          runtime (heap.cost after) ≤ C*((2^depth : Nat)^3) := by sorry
Source
Algo2Lean Chapter 4 development, declaration Chapter4Publication.MatrixRecursive.correctness_and_running_time, immutable source fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41: https://github.com/chutongyang98/Lean_formalization/blob/fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41/proofs/chapter4/Publication/MatrixContracts.lean#L147-L186

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me