14
$\begingroup$

I'm trying to prove that matrix multiplication is associative, but seem to be making mistakes in each of my past write-ups, so hopefully someone can check over my work.

Theorem. Let $A$ be $\alpha \times \beta$, $B$ be $\beta \times \gamma$, and $C$ be $\gamma \times \delta$. Prove that $(AB)C = A(BC)$.

Proof. Define general entries of the matrices $A$, $B$, and $C$ by $a_{g,h}$, $b_{i,j}$, and $c_{k,m}$, respectively. Then, for the LHS: \begin{align*} & (AB)_{\alpha, \gamma} = \sum\limits_{p=1}^{\beta} a_{\alpha,p} b_{p,\gamma} \\ & \left((AB)C\right)_{\alpha, \delta} = \sum\limits_{n=1}^{\gamma} \left(AB\right)_{\alpha, n} c_{n, \delta} = \sum\limits_{n=1}^{\gamma} \left(\sum\limits_{p=1}^{\beta} a_{\alpha,p} b_{p,n} \right) c_{n, \delta} = \sum\limits_{n=1}^{\gamma} \sum\limits_{p=1}^{\beta} \left(a_{\alpha,p} b_{p,n}\right) c_{n, \delta}. \end{align*} For the RHS: \begin{align*} & \left(BC\right)_{\beta, \delta} = \sum\limits_{n=1}^{\gamma} b_{\beta, n} c_{n, \delta} \\ & \left(A\left(BC\right)\right)_{\alpha,\delta} = \sum\limits_{p=1}^{\beta} a_{\alpha,p} (BC)_{p, \delta} = \sum\limits_{p=1}^{\beta} a_{\alpha,p} \left(\sum\limits_{n=1}^{\gamma} b_{p, n} c_{n, \delta} \right) = \sum\limits_{p=1}^{\beta} \sum\limits_{n=1}^{\gamma} a_{\alpha,p} \left(b_{p, n} c_{n, \delta} \right). \end{align*} Assuming I have written these correctly, we can make two observations: first, the summands are equivalent, as multiplication is associative. Second, the order of the summations doesn't matter when we're summing a finite number of entries. Thus, $(AB)C = A(BC)$.

How does this look?

$\endgroup$
3
  • 4
    $\begingroup$ $\checkmark\,\!$ $\endgroup$
    – David
    Commented Sep 11, 2018 at 4:37
  • 5
    $\begingroup$ Just a point on notation: you are using $\alpha$ as both the number of rows of $A$ and as a general row-index; and same for$\beta$, $\gamma$ and $\delta$. You should clean that up for a completely correct proof. $\endgroup$
    – ancient mathematician
    Commented Sep 11, 2018 at 6:56
  • 1
    $\begingroup$ This is very true and I hadn't realized it. Thank you. A general entry of $(AB)C$ and $A(BC)$ should have the indices ${g,m}$, I believe. $\endgroup$
    – user465188
    Commented Sep 11, 2018 at 14:23

2 Answers 2

Reset to default
7
$\begingroup$

Your proof is fine.

We can change the order of summation as the sum is finite. When we mention multiplication is associative, we might want to mention multiplicative of which object, such as multiplicative of real numbers or complex number.

$\endgroup$
3
  • $\begingroup$ So basically the proof lies in the facts that real numbers are associative, and that the order of summation can be changed, i could not understand intuitively why the order of summation shouldn't matter though, can you please also provide an intuitive picture to this, if possible? Thanks! @Sion Thye Goh $\endgroup$
    – Aditya
    Commented Apr 17, 2021 at 20:15
  • 2
    $\begingroup$ It is due to summation is commutative and associative that the order doesn't matter. Given an array, you can sum them up row-wise first or column-wise first, you are going to get the same number. We have to be cautious when we handle infinite sum though as that involves taking limit. $\endgroup$
    – Siong Thye Goh
    Commented Apr 18, 2021 at 4:20
  • $\begingroup$ @Aditya It's the distributive law $\endgroup$
    – Anshuman Agrawal
    Commented Feb 16, 2022 at 5:45
0
$\begingroup$

A matrix represents a linear transformation. The product of two matrices represents the composition of the operation the first matrix in the product represents and the operation the second matrix in the product represents in that order but composition is always associative.

$\endgroup$

You must log in to answer this question.