Matrix Multiplication

Strang, Introduction to Linear Algebra (6th Edition), Section 1.4

Draft

Key Ideas

Suppose a matrix \(B\) acts on a vector and a matrix \(A\) then acts on the result. The question of which single matrix does both steps at once is what forces the definition of the product.

Definition 1 (Matrix Product) If \(A\) is \(m \times n\) and \(B\) is \(n \times p\), then \(AB\) is the \(m \times p\) matrix with entries \[ (AB)_{ij} = \sum_{k=1}^{n} a_{ik}\, b_{kj}. \]

Column View. Column \(j\) of \(AB\) is \(A\) times column \(j\) of \(B\), so \(AB = \begin{bmatrix} A\mathbf b_1 & \cdots & A\mathbf b_p \end{bmatrix}\). Every column of \(AB\) is a combination of the columns of \(A\).

Composition View. \((AB)\mathbf x = A(B\mathbf x)\), so the matrix nearest \(\mathbf x\) acts first. The product \(AB\) means “apply \(B\), then \(A\)”.

Theorem 1 (Grouping and Order) For matrices of compatible sizes, \((AB)C = A(BC)\). In general, however, \(AB \neq BA\).

Example 1 (Swapping Columns and Rows) With \(A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}\) and \(B = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\), \[ AB = \begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}, \qquad BA = \begin{bmatrix} 3 & 4 \\ 1 & 2 \end{bmatrix}. \] Multiplying by \(B\) on the right swaps the columns of \(A\), and multiplying on the left swaps its rows.

Visualization

Choose a transformation for \(A\) and for \(B\). Each panel applies the two in a different order to the letter F. The dashed outline is the starting shape, the thin outline is the shape after the first matrix, and the solid outline is the result. Hover over a panel to bring the middle step forward.

transforms = new Map([
  ["Rotate 90°", [[0, -1], [1, 0]]],
  ["Shear", [[1, 1], [0, 1]]],
  ["Reflect", [[1, 0], [0, -1]]],
  ["Stretch", [[1.3, 0], [0, 1]]]
])

function segmented(label, options, value) {
  const root = html`<div class="seg" role="radiogroup"><span class="seg-label">${label}</span></div>`;
  root.setAttribute("aria-label", label);
  const buttons = options.map(o => {
    const b = html`<button type="button" role="radio">${o}</button>`;
    b.addEventListener("click", () => {
      root.value = o;
      sync();
      root.dispatchEvent(new Event("input", {bubbles: true}));
    });
    root.append(b);
    return b;
  });
  function sync() {
    buttons.forEach(b => b.setAttribute("aria-checked", String(b.textContent === root.value)));
  }
  root.value = value;
  sync();
  return root;
}

viewof aName = segmented("Matrix A", [...transforms.keys()], "Shear")
viewof bName = segmented("Matrix B", [...transforms.keys()], "Rotate 90°")

fmt = v => {
  const r = Math.round(v * 100) / 100;
  return (r < 0 ? "−" : "") + Math.abs(r).toString();
}

mul = (M, N) => [
  [M[0][0] * N[0][0] + M[0][1] * N[1][0], M[0][0] * N[0][1] + M[0][1] * N[1][1]],
  [M[1][0] * N[0][0] + M[1][1] * N[1][0], M[1][0] * N[0][1] + M[1][1] * N[1][1]]
]

{
  const A = transforms.get(aName), B = transforms.get(bName);
  const apply = (M, [x, y]) => [M[0][0] * x + M[0][1] * y, M[1][0] * x + M[1][1] * y];
  const F = [[0, 0], [0, 1.2], [0.8, 1.2], [0.8, 0.95], [0.25, 0.95], [0.25, 0.7], [0.65, 0.7], [0.65, 0.45], [0.25, 0.45], [0.25, 0], [0, 0]];
  const W = 680, P = 300, gap = 40, R = 2.6, yTop = 8;
  const left = (W - 2 * P - gap) / 2;
  const svg = d3.create("svg")
    .attr("viewBox", `0 0 ${W} ${yTop + P + 96}`)
    .attr("class", "viz")
    .attr("role", "img")
    .attr("aria-label", `The letter F under AB and under BA, with A = ${aName} and B = ${bName}`);
  const panels = [
    {name: "AB", order: "B First, Then A", first: B, second: A, product: mul(A, B)},
    {name: "BA", order: "A First, Then B", first: A, second: B, product: mul(B, A)}
  ];
  panels.forEach((pn, k) => {
    const g = svg.append("g").attr("class", "panel").attr("transform", `translate(${left + k * (P + gap)},${yTop})`);
    const sx = d3.scaleLinear([-R, R], [0, P]), sy = d3.scaleLinear([-R, R], [P, 0]);
    g.append("rect").attr("width", P).attr("height", P).attr("fill", "transparent");
    const grid = g.append("g").attr("class", "grid");
    for (let i = -2; i <= 2; i++) {
      grid.append("line").attr("x1", sx(i)).attr("x2", sx(i)).attr("y1", 0).attr("y2", P);
      grid.append("line").attr("x1", 0).attr("x2", P).attr("y1", sy(i)).attr("y2", sy(i));
    }
    g.append("line").attr("class", "axis").attr("x1", sx(0)).attr("x2", sx(0)).attr("y1", 0).attr("y2", P);
    g.append("line").attr("class", "axis").attr("x1", 0).attr("x2", P).attr("y1", sy(0)).attr("y2", sy(0));
    const line = d3.line().x(d => sx(d[0])).y(d => sy(d[1]));
    const clipId = `clip-${k}`;
    g.append("clipPath").attr("id", clipId).append("rect").attr("width", P).attr("height", P);
    const shapes = g.append("g").attr("clip-path", `url(#${clipId})`);
    shapes.append("path").attr("class", "shape start").attr("d", line(F));
    shapes.append("path").attr("class", "shape mid").attr("d", line(F.map(p => apply(pn.first, p))));
    shapes.append("path").attr("class", "shape end").attr("d", line(F.map(p => apply(pn.second, apply(pn.first, p)))));
    const yt = P + 38;
    g.append("text").attr("class", "panel-title").attr("x", 0).attr("y", yt).text(pn.name);
    g.append("text").attr("class", "eq").attr("x", 30).attr("y", yt).text("=");
    const m = g.append("g").attr("class", "mat").attr("transform", `translate(52,${yt - 9})`);
    const cw = 40, rh = 20;
    m.append("path").attr("d", `M6,-7 H0 V${rh + 13} H6`);
    m.append("path").attr("d", `M${2 * cw + 2},-7 H${2 * cw + 8} V${rh + 13} H${2 * cw + 2}`);
    pn.product.forEach((row, i) => row.forEach((v, j) => {
      m.append("text").attr("x", 4 + j * cw + cw / 2).attr("y", 4 + i * rh + 6).attr("text-anchor", "middle").text(fmt(v));
    }));
    g.append("text").attr("class", "panel-sub").attr("x", 0).attr("y", yt + 44).text(pn.order);
  });
  return svg.node();
}

{
  const AB = mul(transforms.get(aName), transforms.get(bName));
  const BA = mul(transforms.get(bName), transforms.get(aName));
  const same = AB.every((row, i) => row.every((v, j) => Math.abs(v - BA[i][j]) < 1e-9));
  return html`<p class="viz-note">${same
    ? "For this pair AB equals BA. These two transformations commute, so the order makes no difference."
    : "For this pair AB and BA differ. The order of the two transformations changes the result."}</p>`;
}

Real-World Application

Two banks share a market of customers. Each month a share of Bank A’s customers moves to Bank B and a share of Bank B’s customers moves to Bank A. If \(a_k\) and \(b_k\) are the two market shares after \(k\) months, one month is one multiplication by a matrix \(P\):

\[ \begin{bmatrix} a_{k+1} \\ b_{k+1} \end{bmatrix} = \begin{bmatrix} 1 - p & q \\ p & 1 - q \end{bmatrix} \begin{bmatrix} a_k \\ b_k \end{bmatrix}, \]

where \(p\) is the share of Bank A’s customers who leave each month and \(q\) is the share of Bank B’s. Two months is \(P(P x_0) = P^2 x_0\), so a single multiplication by \(P^2\) replaces two monthly steps. With the starting rates below, 10% for Bank A and 20% for Bank B, the shares settle where \(Px = x\), at two thirds for Bank A and one third for Bank B. The rates are illustrative.

function slider(label, min, max, step, value, format) {
  const input = html`<input type="range">`;
  input.min = min; input.max = max; input.step = step; input.value = value;
  const out = html`<output>${format(value)}</output>`;
  const root = html`<label class="slider"><span class="slider-label">${label}</span></label>`;
  root.append(input, out);
  root.value = value;
  input.addEventListener("input", () => {
    root.value = +input.value;
    out.textContent = format(root.value);
  });
  return root;
}

pct = v => `${Math.round(v * 100)}%`
pct1 = v => `${(v * 100).toFixed(1)}%`

viewof p = slider("Customers Leaving Bank A Each Month", 0, 0.5, 0.01, 0.10, pct)
viewof q = slider("Customers Leaving Bank B Each Month", 0, 0.5, 0.01, 0.20, pct)
viewof a0 = slider("Bank A's Starting Share", 0, 1, 0.05, 0.5, pct)

Bank ABank BLong-Run Share of Bank A

{
  const N = 24;
  const shares = [a0];
  for (let k = 1; k <= N; k++) {
    const a = shares[k - 1];
    shares.push((1 - p) * a + q * (1 - a));
  }
  const steady = p + q > 0 ? q / (p + q) : a0;
  const W = 680, H = 300, m = {l: 46, r: 116, t: 18, b: 38};
  const x = d3.scaleLinear([0, N], [m.l, W - m.r]);
  const y = d3.scaleLinear([0, 1], [H - m.b, m.t]);
  const svg = d3.create("svg")
    .attr("viewBox", `0 0 ${W} ${H}`)
    .attr("class", "viz chart")
    .attr("role", "img")
    .attr("aria-label", `Market shares over ${N} months. Bank A settles near ${pct1(steady)}.`);
  const yt = [0, 0.25, 0.5, 0.75, 1];
  svg.append("g").attr("class", "grid").selectAll("line").data(yt).join("line")
    .attr("x1", m.l).attr("x2", W - m.r).attr("y1", d => y(d)).attr("y2", d => y(d));
  svg.append("g").attr("class", "tick-labels").selectAll("text").data(yt).join("text")
    .attr("x", m.l - 10).attr("y", d => y(d) + 4).attr("text-anchor", "end").text(d => `${d * 100}%`);
  svg.append("g").attr("class", "tick-labels").selectAll("text").data([0, 6, 12, 18, 24]).join("text")
    .attr("x", d => x(d)).attr("y", H - m.b + 22).attr("text-anchor", "middle")
    .text(d => d === 0 ? "Start" : `Month ${d}`);
  svg.append("line").attr("class", "ref").attr("x1", m.l).attr("x2", W - m.r).attr("y1", y(steady)).attr("y2", y(steady));
  const line = d3.line().x((d, i) => x(i)).y(d => y(d));
  svg.append("path").attr("class", "series s2").attr("d", line(shares.map(a => 1 - a)));
  svg.append("path").attr("class", "series s1").attr("d", line(shares));
  const last = shares[N];
  let ya = y(last), yb = y(1 - last);
  if (Math.abs(ya - yb) < 18) {
    const mid = (ya + yb) / 2;
    if (last >= 0.5) { ya = mid - 9; yb = mid + 9; } else { ya = mid + 9; yb = mid - 9; }
  }
  svg.append("text").attr("class", "end-label").attr("x", W - m.r + 12).attr("y", ya + 4).text(`Bank A ${pct1(last)}`);
  svg.append("text").attr("class", "end-label").attr("x", W - m.r + 12).attr("y", yb + 4).text(`Bank B ${pct1(1 - last)}`);
  const hover = svg.append("g").style("display", "none");
  const cross = hover.append("line").attr("class", "crosshair").attr("y1", m.t).attr("y2", H - m.b);
  const dotB = hover.append("circle").attr("class", "dot s2").attr("r", 4.5);
  const dotA = hover.append("circle").attr("class", "dot s1").attr("r", 4.5);
  const tip = hover.append("text").attr("class", "tip").attr("y", m.t + 4);
  svg.append("rect").attr("x", m.l).attr("y", m.t).attr("width", W - m.l - m.r).attr("height", H - m.t - m.b)
    .attr("fill", "transparent")
    .on("pointermove", event => {
      const [mx] = d3.pointer(event);
      const k = Math.max(0, Math.min(N, Math.round(x.invert(mx))));
      hover.style("display", null);
      cross.attr("x1", x(k)).attr("x2", x(k));
      dotA.attr("cx", x(k)).attr("cy", y(shares[k]));
      dotB.attr("cx", x(k)).attr("cy", y(1 - shares[k]));
      const right = k > N * 0.62;
      tip.attr("x", x(k) + (right ? -10 : 10)).attr("text-anchor", right ? "end" : "start")
        .text(`${k === 0 ? "Start" : "Month " + k}: A ${pct1(shares[k])}, B ${pct1(1 - shares[k])}`);
    })
    .on("pointerleave", () => hover.style("display", "none"));
  return svg.node();
}

{
  const P = [[1 - p, q], [p, 1 - q]];
  const P2 = mul(P, P);
  const two = [P2[0][0] * a0 + P2[0][1] * (1 - a0), P2[1][0] * a0 + P2[1][1] * (1 - a0)];
  const f = v => v.toFixed(2);
  const mat = M => html`<span class="mat-h"><span>${f(M[0][0])}</span><span>${f(M[0][1])}</span><span>${f(M[1][0])}</span><span>${f(M[1][1])}</span></span>`;
  return html`<div class="readout">
    <div><span class="lbl">One Month</span> <em>P</em> = ${mat(P)}</div>
    <div><span class="lbl">Two Months</span> <em>P</em><sup>2</sup> = ${mat(P2)}</div>
    <div class="readout-note">After two months Bank A holds ${pct1(two[0])} and Bank B ${pct1(two[1])}, the same as applying <em>P</em> twice.</div>
  </div>`;
}

Formula Bank

Rule	Statement	Holds when
Size	\((m \times n)(n \times p)\) gives \(m \times p\)	The inner sizes agree
Entry	\((AB)_{ij} = \sum_k a_{ik} b_{kj}\)	Always
Columns	Column \(j\) of \(AB\) is \(A\) times column \(j\) of \(B\)	Always
Rows	Row \(i\) of \(AB\) is row \(i\) of \(A\) times \(B\)	Always
Associative	\((AB)C = A(BC)\)	Always
Transpose	\((AB)^{\mathsf T} = B^{\mathsf T} A^{\mathsf T}\)	Always
Order	\(AB = BA\)	Only for special pairs, not in general
Zero product	\(AB = 0\) forces \(A = 0\) or \(B = 0\)	Never in general

Key Notes and Nuances

1. Order Matters. In general \(AB \neq BA\). In the example above, \(AB\) swaps the columns of \(A\) while \(BA\) swaps its rows.
2. A Product Can Exist in One Order Only. If \(A\) is 2 by 3 and \(B\) is 3 by 4, then \(AB\) exists but \(BA\) does not.
3. A Zero Product Does Not Need a Zero Factor. For \(A = \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}\) and \(B = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}\), \(AB = 0\) while \(BA = \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}\).
4. Cancellation Can Fail. With the same \(A\), the matrices \(B = \begin{bmatrix} 1 & 2 \\ 0 & 0 \end{bmatrix}\) and \(C = \begin{bmatrix} 3 & 4 \\ 0 & 0 \end{bmatrix}\) give \(AB = AC = 0\) although \(B \neq C\). Cancelling \(A\) requires \(A\) to be invertible.
5. The Binomial Formula Needs Commuting Matrices. \((A + B)^2 = A^2 + AB + BA + B^2\), which equals \(A^2 + 2AB + B^2\) only when \(AB = BA\).
6. Reading Direction. In \((AB)\mathbf x = A(B\mathbf x)\) the matrix nearest \(\mathbf x\) acts first, so \(AB\) applies \(B\) before \(A\). I misread this at first (sample note).

Questions and Answers

Question 1 \(A\) is 2 by 3 and \(B\) is 3 by 4. What size is \(AB\), and is \(BA\) defined?

Tests the size rule. ● Solved Alone

Hint

The inner sizes must agree, and the outer sizes give the size of the product.

Answer

\(AB\) is 2 by 4. \(BA\) is not defined.

Solution

For \(AB\) the inner sizes are 3 and 3, which agree, so the product exists and has the outer sizes, 2 by 4. For \(BA\) the inner sizes are 4 and 2, which do not agree, so \(BA\) is not defined.

Question 2 Compute \(AB\) for \(A = \begin{bmatrix} 2 & 1 \\ 1 & 3 \end{bmatrix}\) and \(B = \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix}\), then check the first column with the column view.

Tests the entry rule and the column view. ● Solved Alone

Hint

Entry \((i, j)\) is row \(i\) of \(A\) multiplied by column \(j\) of \(B\).

Answer

\(AB = \begin{bmatrix} 4 & 1 \\ 7 & 3 \end{bmatrix}\)

Solution

Row 1 of \(A\) is \((2, 1)\), which gives \(2 \cdot 1 + 1 \cdot 2 = 4\) and \(2 \cdot 0 + 1 \cdot 1 = 1\). Row 2 of \(A\) is \((1, 3)\), which gives \(1 + 6 = 7\) and \(0 + 3 = 3\).

As a check, column 1 of \(AB\) should be \(A\) times \((1, 2)\), which is \((2 + 2, 1 + 6) = (4, 7)\).

Question 3 Let \(A = \begin{bmatrix} 1 & 2 & 0 \\ 0 & 1 & 1 \end{bmatrix}\) and \(B = \begin{bmatrix} 3 & 1 \\ 0 & 0 \\ 1 & 2 \end{bmatrix}\). Find the second column of \(AB\) without computing the first.

Tests the column view. ◐ Solved with a Hint

Hint

Column 2 of \(AB\) depends only on column 2 of \(B\).

Answer

\((1, 2)\)

Solution

Column 2 of \(B\) is \((1, 0, 2)\), so column 2 of \(AB\) is \(1 \cdot (1, 0) + 0 \cdot (2, 1) + 2 \cdot (0, 1) = (1, 2)\).

Question 4 \(R\) rotates the plane 90 degrees counterclockwise and \(F\) reflects it across the \(x\)-axis. Find the matrix for “reflect, then rotate” and apply it to \((1, 0)\).

Tests the composition view. ◐ Solved with a Hint

Hint

The step that happens first sits nearest the vector, so the product is \(RF\), not \(FR\).

Answer

\(RF = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\), which sends \((1, 0)\) to \((0, 1)\).

Solution

\(R = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}\) and \(F = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}\). Reflecting first means \(F\) acts first, so the matrix is \(RF = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\).

As a check, reflecting \((1, 0)\) leaves it at \((1, 0)\), and rotating then gives \((0, 1)\). The other order, \(FR\), sends \((1, 0)\) to \((0, -1)\).

Question 5 Prove that \((AB)^{\mathsf T} = B^{\mathsf T} A^{\mathsf T}\).

Tests the entry rule in a proof. ○ Solved after Reading the Solution

Hint

Compare entry \((i, j)\) of each side.

Solution

Entry \((i, j)\) of \((AB)^{\mathsf T}\) is entry \((j, i)\) of \(AB\), which is \(\sum_k a_{jk} b_{ki}\). Entry \((i, j)\) of \(B^{\mathsf T} A^{\mathsf T}\) is \(\sum_k (B^{\mathsf T})_{ik} (A^{\mathsf T})_{kj} = \sum_k b_{ki}\, a_{jk}\). The two sums have the same terms, so the matrices are equal.

Sample record. I learnt this section with the tutor asking questions, took one hint each on Questions 3 and 4, and re-solved Question 5 the day after reading its solution.