By now we have many ways to describe a square matrix: its inverse, its pivots, whether its columns are independent or span. For a square matrix, these are not separate facts. They all stand or fall together.
The Invertible Matrix Theorem. For an $n \times n$ matrix $A$, the following statements are equivalent (all true or all false):
- (a) $A$ is invertible.
- (b) $A$ is row equivalent to $I_n$.
- (c) $A$ has $n$ pivot positions.
- (d) $A\mathbf{x} = \mathbf{0}$ has only the trivial solution.
- (e) The columns of $A$ are linearly independent.
- (f) $A\mathbf{x} = \mathbf{b}$ has at least one solution for every $\mathbf{b}$ in $\mathbb{R}^n$.
- (g) The columns of $A$ span $\mathbb{R}^n$.
- (h) There is a matrix $C$ with $CA = I$; (i) there is a matrix $D$ with $AD = I$.
- (j) $A^{T}$ is invertible.
Why it works
The engine is counting pivots. A square matrix has $n$ rows and $n$ columns, so "a pivot in every column" and "a pivot in every row" both mean exactly $n$ pivots. A pivot in every column gives (d) and (e) (no free variables). A pivot in every row gives (f) and (g) (no row can become $0 = c$). And $n$ pivots in an $n \times n$ matrix means its RREF is $I$, which is (b), and then Gauss–Jordan produces the inverse, (a). Going back, if $A$ is invertible then $A\mathbf{x} = \mathbf{0}$ gives $\mathbf{x} = A^{-1}\mathbf{0} = \mathbf{0}$. For a matrix that is not square, the row count and column count differ, and the statements split apart.
Worked example: Using the theorem on a matrix
Is $A = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 7 \\ 1 & 2 & 5 \end{bmatrix}$ invertible? What does that say about its columns and about $A\mathbf{x} = \mathbf{b}$?
- $R_2 \to R_2 - 2R_1$ and $R_3 \to R_3 - R_1$ give $\begin{bmatrix} 1 & 2 & 3 \\ 0 & 0 & 1 \\ 0 & 0 & 2 \end{bmatrix}$, then $R_3 \to R_3 - 2R_2$: $\begin{bmatrix} 1 & 2 & 3 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}$.
- Only 2 pivots for a $3 \times 3$ matrix, so (c) fails, and therefore every statement fails.
- So $A$ is not invertible, its columns are dependent (indeed column 2 is twice column 1), they do not span $\mathbb{R}^3$, and some $\mathbf{b}$ make $A\mathbf{x} = \mathbf{b}$ inconsistent.
Answer: Not invertible; all the statements are false.
Worked example: Reasoning without numbers
$A$ is $5 \times 5$, and $A\mathbf{x} = \mathbf{b}$ has a solution for every $\mathbf{b}$ in $\mathbb{R}^5$. Can $A\mathbf{x} = \mathbf{0}$ have a nontrivial solution?
- The hypothesis is statement (f). Since $A$ is square, (f) implies all the others, including (d).
- So $A\mathbf{x} = \mathbf{0}$ has only the trivial solution. (In fact, each $A\mathbf{x} = \mathbf{b}$ has exactly one solution.)
Answer: No.
The theorem is for square matrices only. A $3 \times 4$ matrix can have columns that span $\mathbb{R}^3$ while its columns are dependent; a $4 \times 3$ matrix can have independent columns that do not span $\mathbb{R}^4$.
Key idea
For a square matrix, invertible, $n$ pivots, independent columns, spanning columns, unique solutions and "only the trivial solution" are the same statement in different clothes. Check one, and you know them all.