Ordinary multiplication: completion of one output row
ProvedCLRS.MatrixMultiplyAnalysis.columns_loopFix natural dimension , output row index , natural remaining-column count
, and integer first column with . At the named columns loop,
the observed arguments and result-row reference must agree with these values.
The current heap extends an original heap representing both inputs. The result
row is valid in the current heap and fresh relative to the original heap.
Then the remainder of matrix_row terminates, writes the ordinary -term
dot-product entry at each of the next columns, and returns the same row.
The final heap is exactly the specified finite row-fill operation followed by this clock increment. The dot-product entry is zero outside the specified finite square. This contract permits shared input rows and nonzero initial counters, and composes a completed row without rebuilding its inner-loop proof.
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.
Catalog organization (2026-10-11). This record was retired from the active Chapter 4 catalog to focus the presentation on three algorithms and four reusable recurrence results. Its mathematical statement and proof status are unchanged, and existing imports and links remain valid. The retained results are CLRS.Chapter4Publication.MatrixMultiply.correctness_and_running_time. Supporting lemmas needed by the retained results are included in their accepted proof files.
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_Algo2LeanLib_MatrixHeap 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 MatrixMultiplyLibrary MatrixMultiplyLibrary.Algo2LeanGenerated open Algo2LeanCore Algo2LeanGenerated open Algo2LeanCore.MatrixHeap namespace CLRS.MatrixMultiplyAnalysis end CLRS.MatrixMultiplyAnalysis open CLRS.MatrixMultiplyAnalysis
theorem CLRS.MatrixMultiplyAnalysis.columns_loop (count : Nat) (state : Configuration) (original : Heap)
(a b : CollectionRef) (av bv : Values) (result : SeqRef) (n : Nat) (row first : Int)
(location : matrix_row.At.columns_loop state)
(ra : matrix_row.Local.a state = some a)
(rb : matrix_row.Local.b state = some b)
(rn : matrix_row.Local.n state = some (n : Int))
(rr : matrix_row.Local.row state = some row)
(ro : matrix_row.Local.result state = some result)
(ri : matrix_row.Local.column state = some first)
(bound : first + (count : Int) = n)
(va : Stored original a av) (vb : Stored original b bv)
(extension : Extends original state.heap) (fresh : original.nextRef ≤ result)
(valid : result < state.heap.nextRef) :
matrix_row.CallFrom state
((fill state.heap result (entry av bv n row) first count).tick
"multiply_add" (count * n)) result := by sorry