Matrix Multiplication
Functions & Advanced AlgebraMatrix multiplication combines two matrices by taking dot products of rows and columns, producing a new matrix that represents a composition of transformations.
Formula
(AB)_{ij} = \sum_k a_{ik} b_{kj}
Definition
Matrix multiplication combines two matrices by multiplying rows of the first matrix by columns of the second and adding the results. It is more complex than just multiplying matching entries.
Example
$\begin{bmatrix}1 & 2\\3 & 4\end{bmatrix} \times \begin{bmatrix}5 & 6\\7 & 8\end{bmatrix}$: top-left entry: $(1\times 5)+(2\times 7)=19$. Top-right: $(1\times 6)+(2\times 8)=22$. Bottom-left: $(3\times 5)+(4\times 7)=43$. Bottom-right: $(3\times 6)+(4\times 8)=50$. Result: $\begin{bmatrix}19 & 22\\43 & 50\end{bmatrix}$.
Key Insight
Matrix multiplication is "row dot column": take a row from the first matrix and a column from the second, multiply pairs, and add. This process produces each entry of the result.
Definition
For $A$ ($m \times n$) and $B$ ($n \times p$), the product $AB$ is $m \times p$ with $(AB)_{ij} = \sum_{k=1}^{n} a_{ik} b_{kj}$. Requirements: columns of $A$ must equal rows of $B$. Matrix multiplication is associative and distributive but NOT commutative: $AB \neq BA$ in general.
Example
$A = \begin{bmatrix}2 & 0\\1 & 3\end{bmatrix}$, $B = \begin{bmatrix}1 & 4\\2 & 1\end{bmatrix}$. $AB = \begin{bmatrix}2+0 & 8+0\\1+6 & 4+3\end{bmatrix} = \begin{bmatrix}2 & 8\\7 & 7\end{bmatrix}$. $BA = \begin{bmatrix}2+4 & 0+12\\4+1 & 0+3\end{bmatrix} = \begin{bmatrix}6 & 12\\5 & 3\end{bmatrix}$. $AB \neq BA$.
Key Insight
Matrix multiplication represents composition of linear transformations. $AB$ means "apply $B$ first, then $A$." This explains non-commutativity: rotating then reflecting is different from reflecting then rotating.
Definition
Matrix multiplication makes $M_n(F)$ a unital associative (non-commutative for $n \ge 2$) $F$-algebra. The product $(AB)_{ij} = \sum a_{ik}b_{kj}$ arises from the composition of linear maps $T_A: F^n \to F^m$ and $T_B: F^p \to F^n$. In numerical linear algebra, matrix multiplication costs $O(n^3)$ naively; Strassen's algorithm achieves $O(n^{2.807})$, and the matrix multiplication exponent $\omega < 2.371$ is unknown in general.
Example
The Cayley-Hamilton theorem: every square matrix satisfies its own characteristic polynomial $p(A) = 0$. For $A = \begin{bmatrix}1 & 2\\3 & 4\end{bmatrix}$, char poly $= \lambda^2 - 5\lambda - 2$, and $A^2 - 5A - 2I = 0$.
Key Insight
Fast matrix multiplication is among the most important open problems in computational mathematics. The value of $\omega$ (the optimal exponent) is conjectured to be $2$ (suggesting nearly linear-time multiplication), but proving this remains open.