Matrix Multiplication
1 Matrix multiplication
Definition 1 (Matrix multiplication) The product [1] of an \(m \times k\) matrix \(\mathbf{A}\) and a \(k \times n\) matrix \(\mathbf{B}\) is the \(m \times n\) matrix \(\mathbf{C} = \mathbf{A}\mathbf{B}\) with entries:
\[c_{ij} = \sum_{s=1}^{k} a_{is}\, b_{sj}\]
Remark 1 (Matrix multiplication is not commutative). When \(\mathbf{A}\mathbf{B}\) and \(\mathbf{B}\mathbf{A}\) are both defined, they are usually different. For example, with
\[ \mathbf{A} = \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix}, \qquad \mathbf{B} = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}, \]
\[ \begin{aligned} \mathbf{A}\mathbf{B} &= \begin{bmatrix} 3 & 2 \\ 1 & 1 \end{bmatrix} \\ \mathbf{B}\mathbf{A} &= \begin{bmatrix} 1 & 2 \\ 1 & 3 \end{bmatrix}, \end{aligned} \]
so \(\mathbf{A}\mathbf{B} \neq \mathbf{B}\mathbf{A}\).
Definition 2 (Shape rule) The shape rule of matrix multiplication says that an \(m \times k\) matrix times a \(k \times n\) matrix is an \(m \times n\) matrix, and that the multiplication is defined only when the inner pair of sizes matches:
\[(m \times k)(k \times n) \;\longrightarrow\; m \times n \tag{1}\]
Example 1 (Shape of a product of three matrices)
Let \(\mathbf{A}\) be \(2 \times 3\), let \(\mathbf{B}\) be \(3 \times 4\), and let \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\in \mathbb{R}^4\), which is a \(4 \times 1\) matrix. Apply the shape rule one product at a time:
- \(\mathbf{A}\mathbf{B}\) is \((2 \times 3)(3 \times 4)\). The inner pair \(3, 3\) matches, so the product is \(2 \times 4\).
- \((\mathbf{A}\mathbf{B})\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\) is \((2 \times 4)(4 \times 1)\). The inner pair \(4, 4\) matches, so the product is \(2 \times 1\), a vector in \(\mathbb{R}^2\).
Example 2 (A product that the shape rule rules out)
Let \(\mathbf{A}\) be \(2 \times 3\), and let \(\mathbf{B}\) be \(3 \times 4\). The product \(\mathbf{B}\mathbf{A}\) is \((3 \times 4)(2 \times 3)\). Its inner pair \(4, 2\) does not match, so the shape rule says that \(\mathbf{B}\mathbf{A}\) is not defined, although \(\mathbf{A}\mathbf{B}\) is.
Example 3 (Dot product as matrix multiplication) The dot product of two column vectors \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\) and \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{\beta}}\vphantom{\beta}}\) can be written as a matrix product of the row vector \({\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}}^{\top}\) with the column vector \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{\beta}}\vphantom{\beta}}\):
\[ \begin{aligned} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{\beta}}\vphantom{\beta}} &= {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}}^{\top}\, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{\beta}}\vphantom{\beta}} \\ &= [x_1,\; x_2,\; \ldots,\; x_p] \begin{bmatrix} \beta_{1} \\ \beta_{2} \\ \vdots \\ \beta_{p} \end{bmatrix} \\ &= x_1\beta_{1} + x_2\beta_{2} + \cdots + x_p \beta_{p} \end{aligned} \]
Exercise 1 (Computing the product of a \(2 \times 3\) and a \(3 \times 2\) matrix) The product of two matrices is defined only when the first has as many columns as the second has rows. Each entry of the product combines one row of the first factor with one column of the second. Let
\[ \mathbf{A} = \begin{bmatrix} 1 & 0 & 2 \\ -1 & 3 & 1 \end{bmatrix}, \qquad \mathbf{B} = \begin{bmatrix} 2 & 1 \\ 0 & -1 \\ 1 & 4 \end{bmatrix}. \]
Find \(\mathbf{A}\mathbf{B}\).
\(\mathbf{A}\) is \(2 \times 3\), and \(\mathbf{B}\) is \(3 \times 2\). By Definition 1, \(\mathbf{A}\mathbf{B}\) is therefore \(2 \times 2\). Its entry \(c_{ij}\) is \(a_{i1} b_{1j} + a_{i2} b_{2j} + a_{i3} b_{3j}\).
Theorem 1 (Matrix multiplication is associative) For an \(m \times k\) matrix \(\mathbf{A}\), a \(k \times l\) matrix \(\mathbf{B}\), and an \(l \times n\) matrix \(\mathbf{C}\):
\[ \underbrace{(\mathbf{A}\mathbf{B})\mathbf{C}}_{m \times n} = \underbrace{\mathbf{A}(\mathbf{B}\mathbf{C})}_{m \times n} \]
Proof. Entry \((i, j)\) of each side, from Definition 1:
\[ \begin{aligned} \mathopen{}\left[(\mathbf{A}\mathbf{B})\mathbf{C}\right]\mathclose{}_{ij} &= \sum_{t=1}^{l} (\mathbf{A}\mathbf{B})_{it}\, c_{tj} && \text{(definition of } (\mathbf{A}\mathbf{B})\mathbf{C} \text{)} \\ &= \sum_{t=1}^{l} \mathopen{}\left(\sum_{s=1}^{k} a_{is}\, b_{st}\right)\mathclose{} c_{tj} && \text{(definition of } \mathbf{A}\mathbf{B} \text{)} \\ &= \sum_{s=1}^{k} a_{is} \mathopen{}\left(\sum_{t=1}^{l} b_{st}\, c_{tj}\right)\mathclose{} && \text{(distribute and swap the finite sums)} \\ &= \sum_{s=1}^{k} a_{is}\, (\mathbf{B}\mathbf{C})_{sj} && \text{(definition of } \mathbf{B}\mathbf{C} \text{)} \\ &= \mathopen{}\left[\mathbf{A}(\mathbf{B}\mathbf{C})\right]\mathclose{}_{ij} && \text{(definition of } \mathbf{A}(\mathbf{B}\mathbf{C}) \text{)} \end{aligned} \]
Exercise 2 (Grouping a product of three matrices) By Theorem 1, a product of three matrices can be grouped either way, so \(\mathbf{A}\mathbf{B}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\) can be computed as \(\mathbf{A}(\mathbf{B}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}})\), without ever forming \(\mathbf{A}\mathbf{B}\). Let
\[ \mathbf{A} = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}, \qquad \mathbf{B} = \begin{bmatrix} 2 & 0 \\ 1 & 1 \end{bmatrix}, \qquad \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}= \begin{bmatrix} 1 \\ 2 \end{bmatrix}, \]
where \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\) is a \(2 \times 1\) matrix.
Find \(\mathbf{A}\mathbf{B}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\) by computing \(\mathbf{B}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\) first.
By Definition 1, \(\mathbf{B}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\) is a \(2 \times 1\) matrix; multiply \(\mathbf{A}\) by it.
Theorem 2 (Matrix multiplication is distributive over addition) Matrix multiplication distributes over addition from the left and from the right. For an \(m \times k\) matrix \(\mathbf{A}\) and \(k \times n\) matrices \(\mathbf{B}\) and \(\mathbf{C}\):
\[\mathbf{A}(\mathbf{B} + \mathbf{C}) = \mathbf{A}\mathbf{B} + \mathbf{A}\mathbf{C}\]
For \(m \times k\) matrices \(\mathbf{A}\) and \(\mathbf{B}\) and a \(k \times n\) matrix \(\mathbf{C}\):
\[(\mathbf{A} + \mathbf{B})\mathbf{C} = \mathbf{A}\mathbf{C} + \mathbf{B}\mathbf{C}\]
Exercise 3 (Proving that matrix multiplication distributes from the left) Theorem 2 lets a product with a matrix sum be expanded term by term, just as multiplication of numbers distributes over addition. Let \(\mathbf{A}\) be an \(m \times k\) matrix, and let \(\mathbf{B}\) and \(\mathbf{C}\) be \(k \times n\) matrices.
Prove that \(\mathbf{A}(\mathbf{B} + \mathbf{C}) = \mathbf{A}\mathbf{B} + \mathbf{A}\mathbf{C}\).
Express the \((i, j)\) entry of the left side with Definition 1 and Definition 8 in Matrices, then split the result with the rule for a sum of sums.
Theorem 3 (Product of two sums of matrices) For \(m \times k\) matrices \(\mathbf{A}\) and \(\mathbf{B}\) and \(k \times n\) matrices \(\mathbf{C}\) and \(\mathbf{D}\),
\[ (\mathbf{A} + \mathbf{B})(\mathbf{C} + \mathbf{D}) = \mathbf{A}\mathbf{C} + \mathbf{A}\mathbf{D} + \mathbf{B}\mathbf{C} + \mathbf{B}\mathbf{D}. \]
Each product keeps its factors in the order they appear on the left, because matrix multiplication is not commutative. So \(\mathbf{A}\mathbf{D}\) and \(\mathbf{B}\mathbf{C}\) are not collected into \(2\mathbf{A}\mathbf{D}\).
Proof. \[ \begin{aligned} (\mathbf{A} + \mathbf{B})(\mathbf{C} + \mathbf{D}) &= (\mathbf{A} + \mathbf{B})\mathbf{C} + (\mathbf{A} + \mathbf{B})\mathbf{D} && \text{(}\href{#thm-matmul-distrib}{\text{Theorem~2}}\text{, from the left)} \\ &= \mathbf{A}\mathbf{C} + \mathbf{B}\mathbf{C} + \mathbf{A}\mathbf{D} + \mathbf{B}\mathbf{D} && \text{(}\href{#thm-matmul-distrib}{\text{Theorem~2}}\text{, from the right, twice)} \\ &= \mathbf{A}\mathbf{C} + \mathbf{A}\mathbf{D} + \mathbf{B}\mathbf{C} + \mathbf{B}\mathbf{D} && \text{(matrix addition is commutative)} \end{aligned} \]
Example 4 (Why the middle terms do not combine) Take \(\mathbf{A} = \mathbf{C} = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\) and \(\mathbf{B} = \mathbf{D} = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}\). Then \(\mathbf{A} + \mathbf{B} = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}\), so
\[ \begin{aligned} (\mathbf{A} + \mathbf{B})^2 &= \begin{bmatrix} 5 & 4 \\ 4 & 5 \end{bmatrix}, \\ \mathbf{A}^2 + \mathbf{A}\mathbf{B} + \mathbf{B}\mathbf{A} + \mathbf{B}^2 &= \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix} + \begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix} + \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix} + \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix} \\ &= \begin{bmatrix} 5 & 4 \\ 4 & 5 \end{bmatrix}. \end{aligned} \]
Here \(\mathbf{A}\mathbf{B} \neq \mathbf{B}\mathbf{A}\), so the middle terms do not combine into \(2\mathbf{A}\mathbf{B}\). The squared norm of a sum of vectors, \(\mathopen{}\left\lVert\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}+ \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}\right\rVert\mathclose{}^2\), is a case where they do combine (Theorem 2 in Inner Products and Orthogonality), because \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}\cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\). Matrices that commute, such as \(\mathbf{A}\) and \(\mathbf{A}^2\), combine the same way.
Exercise 4 (Comparing \((\mathbf{A} + \mathbf{B})(\mathbf{A} + \mathbf{B})\) with the rule for numbers) For numbers, \((a + b)^2 = a^2 + 2ab + b^2\). Theorem 3 expands a product of two matrix sums into four terms instead, because \(\mathbf{A}\mathbf{B}\) and \(\mathbf{B}\mathbf{A}\) can differ. Let
\[ \mathbf{A} = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}, \qquad \mathbf{B} = \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}. \]
Is \((\mathbf{A} + \mathbf{B})(\mathbf{A} + \mathbf{B})\) equal to \(\mathbf{A}\mathbf{A} + 2\mathbf{A}\mathbf{B} + \mathbf{B}\mathbf{B}\)?
Compute \(\mathbf{A} + \mathbf{B}\) and its product with itself, then compute \(\mathbf{A}\mathbf{A}\), \(\mathbf{A}\mathbf{B}\) and \(\mathbf{B}\mathbf{B}\) with Definition 1.
Exercise 5 (Which of these products are defined?) Let \(\mathbf{A}\) be \(4 \times 3\), let \(\mathbf{B}\) be \(3 \times 2\), and let \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\in \mathbb{R}^3\). For each expression, say whether it is defined, and if so give the shape of the result:
- \(\mathbf{A}\mathbf{B}\)
- \(\mathbf{B}\mathbf{A}\)
- \(\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\)
- \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\)
- \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}^{\top}\)
2 Square and identity matrices
Definition 3 (Square matrix) A matrix is square [2] if it has the same number of rows as columns.
Example 5 (Square and not square) \(\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}\) is square (\(2\) rows, \(2\) columns); \(\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}\) is not (\(2\) rows, \(3\) columns).
Exercise 6 (Whether a data matrix times its transpose is square) Many statistical methods start from an \(n \times p\) data matrix \(\mathbf{X}\), with one row per observation, and form the product \({\mathbf{X}}^{\top}\mathbf{X}\) of its transpose with itself. Whether that product is square matters, because some operations, such as taking the inverse of a matrix, apply only to square matrices.
Is \({\mathbf{X}}^{\top}\mathbf{X}\) square?
Find the shape of \({\mathbf{X}}^{\top}\) from Definition 6 in Matrices, then the shape of the product from Definition 1.
Definition 4 (Main diagonal) The main diagonal [3] of an \(m \times n\) matrix \(\mathbf{A}\) is the list of its entries \(a_{11}, a_{22}, \ldots, a_{kk}\), where \(k\) is the smaller of \(m\) and \(n\).
Definition 5 (Diagonal entry) The entries on the main diagonal (Definition 4) of a matrix \(\mathbf{A}\) are the diagonal entries of \(\mathbf{A}\).
Definition 6 (Off-diagonal entry) In an \(m \times n\) matrix \(\mathbf{A}\) with main diagonal (Definition 4), every entry \(a_{ij}\) with \(i \ne j\) is an off-diagonal entry.
Example 6 (Diagonal entries of a square and a non-square matrix)
- For \(\mathbf{A} = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}\), the diagonal entries are \(a_{11} = 1\) and \(a_{22} = 4\), and the off-diagonal entries are \(a_{12} = 2\) and \(a_{21} = 3\).
- For \(\mathbf{B} = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}\), \(m = 2\) and \(n = 3\), so \(k = 2\), and the diagonal entries are \(b_{11} = 1\) and \(b_{22} = 5\); the other four entries, \(2\), \(3\), \(4\) and \(6\), are off-diagonal.
Exercise 7 (The main diagonal of a tall matrix) The main diagonal of a matrix that is not square stops when it runs out of rows or columns, whichever comes first. A tall matrix, with more rows than columns, runs out of columns first. Let
\[ \mathbf{E} = \begin{bmatrix} 7 & -2 \\ 1 & 3 \\ 0 & 5 \\ 4 & -6 \end{bmatrix}. \]
Find the main diagonal of \(\mathbf{E}\).
Find \(m\), \(n\) and \(k\) in Definition 4.
Exercise 8 (Adding the diagonal entries of a square matrix) The sum of the diagonal entries of a square matrix summarizes that matrix in one number, called its trace. Let
\[ \mathbf{F} = \begin{bmatrix} 2 & 5 & -1 \\ 0 & -3 & 8 \\ 4 & 1 & 6 \end{bmatrix}. \]
Find the sum of the diagonal entries of \(\mathbf{F}\).
Find the main diagonal of \(\mathbf{F}\) first.
Exercise 9 (Counting the off-diagonal entries of a square matrix) In a table of pairwise comparisons among several items, the off-diagonal entries are the comparisons between two different items, so counting them counts the ordered pairs of different items. Let \(\mathbf{A}\) be a \(5 \times 5\) matrix, so \(\mathbf{A}\) is square.
How many off-diagonal entries does \(\mathbf{A}\) have?
Count all the entries, then subtract the diagonal entries.
Definition 7 (Identity matrix) The \(p \times p\) identity matrix [4] \(\mathbf{I}_p\) (or \(\mathbf{I}\) when the size is clear from context) has ones on the main diagonal and zeros elsewhere:
\[ (\mathbf{I}_p)_{ij} = \begin{cases} 1 & \text{if } i = j \\ 0 & \text{if } i \neq j \end{cases} \qquad \mathbf{I}_p = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix} \]
Example 7 (The \(3 \times 3\) identity) \[ \mathbf{I}_3 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \]
so, for instance, \((\mathbf{I}_3)_{22} = 1\) and \((\mathbf{I}_3)_{23} = 0\).
Exercise 10 (Whether a matrix with the identity pattern is an identity matrix) An identity matrix has ones on its main diagonal and zeros elsewhere. The matrix below has the same pattern of ones and zeros. Let
\[ \mathbf{J} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}. \]
Is \(\mathbf{J}\) an identity matrix?
Compare the shape of \(\mathbf{J}\) with the shape of \(\mathbf{I}_p\) in Definition 7.
Remark 2 (The identity matrix and the Kronecker delta). The entries of the identity matrix are given by the Kronecker delta: \((\mathbf{I}_p)_{ij} = \delta_{ij}\).
Theorem 4 (Identity matrix is a multiplicative identity) For any \(m \times p\) matrix \(\mathbf{A}\):
\[\mathbf{A}\,\mathbf{I}_p = \mathbf{A}\]
\[\mathbf{I}_m\,\mathbf{A} = \mathbf{A}\]
Exercise 11 (Multiplying by an identity matrix) Theorem 4 says that an identity matrix of the right size leaves a matrix unchanged under matrix multiplication, just as multiplying a number by \(1\) leaves it unchanged. Let
\[ \mathbf{A} = \begin{bmatrix} 2 & 0 & -1 \\ 5 & 3 & 4 \end{bmatrix}. \]
Compute \(\mathbf{I}_2 \mathbf{A}\) entry by entry, from the definition of matrix multiplication.
Entry \((i, j)\) of \(\mathbf{I}_2 \mathbf{A}\) is the dot product of the \(i\)th row of \(\mathbf{I}_2\) with the \(j\)th column of \(\mathbf{A}\), as in Example 3.
3 Matrix-vector multiplication
Definition 8 (Matrix-vector multiplication) The matrix-vector product of an \(m \times p\) matrix \(\mathbf{A}\) and a \(p \times 1\) column vector \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\) is the \(m \times 1\) column vector \(\mathbf{A}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\) with entries:
\[(\mathbf{A}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}})_i = \sum_{j=1}^pa_{ij}\, x_j\]
Remark 3 (Each entry is a dot product). Matrix-vector multiplication extends the dot product (Definition 10 in Vectors): entry \(i\) of \(\mathbf{A}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\) is the dot product of row \(i\) of \(\mathbf{A}\) with \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\). For example,
\[ \begin{aligned} \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \begin{bmatrix} 1 \\ -1 \end{bmatrix} &= \begin{bmatrix} 1 \cdot 1 + 2 \cdot(-1) \\ 3 \cdot 1 + 4 \cdot(-1) \end{bmatrix} \\ &= \begin{bmatrix} -1 \\ -1 \end{bmatrix}. \end{aligned} \]
Exercise 12 (A matrix-vector product with more columns than rows) A matrix-vector product \(\mathbf{A}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\) computes one weighted sum of the entries of \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\) for each row of \(\mathbf{A}\), so one multiplication computes several weighted sums at once. The matrix \(\mathbf{A}\) below has more columns than rows, so \(\mathbf{A}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\) is shorter than \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\). Let
\[ \mathbf{A} = \begin{bmatrix} 2 & 0 & -1 \\ 5 & 3 & 4 \end{bmatrix}, \qquad \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}= \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}. \]
Compute \(\mathbf{A}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\).
Entry \(i\) of \(\mathbf{A}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\) is the dot product of the \(i\)th row of \(\mathbf{A}\) with \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\), as in Remark 3.
Definition 9 (Linear system, system of linear equations) A linear system [5] (or system of linear equations) with \(m\) equations in \(n\) unknowns is an equation \(\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{b}}\vphantom{b}}\) in which the \(m \times n\) matrix \(\mathbf{A}\) and the vector \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{b}}\vphantom{b}} \in \mathbb{R}^m\) are given. A solution of the system is a vector \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\in \mathbb{R}^n\) for which \(\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{b}}\vphantom{b}}\) holds.
Example 8 (Two equations in two unknowns) By Definition 8, row \(i\) of \(\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{b}}\vphantom{b}}\) is the equation \(a_{i1} x_1 + \cdots + a_{in} x_n = b_i\). So the two equations \(x_1 + 2 x_2 = 5\) and \(3 x_1 + 4 x_2 = 6\) form the linear system \(\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}= \begin{bmatrix} 5 \\ 6 \end{bmatrix}\). The vector \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}= (-4, 4.5)\) is a solution:
\[ \begin{aligned} \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \begin{bmatrix} -4 \\ 4.5 \end{bmatrix} &= \begin{bmatrix} 1 \cdot(-4) + 2 \cdot 4.5 \\ 3 \cdot(-4) + 4 \cdot 4.5 \end{bmatrix} && \text{(}\href{#def-matvec-mult}{\text{Definition~8}}\text{)} \\ &= \begin{bmatrix} -4 + 9 \\ -12 + 18 \end{bmatrix} && \text{(multiply)} \\ &= \begin{bmatrix} 5 \\ 6 \end{bmatrix} && \text{(add)} \end{aligned} \]
The vector \((1, 2)\) is not a solution: its first equation holds, since \(1 + 2 \cdot 2 = 5\), but its second gives \(3 \cdot 1 + 4 \cdot 2 = 11 \ne 6\).
Exercise 13 (Checking whether a vector solves a linear system) Checking whether a vector solves a linear system takes only one matrix-vector product, which is much less work than solving the system. Let
\[ \mathbf{A} = \begin{bmatrix} 3 & 1 \\ 1 & -2 \end{bmatrix}, \qquad \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{b}}\vphantom{b}} = \begin{bmatrix} 5 \\ 4 \end{bmatrix}, \qquad \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}= \begin{bmatrix} 2 \\ -1 \end{bmatrix}. \]
Is \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\) a solution of \(\mathbf{A}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{b}}\vphantom{b}}\)?
Compute \(\mathbf{A}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\) with Definition 8. Then compare it with \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{b}}\vphantom{b}}\), as in Example 8.
4 Transposes of sums and products
Theorem 5 (Transpose of a sum) For \(m \times n\) matrices \(\mathbf{A}\) and \(\mathbf{B}\):
\[{(\mathbf{A} + \mathbf{B})}^{\top} = {\mathbf{A}}^{\top} + {\mathbf{B}}^{\top}\]
In particular, for column vectors \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\) and \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}\) of the same length:
\[{(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}+ \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}})}^{\top} = {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}}^{\top} + {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}}^{\top}\]
Proof. Entry \((i, j)\) of each side:
\[ \begin{aligned} \mathopen{}\left[{(\mathbf{A} + \mathbf{B})}^{\top}\right]\mathclose{}_{ij} &= (\mathbf{A} + \mathbf{B})_{ji} && \text{(definition of the transpose)} \\ &= a_{ji} + b_{ji} && \text{(definition of matrix addition)} \\ &= ({\mathbf{A}}^{\top})_{ij} + ({\mathbf{B}}^{\top})_{ij} && \text{(definition of the transpose)} \\ &= \mathopen{}\left[{\mathbf{A}}^{\top} + {\mathbf{B}}^{\top}\right]\mathclose{}_{ij} && \text{(definition of matrix addition)} \end{aligned} \]
Exercise 14 (Transposing a sum of two matrices) Theorem 5 lets a transpose be taken before or after adding, whichever is less work. Let
\[ \mathbf{A} = \begin{bmatrix}1 & 2 & 0 \\ 3 & -1 & 4\end{bmatrix}, \qquad \mathbf{B} = \begin{bmatrix}0 & 1 & 1 \\ 2 & 2 & -3\end{bmatrix}. \]
Find \({(\mathbf{A} + \mathbf{B})}^{\top}\).
Add first with Definition 8 in Matrices, then take the transpose.
Theorem 6 (Transpose of a product) For an \(m \times k\) matrix \(\mathbf{A}\) and a \(k \times n\) matrix \(\mathbf{B}\):
\[ \underbrace{{(\mathbf{A}\mathbf{B})}^{\top}}_{n \times m} = \underbrace{{\mathbf{B}}^{\top}}_{n \times k}\,\underbrace{{\mathbf{A}}^{\top}}_{k \times m} \]
Proof. Entry \((i, j)\) of each side:
\[ \begin{aligned} \mathopen{}\left[{(\mathbf{A}\mathbf{B})}^{\top}\right]\mathclose{}_{ij} &= (\mathbf{A}\mathbf{B})_{ji} && \text{(definition of the transpose)} \\ &= \sum_{s=1}^{k} a_{js}\, b_{si} && \text{(definition of matrix multiplication)} \\ &= \sum_{s=1}^{k} ({\mathbf{B}}^{\top})_{is}\, ({\mathbf{A}}^{\top})_{sj} && \text{(definition of the transpose; reorder each product)} \\ &= \mathopen{}\left[{\mathbf{B}}^{\top}\,{\mathbf{A}}^{\top}\right]\mathclose{}_{ij} && \text{(definition of matrix multiplication)} \end{aligned} \]
Remark 4 (The order of the factors reverses). Transposing a product reverses the order of the factors. Keeping the original order usually gives an undefined product or a different matrix. For example, with \(\mathbf{A} = [1,\; 2]\) (\(1 \times 2\)) and \(\mathbf{B} = \begin{bmatrix} 3 \\ 4 \end{bmatrix}\) (\(2 \times 1\)),
\[ \begin{aligned} \mathbf{A}\mathbf{B} &= 1 \cdot 3 + 2 \cdot 4 \\ &= 11, \end{aligned} \]
so \({(\mathbf{A}\mathbf{B})}^{\top} = 11\), and
\[ {\mathbf{B}}^{\top}\,{\mathbf{A}}^{\top} = [3,\; 4] \begin{bmatrix} 1 \\ 2 \end{bmatrix} = 11, \qquad {\mathbf{A}}^{\top}\,{\mathbf{B}}^{\top} = \begin{bmatrix} 1 \\ 2 \end{bmatrix} [3,\; 4] = \begin{bmatrix} 3 & 4 \\ 6 & 8 \end{bmatrix}. \]
If instead \(\mathbf{A}\) is \(2 \times 3\) and \(\mathbf{B}\) is \(3 \times 1\), then \({\mathbf{B}}^{\top}\,{\mathbf{A}}^{\top}\) is a \((1 \times 3)(3 \times 2)\) product, but \({\mathbf{A}}^{\top}\,{\mathbf{B}}^{\top}\) is a \((3 \times 2)(1 \times 3)\) product, which is undefined.
Exercise 15 (The order of the factors in a transposed square product) Remark 4 shows that, for factors that are not square, keeping the original order of the factors in the transpose of a product can give an undefined product. For two square matrices of the same size, both \({\mathbf{A}}^{\top}{\mathbf{B}}^{\top}\) and \({\mathbf{B}}^{\top}{\mathbf{A}}^{\top}\) are defined, so the shapes alone cannot settle which order gives \({(\mathbf{A}\mathbf{B})}^{\top}\). Let
\[ \mathbf{A} = \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix}, \qquad \mathbf{B} = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}. \]
Does \({\mathbf{A}}^{\top}{\mathbf{B}}^{\top}\) equal \({(\mathbf{A}\mathbf{B})}^{\top}\) for these \(\mathbf{A}\) and \(\mathbf{B}\)?
Compute \(\mathbf{A}\mathbf{B}\) with Definition 1 and take its transpose, then compute \({\mathbf{A}}^{\top}{\mathbf{B}}^{\top}\) and compare the two entry by entry.
Theorem 7 (A \(1 \times 1\) product equals its own transpose) If \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}\) and \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}\) are vectors of length \(p\) and \(\mathbf{M}\) is a \(p \times p\) matrix, then \({\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}}^{\top}\mathbf{M}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}\) is a number, and
\[ {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}}^{\top}\mathbf{M}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}} = {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}}^{\top}\,{\mathbf{M}}^{\top}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}. \]
In particular, \({\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}}^{\top}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}} = {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}}^{\top}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}\).
Proof. The product \({\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}}^{\top}\mathbf{M}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}\) is a \((1 \times p)(p \times p)(p \times 1)\) product, so it is a \(1 \times 1\) matrix. The transpose of a \(1 \times 1\) matrix is itself, so
\[ \begin{aligned} {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}}^{\top}\mathbf{M}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}} &= {\mathopen{}\left({\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}}^{\top}\mathbf{M}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}\right)\mathclose{}}^{\top} && \text{(a } 1 \times 1 \text{ matrix equals its transpose)} \\ &= {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}}^{\top}\,{\mathbf{M}}^{\top}\,{\mathopen{}\left({\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}}^{\top}\right)\mathclose{}}^{\top} && \text{(transpose of a product, twice)} \\ &= {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}}^{\top}\,{\mathbf{M}}^{\top}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} && \text{(transposing twice changes nothing)} \end{aligned} \]
The transpose step is Theorem 6. Taking \(\mathbf{M} = \mathbf{I}\) gives the last statement.
Example 9 (Two ways to write the same number) Take \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} = (1, 2)\), \(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}} = (3, -1)\) and \(\mathbf{M} = \begin{bmatrix} 1 & 2 \\ 0 & 3 \end{bmatrix}\). Then \(\mathbf{M}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}} = (1, -3)\), so
\[ {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}}^{\top}\mathbf{M}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}} = 1 \cdot 1 + 2 \cdot (-3) = -5. \]
Also \({\mathbf{M}}^{\top} = \begin{bmatrix} 1 & 0 \\ 2 & 3 \end{bmatrix}\) and \({\mathbf{M}}^{\top}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} = (1, 8)\), so
\[ {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}}^{\top}\,{\mathbf{M}}^{\top}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} = 3 \cdot 1 + (-1) \cdot 8 = -5. \]
The two products are equal, as the theorem says. In least squares, this is why the two cross terms of \({(\mathbf{X}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{\beta}}\vphantom{\beta}}- \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}})}^{\top}(\mathbf{X}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{\beta}}\vphantom{\beta}}- \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}})\) are equal and can be combined.
Exercise 16 (Evaluating a product of a vector, a matrix and a vector) Theorem 7 turns \({\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}}^{\top}\,{\mathbf{M}}^{\top}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}\) back into \({\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}}^{\top}\mathbf{M}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}\), which can be the easier product of a vector, a matrix and a vector to compute. Let
\[ \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} = \begin{bmatrix}1 \\ -1\end{bmatrix}, \qquad \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}} = \begin{bmatrix}2 \\ 3\end{bmatrix}, \qquad \mathbf{M} = \begin{bmatrix}0 & 1 \\ 2 & 0\end{bmatrix}. \]
Find \({\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}}^{\top}\,{\mathbf{M}}^{\top}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}\).
By Theorem 7, it is enough to compute \({\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}}^{\top}\mathbf{M}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}\).
Definitions on this page
- Definition 1 (Matrix multiplication)
- Definition 2 (Shape rule)
- Definition 3 (Square matrix)
- Definition 4 (Main diagonal)
- Definition 5 (Diagonal entry)
- Definition 6 (Off-diagonal entry)
- Definition 7 (Identity matrix)
- Definition 8 (Matrix-vector multiplication)
- Definition 9 (Linear system, system of linear equations)