Why is matrix multiplication associative?

Question

When I wonder why the product of elements of symmetric group of order 3 are associative, I just say they are isomorphic to permutation matrices and they just share that feature. Don't take me light....

Answer 1

In my answer below, scalars will be real numbers, but everything I'm going to say will work equally well for complex numbers, or for an arbitrary field, or for an arbitrary commutative ring. It may be possible to generalize what I say below even further.

Let's use $\Bbb{R}^{n\times m}$ to denote the set of $n\times m$ matrices with coefficients in $\Bbb{R}$.

And let's let $\mathcal{L}(\Bbb{R}^m,\Bbb{R}^n)$ be the set of linear transformations $\Bbb{R}^m\to\Bbb{R}^n$. A linear transformation $\Bbb{R}^m\to\Bbb{R}^n$ is a function $T:\Bbb{R}^m\to\Bbb{R}^n$, such that for every $u,v\in\Bbb{R}^m$, and every $\lambda,\mu\in\Bbb{R}$

$$T\left(\lambda\cdot u+\mu\cdot v\right)=\lambda\cdot T(u)+\mu\cdot T(v).$$

Exercise 1: Show that for any $T\in\mathcal{L}(\Bbb{R}^m,\Bbb{R}^n)$ and any $S\in\mathcal{L}(\Bbb{R}^n,\Bbb{R}^k)$, the composition $S\circ T\in\mathcal{L}(\Bbb{R}^m,\Bbb{R}^k)$. In other words, the composition of two linear transformations is a linear transformation.

It turns out that there is a one-to-one correspondance:

$$\mathcal{L}(\Bbb{R}^m,\Bbb{R}^n)\to\Bbb{R}^{n\times m}$$

so that every $T\in\mathcal{L}(\Bbb{R}^m,\Bbb{R}^n)$ is associated with a unique matrix $M_T\in\Bbb{R}^{n\times m}$.

It turns out that this correspondence is particularly nice, because it satisfies the following property: for any $T\in\mathcal{L}(\Bbb{R}^m,\Bbb{R}^n)$ and any $S\in\mathcal{L}(\Bbb{R}^n,\Bbb{R}^k)$, we have that

$$M_S M_T=M_{S\circ T}$$

where $M_{S\circ T}$, is the matrix associated with the composition $S\circ T$. As I'll show below, matrix multiplication will end up being associative because function composition is associative.

Another nice thing about the correspondence between linear transformations and matrices is the following:

Exercise 2: Let $A$ and $B$ be two matrices. Then $A=M_S$ and $B=M_T$ for unique linear transformations $S$ and $T$. Show that the product $AB$ is defined iff the composition $S\circ T$ is defined.

Now let $A$, $B$, $C$ be three matrices with real coefficients. $A=M_R$, $B=M_S$, and $C=M_T$ for some unique linear transformations $R$, $S$, and $T$. Note that the following are equivalent:

$$\text{The product }(AB)C\text{ is defined.}$$ $$\text{The product }A(BC)\text{ is defined.}$$ $$\text{The composition }(R\circ S)\circ T\text{ is defined.}$$ $$\text{The composition }R\circ(S\circ T)\text{ is defined.}$$

And we have that

$$(AB)C=M_{(R\circ S)\circ T}=M_{R\circ(S\circ T)}=A(BC)$$

provided that the above products exist.

If you've ever wondered where the peculiar definition of matrix multiplication comes from: it comes from thinking of matrices as linear transformations and defining the product of two matrices $A$ and $B$ so that the product $AB$ corresponds to the composition of the linear transformations that $A$ and $B$ correspond to.

Answer 2

I've already posted an answer to this question. Whereas my previous answer was more conceptual, this answer will be more concrete. Hopefully, you will find one of these answers to be helpful.

The proof below is a straightforward application of the definition matrix multiplication, and you can probably find it any linear algebra text. The only "trick" would be switching the order summation in a double summation. Although, if you have a lot of experience with sums, then you probably don't think of this as a "trick".

For the rest of this answer, scalars will be real numbers, although everything I'm going to say will work equally well for complex numbers, or for elements of an arbitrary (not necessarily commutative) ring.

The make the problem more manageable, we'll adopt the following notation:

$$\text{For any matrix }M,\;M_{ij}\text{ will denote the entry in row }i,\text{ column }j,\text{ of }M.$$

Let $A$, $B$, $C$ be matrices for which the products $(AB)C$ and $A(BC)$ are defined. Hence

$$A\text{ is }m\times n,$$ $$B\text{ is }n\times p,$$ $$C\text{ is }p\times q,$$

for some positive integers $m$, $n$, $p$, and $q$.

It follows that

$$\begin{align*} ((AB)C)_{il} &= \sum_{k=1}^p\left(AB\right)_{ik}C_{kl} \\ &= \sum_{k=1}^p\left(\sum_{j=1}^n A_{ij}B_{jk}\right)C_{kl} \\ &= \sum_{k=1}^p\sum_{j=1}^n A_{ij}B_{jk}C_{kl} \\ &= \sum_{j=1}^n\sum_{k=1}^p A_{ij}B_{jk}C_{kl} \\ &= \sum_{j=1}^n A_{ij}\left(\sum_{k=1}^p B_{jk}C_{kl}\right) \\ &= \sum_{j=1}^n A_{ij}\left(BC\right)_{jl} \\ &= (A(BC))_{il} \end{align*}$$

This shows that for each $i$ and $l$ with $1\le i\le m$ and $1\le l\le q$, we have that

$$((AB)C)_{il}=(A(BC))_{il}.$$

Hence $(AB)C=A(BC)$.