Matrix multiplication is associative

Dependencies:

  1. Matrix

Let $R$ be a semiring. Let $A \in \mathbb{M}_{n_0, n_1}(R), B \in \mathbb{M}_{n_1, n_2}(R), C \in \mathbb{M}_{n_2, n_3}(R)$. Then $(AB)C = A(BC)$ and \[ (ABC)[p, q] = \sum_{i=1}^{n_1} \sum_{j=1}^{n_2} A[p, i] B[i, j] C[j, q] \]

Proof

\begin{align} & ((AB)C)[p, q] \\ &= \sum_{j=1}^{n_2} (AB)[p, j] C[j, q] \\ &= \sum_{j=1}^{n_2} \left( \sum_{i=1}^{n_1} A[p, i] B[i, j]\right) C[j, q] \\ &= \sum_{j=1}^{n_2} \sum_{i=1}^{n_1} (A[p, i] B[i, j]) C[j, q] \tag{Distributivity in $R$} \\ &= \sum_{i=1}^{n_1} \sum_{j=1}^{n_2} (A[p, i] B[i, j]) C[j, q] \tag{Additive commutativity in $R$} \\ &= \sum_{i=1}^{n_1} \sum_{j=1}^{n_2} A[p, i] (B[i, j] C[j, q]) \tag{Multiplicative associativity in $R$} \\ &= \sum_{i=1}^{n_1} A[p, i] \left( \sum_{j=1}^{n_2} B[i, j] C[j, q] \right) \tag{Distributivity in $R$} \\ &= \sum_{i=1}^{n_1} A[p, i] (BC)[i, q] \\ &= (A(BC))[p, q] \\ &\Rightarrow (AB)C = A(BC) \end{align}

Dependency for:

  1. Eigenpair of power of a matrix
  2. All eigenvalues of a hermitian matrix are real
  3. Square matrices form a (semi)ring
  4. Full-rank square matrix is invertible
  5. Row equivalence matrix
  6. Inverse of a matrix
  7. Bounding matrix quadratic form using eigenvalues
  8. Inverse of product
  9. AB = I implies BA = I
  10. Determinant of product is product of determinants
  11. Equations with row equivalent matrices have the same solution set

Info:

Transitive dependencies:

  1. Group
  2. Ring
  3. Semiring
  4. Matrix