The invertible matrix theorem

Theorem

The invertible matrix theorem

T-016Home MU-103Threads structure

Statement

Let \( F \) be a field, let \( n \in \mathbb{N} \), and let \( A \in M_n(F) \) be a square \( n \times n \) matrix. Write \( T_A : F^n \to F^n \), \( x \mapsto Ax \), for the associated linear map. Then the following thirteen conditions are all equivalent — either all true or all false: (i) \( A \) is invertible, i.e. there exists \( B \in M_n(F) \) with \( AB = BA = I_n \); (ii) \( A \) is row equivalent to the identity matrix \( I_n \); (iii) \( A \) has \( n \) pivot positions; (iv) the homogeneous system \( Ax = 0 \) has only the trivial solution \( x = 0 \); (v) the columns of \( A \) are linearly independent in \( F^n \); (vi) \( T_A \) is injective; (vii) for every \( b \in F^n \) the system \( Ax = b \) has at least one solution; (viii) the columns of \( A \) span \( F^n \); (ix) \( T_A \) is surjective; (x) there exists \( C \in M_n(F) \) with \( CA = I_n \); (xi) there exists \( D \in M_n(F) \) with \( AD = I_n \); (xii) the transpose \( A^{\mathsf{T}} \) is invertible; (xiii) \( \det A \neq 0 \). Moreover, when these hold, the inverse is unique, and any one-sided inverse \( C \) or \( D \) automatically equals \( A^{-1} \).

Why it matters

This theorem is the central switchboard of first-year linear algebra: it welds together the computational picture (pivots, row reduction, determinants), the equation-solving picture (existence and uniqueness for \( Ax = b \)), and the geometric picture (injectivity, surjectivity, bases). Whenever you verify any one condition — often the cheapest one available — you may immediately invoke all the others. Almost every later theorem that begins "if \( A \) is invertible…" is in practice applied by checking a pivot count or a determinant instead.

It also isolates exactly what is special about the square, finite-dimensional setting: for square matrices, injective and surjective are equivalent, and a one-sided inverse is automatically two-sided. Both statements are false for rectangular matrices and false in infinite dimensions, so the theorem marks the boundary beyond which linear algebra becomes genuinely harder.

Hypotheses

\( A \) is square (\( n \times n \)).For rectangular matrices the equivalences collapse. Take \( A = \begin{pmatrix} 1 & 0 \end{pmatrix} \in F^{1 \times 2} \) and \( B = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \): then \( AB = I_1 \) but \( BA = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} \neq I_2 \), so (xi) holds for \( A \) without invertibility. Likewise the columns of a \( 3 \times 2 \) matrix can be linearly independent (condition (v)) yet can never span \( F^3 \) (condition (viii)).

The entries lie in a field, not merely a commutative ring.Over \( \mathbb{Z} \), the \( 1 \times 1 \) matrix \( A = (2) \) has \( \det A = 2 \neq 0 \) and \( x \mapsto 2x \) is injective on \( \mathbb{Z} \), yet \( A \) has no inverse in \( M_1(\mathbb{Z}) \): (xiii) and (vi) hold while (i) fails. Over \( \mathbb{Z}/6\mathbb{Z} \), the matrix \( (2) \) has \( \det = 2 \neq 0 \) but \( 2 \cdot 3 = 0 \), so \( Ax = 0 \) has the nontrivial solution \( x = 3 \): (xiii) holds while (iv) fails. The proof repeatedly divides by nonzero pivots, which is exactly what a field licenses.

Finite dimensionality (implicit in "\( n \times n \)").On the infinite-dimensional space \( V = \{ (x_1, x_2, \dots) : x_i \in F \} \), the right shift \( S(x_1, x_2, \dots) = (0, x_1, x_2, \dots) \) is linear and injective and has a left inverse (the left shift), but it is not surjective: \( (1,0,0,\dots) \) is not in its image. So (vi) and (x) hold while (ix) fails. Every "counting" step of the proof — pivots per row versus pivots per column — silently uses that \( n \) rows and \( n \) columns are the same finite number.

Proof

Strategy: we prove the cycle \( \text{(i)} \Rightarrow \text{(iv)} \Leftrightarrow \text{(v)} \Leftrightarrow \text{(vi)} \), \( \text{(iv)} \Rightarrow \text{(iii)} \Rightarrow \text{(ii)} \Rightarrow \text{(i)} \), then splice the surjectivity block (vii)–(ix) into the cycle via (iii), then reduce the one-sided-inverse conditions (x), (xi) to conditions already in the cycle, and finally attach (xii) and (xiii). Proving a cycle rather than all pairwise implications is what makes thirteen equivalences tractable: each condition is reachable from every other by following arrows.

\[ \text{(i)} \Rightarrow \text{(iv)}: \quad Ax = 0 \;\Longrightarrow\; x = I_n x = (A^{-1}A)x = A^{-1}(Ax) = A^{-1}0 = 0. \]

Multiply both sides of \( Ax = 0 \) on the left by the inverse guaranteed by (i); uses associativity of matrix multiplication. A

\[ \text{(iv)} \Leftrightarrow \text{(v)}: \quad Ax = x_1 a_1 + x_2 a_2 + \dots + x_n a_n, \]

where \( a_1, \dots, a_n \) are the columns of \( A \) (the column view of matrix–vector multiplication). Thus "\( Ax = 0 \) only for \( x = 0 \)" is word-for-word the definition of linear independence of \( a_1, \dots, a_n \). A

\[ \text{(iv)} \Leftrightarrow \text{(vi)}: \quad T_A(x) = T_A(y) \;\Longleftrightarrow\; T_A(x - y) = 0. \]

Linearity of \( T_A \). If \( \ker T_A = \{0\} \) then \( T_A(x) = T_A(y) \) forces \( x - y = 0 \), i.e. injectivity; conversely an injective map can only send \( 0 \) to \( 0 \) once, so the kernel is trivial. A

\[ \text{(iv)} \Rightarrow \text{(iii)}: \quad \text{every column of } A \text{ is a pivot column, hence } A \text{ has } n \text{ pivots.} \]

Contrapositive. Row reduce \( A \) to reduced echelon form. If some column carries no pivot, its variable is free: by the existence–uniqueness theorem for linear systems (echelon-form lemma), setting the free variable to \( 1 \) and back-substituting produces a nonzero solution of \( Ax = 0 \), contradicting (iv). A square matrix with a pivot in each of its \( n \) columns has exactly \( n \) pivots. B

\[ \text{(iii)} \Rightarrow \text{(ii)}: \quad \operatorname{RREF}(A) = I_n. \]

A pivot lies in each row and each column (there are \( n \) pivots, at most one per row and per column, and \( n \) rows and \( n \) columns). Pivots move strictly right as we descend rows, so with \( n \) of them in an \( n \times n \) matrix they must occupy the diagonal. In reduced echelon form each pivot is \( 1 \) and is the only nonzero entry of its column; the only such matrix is \( I_n \). A

\[ \text{(ii)} \Rightarrow \text{(i)}: \quad E_k \cdots E_1 A = I_n \;\Longrightarrow\; A = E_1^{-1} \cdots E_k^{-1}, \]

by the elementary-matrix lemma: performing a row operation equals left multiplication by the corresponding elementary matrix, and each elementary matrix is invertible by an elementary matrix (a swap is its own inverse; scaling a row by \( c \neq 0 \) is undone by scaling by \( c^{-1} \), legal because \( F \) is a field; adding \( c \) times row \( j \) to row \( i \) is undone by subtracting it). A product of invertible matrices is invertible with \( A^{-1} = E_k \cdots E_1 \), checked directly: \( (E_1^{-1}\cdots E_k^{-1})(E_k \cdots E_1) = I_n \) and symmetrically. This closes the cycle (i) \( \Leftrightarrow \) (ii) \( \Leftrightarrow \) (iii) \( \Leftrightarrow \) (iv) \( \Leftrightarrow \) (v) \( \Leftrightarrow \) (vi). B

\[ \text{(iii)} \Rightarrow \text{(vii)}: \quad Ax = b \text{ is consistent for every } b \in F^n. \]

With \( n \) pivots in an \( n \times n \) matrix there is a pivot in every row, so no echelon form of \( A \) has a zero row. Row reducing the augmented matrix \( \left( A \mid b \right) \) therefore can never produce a row of the form \( ( 0 \; \cdots \; 0 \mid c ) \) with \( c \neq 0 \); by the consistency criterion (echelon-form lemma), the system is solvable for every right-hand side. B

\[ \text{(vii)} \Leftrightarrow \text{(viii)} \Leftrightarrow \text{(ix)}: \quad \{ b : Ax = b \text{ solvable} \} = \operatorname{span}(a_1, \dots, a_n) = \operatorname{im} T_A. \]

All three are restatements: \( Ax = b \) is solvable exactly when \( b \) is a linear combination of the columns (Step 2's column view), and the image of \( T_A \) is by definition the set of all vectors of the form \( Ax \). Solvability for every \( b \) says this common set is all of \( F^n \). A

\[ \text{(ix)} \Rightarrow \text{(iii)}: \quad \text{if } A \text{ has fewer than } n \text{ pivots, } T_A \text{ is not surjective.} \]

Contrapositive, and this is the step where "surjective" is spliced back into the cycle. Write \( U = EA \) with \( U \) in reduced echelon form and \( E = E_k \cdots E_1 \) invertible (Step 6's lemma). If the pivot count is at most \( n - 1 \), the last row of \( U \) is zero. Let \( e_n = (0, \dots, 0, 1)^{\mathsf{T}} \) and set \( b = E^{-1} e_n \). If some \( x \) satisfied \( Ax = b \), then \( Ux = EAx = Eb = e_n \); but the last equation of \( Ux = e_n \) reads \( 0 = 1 \), a contradiction. Hence \( b \notin \operatorname{im} T_A \). C

\[ \text{(i)} \Rightarrow \text{(x)} \text{ and } \text{(i)} \Rightarrow \text{(xi)}: \quad \text{take } C = D = A^{-1}. \]

Immediate from the definition of the two-sided inverse in (i). A

\[ \text{(x)} \Rightarrow \text{(iv)}: \quad Ax = 0 \;\Longrightarrow\; x = (CA)x = C(Ax) = 0; \quad \text{and then } C = A^{-1}. \]

A left inverse forces a trivial kernel, which drops us into the cycle at (iv), so \( A \) is invertible by Steps 4–6. Uniqueness bonus: \( C = C I_n = C(AA^{-1}) = (CA)A^{-1} = A^{-1} \), so the left inverse is the two-sided inverse. B

\[ \text{(xi)} \Rightarrow \text{(vii)}: \quad \text{given } b, \text{ the vector } x = Db \text{ satisfies } Ax = (AD)b = I_n b = b. \]

A right inverse manufactures explicit solutions, dropping us into the cycle at (vii); \( A \) is then invertible by Steps 9, 5, 6. As in Step 11, \( D = (A^{-1}A)D = A^{-1}(AD) = A^{-1} \). Note the pleasing symmetry: a left inverse certifies uniqueness of solutions, a right inverse certifies existence, and for square matrices either alone certifies both. B

\[ \text{(i)} \Leftrightarrow \text{(xii)}: \quad (A^{-1})^{\mathsf{T}} A^{\mathsf{T}} = (A A^{-1})^{\mathsf{T}} = I_n^{\mathsf{T}} = I_n, \qquad A^{\mathsf{T}} (A^{-1})^{\mathsf{T}} = (A^{-1} A)^{\mathsf{T}} = I_n. \]

Uses the reversal law \( (XY)^{\mathsf{T}} = Y^{\mathsf{T}} X^{\mathsf{T}} \) (transpose lemma) and \( I_n^{\mathsf{T}} = I_n \). This shows (i) \( \Rightarrow \) (xii) with \( (A^{\mathsf{T}})^{-1} = (A^{-1})^{\mathsf{T}} \); the converse follows by applying the same implication to \( A^{\mathsf{T}} \), since \( (A^{\mathsf{T}})^{\mathsf{T}} = A \). A

\[ \text{(i)} \Leftrightarrow \text{(xiii)}: \quad \det A = \gamma \cdot \det \operatorname{RREF}(A) \text{ for some } \gamma \neq 0. \]

By the row-operation lemma for determinants (proved in the determinants unit): a row swap multiplies \( \det \) by \( -1 \), scaling a row by \( c \neq 0 \) multiplies it by \( c \), and a row replacement leaves it unchanged — so the reduction from \( A \) to its RREF changes the determinant by a nonzero factor \( \gamma \in F \). If \( A \) is invertible, \( \operatorname{RREF}(A) = I_n \) by Step 5, so \( \det A = \gamma \cdot 1 \neq 0 \). If \( A \) is not invertible, then by the (already proved) equivalence with (iii) it has fewer than \( n \) pivots, so \( \operatorname{RREF}(A) \) has a zero row, and a matrix with a zero row has determinant \( 0 \) (expand along that row, or use linearity of \( \det \) in that row); hence \( \det A = \gamma \cdot 0 = 0 \). Both directions established, and the proof of all thirteen equivalences is complete. \( \blacksquare \) C

Result

\[ A \in M_n(F): \quad A \text{ invertible} \;\Longleftrightarrow\; \operatorname{RREF}(A) = I_n \;\Longleftrightarrow\; \ker T_A = \{0\} \;\Longleftrightarrow\; \operatorname{im} T_A = F^n \;\Longleftrightarrow\; \exists C,\; CA = I_n \;\Longleftrightarrow\; \exists D,\; AD = I_n \;\Longleftrightarrow\; \det A \neq 0 \]

Reading. For a square matrix, every reasonable notion of "non-degenerate" coincides: solvability of every system, uniqueness of solutions, independence of columns, a full set of pivots, a nonzero determinant, a one-sided inverse of either handedness. Check whichever is cheapest; conclude them all.

Scope. Applies to square matrices with entries in any field \( F \) — including \( \mathbb{Q} \), \( \mathbb{R} \), \( \mathbb{C} \), and finite fields. It fails for rectangular matrices, for matrices over general commutative rings (where the correct criterion is \( \det A \) being a unit of the ring), and for linear operators on infinite-dimensional spaces.

Corollaries & converses

One-sided suffices. For square \( A \), verifying \( AB = I_n \) alone proves \( B = A^{-1} \) and \( BA = I_n \). This halves the work in every "check that \( B \) is the inverse" computation.
Unique solution formula. If \( A \) is invertible, \( Ax = b \) has the unique solution \( x = A^{-1}b \) (existence from (vii), uniqueness from (iv)).
The general linear group. The invertible matrices form a group \( GL_n(F) \) under multiplication, with \( (AB)^{-1} = B^{-1}A^{-1} \) and \( (A^{\mathsf{T}})^{-1} = (A^{-1})^{\mathsf{T}} \).
Eigenvalue criterion. \( \lambda \) is an eigenvalue of \( A \) iff \( A - \lambda I_n \) is not invertible, iff \( \det(A - \lambda I_n) = 0 \) — the entire theory of characteristic polynomials is this theorem applied to \( A - \lambda I_n \).
Rank formulation. \( A \) is invertible iff \( \operatorname{rank} A = n \), iff the rows (not just the columns) are linearly independent — via condition (xii) applied through the transpose.
Converses. The theorem is a closed web of biconditionals, so every "converse" within the list holds automatically. The genuine one-directional warning lives outside the hypotheses: for an \( m \times n \) matrix with \( m \neq n \), injectivity and surjectivity can never both hold, and \( AB = I_m \) does not imply \( BA = I_n \) (see Fails without).

Fails without

Drop squareness. \( A = \begin{pmatrix} 1 & 0 \end{pmatrix} \), \( B = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \): then \( AB = (1) = I_1 \), so \( A \) has a right inverse and \( T_A : F^2 \to F^1 \) is surjective — yet \( BA = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} \neq I_2 \), \( \ker T_A = \operatorname{span}\{(0,1)^{\mathsf{T}}\} \neq \{0\} \), and no two-sided inverse can exist. Conditions (ix) and (xi) hold while (i), (iv), (v), (vi), (x) all fail.
Drop the field (work over a ring). \( A = (2) \in M_1(\mathbb{Z}) \): \( \det A = 2 \neq 0 \), the map \( x \mapsto 2x \) is injective on \( \mathbb{Z} \), the RREF over \( \mathbb{Q} \) would be \( I_1 \) — but there is no \( B \in M_1(\mathbb{Z}) \) with \( AB = I_1 \), since \( 2b = 1 \) has no integer solution. (xiii) and (vi) hold, (i), (vii), (ix) fail: \( 2x = 1 \) is unsolvable in \( \mathbb{Z} \).
Drop finite dimensionality. On the sequence space \( V = F^{\mathbb{N}} \), the right shift \( S(x_1, x_2, x_3, \dots) = (0, x_1, x_2, \dots) \) is injective with left inverse the left shift \( L \) (so \( LS = \operatorname{id} \)), but \( S \) is not surjective and \( SL \neq \operatorname{id} \): (vi) and (x) hold while (ix) and (i) fail. Dually, \( L \) is surjective with a right inverse but is not injective: \( \ker L = \operatorname{span}\{(1,0,0,\dots)\} \).

Common errors

Rectangular overreach. Citing "\( AB = I \Rightarrow BA = I \)" for non-square \( A, B \). The one-sided-implies-two-sided miracle is strictly a square phenomenon (Steps 11–12 both route through the cycle, which needs \( n \) pivots to fill both \( n \) rows and \( n \) columns).
"Small determinant means nearly singular." \( \det(\varepsilon I_n) = \varepsilon^n \) is astronomically small for modest \( \varepsilon \) and large \( n \), yet \( \varepsilon I_n \) is perfectly well-conditioned. Invertibility is a yes/no algebraic property; numerical health is measured by the condition number, not by \( \lvert \det A \rvert \).
Determinant bookkeeping. Row reducing to echelon form, then reading \( \det A \) as the product of pivots while forgetting that row swaps flipped the sign and row scalings changed the value. Only replacement operations are determinant-neutral.
Pivot miscounting. Concluding invertibility from "a pivot in every row" of a wide matrix, or "independent columns" of a tall one. A \( 3 \times 5 \) matrix can have 3 pivots and be nowhere near invertible; the theorem needs pivots to exhaust rows and columns simultaneously, which forces \( m = n \).
Kernel-checking half the conditions. Verifying \( Ax = 0 \) has only the trivial solution and then asserting "so \( Ax = b \) is solvable" for a non-square \( A \). For square matrices the theorem grants this; for a \( 5 \times 3 \) matrix, injectivity says nothing about surjectivity.
Circular determinant proofs. "Proving" (i) \( \Leftrightarrow \) (xiii) by writing \( A^{-1} = \frac{1}{\det A}\operatorname{adj}(A) \) without first establishing the adjugate identity independently — the adjugate route is legitimate, but only after \( A \cdot \operatorname{adj}(A) = (\det A) I_n \) has been proved from the cofactor expansion, not assumed.

Discussion

The theorem earns its capital letters not by depth but by architecture. Thirteen conditions would naively require \( 13 \times 12 = 156 \) pairwise implications; the proof above establishes fourteen arrows arranged so that every condition can reach every other by following the cycle. This hub-and-spoke economy is a standard proof pattern for equivalence clusters (compare the many characterisations of compactness in metric spaces), and the Invertible Matrix Theorem is usually a student's first encounter with it. The name itself was popularised by David Lay's 1994 textbook, which numbered the conditions and encouraged students to grow the list as the course progressed — later chapters append "the columns form a basis of \( F^n \)", "\( 0 \) is not an eigenvalue of \( A \)", "\( \operatorname{rank} A = n \)", and "\( \operatorname{Nul} A = \{0\} \)" to the same web.

Historically the determinant condition came first and the matrix came second. Determinants were manipulated by Leibniz (1693) and systematised by Cramer (1750) and Cauchy (1812) decades before Cayley's 1858 Memoir on the theory of matrices introduced the matrix inverse, which Cayley constructed explicitly via the adjugate: \( A^{-1} = \frac{1}{\det A} \operatorname{adj}(A) \). The modern arrangement — invertibility defined algebraically, determinant demoted to one test among many — reflects the twentieth-century shift, driven by Frobenius's rank concept and later by the operator-theoretic viewpoint, toward seeing a matrix primarily as a linear map.

Conceptually, the engine underneath the theorem is the rank–nullity theorem: \( \dim \ker T_A + \operatorname{rank} T_A = n \). Injectivity says the first summand is \( 0 \); surjectivity says the second is \( n \); since the two summands share a fixed budget of \( n \), each condition forces the other. The pivot-counting steps (4, 7, 9) of the proof are exactly this budget argument carried out by hand, before rank–nullity is available as a named tool. Seen this way, the theorem is the statement that at full rank the ledger has no slack — and every one of the thirteen conditions is a different accountant's phrasing of "full rank".

The deepest hypothesis is finiteness. A unital ring in which \( xy = 1 \) implies \( yx = 1 \) is called Dedekind-finite, and the theorem asserts that \( M_n(F) \) is Dedekind-finite — a genuinely non-formal fact, since the endomorphism ring of an infinite-dimensional vector space is not: the unilateral shift \( S \) satisfies \( LS = \operatorname{id} \neq SL \). In functional analysis this failure is not a pathology but a resource: the Fredholm index \( \operatorname{ind}(T) = \dim \ker T - \dim \operatorname{coker} T \), which is identically \( 0 \) for square matrices by rank–nullity, becomes a nontrivial homotopy invariant of operators (the shift has index \( -1 \)), and its study leads to Atiyah–Singer index theory. The Invertible Matrix Theorem is thus the statement that in finite dimensions the index obstruction vanishes.

Common misconceptions. The theorem does not say the determinant is a good numerical test of invertibility (it is not: it overflows, underflows, and ignores conditioning — Gaussian elimination with pivoting is the practical tool). It does not say row independence and column independence are different tests — condition (xii) makes them equivalent for square matrices. And it is not a computational recipe: it tells you thirteen questions have the same answer, but computing that answer is still the job of elimination.

Worked examples

Example 1 (one pivot count, thirteen conclusions). Decide whether \( A = \begin{pmatrix} 1 & 2 & 1 \\ 2 & 5 & 3 \\ 1 & 0 & 0 \end{pmatrix} \in M_3(\mathbb{R}) \) is invertible, and extract everything the theorem then gives for free.

\[ \begin{pmatrix} 1 & 2 & 1 \\ 2 & 5 & 3 \\ 1 & 0 & 0 \end{pmatrix} \xrightarrow{\substack{R_2 \to R_2 - 2R_1 \\ R_3 \to R_3 - R_1}} \begin{pmatrix} 1 & 2 & 1 \\ 0 & 1 & 1 \\ 0 & -2 & -1 \end{pmatrix} \]

Two row-replacement operations clear the first column below the pivot; replacements are the determinant-neutral operation, which we exploit in Step 3. A

\[ \xrightarrow{R_3 \to R_3 + 2R_2} \begin{pmatrix} 1 & 2 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \quad \text{— echelon form with pivots in columns } 1, 2, 3. \]

One more replacement. The echelon form has three pivots: condition (iii) of the theorem holds with \( n = 3 \). A

\[ \det A = 1 \cdot 1 \cdot 1 = 1 \neq 0, \]

because only replacement operations were used, the determinant of \( A \) equals the determinant of the upper-triangular echelon form, which is the product of its diagonal entries (triangular-determinant lemma). This independently confirms condition (xiii). B

\[ \text{Invoke the Invertible Matrix Theorem at condition (iii).} \]

Three pivots in a \( 3 \times 3 \) real matrix: all thirteen conditions now hold simultaneously — no further computation is needed for any of them. A

\[ A \text{ is invertible, } \det A = 1 \]

Reading. For free: the columns \( (1,2,1)^{\mathsf{T}}, (2,5,0)^{\mathsf{T}}, (1,3,0)^{\mathsf{T}} \) form a basis of \( \mathbb{R}^3 \); the system \( Ax = b \) has exactly one solution for every \( b \in \mathbb{R}^3 \); \( Ax = 0 \) forces \( x = 0 \); \( A^{\mathsf{T}} \) is invertible, so the rows are a basis too; and any matrix \( C \) found to satisfy \( CA = I_3 \) is automatically the full inverse.

Scope. One elimination, thirteen theorems' worth of conclusions — this is the theorem used as intended.

Example 2 (eigenvalue detection via non-invertibility). Determine whether \( \lambda = 2 \) is an eigenvalue of \( B = \begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix} \), using the theorem rather than the characteristic polynomial.

\[ \lambda = 2 \text{ is an eigenvalue of } B \;\Longleftrightarrow\; \exists v \neq 0: \; (B - 2I_2)v = 0 \;\Longleftrightarrow\; B - 2I_2 \text{ is not invertible,} \]

by the definition of eigenvalue and the equivalence (i) \( \Leftrightarrow \) (iv) of the theorem applied to the square matrix \( B - 2I_2 \): a nontrivial kernel is exactly the failure of invertibility. B

\[ B - 2I_2 = \begin{pmatrix} 2 & 1 \\ 2 & 1 \end{pmatrix}, \qquad \begin{pmatrix} 2 & 1 \\ 2 & 1 \end{pmatrix} \xrightarrow{R_2 \to R_2 - R_1} \begin{pmatrix} 2 & 1 \\ 0 & 0 \end{pmatrix}. \]

Direct computation and one row replacement: the echelon form has a single pivot, so condition (iii) fails for the \( 2 \times 2 \) matrix \( B - 2I_2 \), and with it all thirteen conditions fail. A

\[ \text{Free variable } x_2 = t: \quad 2x_1 + x_2 = 0 \;\Longrightarrow\; v = t \begin{pmatrix} 1 \\ -2 \end{pmatrix}, \quad t \neq 0. \]

Back-substitution in the echelon form exhibits an explicit nonzero kernel vector; check: \( Bv = \begin{pmatrix} 4 - 2 \\ 2 - 6 \end{pmatrix} = \begin{pmatrix} 2 \\ -4 \end{pmatrix} = 2v \). A

\[ \lambda = 2 \text{ is an eigenvalue of } B, \text{ with eigenvector } (1, -2)^{\mathsf{T}} \]

Reading. The theorem converts the existential question "is there a nonzero \( v \) with \( Bv = 2v \)?" into the concrete checkable question "does \( B - 2I_2 \) have a full set of pivots?" — and, en route, it certifies that \( \det(B - 2I_2) = 0 \) without our computing a single determinant.

Scope. This is precisely how the characteristic polynomial is born: \( \lambda \) ranges over the scalars, and the theorem's (i) \( \Leftrightarrow \) (xiii) turns "eigenvalue" into "root of \( \det(B - \lambda I) \)".

Problems

Decide whether \( A = \begin{pmatrix} 1 & 3 \\ 2 & 6 \end{pmatrix} \) is invertible, and for each of the conditions (iv), (v), (vii), (xiii) of the theorem, verify directly that it fails.
Solution
Row reduce: \( R_2 \to R_2 - 2R_1 \) gives \( \begin{pmatrix} 1 & 3 \\ 0 & 0 \end{pmatrix} \), only one pivot, so \( A \) is not invertible by condition (iii). Directly: (iv) \( x = (3, -1)^{\mathsf{T}} \) satisfies \( Ax = (3 - 3,\; 6 - 6)^{\mathsf{T}} = 0 \), a nontrivial solution. (v) the second column is \( 3 \) times the first: \( (3,6)^{\mathsf{T}} = 3 \cdot (1,2)^{\mathsf{T}} \), so the columns are dependent. (vii) the image is \( \operatorname{span}\{(1,2)^{\mathsf{T}}\} \); the system \( Ax = (0,1)^{\mathsf{T}} \) is inconsistent, since any \( Ax \) has second entry twice its first. (xiii) \( \det A = 1 \cdot 6 - 3 \cdot 2 = 0 \). All thirteen conditions fail together, as the theorem demands.
Let \( A \in M_n(F) \) with \( A^2 = 0 \) and \( A \neq 0 \). Show that \( A \) is not invertible, and show that \( I_n - A \) is invertible by exhibiting its inverse.
Solution
If \( A \) were invertible, then \( A = I_n A = (A^{-1} A) A = A^{-1} A^2 = A^{-1} 0 = 0 \), contradicting \( A \neq 0 \); so \( A \) is not invertible. For the second part, guess a truncated geometric series: compute \( (I_n - A)(I_n + A) = I_n + A - A - A^2 = I_n - A^2 = I_n \). Thus \( I_n + A \) is a right inverse of the square matrix \( I_n - A \), and by condition (xi) of the Invertible Matrix Theorem this alone proves \( I_n - A \) is invertible with \( (I_n - A)^{-1} = I_n + A \) — no need to verify the product in the other order, though it also equals \( I_n \) by the same expansion.
Let \( A, B \in M_n(F) \) and suppose the product \( AB \) is invertible. Prove that both \( A \) and \( B \) are invertible. Then give \( 1 \times 2 \) and \( 2 \times 1 \) matrices showing this fails when \( A \) and \( B \) are not square.
Solution
\( B \) is invertible: if \( Bx = 0 \) then \( (AB)x = A(Bx) = 0 \), so \( x = (AB)^{-1}(AB)x = 0 \); thus \( B \) has trivial kernel and, being square, is invertible by (iv) \( \Rightarrow \) (i). \( A \) is invertible: \( A \cdot \big( B (AB)^{-1} \big) = (AB)(AB)^{-1} = I_n \), so the square matrix \( A \) has a right inverse and is invertible by condition (xi). (Alternatively, once \( B \) is invertible, \( A = (AB)B^{-1} \) is a product of invertible matrices.) Non-square failure: take \( A = \begin{pmatrix} 1 & 0 \end{pmatrix} \) and \( B = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \): then \( AB = (1) = I_1 \) is invertible, but neither rectangular matrix can be invertible, and indeed \( BA = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} \) is not even injective.
Prove from the theorem that a linear map \( T : F^n \to F^n \) is injective if and only if it is surjective. Then show both implications fail in infinite dimensions, using the space \( \mathbb{R}[x] \) of real polynomials: exhibit one linear map that is surjective but not injective, and one that is injective but not surjective.
Solution
Choose the standard matrix \( A \) of \( T \) (so \( T = T_A \) with \( A \in M_n(F) \), using that every linear map \( F^n \to F^n \) is matrix multiplication). Conditions (vi) and (ix) of the theorem are both equivalent to invertibility of the square matrix \( A \), hence equivalent to each other. Infinite dimensions: on \( \mathbb{R}[x] \), the differentiation map \( D(p) = p' \) is linear and surjective — every \( q \in \mathbb{R}[x] \) is \( D \) of one of its antiderivatives, which is again a polynomial — but not injective, since \( D(1) = D(0) = 0 \) and \( \ker D \) is the line of constant polynomials. The multiplication map \( M(p) = x \cdot p(x) \) is linear and injective — \( xp = 0 \) forces \( p = 0 \) since \( \mathbb{R}[x] \) has no zero divisors — but not surjective, since every polynomial in its image vanishes at \( 0 \), so the constant \( 1 \) is not attained. Both halves of the square-case equivalence therefore fail once the dimension budget argument (rank–nullity on a finite total) is unavailable.
(Harder.) Let \( A \in M_n(\mathbb{Z}) \) be a matrix with integer entries. Prove that \( A \) has an inverse with integer entries if and only if \( \det A = \pm 1 \). You may use the adjugate identity \( A \cdot \operatorname{adj}(A) = \operatorname{adj}(A) \cdot A = (\det A) I_n \) and multiplicativity of the determinant.
Solution
(\( \Rightarrow \)) Suppose \( B \in M_n(\mathbb{Z}) \) with \( AB = I_n \). Taking determinants and using multiplicativity, \( \det A \cdot \det B = \det I_n = 1 \). Both \( \det A \) and \( \det B \) are integers (the determinant is a polynomial with integer coefficients in the entries), and the only integer divisors of \( 1 \) are \( \pm 1 \); hence \( \det A = \pm 1 \). (\( \Leftarrow \)) Suppose \( \det A = \pm 1 \). Every entry of \( \operatorname{adj}(A) \) is a cofactor of \( A \), i.e. \( \pm \) the determinant of an integer submatrix, hence an integer, so \( \operatorname{adj}(A) \in M_n(\mathbb{Z}) \). Set \( B = (\det A)^{-1} \operatorname{adj}(A) = \pm \operatorname{adj}(A) \in M_n(\mathbb{Z}) \). The adjugate identity gives \( AB = BA = (\det A)^{-1} (\det A) I_n = I_n \). Remark. This is the Invertible Matrix Theorem's field hypothesis made quantitative: over a field, "\( \det A \) nonzero" suffices because every nonzero scalar is a unit; over the ring \( \mathbb{Z} \), the criterion sharpens to "\( \det A \) is a unit of \( \mathbb{Z} \)", i.e. \( \det A = \pm 1 \). Such matrices form the group \( GL_n(\mathbb{Z}) \).