Extend the original example by a matrix $D$ with matrix dimensions $3\times 15$, so $(p_0,p_1,p_2,p_3,p_4)=(12,5,40,3,15)$. The Catalan number $C_3=5$ counts all possible groupings. Their scalar multiplication costs areThe optimum is $(A(BC))D$, with cost $1320$. Enumeration makes a useful check here, but dynamic programming reaches the same answer by solving ten integer intervals, including the four single-matrix base cases:For example, $m[2,4]=\min \{1800+5\cdot 40\cdot 15,600+5\cdot 3\cdot 15\}=\min \{4800,825\}=825$. The three final-split candidates for the full matrix product supply a compact certificate:The first candidate already uses the better grouping of $BCD$; the worse $A(B(CD))$ need not be reconsidered at the top level. This is how optimal substructure lets the table represent all five possibilities with only three final candidates.

Read $s[1,4]=3$, which separates $ABC$ from $D$. Then $s[1,3]=1$ separates $A$ from $BC$, and $s[2,3]=2$ separates $B$ from $C$. This recursion stops at every $i=j$, returning the corresponding matrix name. Combining the returned expressions recovers $(A(BC))D$, rather than only its cost. Every recursive call uses a shorter integer interval, establishing algorithm termination; a tied minimum may choose any attaining split. The recovered binary tree has $n$ leaves and $n-1$ internal nodes, so reconstruction takes $O(n)$ steps. Its attraction is the separation between an enormous family of groupings and a small set of reusable dynamic programming states.

Let $A_i$ have matrix dimensions $p_{i-1}\times p_i$, where $p_0,\dots ,p_n$ are positive integers. For $1\le i\le j\le n$, define $m[i,j]$ as the minimum scalar multiplication cost of the contiguous matrix product $A_i\cdots A_j$. The endpoints $(i,j)$ of an integer interval identify a dynamic programming state. A single matrix needs no matrix multiplication, giving the base case $m[i,i]=0$. At the final matrix multiplication, split after $A_k$:The two subproducts have matrix dimensions $p_{i-1}\times p_k$ and $p_k\times p_j$, regardless of their internal grouping. The recurrence relation adds their optimal costs and the final scalar multiplication cost.^[ref]

Why is this optimal substructure? For a chosen final split $k$, replacing either subproduct's grouping by a cheaper one leaves its matrix dimensions and exact matrix product unchanged, so it decreases the whole cost by the same amount. Therefore an optimal grouping can use optimal groupings on both sides. Conversely, each candidate in the recurrence relation joins two achievable groupings. Mathematical induction on $j-i+1$, starting with the single-matrix base case, proves that the minimum is achievable and no grouping is cheaper.

There are also overlapping subproblems: while evaluating the different final splits of $ABCD$, the cases $A(BCD)$ and $(ABC)D$ both request the cost of $BC$. Recursion without reuse recomputes this answer; memoization or a dynamic programming table stores it once. Fill the table by increasing length $j-i+1$, so both dependencies are ready. Record an attaining split $s[i,j]$ alongside each cost.^[ref]

The dynamic programming table has $n(n+1)/2$ cost entries. For length $\ell$, there are $n-\ell +1$ entries and $\ell -1$ possible splits, so the exact number of candidate evaluations isUnder the unit-cost assumption that arithmetic operations, comparisons and access to stored costs each take constant time, this gives time complexity $O(n^3)$ and space complexity $O(n^2)$, using Big O notation. These bounds concern choosing a grouping from the matrix dimensions; they exclude the subsequent matrix multiplication work. If the dimensions or costs require arbitrarily long integers, their arithmetic and storage costs must also be counted.

For matrix dimensions $r\times s$ and $s\times t$, ordinary matrix multiplication computes $rt$ matrix entries, each using $s$ scalar multiplications. Thus its cost is $rst$ scalar multiplications, with $rt(s-1)$ additions if each sum starts from its first term. Here we minimize only the scalar multiplication count, using this dense matrix multiplication rule throughout. The counts describe arithmetic operations, rather than measured elapsed time; matrix multiplication methods that exploit structure or use faster formulas require a different cost rule.

Take matrices $A$, $B$, $C$ with matrix dimensions $12\times 5$, $5\times 40$, $40\times 3$. Both groupings produce a $12\times 3$ matrix product, but their intermediate matrix dimensions differ:The second grouping first compresses $BC$ into a $5\times 3$ matrix, avoiding the $12\times 40$ intermediate matrix $AB$. The saving is $3060$ scalar multiplications, although both groupings use exactly two matrix multiplications. This is why counting only matrix multiplication operations hides the interesting choice.

Associativity permits these regroupings in exact arithmetic; commutativity is neither assumed nor generally true for matrix multiplication. Swapping $A$ and $B$ here would even make their matrix product undefined. In floating-point arithmetic, round-off error can make the two groupings yield different computed matrix entries; the cost optimum alone does not guarantee the smallest numerical error.

Project documentation with no individual byline.

Online text: matplotlib.org/3.10.7/gallery/scales/log_demo.html

Cited passages: Convenience functions semilogx, semilogy, and loglog; Logarithms with other bases; Dealing with negative values.

Build identifier: v3.10.7-3-g1f3ab23ea7. The footer credits copyright holders; those names are not article bylines.

Lecture notes in Math 221, Matrix Computations, Fall 2023, dated 1 December 2023 in the heading. No explicit author byline or institutional authorship is established. The University of California, Berkeley EECS faculty website hosts the notes; James Demmel is the course instructor. The lecture date is distinct from any publication or revision date.

Lecture notes: people.eecs.berkeley.edu/~demmel/ma221_Fall23/Lectures/Lecture_15.pdf

Cited passages: PDF p. 1 heading and opening left/symmetric transformations; PDF p. 1, Preconditioned CG algorithm and equivalent symmetric system; PDF p. 1, goals (1) and (2), M = I and M = A comparison, example (1) Jacobi preconditioning; PDF p. 2, example (3) triangular factor solves; Course homepage, title and Instructor section, web lines 2–14.

Lecture notes in Math 221, Matrix Computations, Fall 2009, dated 10 November 2009 in the heading. The page has no explicit author byline. James Demmel is the verified course instructor; the University of California, Berkeley EECS faculty website hosts the notes. No separate publication date or institutional authorship is asserted.

Online text: people.eecs.berkeley.edu/~demmel/ma221_Fall09/Lectures/Lecture_21.html

Cited passages: Basic iterative methods, splitting and recurrence (*); spectral-radius lemmas and convergence-for-all-starts theorem; Jacobi and Gauss-Seidel component loops; strict row diagonal dominance, Theorem 1 and proof; 1D Dirichlet Poisson matrix and sine eigenvectors.

Additional cited passages: opening solver building blocks; Gauss-Seidel component loop, splitting, ordering remark and red-black scheduling; Theorem 1, strict row diagonal dominance; Theorem 3, SOR convergence for symmetric positive-definite matrices with the ω = 1 specialization. The lecture date and instructor association above remain distinct from author bylines and publication dates.

In Mass spectra and isotopes by Francis William Aston, printed pp. 10–12, Fig. 1, Francis William Aston describes successive electric and magnetic deflections in one plane, with opposite senses. This geometry focuses a range of ion speeds; it does not require the straight-through cancellation of a velocity selector.

The reason compensation is possible follows from the Lorentz force. In a short region of length ${\ell }_E$, a small electric deflection angle has magnitude ${\theta }_E\simeq qE{\ell }_E/(m{v}^2)$: the transverse acceleration acts for a time ${\ell }_E/v$, and the deflection angle is the acquired transverse velocity divided by $v$. A short magnetic region of length ${\ell }_B$ gives ${\theta }_B\simeq qB{\ell }_B/(mv)$, since the magnetic force already contains one factor of speed. Slower ions therefore receive a disproportionately larger electric deflection.

An original local approximation makes the focusing idea explicit. At fixed mass-to-charge ratio, replace each region by a small angular kick and include the drift distances in two positive constants $a$ and $b$. With $t=v/v_0$, write the detector coordinate asChoosing the geometry and fields so that $b=2a$ eliminates the first-order speed sensitivity. Indeed,A fractional speed error $\epsilon =t-1$ then contributes only at order ${\epsilon }^2$ in this approximation. This is a local thin-kick explanation, not Aston's exact pole geometry, focal-plane equation, or a prediction of its measured mass resolution. Finite slit widths, initial directions, and field boundaries still matter. Unlike a velocity selector, focusing can collect nearby speeds into a narrow image instead of discarding all but a narrow accepted range.