Linear algebra · The Lumenary

MotivationH

Two puzzles with one theory behind them

Balancing a reaction. In photosynthesis, a leaf turns carbon dioxide and water into glucose and oxygen:

a\,\mathrm{CO_2} + b\,\mathrm{H_2O} \longrightarrow c\,\mathrm{C_6H_{12}O_6} + d\,\mathrm{O_2}.

Counting atoms of carbon, hydrogen and oxygen on both sides gives three equations in four unknowns:

a - 6c = 0, \qquad 2b - 12c = 0, \qquad 2a + b - 6c - 2d = 0.

Must there be a solution other than $a = b = c = d = 0$ ? Is it unique up to scaling? (Chemists find $6, 6, 1, 6$ .) The answers — yes, and yes — come from a single theorem about dimensions, the rank–nullity theorem, which says that three equations can "use up" at most three of the four degrees of freedom.

Growth. The Fibonacci numbers $0, 1, 1, 2, 3, 5, 8, 13, \dots$ satisfy $F_{n+1} = F_n + F_{n-1}$ . In matrix form,

\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix},

so computing $F_n$ means computing powers of a matrix. The ratios $F_{n+1}/F_n$ approach the golden ratio $\varphi = (1 + \sqrt5)/2 \approx 1.618$ . Why that number? Because $\varphi$ is an eigenvalue of the matrix: there is a direction that the matrix only stretches, by the factor $\varphi$ , and after many steps that direction wins.

The same two questions — solve a linear system, understand repeated application of a linear map — appear in circuit analysis, economics, computer graphics, statistics, quantum mechanics, search engines and machine learning. Linear algebra is the theory that answers both. It starts where school algebra stops: from simultaneous linear equations in two or three unknowns, with scalars from the real numbers (or any other field).

IntuitionH

Linear maps as transformations of space

A $2 \times 2$ matrix $A$ moves every point $x$ of the plane to $Ax$ . Because $A(x + y) = Ax + Ay$ and $A(cx) = c\,Ax$ , the whole picture is determined by where the two basis vectors $e_1 = (1, 0)$ and $e_2 = (0, 1)$ go: they go to the columns of $A$ . The square grid becomes a grid of parallelograms, the origin stays put, and straight lines stay straight (or collapse).

Three numbers measure what happens:

the determinant is the factor by which areas are multiplied, with a minus sign if the map flips the plane over;
the rank is the dimension of the image: $2$ if the plane goes onto the plane, $1$ if it is squashed onto a line, $0$ if everything goes to the origin;
the eigenvectors are the directions that are not turned at all, only stretched (by the eigenvalue).

A linear map of the plane

Drag the entries or pick a preset. Watch the columns, the area of the unit square, the flag and the dashed invariant lines.

Your own matrix

image of the grid
image of the unit square
image of the flag
before the transformation
invariant line

From the identity I to As = 1

A =

The columns of A are the images of e₁ = (1, 0) and e₂ = (0, 1): Ae₁ = (1, 0.5), Ae₂ = (1, 1.5)

det A = ad − bc = 1

The unit square (area 1) becomes a parallelogram of area |det A| = 1. Since det A > 0, orientation is preserved.

Invariant lines (real eigenvectors)

λ₁ = 2, v₁ = (1, 1)
λ₂ = 0.5, v₂ = (1, −0.5)

Vectors on the two dashed lines are only stretched, by the factors λ₁ = 2 and λ₂ = 0.5; every other direction is turned.

Try the "singular" preset: the whole plane collapses onto a line, the determinant is $0$ , and some non-zero vectors are sent to $0$ . That collapse is exactly what makes a system of equations fail to have a unique solution. Try "rotation": no real direction survives unturned, so there are no real eigenvectors.

DefinitionsH

Definitions

Throughout, $k$ is a field: $\Q$ , $\R$ , $\C$ , or the two-element field $\mathbb F_2 = \{0, 1\}$ with $1 + 1 = 0$ (see algebraic structures). Elements of $k$ are called scalars.

Definition— vector space

A vector space over $k$ is a set $V$ with an addition $V \times V \to V$ and a scalar multiplication $k \times V \to V$ such that $(V, +)$ is an abelian group (with zero vector $0$ ) and, for all $a, b \in k$ and $u, v \in V$ ,

a(u + v) = au + av, \qquad (a + b)v = av + bv, \qquad (ab)v = a(bv), \qquad 1v = v.

A subspace is a subset $U \subseteq V$ containing $0$ and closed under addition and scalar multiplication; it is a vector space in its own right.

Definition— span, linear independence, basis, dimension

A linear combination of $v_1, \dots, v_n \in V$ is a vector $a_1 v_1 + \cdots + a_n v_n$ with $a_i \in k$ . Their span is the set of all linear combinations, the smallest subspace containing them. The list is linearly independent if

a_1 v_1 + \cdots + a_n v_n = 0 \implies a_1 = \cdots = a_n = 0,

and dependent otherwise. A basis of $V$ is a linearly independent list that spans $V$ ; then every $v \in V$ is $a_1 v_1 + \cdots + a_n v_n$ for unique scalars $a_i$ , its coordinates. $V$ is finite-dimensional if some finite list spans it, and then $\dim V$ is the number of vectors in a basis — a definition that only makes sense once we prove that all bases have the same size (the exchange lemma, below).

Definition— linear map, kernel, image, rank

A map $T : V \to W$ between vector spaces over $k$ is linear if

T(u + v) = T(u) + T(v) \quad\text{and}\quad T(cv) = c\,T(v) \qquad \text{for all } u, v \in V,\ c \in k.

Then $T(0) = 0$ . Its kernel $\ker T = \{v \in V : Tv = 0\}$ and image $\operatorname{im} T = \{Tv : v \in V\}$ are subspaces of $V$ and $W$ . The rank of $T$ is $\dim \operatorname{im} T$ and its nullity is $\dim \ker T$ . A linear map is injective if and only if $\ker T = \{0\}$ , because $Tu = Tv \iff T(u - v) = 0$ .

Definition— matrix of a linear map

Let $B = (v_1, \dots, v_n)$ be a basis of $V$ and $C = (w_1, \dots, w_m)$ a basis of $W$ . The matrix of $T$ with respect to $B$ and $C$ is the $m \times n$ matrix $[T]$ whose $j$ -th column holds the coordinates of $T v_j$ :

T v_j = \sum_{i=1}^m t_{ij}\, w_i .

For $V = k^n$ and $W = k^m$ with their standard bases, $[T]$ is the matrix $A$ with $Tx = Ax$ . The product of an $\ell \times m$ matrix $S$ and an $m \times n$ matrix $T$ is the $\ell \times n$ matrix with entries $(ST)_{ij} = \sum_{r} s_{ir} t_{rj}$ .

Definition— determinant

The determinant of an $n \times n$ matrix $A = (a_{ij})$ is

\det A = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma)\, a_{\sigma(1)1}\, a_{\sigma(2)2} \cdots a_{\sigma(n)n},

the sum over all permutations $\sigma$ of $\{1, \dots, n\}$ , where $\operatorname{sgn}(\sigma) = \pm 1$ according as $\sigma$ is a product of an even or odd number of swaps. For $n = 2$ : $\det \begin{pmatrix} a & b \\ c & d \end{pmatrix} = ad - bc$ .

Definition— eigenvalue, eigenvector, diagonalisable

Let $T : V \to V$ be linear. A scalar $\lambda \in k$ is an eigenvalue of $T$ if $Tv = \lambda v$ for some non-zero vector $v$ , called an eigenvector. The eigenspace $E_\lambda = \ker(T - \lambda I)$ consists of the eigenvectors for $\lambda$ together with $0$ ; its dimension is the geometric multiplicity of $\lambda$ . For a square matrix $A$ , the characteristic polynomial is $p_A(t) = \det(tI - A)$ , and the multiplicity of $\lambda$ as a root of $p_A$ is its algebraic multiplicity. $A$ is diagonalisable (over $k$ ) if $P^{-1} A P$ is diagonal for some invertible matrix $P$ with entries in $k$ .

Worked examplesH

Examples and non-examples

Example— Vector spaces you already know (and some you may not)

$k^n$ , lists of $n$ scalars; $\dim k^n = n$ , with the standard basis $e_1, \dots, e_n$ .
The polynomials of degree at most $d$ , with basis $1, x, \dots, x^d$ : dimension $d + 1$ .
The solutions of the differential equation $y'' + y = 0$ on $\R$ : a vector space of dimension $2$ , with basis $\cos, \sin$ .
$\mathbb F_2^7$ : the seven-bit words used in error-correcting codes. Over $\mathbb F_2$ we have $v + v = 0$ for every $v$ .
All functions $\R \to \R$ : a vector space that is not finite-dimensional (the functions $1, x, x^2, \dots$ are independent).

Not subspaces of $\R^3$ : the plane $z = 1$ (it does not contain $0$ ); the octant $x, y, z \ge 0$ (not closed under multiplication by $-1$ ); the union of the $x$ - and $y$ -axes in $\R^2$ (closed under scaling, but $(1, 0) + (0, 1)$ is on neither axis).

Example— Gaussian elimination, worked

Solve $x + 2y + z = 4$ and $2x + 4y + 3z = 9$ . Row-reduce the augmented matrix: subtract twice row 1 from row 2, then subtract the new row 2 from row 1:

\left(\begin{array}{ccc|c} 1 & 2 & 1 & 4 \\ 2 & 4 & 3 & 9 \end{array}\right) \to \left(\begin{array}{ccc|c} 1 & 2 & 1 & 4 \\ 0 & 0 & 1 & 1 \end{array}\right) \to \left(\begin{array}{ccc|c} 1 & 2 & 0 & 3 \\ 0 & 0 & 1 & 1 \end{array}\right).

This is the reduced row echelon form: each non-zero row starts with a pivot $1$ , which is the only non-zero entry in its column. The pivot columns belong to $x$ and $z$ ; the column of $y$ has no pivot, so $y = t$ is free. Reading off, $z = 1$ and $x = 3 - 2t$ :

(x, y, z) = (3, 0, 1) + t\,(-2, 1, 0), \qquad t \in \R.

The solution set is a line: one particular solution $(3, 0, 1)$ plus every multiple of $(-2, 1, 0)$ , which spans the null space of the coefficient matrix. A system is inconsistent exactly when elimination produces a row $(0 \ \cdots\ 0 \mid c)$ with $c \neq 0$ , that is, the equation $0 = c$ .

Example— Differentiation as a matrix

Let $V$ be the polynomials of degree at most $3$ with basis $1, x, x^2, x^3$ , and $D = d/dx : V \to V$ . Since $D(1) = 0$ , $D(x) = 1$ , $D(x^2) = 2x$ and $D(x^3) = 3x^2$ , the columns of $[D]$ are these coordinates:

[D] = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 3 \\ 0 & 0 & 0 & 0 \end{pmatrix}.

$\ker D$ is the constants (dimension $1$ ) and $\operatorname{im} D$ is the polynomials of degree at most $2$ (dimension $3$ ); indeed $1 + 3 = 4 = \dim V$ . Since $D^4 = 0$ , any eigenvalue $\lambda$ satisfies $\lambda^4 v = D^4 v = 0$ , so $\lambda = 0$ , and $E_0 = \ker D$ has dimension $1$ : $D$ has too few eigenvectors to be diagonalisable.

Example— Maps that are not linear

$x \mapsto x + 1$ on $\R$ is not linear: it moves $0$ . (It is affine: linear followed by a translation; see transformation geometry.) $x \mapsto x^2$ is not linear: $(1 + 1)^2 \neq 1^2 + 1^2$ . A linear map need not be injective: the projection $(x, y) \mapsto (x, 0)$ sends the whole $y$ -axis — a line through the origin — to the single point $0$ .

ProofH

Linear systems

A system of $m$ linear equations in $n$ unknowns is $Ax = b$ with $A$ an $m \times n$ matrix. The elementary row operations are: swap two rows; multiply a row by a non-zero scalar; add a multiple of one row to another.

Theorem— Proposition (row operations do not change the solutions)

If an augmented matrix $(A \mid b)$ is turned into $(A' \mid b')$ by elementary row operations, then $Ax = b$ and $A'x = b'$ have exactly the same solutions.

Proof

Each new equation is a linear combination of the old ones, so every solution of the old system solves the new one. Each operation can be undone by an operation of the same kind (swap back; multiply by $c^{-1}$ ; subtract the multiple again), so by the same argument every solution of the new system solves the old one.

∎

By repeatedly choosing a pivot, scaling it to $1$ and clearing its column, any matrix can be brought to reduced row echelon form; this is Gaussian elimination. Its output is read off as in the worked example: the system is consistent if and only if no pivot lies in the last column, and then the free variables can be chosen arbitrarily and determine the pivot variables uniquely.

Theorem— Theorem (structure of the solution set)

Let $T : V \to W$ be linear and $b \in W$ . If $x_0$ is one solution of $Tx = b$ , then the set of all solutions is the translate

\{x \in V : Tx = b\} = x_0 + \ker T = \{x_0 + z : z \in \ker T\}.

In particular, a consistent system has a unique solution exactly when $\ker T = \{0\}$ .

Proof

By linearity $Tx - Tx_0 = T(x - x_0)$ , so $Tx = b = Tx_0$ holds if and only if $T(x - x_0) = 0$ , that is, $x - x_0 \in \ker T$ , that is, $x \in x_0 + \ker T$ .

∎

So the solution set of a linear system is empty, or a point, or a line, plane, … that need not pass through the origin, parallel to the null space. This is the shape of the solutions of linear differential equations too: general solution = particular solution + general solution of the homogeneous equation.

ProofH

Bases and dimension

Theorem— Lemma (adding a vector outside the span)

If $u_1, \dots, u_m$ are linearly independent and $v \notin \operatorname{span}(u_1, \dots, u_m)$ , then $u_1, \dots, u_m, v$ are linearly independent.

Proof

Suppose $a_1 u_1 + \cdots + a_m u_m + cv = 0$ . If $c \neq 0$ then $v = -c^{-1}(a_1 u_1 + \cdots + a_m u_m)$ lies in the span, which is false; so $c = 0$ , and then independence of the $u_i$ gives $a_1 = \cdots = a_m = 0$ .

∎

Theorem— Theorem (Steinitz exchange lemma)

If $u_1, \dots, u_m$ are linearly independent in $V$ and $w_1, \dots, w_n$ span $V$ , then $m \le n$ .

Proof

We replace the $w$ 's by $u$ 's one at a time, keeping a spanning list. We claim that for each $j = 0, 1, \dots, m$ , after renumbering the $w$ 's, $j \le n$ and the list $u_1, \dots, u_j, w_{j+1}, \dots, w_n$ spans $V$ . For $j = 0$ this is the hypothesis.

Suppose it holds for some $j < m$ . Since the list spans, $u_{j+1} = b_1 u_1 + \cdots + b_j u_j + c_{j+1} w_{j+1} + \cdots + c_n w_n$ for some scalars. If every $c_i$ were $0$ — in particular, if no $w$ 's were left, $j = n$ — then $u_{j+1}$ would be a combination of $u_1, \dots, u_j$ , contradicting independence. So $j < n$ , and after renumbering $c_{j+1} \neq 0$ . Solving for $w_{j+1}$ ,

w_{j+1} = c_{j+1}^{-1}\Big(u_{j+1} - \sum_{i \le j} b_i u_i - \sum_{i > j+1} c_i w_i\Big) \in \operatorname{span}(u_1, \dots, u_{j+1}, w_{j+2}, \dots, w_n),

so this new list still spans everything the old one did, namely $V$ . This proves the claim for $j + 1$ , and with $j = m$ it gives $m \le n$ .

∎

Theorem— Corollary (invariance of dimension)

Any two bases of a finite-dimensional vector space have the same number of elements.

Proof

If $(u_1, \dots, u_m)$ and $(w_1, \dots, w_n)$ are bases, each is independent and each spans, so the exchange lemma gives $m \le n$ and $n \le m$ .

∎

Theorem— Corollary (extending to a basis)

In a vector space of dimension $n$ , every linearly independent list has at most $n$ vectors and can be extended to a basis; every subspace $U$ is finite-dimensional with $\dim U \le n$ .

Proof

An independent list has at most $n$ elements by the exchange lemma (a basis spans). If an independent list does not span, add a vector outside its span; by the lemma it stays independent. This must stop after at most $n$ additions, and it stops only at a spanning list, i.e. a basis. For a subspace $U$ , start from the empty list and add vectors of $U$ outside the current span: the lists stay independent in $V$ , so the process stops after at most $n$ steps, at a basis of $U$ .

∎

ProofH

The rank–nullity theorem

Theorem— Theorem (rank–nullity)

Let $T : V \to W$ be linear with $V$ finite-dimensional. Then $\operatorname{im} T$ is finite-dimensional and

\dim V = \dim \ker T + \dim \operatorname{im} T.

Proof

Choose a basis $u_1, \dots, u_s$ of $\ker T$ and extend it to a basis $u_1, \dots, u_s, v_1, \dots, v_r$ of $V$ , so $\dim V = s + r$ . We show that $Tv_1, \dots, Tv_r$ is a basis of $\operatorname{im} T$ .

Spanning. Any $x \in V$ is $\sum a_i u_i + \sum b_j v_j$ , and $Tu_i = 0$ , so $Tx = \sum b_j\, Tv_j$ .

Independence. If $\sum b_j\, Tv_j = 0$ then $T(\sum b_j v_j) = 0$ , so $\sum b_j v_j \in \ker T$ and $\sum b_j v_j = \sum a_i u_i$ for some $a_i$ . Then $\sum a_i u_i - \sum b_j v_j = 0$ is a relation among the vectors of a basis of $V$ , so all $b_j$ (and $a_i$ ) are $0$ .

Hence $\dim \operatorname{im} T = r$ and $\dim V = s + r = \dim\ker T + \dim\operatorname{im} T$ .

∎

For a matrix $A$ , Gaussian elimination makes this concrete: $\operatorname{rank} A$ is the number of pivots (the pivot columns of $A$ form a basis of its column space, because row operations preserve the linear relations between columns), and the nullity is the number of free variables (each free variable gives one basis vector of the null space, as in the worked example). Every column is either a pivot column or a free one.

Theorem— Corollary (more unknowns than equations)

A homogeneous system $Ax = 0$ of $m$ equations in $n > m$ unknowns has a non-zero solution.

Proof

The image of $x \mapsto Ax$ lies in $k^m$ , so has dimension at most $m$ . By rank–nullity $\dim \ker A = n - \dim \operatorname{im} A \ge n - m > 0$ , so $\ker A$ contains a non-zero vector.

∎

For photosynthesis, $n = 4 > 3 = m$ , so a non-zero balancing exists. Elimination shows the rank is exactly $3$ , so the null space is a line: the balancing $(6, 6, 1, 6)$ is unique up to scaling.

Theorem— Corollary (injective, surjective, bijective)

If $T : V \to V$ is linear and $V$ is finite-dimensional, then $T$ is injective $\iff$ $T$ is surjective $\iff$ $T$ is bijective.

Proof

$T$ is injective iff $\dim \ker T = 0$ , iff (by rank–nullity) $\dim \operatorname{im} T = \dim V$ , iff $\operatorname{im} T = V$ (a subspace of full dimension is the whole space: a basis of it is an independent list of $\dim V$ vectors, which cannot be extended, so it already spans $V$ ).

∎

This fails in infinite dimensions: on sequences, the shift $(a_0, a_1, \dots) \mapsto (0, a_0, a_1, \dots)$ is injective but not surjective.

ProofH

Matrices, composition and change of basis

Theorem— Theorem (composition is matrix multiplication)

Let $T : U \to V$ and $S : V \to W$ be linear, and fix bases $(u_j)$ , $(v_r)$ , $(w_i)$ . Then $S \circ T$ is linear, and $[S \circ T] = [S]\,[T]$ .

Proof

Linearity: $S(T(x + y)) = S(Tx + Ty) = S(Tx) + S(Ty)$ , and similarly for scalars. For the matrix, with $[T] = (t_{rj})$ and $[S] = (s_{ir})$ ,

(S \circ T)(u_j) = S\Big(\sum_r t_{rj} v_r\Big) = \sum_r t_{rj}\, S v_r = \sum_r t_{rj} \sum_i s_{ir} w_i = \sum_i \Big(\sum_r s_{ir} t_{rj}\Big) w_i,

so the $(i, j)$ entry of $[S \circ T]$ is $\sum_r s_{ir} t_{rj} = ([S][T])_{ij}$ .

∎

This is why matrices are multiplied rows-into-columns. It also proves for free that matrix multiplication is associative, because composition of functions is. It is not commutative, because composition is not: with $A = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$ and $B = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}$ , $AB = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}$ but $BA = \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}$ . Rotations of the plane do commute: multiplying the rotation matrices $R_\alpha R_\beta$ produces the addition formulas for sine and cosine and gives $R_{\alpha + \beta}$ .

Theorem— Proposition (change of basis)

Let $B$ and $B'$ be bases of $V$ , and let $P$ be the matrix whose $j$ -th column holds the $B$ -coordinates of the $j$ -th vector of $B'$ . Then $P$ is invertible, $[x]_B = P\,[x]_{B'}$ for every $x$ , and for every linear $T : V \to V$ ,

[T]_{B'} = P^{-1}\, [T]_B\, P .

Proof

$P$ is the matrix of the identity map of $V$ from $B'$ -coordinates to $B$ -coordinates, so $[x]_B = P[x]_{B'}$ ; the matrix the other way is an inverse. Then $[Tx]_{B'} = P^{-1}[Tx]_B = P^{-1}[T]_B[x]_B = P^{-1}[T]_B P\,[x]_{B'}$ for all $x$ , and a matrix is determined by what it does to all coordinate vectors.

∎

Matrices $A$ and $P^{-1}AP$ are called similar: they describe the same linear map in two coordinate systems. Everything intrinsic to the map — rank, determinant, trace, eigenvalues, characteristic polynomial — is the same for similar matrices.

ProofH

Determinants and invertibility

We use the following properties of the determinant, all derived from the permutation formula (see Axler, ch. 9, or Strang, ch. 5):

$\det$ is linear in each column when the other columns are fixed;
it is alternating: if two columns are equal, $\det A = 0$ (so swapping two columns changes the sign);
$\det I = 1$ ;
it is multiplicative: $\det(AB) = \det A \det B$ .

Properties 1 and 2 almost characterise the determinant. Let $D$ be any function of $n \times n$ matrices that is linear in each column and alternating. Expanding each column $b_j = \sum_i b_{ij} e_i$ of $B$ by multilinearity writes $D(B)$ as a sum, over all functions $f$ from $\{1, \dots, n\}$ to itself, of $b_{f(1)1} \cdots b_{f(n)n}\, D(e_{f(1)}, \dots, e_{f(n)})$ . Alternation kills every term with $f$ not injective, and for a permutation $\sigma$ the swaps that sort $(e_{\sigma(1)}, \dots, e_{\sigma(n)})$ into $(e_1, \dots, e_n)$ give $D(e_{\sigma(1)}, \dots, e_{\sigma(n)}) = \operatorname{sgn}(\sigma)\, D(I)$ . Comparing with the permutation formula: $D(B) = D(I) \det B$ . Property 4 follows: for fixed $A$ , the function $D(B) = \det(AB)$ is linear in each column of $B$ (the $j$ -th column of $AB$ is $Ab_j$ ) and alternating (equal columns of $B$ give equal columns of $AB$ ), so $\det(AB) = D(I)\det B = \det A \det B$ . Geometrically, $|\det A|$ is the factor by which $A$ multiplies areas ( $n = 2$ ) or volumes ( $n = 3$ ), and the sign records orientation.

Theorem— Theorem (invertibility)

For an $n \times n$ matrix $A$ over a field, the following are equivalent:

$A$ is invertible;
$Ax = 0$ only for $x = 0$ ;
the columns of $A$ are linearly independent;
$\operatorname{rank} A = n$ ;
$\det A \neq 0$ .

Proof

(2 ⇔ 3) $Ax = x_1 a_1 + \cdots + x_n a_n$ where $a_j$ are the columns, so a non-zero solution of $Ax = 0$ is exactly a dependence relation among the columns.

(2 ⇔ 4 ⇔ 1) By rank–nullity, $\dim\ker A = 0$ iff $\operatorname{rank} A = n$ ; and by the corollary on injective maps, this holds iff $x \mapsto Ax$ is bijective. The inverse of a linear bijection is linear (apply the bijection to $T^{-1}u + T^{-1}v$ ), and its matrix is an inverse of $A$ . Conversely an invertible $A$ is injective.

(1 ⇒ 5) $\det A \cdot \det A^{-1} = \det(AA^{-1}) = \det I = 1$ , so $\det A \ne 0$ .

(5 ⇒ 3) Contrapositive. If the columns are dependent, some column is a combination of the others: $a_q = \sum_{j \ne q} c_j a_j$ . By linearity in column $q$ , $\det A = \sum_{j \neq q} c_j \det A_j$ , where $A_j$ is $A$ with column $q$ replaced by $a_j$ . Each $A_j$ has two equal columns, so $\det A_j = 0$ and $\det A = 0$ .

∎

For $2 \times 2$ matrices, $A^{-1} = \dfrac{1}{ad - bc}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$ , which visibly needs $ad - bc \ne 0$ .

ProofH

Eigenvalues and diagonalisation

Theorem— Proposition (eigenvalues are roots of the characteristic polynomial)

$\lambda$ is an eigenvalue of the square matrix $A$ if and only if $\det(\lambda I - A) = 0$ . Hence an $n \times n$ matrix has at most $n$ eigenvalues.

Proof

$Av = \lambda v$ for some $v \ne 0$ iff $(\lambda I - A)v = 0$ has a non-zero solution, iff (invertibility theorem) $\det(\lambda I - A) = 0$ . By the permutation formula, $\det(tI - A)$ is a monic polynomial of degree $n$ in $t$ , so it has at most $n$ roots.

∎

The rotation $\begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$ has $p(t) = t^2 + 1$ : no real eigenvalues, but eigenvalues $\pm i$ over $\C$ . Over $\C$ every square matrix has an eigenvalue, by the fundamental theorem of algebra; this is one reason complex scalars are so useful.

Theorem— Theorem (eigenvectors for distinct eigenvalues are independent)

If $v_1, \dots, v_m$ are eigenvectors of $T : V \to V$ with pairwise distinct eigenvalues $\lambda_1, \dots, \lambda_m$ , then $v_1, \dots, v_m$ are linearly independent.

Proof

Induction on $m$ . For $m = 1$ , $v_1 \ne 0$ is independent. Let $m \ge 2$ , assume the result for $m - 1$ , and suppose $c_1 v_1 + \cdots + c_m v_m = 0$ . Applying $T$ gives $c_1 \lambda_1 v_1 + \cdots + c_m \lambda_m v_m = 0$ . Subtracting $\lambda_m$ times the first relation,

c_1(\lambda_1 - \lambda_m) v_1 + \cdots + c_{m-1}(\lambda_{m-1} - \lambda_m) v_{m-1} = 0 .

By the induction hypothesis every $c_i(\lambda_i - \lambda_m) = 0$ , and $\lambda_i \neq \lambda_m$ , so $c_1 = \cdots = c_{m-1} = 0$ . Then $c_m v_m = 0$ with $v_m \neq 0$ , so $c_m = 0$ .

∎

Theorem— Theorem (diagonalisability)

An $n \times n$ matrix $A$ over $k$ is diagonalisable if and only if $k^n$ has a basis of eigenvectors of $A$ ; then $P^{-1}AP = D$ where the columns of $P$ are the eigenvectors and the diagonal of $D$ lists their eigenvalues. In particular, if $A$ has $n$ distinct eigenvalues in $k$ , it is diagonalisable.

Proof

Write $p_1, \dots, p_n$ for the columns of $P$ and $D = \operatorname{diag}(d_1, \dots, d_n)$ . The $j$ -th column of $AP$ is $Ap_j$ and that of $PD$ is $d_j p_j$ , so $AP = PD$ says exactly that $Ap_j = d_j p_j$ for each $j$ . $P$ is invertible iff its columns form a basis (invertibility theorem), so " $P^{-1}AP = D$ with $P$ invertible" says exactly "the $p_j$ are a basis of eigenvectors". With $n$ distinct eigenvalues, choose one eigenvector for each; they are independent by the previous theorem, and $n$ independent vectors in $k^n$ form a basis.

∎

More generally — by the same independence argument applied to eigenspaces — $A$ is diagonalisable if and only if the geometric multiplicities of its eigenvalues add up to $n$ .

Theorem— Proposition (a matrix that cannot be diagonalised)

$N = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$ is not diagonalisable over any field.

Proof

$p_N(t) = t^2$ , so $0$ is the only eigenvalue, and $E_0 = \ker N = \operatorname{span}(e_1)$ is one-dimensional: there is no basis of eigenvectors. Here is a second proof, the one formalised in Lean, that avoids eigenvectors. Suppose $NP = PD$ with $P$ invertible and $D$ diagonal. Since $N^2 = 0$ ,

PD^2 = (PD)D = NPD = N(PD) = N^2 P = 0,

so $D^2 = 0$ (multiply by $P^{-1}$ ), so each diagonal entry $d_i$ satisfies $d_i^2 = 0$ , i.e. $D = 0$ . Then $NP = 0$ , so $N = 0$ — false.

∎

Example— Fibonacci numbers by diagonalisation

$A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ has $p_A(t) = t^2 - t - 1$ , with distinct roots $\varphi = \frac{1 + \sqrt5}{2}$ and $\psi = \frac{1 - \sqrt5}{2}$ , so it is diagonalisable over $\R$ . Since $\lambda^2 = \lambda + 1$ for both roots, $A\begin{pmatrix} \lambda \\ 1 \end{pmatrix} = \begin{pmatrix} \lambda + 1 \\ \lambda \end{pmatrix} = \lambda \begin{pmatrix} \lambda \\ 1 \end{pmatrix}$ . Write $e_1 = \frac{1}{\sqrt5}\left(\begin{pmatrix} \varphi \\ 1 \end{pmatrix} - \begin{pmatrix} \psi \\ 1 \end{pmatrix}\right)$ (using $\varphi - \psi = \sqrt5$ ). Then

\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = A^n e_1 = \frac{1}{\sqrt5}\left(\varphi^n \begin{pmatrix} \varphi \\ 1 \end{pmatrix} - \psi^n \begin{pmatrix} \psi \\ 1 \end{pmatrix}\right), \qquad\text{so}\qquad F_n = \frac{\varphi^n - \psi^n}{\sqrt5}.

Since $|\psi| < 1$ , $\psi^n \to 0$ and $F_{n+1}/F_n \to \varphi$ : the eigenvector with the larger eigenvalue dominates. This is Binet's formula.

Formal mathematicsF

Linear algebra in Lean and Mathlib

Mathlib's linear algebra is written for modules over rings, and specialises to vector spaces over a field K: Module K V is the vector-space structure, V →ₗ[K] W the type of linear maps, LinearMap.ker and LinearMap.range the kernel and image, Module.finrank K V the dimension (as a natural number), and Matrix m n K the matrices, acting on vectors by A *ᵥ x. The lesson's module proves several results again from basic facts (independent) and cites the library for others.

Linear systems. The structure theorem is a two-line rewrite, exactly the human proof $Tx - Tx_0 = T(x - x_0)$ ; the worked elimination is then checked in full: the solutions of $x + 2y + z = 4$ , $2x + 4y + 3z = 9$ are precisely $(3, 0, 1) + t(-2, 1, 0)$ , both directions of the "if and only if".

solutions_translate_kerLean 4Proved here from basic factsFormally verified

/-- **Solution sets are translates of the kernel.** If `x₀` is one solution of `f x = b`,
then `x` is a solution exactly when `x - x₀` lies in the kernel of `f`: the general solution is
"one particular solution plus the general solution of the homogeneous system". The proof is
the human one: `f x - f x₀ = f (x - x₀)` by linearity. -/
theorem solutions_translate_ker {K V W : Type*} [Field K] [AddCommGroup V] [Module K V]
    [AddCommGroup W] [Module K W] (f : V →ₗ[K] W) {x₀ : V} {b : W} (h₀ : f x₀ = b) (x : V) :
    f x = b ↔ x - x₀ ∈ LinearMap.ker f := by
  rw [LinearMap.mem_ker, map_sub, h₀, sub_eq_zero]