This page assumes you have seen nothing. Before you can read the parent MCM note, every symbol it throws at you must first be earned. We build them one at a time, each on top of the last.
Look at the figure. The magenta grid has 2 rows and 3 columns, so it is a 2×3 matrix. The little labels on the outside are the dimensions. That is the entire vocabulary you need — we never look inside the grid on this page, only at its shape.
Why shape and not contents? Because MCM asks "how much work is the multiplication?", and — as we will see — the workload depends only on the shape, never on the actual numbers inside.
You cannot multiply just any two matrices. There is one rule about their shapes.
In the picture the inner numbers (violet, touching in the middle) must match — they are the shared dimension b. The outer numbers (orange) survive to become the shape of the answer. A handy way to remember it:
Now the heart of it: how much work is one matrix multiply? We keep the exact same a,b,c from §1 — a rows on the left, shared middle b, c columns on the right.
The figure shows one highlighted output cell (orange). To compute it, we slide along the shared strip of length b (violet), doing b multiplications. There are a⋅c such cells, so we pay b that many times.
Why count multiplications and not additions? By long tradition, and because on real hardware multiplications historically dominated the cost. The parent note fixes this convention; we follow it.
The parent note never lists the matrices' shapes separately. Instead it uses a single array p. Here is why that is enough.
Look at the figure: each Ai straddles two adjacent p-values. A1 sits on [p0,p1], A2 on [p1,p2], and they sharep1 — which is exactly the matching-inner-dimensions rule automatically satisfied.
The little number under A or p is a subscript — a nametag, not arithmetic. Ai means "the i-th matrix"; pi−1 means "the p-value one step to the left of position i".
We will meet three at once in the recurrence: i (start of a sub-chain), j (end of a sub-chain), and k (the place we cut). Keep them straight: i and j are the ends; k roams between them.
Both trees in the figure produce the same final matrix — that is a property called associativity (rearranging the brackets in a product does not change the answer). But, as §2 showed, the two orders can cost wildly different amounts. That gap is the entire reason MCM exists, and it connects to Catalan Numbers, which count how many bracketings are possible.
Now we can name the storage and — finally — assemble the formula.
The figure shows why the loop is ordered by length: to fill a length-3 entry (top), the arrows show it reaches down into length-2 and length-1 entries — which only exist if we already filled them. Fill row-by-row and you would ask for numbers that aren't there yet. Fill by length, shortest first, and every value you need is guaranteed ready.
Every piece is defined: Ai (=pi−1×pi), the cut index k, the cost pi−1pkpj of one combine, the table m, the min over all cuts, the base case. Here is how they click together.
Everything you defined above feeds exactly one slot in this formula. That is the payoff: not a single symbol here is new.
Read this map as a flow: the shape rule and the cost formula (top) both feed the cost of a bracketing; the base case and length-ordering feed the table; and everything converges on the single MCM recurrence at the bottom. Trace any arrow and you should be able to say why that dependency exists.
