2.3 Characterizations of Invertible Matrices (IMT)

Theory: Characterizations of Invertible Matrices (The IMT)

One of the most foundational milestones in linear algebra is the Invertible Matrix Theorem (IMT) (Theorem 8 in Lay §2.3). It binds together almost all major concepts developed in Chapters 1 and 2 for square $n \times n$ matrices.

[!IMPORTANT] The Invertible Matrix Theorem (Lay §2.3, Theorem 8): Let $A$ be a square $n \times n$ matrix. Then the following statements are equivalent. That is, for a given $A$ , the statements are either all true or all false:

$A$ is an invertible matrix.

$A$ is row equivalent to the $n \times n$ identity matrix $I_n$ .

$A$ has $n$ pivot positions.

The equation $A\mathbf{x} = \mathbf{0}$ has only the trivial solution.

The columns of $A$ form a linearly independent set.

The linear transformation $\mathbf{x} \mapsto A\mathbf{x}$ is one-to-one.

The equation $A\mathbf{x} = \mathbf{b}$ has at least one solution for each $\mathbf{b} \in \mathbb{R}^n$ .

The columns of $A$ span $\mathbb{R}^n$ .

The linear transformation $\mathbf{x} \mapsto A\mathbf{x}$ maps $\mathbb{R}^n$ onto $\mathbb{R}^n$ .

There is an $n \times n$ matrix $C$ such that $CA = I_n$ .

There is an $n \times n$ matrix $D$ such that $AD = I_n$ .

$A^T$ is an invertible matrix.

Strategic Consequences for Square Matrices

Because of the IMT, for an $n \times n$ matrix $A$ :

To verify that $A$ is invertible, you do not need to find $A^{-1}$ ; you only need to show that $A$ has $n$ pivots.
A square matrix cannot be one-to-one without also being onto; one-to-one and onto are completely equivalent for square matrices.
If $AB = I_n$ for square matrices $A$ and $B$ , then automatically $BA = I_n$ and $B = A^{-1}$ (you don’t have to check both directions).

Solved Examples (Textbook Questions)

Exercise 1

(Adapted from Lay §2.3, Exercises 11–14)

Determine whether each of the following statements is True or False for an $n \times n$ matrix $A$ . Justify each answer using the Invertible Matrix Theorem.

Statement A: If the equation $A\mathbf{x} = \mathbf{0}$ has a non-trivial solution, then the columns of $A$ cannot span $\mathbb{R}^n$ .
Statement B: If $A$ is an $n \times n$ matrix and the transformation $\mathbf{x} \mapsto A\mathbf{x}$ is one-to-one, then $A\mathbf{x} = \mathbf{b}$ has a unique solution for each $\mathbf{b} \in \mathbb{R}^n$ .
Statement C: If $A$ has $n$ pivot positions, then $A^T$ is also invertible.

Show solution ↓

Solution

Statement A: True. By the IMT, if $A\mathbf{x} = \mathbf{0}$ has only the trivial solution (statement d), then the columns of $A$ span $\mathbb{R}^n$ (statement h). By the contrapositive, if $A\mathbf{x} = \mathbf{0}$ has a non-trivial solution (statement d is false), then all statements in the IMT are false, meaning the columns of $A$ cannot span $\mathbb{R}^n$ .
Statement B: True. If $\mathbf{x} \mapsto A\mathbf{x}$ is one-to-one (statement f), then $A$ is invertible (statement a). When $A$ is invertible, the equation $A\mathbf{x} = \mathbf{b}$ has the unique solution $\mathbf{x} = A^{-1}\mathbf{b}$ for each $\mathbf{b} \in \mathbb{R}^n$ (Theorem 5, Lay §2.2).
Statement C: True. If $A$ has $n$ pivot positions (statement c), then $A$ is invertible (statement a). By statement (l) of the IMT, $A^T$ is also an invertible matrix.

Exercise 2

(Adapted from Lay §2.3, Exercise 33)

Let $A$ and $B$ be $n \times n$ square matrices. Show that if the matrix product $AB$ is invertible, then both $A$ and $B$ must be invertible.

(Provide a proof using the Invertible Matrix Theorem without calculating determinants).

Show solution ↓

Solution

Let $W = AB$ . We are given that $W$ is invertible.

Step 1: Prove $B$ is invertible. Consider the equation $B\mathbf{x} = \mathbf{0}$ . Multiply both sides from the left by $A$ :

A(B\mathbf{x}) = A\mathbf{0} \implies (AB)\mathbf{x} = \mathbf{0}

Since $AB$ is invertible, by IMT statement (d), the equation $(AB)\mathbf{x} = \mathbf{0}$ has only the trivial solution $\mathbf{x} = \mathbf{0}$ . Therefore, $B\mathbf{x} = \mathbf{0}$ must also have only the trivial solution $\mathbf{x} = \mathbf{0}$ . By IMT statement (d) applied to $B$ , $B$ is invertible.

Step 2: Prove $A$ is invertible. Since $B$ is invertible, its inverse $B^{-1}$ exists. Now write:

A = A(B B^{-1}) = (AB)B^{-1}

Since $AB$ is invertible and $B^{-1}$ is invertible, $A$ is the product of two invertible matrices. By Theorem 6 (Lay §2.2), the product of invertible matrices is invertible, with:

A^{-1} = ((AB)B^{-1})^{-1} = (B^{-1})^{-1}(AB)^{-1} = B(AB)^{-1}

Thus, $A$ is invertible.

Exercise 3

(Adapted from Lay §2.3, Exercise 23)

An $n \times n$ upper triangular matrix $U$ has non-zero entries on its main diagonal:

U = \begin{bmatrix} u_{11} & u_{12} & \cdots & u_{1n} \\ 0 & u_{22} & \cdots & u_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & u_{nn} \end{bmatrix}, \quad \text{with } u_{ii} \ne 0 \text{ for all } i = 1, \dots, n.

Use the Invertible Matrix Theorem to explain why $U$ must be invertible.

Show solution ↓

Solution

Since $U$ is upper triangular and all entries below the main diagonal are zero, the matrix is already in row echelon form (REF).
Because $u_{ii} \ne 0$ for each $i = 1, \dots, n$ , the leading entry of every row is situated on the main diagonal in column $i$ .
Therefore, $U$ has a pivot in every row from row 1 to row $n$ .
Since $U$ has $n$ pivot positions, statement (c) of the Invertible Matrix Theorem is satisfied.
By the IMT, $U$ is an invertible matrix.

(Furthermore, dividing each row $i$ by $u_{ii}$ yields 1s on the diagonal, and backward elimination easily reduces $U$ to $I_n$ , verifying statement b).