Matrix Multiplication
Matrix 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 by columns of the second and adding the results, "row dot column," more complex than just multiplying matching entries. 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}$; the columns of $A$ must equal the rows of $B$, and multiplication is associative and distributive but NOT commutative, $AB \neq BA$ in general, since it represents composition of linear transformations ("apply $B$ first, then $A$"). This makes $M_n(F)$ a unital associative (non-commutative for $n \ge 2$) $F$-algebra; naive multiplication costs $O(n^3)$, Strassen's algorithm achieves $O(n^{2.807})$, and the optimal matrix multiplication exponent $\omega < 2.371$ remains an open problem in computational mathematics, conjectured to approach $2$.
Example
$\begin{bmatrix}1 & 2\\3 & 4\end{bmatrix} \times \begin{bmatrix}5 & 6\\7 & 8\end{bmatrix} = \begin{bmatrix}19 & 22\\43 & 50\end{bmatrix}$, where the top-left entry is $(1\times 5)+(2\times 7)=19$. For $A = \begin{bmatrix}2 & 0\\1 & 3\end{bmatrix}$ and $B = \begin{bmatrix}1 & 4\\2 & 1\end{bmatrix}$: $AB = \begin{bmatrix}2 & 8\\7 & 7\end{bmatrix}$ while $BA = \begin{bmatrix}6 & 12\\5 & 3\end{bmatrix}$, confirming $AB \neq BA$. The Cayley-Hamilton theorem states every square matrix satisfies its own characteristic polynomial: for $A = \begin{bmatrix}1 & 2\\3 & 4\end{bmatrix}$, the characteristic polynomial is $\lambda^2 - 5\lambda - 2$, and $A^2 - 5A - 2I = 0$.
Key Insight
Matrix multiplication represents composition of linear transformations, $AB$ means "apply $B$ first, then $A$," which explains its non-commutativity: rotating then reflecting is different from reflecting then rotating. Fast matrix multiplication is among the most important open problems in computational mathematics, the optimal exponent $\omega$ is conjectured to be $2$, suggesting nearly linear-time multiplication, but proving this remains open.