Problem on showing that matrix multiplication is associative

$\newcommand{\bfA}{\mathbf{A}}$ $\newcommand{\bfB}{\mathbf{B}}$ $\newcommand{\bfC}{\mathbf{C}}$ $\newcommand{\bfF}{\mathbf{F}}$ $\newcommand{\bfI}{\mathbf{I}}$ $\newcommand{\bfa}{\mathbf{a}}$ $\newcommand{\bfb}{\mathbf{b}}$ $\newcommand{\bfc}{\mathbf{c}}$ $\newcommand{\bfd}{\mathbf{d}}$ $\newcommand{\bfe}{\mathbf{e}}$ $\newcommand{\bfi}{\mathbf{i}}$ $\newcommand{\bfj}{\mathbf{j}}$ $\newcommand{\bfk}{\mathbf{k}}$ $\newcommand{\bfn}{\mathbf{n}}$ $\newcommand{\bfr}{\mathbf{r}}$ $\newcommand{\bfu}{\mathbf{u}}$ $\newcommand{\bfv}{\mathbf{v}}$ $\newcommand{\bfw}{\mathbf{w}}$ $\newcommand{\bfx}{\mathbf{x}}$ $\newcommand{\bfy}{\mathbf{y}}$ $\newcommand{\bfz}{\mathbf{z}}$
Show that matrix multiplication is associative. That is, show that $(AB)C = A(BC)$ for any matrices $A$, $B$, and $C$ that are of the appropriate dimensions for matrix multiplication.

  • Solution

    To show that two matrices are equal, we need to show that all of their entries are equal. Our plan is thus to show that the $(i,j)$ entry of $(AB)C$ equals the $(i,j)$ entry of $A(BC)$.
    Recall that
    The $(i,j)$ entry of the matrix product $AB$ is $(AB)_{ij} = \sum_k A_{ik} B_{kj}.$
    Hence, the $(i,j)$ entry of $(AB)C$ can be written in terms of the entries of $AB$ and $C$: $$\bigl((AB)C\bigr)_{ij} = \sum_k (AB)_{ik} C_{kj}.$$
    This formula uses the $(i,k)$ entry of the matrix product $AB$, which is $$(AB)_{ik} = \sum_\ell A_{i\ell} B_{\ell k}.$$
    Hence, $$\bigl((AB)C\bigr)_{ij} = \sum_k \sum_\ell A_{i \ell} B_{\ell k} C_{kj}. \tag{1}$$
    Similarly, the $(i,j)$ entry of $A(BC)$ is $$\bigl(A(BC)\bigr)_{ij} = \sum_k A_{ik} (BC)_{kj}.$$
    This formula uses the $(k,j)$ entry of the matrix product $BC$, which is $$(BC)_{kj} = \sum_m B_{k m} C_{m j}.$$
    Hence, $$\bigl(A(BC)\bigr)_{ij} = \sum_k \sum_m A_{i k} B_{k m} C_{m j}. \tag{2}$$
    We need to argue that (1) and (2) are equal.
    Contrasting (1) and (2), we notice that the $k$ index in (1) corresponds to the $BC$ product, and the $k$ index in (2) corresponds to the $AB$ product. To see if (1) and (2) are equal, we would like to use the same indices in the same positions.
    Because the indices are dummy variables, we can rename them. In (2), replacing $k$ with $\ell$ gives $$\bigl(A(BC)\bigr)_{ij} = \sum_\ell \sum_m A_{i \ell} B_{\ell m} C_{m j}. \tag{2'}$$
    Now replace $m$ with $k$ in (2') to get $$\bigl(A(BC)\bigr)_{ij} = \sum_\ell \sum_k A_{i \ell} B_{\ell k} C_{k j}. \tag{2''}$$
    We now see that (1) and (2'') are equal because the sums over $\ell$ and $k$ can be interchanged.

Related topics