Matrix Multiplication is Associative

From ProofWiki
Jump to: navigation, search

Theorem

Let $R$ be a ring.

Matrix multiplication (conventional) is associative.


Proof

Let $\mathbf A = \sqbrk a_{m n}, \mathbf B = \sqbrk b_{n p}, \mathbf C = \sqbrk c_{p q}$ be matrices.


From inspection of the subscripts, we can see that both $\paren {\mathbf A \mathbf B} \mathbf C$ and $\mathbf A \paren {\mathbf B \mathbf C}$ are defined:

$\mathbf A$ has $n$ columns and $\mathbf B$ has $n$ rows, while $\mathbf B$ has $p$ columns and $\mathbf C$ has $p$ rows.


Consider $\paren {\mathbf A \mathbf B} \mathbf C$.

Let $\mathbf R = \sqbrk r_{m p} = \mathbf A \mathbf B, \mathbf S = \sqbrk s_{m q} = \mathbf A \paren {\mathbf B \mathbf C}$.

Then:

\(\displaystyle s_{i j}\) \(=\) \(\displaystyle \sum_{k \mathop = 1}^p r_{i k} \circ c_{k j}\) Definition of Matrix Product (Conventional)
\(\displaystyle r_{i k}\) \(=\) \(\displaystyle \sum_{l \mathop = 1}^n a_{i l} \circ b_{l k}\) Definition of Matrix Product (Conventional)
\(\displaystyle \implies \ \ \) \(\displaystyle s_{i j}\) \(=\) \(\displaystyle \sum_{k \mathop = 1}^p \paren {\sum_{l \mathop = 1}^n a_{i l} \circ b_{l k} } \circ c_{k j}\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{k \mathop = 1}^p \sum_{l \mathop = 1}^n \paren {a_{i l} \circ b_{l k} } \circ c_{k j}\) Ring axiom $(D)$ (distributivity)


Now consider $\mathbf A \paren {\mathbf B \mathbf C}$.

Let $\mathbf R = \sqbrk r_{n q} = \mathbf B \mathbf C, \mathbf S = \sqbrk s_{m q} = \mathbf A \paren {\mathbf B \mathbf C}$.

Then:

\(\displaystyle s_{i j}\) \(=\) \(\displaystyle \sum_{l \mathop = 1}^n a_{i l} \circ r_{l j}\) Definition of Matrix Product (Conventional)
\(\displaystyle r_{l j}\) \(=\) \(\displaystyle \sum_{k \mathop = 1}^p b_{l k} \circ c_{k j}\) Definition of Matrix Product (Conventional)
\(\displaystyle \implies \ \ \) \(\displaystyle s_{i j}\) \(=\) \(\displaystyle \sum_{l \mathop = 1}^n a_{i l} \circ \paren {\sum_{k \mathop = 1}^p b_{l k} \circ c_{k j} }\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{l \mathop = 1}^n \sum_{k \mathop = 1}^p a_{i l} \circ \paren {b_{l k} \circ c_{k j} }\) Ring axiom $(D)$ (distributivity)


Using ring axiom $(M1)$ (associativity of $\circ$):

$\displaystyle s_{i j} = \sum_{k \mathop = 1}^p \sum_{l \mathop = 1}^n \paren {a_{i l} \circ b_{l k} } \circ c_{k j} = \sum_{l \mathop = 1}^n \sum_{k \mathop = 1}^p a_{i l} \circ \paren {b_{l k} \circ c_{k j} } = s'_{i j}$

It is concluded that:

$\paren {\mathbf A \mathbf B} \mathbf C = \mathbf A \paren {\mathbf B \mathbf C}$

$\blacksquare$


Sources