Matrix Multiplication and Composition

Definition Vectors are columns, and on this page a tuple such as $(x, y)$ written inline stands for the column with those entries. Let $T$ be a linear transformation from $\mathbb{R}^p$ to $\mathbb{R}^n$ and $U$ a linear transformation from $\mathbb{R}^n$ to $\mathbb{R}^m$. The composition $U \circ T$, read as $U$ after $T$, is the map from $\mathbb{R}^p$ to $\mathbb{R}^m$ given by

so $T$ acts first and $U$ acts on its output. The composition makes sense because every output of $T$ lies in $\mathbb{R}^n$, the domain of $U$. It is linear, since for all $\mathbf{u}, \mathbf{v}$ in $\mathbb{R}^p$ and all real $a, b$

If $B$ is the standard matrix of $T$ and $A$ is the standard matrix of $U$, then column $j$ of the standard matrix of $U \circ T$ is $U(T(\mathbf{e}_j)) = A\mathbf{b}_j$, where $\mathbf{b}_j = T(\mathbf{e}_j)$ is column $j$ of $B$. The matrix with these columns is the product $AB$, defined in the next card.

Definition Let $A$ be an $m \times n$ matrix and $B$ an $n \times p$ matrix with columns $\mathbf{b}_1, \dots, \mathbf{b}_p$. The product $AB$ is the $m \times p$ matrix

Its entry in row $i$ and column $j$ is row $i$ of $A$ times column $j$ of $B$,

The sizes are compatible when the number of columns of $A$ equals the number of rows of $B$, and only then is $AB$ defined. An $m \times n$ matrix times an $n \times p$ matrix is an $m \times p$ matrix. The shared inner size $n$ counts the coordinates handed from the first map to the second, and the outer sizes are the output size $m$ and the input size $p$. For every $\mathbf{x}$ in $\mathbb{R}^p$ the product satisfies $(AB)\mathbf{x} = A(B\mathbf{x})$, so $AB$ is the matrix of the composition that applies $B$ first and then $A$. The product is not formed by multiplying entries in matching positions.

Definition Matrix multiplication is not commutative, which means $AB$ and $BA$ need not be equal. If $AB$ is defined, then $BA$ may be undefined. If $A$ is $m \times n$ and $B$ is $n \times m$, both products are defined but have sizes $m \times m$ and $n \times n$, which differ when $m \ne n$. When $A$ and $B$ are both $n \times n$ with $n \ge 2$, the two products have the same size and can still differ. Matrices of size $1 \times 1$ always commute, because they multiply like numbers. Some pairs do commute, for example two diagonal matrices of the same size, a square matrix and the identity matrix of its size, or a square matrix and itself. Before exchanging two factors, check that $AB = BA$ for those particular matrices.

Definition If $A$ is $m \times n$, $B$ is $n \times p$ and $C$ is $p \times q$, then

To prove it, apply both sides to any $\mathbf{x}$ in $\mathbb{R}^q$ and use the rule $(XY)\mathbf{x} = X(Y\mathbf{x})$ for products,

Two matrices that agree on every vector agree on each $\mathbf{e}_j$, so they have the same columns and are equal. This is why a product such as $ABC$ needs no parentheses. The identity matrix $I_n$ is the $n \times n$ matrix with columns $\mathbf{e}_1, \dots, \mathbf{e}_n$, that is, with $1$ in every diagonal position and $0$ elsewhere. It satisfies $I_n\mathbf{x} = \mathbf{x}$ for every $\mathbf{x}$ in $\mathbb{R}^n$, and for every $m \times n$ matrix $A$

Definition If $A$ is $m \times n$ and $B$ is $n \times p$, then

Both sides are $p \times m$. To prove it, compare the entries in row $i$ and column $j$,

where the middle step uses $a_{jk}b_{ki} = b_{ki}a_{jk}$ for real numbers. The order of the factors reverses. The product $A^{\top}B^{\top}$ in the original order is in general a different matrix, and it may not be defined at all.

Definition Cut the rows and the columns of a matrix $A$ into consecutive groups, which splits $A$ into blocks $A_{ik}$, and cut the rows and the columns of $B$ into groups as well, giving blocks $B_{kj}$. The partitions conform when the column groups of $A$ have the same sizes, in the same order, as the row groups of $B$. Then $AB$ can be computed block by block. Its block in block row $i$ and block column $j$ is

the entry formula with blocks in place of numbers. With two block columns in $A$ and two block rows in $B$, for instance, the top left block of $AB$ is $A_{11}B_{11} + A_{12}B_{21}$. Conforming partitions make every product $A_{ik}B_{kj}$ defined and give the terms of each sum the same size. Each product must keep its order, because blocks are matrices and need not commute. The row groups of $A$ and the column groups of $B$ may be chosen freely, and they become the row and column groups of $AB$.