The Extended Invertible Matrix Theorem

Why Square Matrices Have Several Tests for Invertibility

For a square matrix, invertibility can be recognized in several ways. One test asks whether an inverse matrix exists; others ask whether the columns are independent, whether they span the whole space, or whether a related homogeneous system has only the zero solution. These are not separate coincidences. Each condition describes the same underlying fact: the matrix sends the \(n\) coordinate directions to \(n\) directions that still contain all the information needed to recover an input.

Throughout, let \(\mathbf{A}\in\mathbb{R}^{n\times n}\). Its columns are \(\mathbf{a}_1,\dots,\mathbf{a}_n\), its column space is \(\operatorname{Col}\mathbf{A}=\operatorname{span}\{\mathbf{a}_1,\dots,\mathbf{a}_n\}\), and its null space is \(\operatorname{Nul}\mathbf{A}=\{\mathbf{x}\in\mathbb{R}^n:\mathbf{A}\mathbf{x}=\mathbf{0}\}\). The left null space is \(\operatorname{Nul}\mathbf{A}^{\top}=\{\mathbf{y}\in\mathbb{R}^n:\mathbf{A}^{\top}\mathbf{y}=\mathbf{0}\}\). The rank of \(\mathbf{A}\) is \(\dim(\operatorname{Col}\mathbf{A})\). The matrix is invertible if there is a matrix \(\mathbf{A}^{-1}\) satisfying both \(\mathbf{A}\mathbf{A}^{-1}=\mathbf{I}_n\) and \(\mathbf{A}^{-1}\mathbf{A}=\mathbf{I}_n\).

What the Conditions Measure

The independence condition concerns the equation \(\mathbf{A}\mathbf{x}=\mathbf{0}\). Since \(\mathbf{A}\mathbf{x}=x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n\), a nonzero vector in \(\operatorname{Nul}\mathbf{A}\) is exactly a nontrivial dependence relation among the columns. Thus, independent columns mean that the null space contains only \(\mathbf{0}\).

The spanning condition asks whether every possible right-hand side \(\mathbf{b}\in\mathbb{R}^n\) can be written as \(\mathbf{A}\mathbf{x}\). This is equivalent to asking whether \(\mathbf{A}\mathbf{x}=\mathbf{b}\) is solvable for every \(\mathbf{b}\). The left null space has a different role: its vectors give linear combinations of the rows that equal the zero row. In particular, \(\mathbf{y}\in\operatorname{Nul}\mathbf{A}^{\top}\) means \(\mathbf{y}^{\top}\mathbf{A}=\mathbf{0}^{\top}\), not \(\mathbf{A}\mathbf{y}=\mathbf{0}\).

Two earlier results about rank will be used in the proof. The Matrix Rank-Nullity Theorem says that for a matrix with \(n\) columns, \(\operatorname{rank}\mathbf{A}+\operatorname{nullity}\mathbf{A}=n\). The Rank of a Transpose result says that \(\operatorname{rank}\mathbf{A}^{\top}=\operatorname{rank}\mathbf{A}\). Both apply here because \(\mathbf{A}\) and \(\mathbf{A}^{\top}\) are square \(n\times n\) matrices.

Proof of the Equivalences

One elementary fact connects rank with spanning: a subspace of \(\mathbb{R}^n\) has dimension \(n\) exactly when it is all of \(\mathbb{R}^n\). For completeness, if a subspace \(U\) has dimension \(n\), a basis of \(U\) is an independent list of \(n\) vectors in \(\mathbb{R}^n\). Such a list spans \(\mathbb{R}^n\), as follows from the usual pivot test: placing its vectors as columns gives an \(n\times n\) matrix with a pivot in every column, hence a pivot in every row, so its RREF is \(\mathbf{I}_n\). The row operations are invertible, so the columns of the original matrix span \(\mathbb{R}^n\) as well. Conversely, if \(U=\mathbb{R}^n\), its dimension is \(n\), since the standard basis \(\mathbf{e}_1,\dots,\mathbf{e}_n\) is a basis.

Proof. First, (3) and (5) are equivalent directly from the definition of matrix multiplication: \(\mathbf{A}\mathbf{x}=\mathbf{0}\) says \(x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n=\mathbf{0}\), so the columns are independent exactly when the only such coefficients are all zero. By the Matrix Rank-Nullity Theorem, \(\operatorname{rank}\mathbf{A}+\operatorname{nullity}\mathbf{A}=n\), so (2) and (5) are equivalent. By the definition of rank, \(\operatorname{rank}\mathbf{A}=\dim(\operatorname{Col}\mathbf{A})\); the finite-dimensional fact just explained gives the equivalence of (2) and (4). Also, rank-nullity applied to \(\mathbf{A}^{\top}\) gives \(\operatorname{rank}\mathbf{A}^{\top}+\operatorname{nullity}\mathbf{A}^{\top}=n\). Since \(\operatorname{rank}\mathbf{A}^{\top}=\operatorname{rank}\mathbf{A}\), condition (2) holds exactly when \(\operatorname{nullity}\mathbf{A}^{\top}=0\), which is (6). If (1) holds and \(\mathbf{A}\mathbf{x}=\mathbf{0}\), then \(\mathbf{x}=\mathbf{A}^{-1}\mathbf{A}\mathbf{x}=\mathbf{0}\); therefore (1) implies (5). Finally, assume (2). The RREF of \(\mathbf{A}\) has \(n\) pivots, one in each of its \(n\) columns and \(n\) rows, so it is \(\mathbf{I}_n\). Each row operation is multiplication on the left by an invertible elementary matrix. Consequently a product \(\mathbf{E}\) of these matrices satisfies \(\mathbf{E}\mathbf{A}=\mathbf{I}_n\), and \(\mathbf{E}\) is invertible. It follows that \(\mathbf{A}=\mathbf{E}^{-1}\), so \(\mathbf{A}\) is invertible. We have shown that (1) implies (5), and that (2), (3), (4), (5), and (6) are equivalent, while (2) implies (1). Hence all six conditions are equivalent. \(\square

A Singular Matrix and Its Two Null Spaces

Using the Conditions Efficiently

The theorem allows a proof to begin from whichever condition is easiest to establish. To prove a square matrix invertible, it is enough to show that its columns are independent, or that its columns span the target space, or that its null space is trivial. To prove it is not invertible, any one nontrivial null vector or any nontrivial left-null vector is enough. Full rank is often a convenient summary: for a square matrix, rank \(n\) means there are \(n\) pivots and every one of the six conditions follows.

The square-matrix hypothesis matters. For a rectangular matrix, having independent columns does not generally mean that the columns span the entire coordinate space, and a matrix with full row rank need not have a two-sided inverse. The theorem joins these properties because there are exactly \(n\) columns and the codomain is also \(\mathbb{R}^n\).

Common Mistake: Confusing the Two Null Spaces

A row dependence does not usually give a vector in \(\operatorname{Nul}\mathbf{A}\). For the matrix \(\mathbf{C}\) above, row 2 equals twice row 1, so \((-2,1,0)^{\top}\) belongs to \(\operatorname{Nul}\mathbf{C}^{\top}\). A mistaken calculation might treat that vector as a null vector of \(\mathbf{C}\). But:

The correction is to keep the equations distinct. A column dependence supplies coefficients \(\mathbf{x}\) for \(\mathbf{A}\mathbf{x}=\mathbf{0}\). A row dependence supplies coefficients \(\mathbf{y}\) for \(\mathbf{A}^{\top}\mathbf{y}=\mathbf{0}\). Both are useful tests for invertibility, but they are not interchangeable calculations.