Matrix Algebra

Let \(n\) be the number of columns of \(A\) (equivalently, the number of rows of \(B\)). Then \[ \bigl((AB)^top\bigr)_{ij} = (AB)_{ji} = \sum_{k=1}^n a_{jk} b_{ki}, \] and on the other hand \[ (B^top A^top)_{ij} = \sum_{k=1}^n (B^top)_{ik} (A^top)_{kj} = \sum_{k=1}^n b_{ki} a_{jk} = \sum_{k=1}^n a_{jk} b_{ki}. \] The two expressions agree entry by entry, so \((AB)^top = B^top A^top\). The identity extends inductively to products of more than two matrices: \((A_1 A_2 \cdots A_k)^top = A_k^top \cdots A_2^top A_1^top\).

By the transpose-of-product theorem above, \[ (A^{-1})^top A^top = (A A^{-1})^top = I^top = I, \] and similarly \[ A^top (A^{-1})^top = (A^{-1} A)^top = I^top = I. \] Hence \(A^top\) is invertible with inverse \((A^{-1})^top\).

(Sufficiency) If \(ad - bc \neq 0\), direct computation gives \[ \frac{1}{ad - bc} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix} \begin{bmatrix} a & b \\ c & d \end{bmatrix} = \frac{1}{ad - bc} \begin{bmatrix} ad - bc & 0 \\ 0 & ad - bc \end{bmatrix} = I, \] and similarly for the product in the reverse order.

(Necessity) Suppose \(ad - bc = 0\). We show \(A\) is not invertible by exhibiting a nonzero vector \(\mathbf{v}\) with \(A\mathbf{v} = \mathbf{0}\) — for then no inverse can exist, since an inverse would force \(\mathbf{v} = A^{-1}\mathbf{0} = \mathbf{0}\), a contradiction. Direct computation shows \[ A \begin{bmatrix} d \\ -c \end{bmatrix} = \begin{bmatrix} ad - bc \\ cd - cd \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}, \qquad A \begin{bmatrix} -b \\ a \end{bmatrix} = \begin{bmatrix} -ab + ab \\ -bc + ad \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}. \] If \(A\) has any nonzero entry, then at least one of the two vectors \(\begin{bmatrix} d \\ -c \end{bmatrix}\) and \(\begin{bmatrix} -b \\ a \end{bmatrix}\) is nonzero — so we have produced the required \(\mathbf{v}\). The remaining case is \(A = 0\), the zero matrix, which is trivially not invertible (any candidate inverse \(B\) satisfies \(AB = 0 \neq I\)).

For \(A = \begin{bmatrix} 1 & 9 \\ 8 & 2 \end{bmatrix}\), we have \(ad - bc = 2 - 72 = -70\), so \[ A^{-1} = \frac{1}{-70}\begin{bmatrix} 2 & -9 \\ -8 & 1 \end{bmatrix} = \begin{bmatrix} -\tfrac{1}{35} & \tfrac{9}{70} \\[2pt] \tfrac{4}{35} & -\tfrac{1}{70} \end{bmatrix}. \] One can check directly that \(A A^{-1} = I\).

Take \(A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}\) and the elementary matrices \[ \begin{align*} &E_1 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}, \quad E_2 = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \\\\ &E_3 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -3 & 1 \end{bmatrix}. \end{align*} \] Multiplying on the left: \[ \begin{align*} &E_1 A = \begin{bmatrix} 1 & 2 & 3 \\ 7 & 8 & 9 \\ 4 & 5 & 6 \end{bmatrix} \quad &\text{(interchange Row 2 and Row 3)} \\\\ &E_2 A = \begin{bmatrix} 2 & 4 & 6 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} \quad &\text{(scale Row 1 by 2)} \\\\ &E_3 A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ -5 & -7 & -9 \end{bmatrix} \quad &\text{(Row 3} \to \text{Row 3} - 3\,\text{Row 2)}. \end{align*} \]

A sequence of row operations is encoded as a single matrix by multiplying the elementary matrices together (in the same order as the operations are applied — read right-to-left because matrix products act on the right): \[ \begin{align*} E_3 E_2 E_1 A &= \begin{bmatrix} 2 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & -3 \end{bmatrix} \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} \\\\ &= \begin{bmatrix} 2 & 4 & 6 \\ 7 & 8 & 9 \\ -17 & -19 & -21 \end{bmatrix} = B. \end{align*} \] Each elementary row operation is reversible (interchange undoes itself; scaling reverses by reciprocal; replacement reverses by negation), so each elementary matrix is invertible. Multiplying both sides by \((E_3 E_2 E_1)^{-1} = E_1^{-1} E_2^{-1} E_3^{-1}\) recovers the original \(A\): \[ A = E_1^{-1} E_2^{-1} E_3^{-1} B = \begin{bmatrix} 0.5 & 0 & 0 \\ 0 & 3 & 1 \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 2 & 4 & 6 \\ 7 & 8 & 9 \\ -17 & -19 & -21 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}. \] (The matrix \(A\) used here is in fact singular — its rows satisfy \(\text{Row 3} = 2\,\text{Row 2} - \text{Row 1}\) — so this example illustrates only the operations of elementary matrices, not their use for inversion. We turn to that next.)

(\(\Leftarrow\)) Suppose the RREF of \(A\) is \(I_n\). Then there is a sequence of elementary row operations transforming \(A\) into \(I_n\); each operation is performed by left-multiplication by an elementary matrix, so \[ (E_k \cdots E_2 E_1)\, A = I_n. \tag{1} \] The matrix \(M := E_k \cdots E_2 E_1\) is a product of invertible matrices and therefore invertible, with explicit inverse \(M^{-1} = E_1^{-1} E_2^{-1} \cdots E_k^{-1}\). Equation (1) reads \(MA = I_n\); multiplying on the left by \(M^{-1}\) gives \(A = M^{-1}\), which exhibits \(A\) as invertible. Moreover \(A^{-1} = M = E_k \cdots E_1\), and since \(M = M \cdot I_n\) we have \[ A^{-1} = (E_k \cdots E_2 E_1)\, I_n. \tag{2} \] Equations (1) and (2) say: the same sequence of elementary matrices, applied to \(A\), produces \(I_n\); applied to \(I_n\), produces \(A^{-1}\). Performing the operations side by side on the augmented matrix \([A \mid I]\) therefore yields \([I \mid A^{-1}]\) in a single sweep.

(\(\Rightarrow\)) Suppose \(A\) is invertible. Reduce \(A\) to its RREF, call it \(R\); as in the previous direction, this gives \(NA = R\) for some invertible \(N\) (a product of elementary matrices). Hence \(R = NA\) is invertible, being the product of two invertible matrices.

We claim that an invertible \(n \times n\) matrix in RREF must equal \(I_n\). Indeed, if \(R\) had any zero row — say its \(i\)-th row — then for every \(\mathbf{x}\) the \(i\)-th coordinate of \(R\mathbf{x}\) would be zero, so the equation \(R\mathbf{x} = \mathbf{e}_i\) would be unsolvable, contradicting invertibility. Hence every row of \(R\) contains a leading \(1\) — giving \(n\) leading \(1\)'s in \(n\) distinct columns. Combined with the RREF staircase condition (each leading \(1\) lies strictly to the right of the previous one), the \(n\) leading \(1\)'s must occupy positions \((1,1), (2,2), \ldots, (n,n)\). The remaining RREF condition (each pivot column has zeros above and below its leading \(1\)) then forces all off-diagonal entries to vanish: \(R = I_n\).

The result follows by tracking which entries of \(A\) and \(B\) contribute to a given entry of \(AB\). Pick any scalar entry \((AB)_{rs}\): by the entrywise definition of matrix multiplication, \[ (AB)_{rs} = \sum_{\ell} a_{r\ell} b_{\ell s}. \] Now suppose the global indices \(r, \ell, s\) lie in row-block \(i\), column-block-of-\(A\) (= row-block-of-\(B\)) \(k\), and column-block \(j\) respectively. The compatibility condition guarantees this assignment is well-defined: every middle index \(\ell\) belongs to exactly one matching pair \((A\)-column-block-\(k\), \(B\)-row-block-\(k\)). Splitting the sum over \(\ell\) according to which block it belongs to, \[ (AB)_{rs} = \sum_{k} \, \sum_{\ell \in \text{block } k} a_{r\ell} b_{\ell s} = \sum_k (A_{ik} B_{kj})_{r' s'}, \] where \(r', s'\) are the local indices of \(r, s\) within their respective blocks. The right-hand side is exactly the \((r', s')\)-entry of the block sum \(C_{ij} = \sum_k A_{ik} B_{kj}\). Hence \(AB\), reassembled from its blocks, has \((i, j)\)-block equal to \(C_{ij}\), as claimed.

Consider \[ A = \left[\begin{array}{ccc|cc} 1 & 2 & -1 & 3 & 4 \\ 5 & 3 & 0 & -2 & 1 \\ \hline -1 & 3 & 1 & 7 & 1 \end{array}\right] = \left[\begin{array}{c|c} A_{11} & A_{12} \\ \hline A_{21} & A_{22} \end{array}\right], \qquad B = \left[\begin{array}{cc} 3 & 2 \\ 3 & -5 \\ -1 & 6 \\ \hline 4 & 7\\ 1 & 1 \end{array}\right] = \left[\begin{array}{c} B_1 \\ \hline B_2 \end{array}\right], \] where \(A_{11}\) is \(2 \times 3\), \(A_{12}\) is \(2 \times 2\), \(A_{21}\) is \(1 \times 3\), \(A_{22}\) is \(1 \times 2\), \(B_1\) is \(3 \times 2\), and \(B_2\) is \(2 \times 2\). The column partition of \(A\) (3 + 2) matches the row partition of \(B\) (3 + 2), so block multiplication applies: \[ AB = \left[\begin{array}{c} A_{11}B_1 + A_{12}B_2 \\ \hline A_{21}B_1 + A_{22}B_2 \end{array}\right]. \] Computing each block: \[ \begin{align*} A_{11}B_1 &= \begin{bmatrix} 1 & 2 & -1 \\ 5 & 3 & 0 \end{bmatrix} \begin{bmatrix} 3 & 2 \\ 3 & -5 \\ -1 & 6 \end{bmatrix} = \begin{bmatrix} 10 & -14 \\ 24 & -5 \end{bmatrix}, \\ A_{12}B_2 &= \begin{bmatrix} 3 & 4 \\ -2 & 1 \end{bmatrix} \begin{bmatrix} 4 & 7 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} 16 & 25 \\ -7 & -13 \end{bmatrix}, \\ A_{21}B_1 &= \begin{bmatrix} -1 & 3 & 1 \end{bmatrix} \begin{bmatrix} 3 & 2 \\ 3 & -5 \\ -1 & 6 \end{bmatrix} = \begin{bmatrix} 5 & -11 \end{bmatrix}, \\ A_{22}B_2 &= \begin{bmatrix} 7 & 1 \end{bmatrix} \begin{bmatrix} 4 & 7 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} 29 & 50 \end{bmatrix}. \end{align*} \] Assembling, \[ AB = \left[\begin{array}{cc} 26 & 11 \\ 17 & -18\\ \hline 34 & 39 \end{array}\right]. \]

Let \[ A = \begin{bmatrix} 1 & 2 & -1 \\ 2 & 1 & -2 \\ -3 & 1 & 1 \end{bmatrix}. \] Reducing \(A\) to row echelon form (no row interchanges needed) gives \[ U = \begin{bmatrix} 1 & 2 & -1 \\ 0 & -3 & 0 \\ 0 & 0 & -2 \end{bmatrix}. \] We track the elementary matrices that perform each step of the reduction: \[ \begin{align*} &E_1 = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \quad E_2 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 3 & 0 & 1 \end{bmatrix}, \\\\ &E_3 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & \tfrac{7}{3} & 1 \end{bmatrix}. \end{align*} \]

Since \(E_3 E_2 E_1 A = U\), we have \(A = (E_3 E_2 E_1)^{-1} U = E_1^{-1} E_2^{-1} E_3^{-1}\, U\). Each \(E_i^{-1}\) is obtained by negating the off-diagonal entry: e.g., \(E_1^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\). Multiplying these three out gives \[ L = E_1^{-1} E_2^{-1} E_3^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -3 & -\tfrac{7}{3} & 1 \end{bmatrix}. \] Verifying: \[ LU = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -3 & -\tfrac{7}{3} & 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & -1 \\ 0 & -3 & 0 \\ 0 & 0 & -2 \end{bmatrix} = \begin{bmatrix} 1 & 2 & -1 \\ 2 & 1 & -2\\ -3 & 1 & 1 \end{bmatrix} = A. \checkmark \]