Ordinary multiplication: every returned finite row is fresh and distinct
ProvedCLRS.MatrixMultiplyAnalysis.every_execution_fresh_rowsLet be natural, let the initial heap store both input nested matrices, and
let a completed matrix_multiply run return outer array in a final heap.
Write for the initial next unused row identifier. For every ,
the returned row reference is exactly , lies strictly above , and is
allocated in the final heap. Moreover,
The result applies to every completed run, including with shared input rows. For the finite-row assertions are vacuous. This supplies the allocation guarantee needed to mutate one returned row independently of another.
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.every_execution_fresh_rows (h after : Heap) (a b result : CollectionRef)
(av bv : Values) (n : Nat) (va : Stored h a av) (vb : Stored h b bv)
(run : matrix_multiply.Run h (a, b, n) after result) :
(∀ i : Nat, i < n → rows.get after result i = some (h.nextRef + 1 + i) ∧
h.nextRef < h.nextRef + 1 + i ∧ h.nextRef + 1 + i < after.nextRef) ∧
(∀ i j : Nat, i < n → j < n → i ≠ j →
rows.get after result i ≠ rows.get after result j) := by sorry