Matrices and Linear Systems: Coordinate Representations of Linear Maps and the Structure of Solutions

0. Key points

• Once we fix one ordered basis in the domain and one in the codomain, linear maps between finite-dimensional vector spaces correspond bijectively to matrices. A matrix is the coordinate representation of a linear map; the array of numbers by itself carries no meaning.
• The matrix product is defined by the strange-looking rule “multiply a row by a column and add”. This rule is forced on us: it is exactly what appears when we compute the representation matrix of a composition. The product is associative because composition is.
• When the bases are changed, the representation matrix of the same linear map becomes $A' = Q^{-1} A P$. How complicated a matrix looks reflects the choice of basis, not a property of the map.
• A linear system $A\boldsymbol{x} = \boldsymbol{b}$ translates into the question: “does $\boldsymbol{b}$ lie in the image of the linear map $\boldsymbol{x} \mapsto A\boldsymbol{x}$, and if so, what is its preimage?”
• Gaussian elimination brings the coefficient matrix to reduced row echelon form using only operations that leave the solution set unchanged. The number of pivots that appear is the rank $\operatorname{rank} A$, and it equals the dimension of the image.
• The solution set is either empty or a translated subspace, “one particular solution + the kernel”, of dimension $n - \operatorname{rank} A$. Solvability is decided by $\operatorname{rank} A = \operatorname{rank} [A \mid \boldsymbol{b}]$.

1. Motivation: how does a table of numbers become an algebra?

Linear systems are an old subject. Chapter 8, “Fangcheng”, of the Chinese Nine Chapters on the Mathematical Art (around the first century) describes laying out counting rods for the coefficients and subtracting one column from another to eliminate unknowns. This is essentially elimination. In the nineteenth century Gauss used the method systematically in the least-squares computations that arose from determining the orbits of asteroids. The idea of writing down only the coefficients and processing them mechanically is nearly two thousand years older than the word “matrix”.

What, then, did the notion of a matrix add? The word matrix was introduced by J. J. Sylvester in 1850, and in 1858 Cayley, in his “A Memoir on the Theory of Matrices”, treated matrices themselves as objects one adds and multiplies. The decisive step was the definition of the product. Cayley defined the product of matrices so that it corresponds to performing one linear substitution after another. At that moment a table of numbers was promoted from a mere storage place for coefficients to a mathematical object equipped with operations.

When one first meets matrices, it is usually the product that causes trouble. Addition is entrywise, so why is multiplication given by the convoluted expression

$$(BA)_{ij} = \sum_{k} b_{ik} a_{kj}$$

rather than entrywise as well? There is only one answer. Matrices exist in order to represent linear maps, and the product was defined in order to represent composition. The entrywise product (the Hadamard product) can certainly be defined, but it does not correspond to composition. The demand that the correspondence be compatible with composition forces that sum upon us.

In this article we first build that correspondence, the representation matrix. A matrix is the face a linear map shows once a basis is fixed, and changing the basis changes the face. From this point of view, $A\boldsymbol{x} = \boldsymbol{b}$ becomes a geometric problem: find the preimage of $\boldsymbol{b}$ under the linear map $f_A$. The classification into zero, one, or infinitely many solutions is then settled all at once in the language of two subspaces, the image and the kernel.

2. Preliminaries: bases, coordinates, and linear maps

Throughout, $K$ denotes a field, and the reader may safely take $K = \mathbb{R}$ or $K = \mathbb{C}$. Vector spaces, linear independence, bases, dimension, linear maps, kernels and images were treated in Vector Spaces and Linear Transformations (linear independence, spanning sets, and bases（Definition 5.1）［Vector Spaces and Linear Maps］, kernel and image（Definition 7.1）［Vector Spaces and Linear Maps］). Here we record, with proofs, two facts that will be used repeatedly.

Let $V$ be a vector space over $K$ and $\mathcal{B} = (\boldsymbol{e}_1, \ldots, \boldsymbol{e}_n)$ a basis of $V$; since the order matters for us, we call it an ordered basis. We write $M_{m,n}(K)$ for the set of all $m \times n$ matrices, $M_n(K)$ for the square matrices of size $n$, and $I_n$ for the identity matrix of size $n$. Elements of $K^n$ are treated as column vectors, and the transpose is written $A^{\mathsf{T}}$.

Proposition 2.1（The coordinate isomorphism, and determination of a linear map by a basis）

Let $V$ be an $n$-dimensional vector space over $K$ and $\mathcal{B} = (\boldsymbol{e}_1, \ldots, \boldsymbol{e}_n)$ an ordered basis of $V$.

1. For each $\boldsymbol{v} \in V$ the coefficients $(x_1, \ldots, x_n)$ in an expression $\boldsymbol{v} = \sum_{j=1}^{n} x_j \boldsymbol{e}_j$ are uniquely determined, and the map

$$\varphi_{\mathcal{B}} : V \to K^n, \qquad \varphi_{\mathcal{B}}(\boldsymbol{v}) = (x_1, \ldots, x_n)^{\mathsf{T}}$$

is a linear isomorphism. We call it the coordinate isomorphism with respect to $\mathcal{B}$. 2. Let $W$ be an arbitrary vector space over $K$ and let $\boldsymbol{w}_1, \ldots, \boldsymbol{w}_n \in W$ be arbitrary elements. Then there is exactly one linear map $f : V \to W$ with $f(\boldsymbol{e}_j) = \boldsymbol{w}_j\ (j = 1, \ldots, n)$.

Proof（Proposition 2.1）

1. Since $\mathcal{B}$ spans $V$, at least one expression $\boldsymbol{v} = \sum_j x_j \boldsymbol{e}_j$ exists. If $\sum_j x_j \boldsymbol{e}_j = \sum_j y_j \boldsymbol{e}_j$, then $\sum_j (x_j - y_j)\boldsymbol{e}_j = \boldsymbol{0}$, and since $\mathcal{B}$ is linearly independent we get $x_j - y_j = 0$ for every $j$; the expression is therefore unique. Hence $\varphi_{\mathcal{B}}$ is well defined.

We check linearity. Let $\boldsymbol{v} = \sum_j x_j \boldsymbol{e}_j$, $\boldsymbol{w} = \sum_j y_j \boldsymbol{e}_j$ and $c \in K$. The vector space axioms give $\boldsymbol{v} + c\boldsymbol{w} = \sum_j (x_j + c y_j)\boldsymbol{e}_j$, and by uniqueness these are the coordinates of $\boldsymbol{v} + c\boldsymbol{w}$. Hence $\varphi_{\mathcal{B}}(\boldsymbol{v} + c\boldsymbol{w}) = \varphi_{\mathcal{B}}(\boldsymbol{v}) + c\,\varphi_{\mathcal{B}}(\boldsymbol{w})$.

Surjectivity follows because $\boldsymbol{v} = \sum_j x_j \boldsymbol{e}_j$ is a preimage of $(x_1, \ldots, x_n)^{\mathsf{T}} \in K^n$. Injectivity follows because $\varphi_{\mathcal{B}}(\boldsymbol{v}) = \boldsymbol{0}$ forces $\boldsymbol{v} = \sum_j 0 \cdot \boldsymbol{e}_j = \boldsymbol{0}$, and a linear map with kernel $\{\boldsymbol{0}\}$ is injective.

2. Existence: using the uniqueness in part 1, define $f\left(\sum_j x_j \boldsymbol{e}_j\right) := \sum_j x_j \boldsymbol{w}_j$. Since coordinates are unique, there is no ambiguity in this definition. Linearity is the same computation as in part 1. The coordinates of $\boldsymbol{e}_j$ have $1$ in the $j$-th slot and $0$ elsewhere, so $f(\boldsymbol{e}_j) = \boldsymbol{w}_j$.

Uniqueness: if $g : V \to W$ is also linear with $g(\boldsymbol{e}_j) = \boldsymbol{w}_j$, then for any $\boldsymbol{v} = \sum_j x_j \boldsymbol{e}_j$ linearity of $g$ gives $g(\boldsymbol{v}) = \sum_j x_j g(\boldsymbol{e}_j) = \sum_j x_j \boldsymbol{w}_j = f(\boldsymbol{v})$, so $g = f$.

∎

Part 2 of Proposition 2.1 should be read as: “a linear map is determined by where it sends the basis vectors, and those destinations may be prescribed freely”. A map that ought to require specifying values at infinitely many points is pinned down by $n$ pieces of data. This is precisely why a map can be described by the finite data of a matrix.

3. The representation matrix: translating a linear map into a table of numbers

Definition 3.1（Representation matrix）

Let $V$ be an $n$-dimensional and $W$ an $m$-dimensional vector space over $K$, let $\mathcal{B} = (\boldsymbol{e}_1, \ldots, \boldsymbol{e}_n)$ be an ordered basis of $V$ and $\mathcal{C} = (\boldsymbol{u}_1, \ldots, \boldsymbol{u}_m)$ an ordered basis of $W$. For a linear map $f : V \to W$ and each $j$, let $a_{ij}$ be the coefficients obtained by expanding $f(\boldsymbol{e}_j) \in W$ in $\mathcal{C}$, that is,

$$f(\boldsymbol{e}_j) = \sum_{i=1}^{m} a_{ij}\,\boldsymbol{u}_i \qquad (j = 1, \ldots, n).$$

Then $A = (a_{ij}) \in M_{m,n}(K)$ is called the representation matrix of $f$ with respect to the bases $\mathcal{B}, \mathcal{C}$, and is denoted $M_{\mathcal{C}\mathcal{B}}(f)$.

Note the indices. The second index $j$ of $a_{ij}$ records which basis vector was mapped, and the first index $i$ records which component of the destination is meant. In other words,

$$\text{the } j\text{-th column of } A = \varphi_{\mathcal{C}}\bigl(f(\boldsymbol{e}_j)\bigr),$$

so the columns of a representation matrix list the destinations of the basis vectors. Whenever you see a matrix, read its columns one at a time as “the vector this one goes to”.

Theorem 3.2（The correspondence between linear maps and matrices）

Let $V, W, \mathcal{B}, \mathcal{C}$ be as in Definition 3.1, with $\dim V = n$ and $\dim W = m$. For $\boldsymbol{x} = (x_1, \ldots, x_n)^{\mathsf{T}} \in K^n$ and $A = (a_{ij}) \in M_{m,n}(K)$, define $A\boldsymbol{x} \in K^m$ by

$$(A\boldsymbol{x})_i = \sum_{j=1}^{n} a_{ij} x_j \qquad (i = 1, \ldots, m).$$

Then the following hold.

1. If $A = M_{\mathcal{C}\mathcal{B}}(f)$, then $\varphi_{\mathcal{C}}\bigl(f(\boldsymbol{v})\bigr) = A\,\varphi_{\mathcal{B}}(\boldsymbol{v})$ for all $\boldsymbol{v} \in V$.
2. The map $M_{\mathcal{C}\mathcal{B}} : \operatorname{Hom}(V, W) \to M_{m,n}(K)$, $f \mapsto M_{\mathcal{C}\mathcal{B}}(f)$, is a linear isomorphism. Here $\operatorname{Hom}(V,W)$ denotes the vector space of all linear maps from $V$ to $W$.

In particular $\dim \operatorname{Hom}(V, W) = mn$.

Proof（Theorem 3.2）

1. Take $\boldsymbol{v} \in V$ and write $\varphi_{\mathcal{B}}(\boldsymbol{v}) = (x_1, \ldots, x_n)^{\mathsf{T}}$, that is, $\boldsymbol{v} = \sum_{j} x_j \boldsymbol{e}_j$. Linearity of $f$ together with Definition 3.1 gives

$$\begin{aligned} f(\boldsymbol{v}) &= f\Bigl(\sum_{j=1}^{n} x_j \boldsymbol{e}_j\Bigr) = \sum_{j=1}^{n} x_j\, f(\boldsymbol{e}_j) \\ &= \sum_{j=1}^{n} x_j \sum_{i=1}^{m} a_{ij}\,\boldsymbol{u}_i = \sum_{i=1}^{m} \Bigl(\sum_{j=1}^{n} a_{ij} x_j\Bigr) \boldsymbol{u}_i . \end{aligned}$$

The last equality is an interchange of the order of summation in a finite sum. By part 1 of Proposition 2.1 the coordinates with respect to $\mathcal{C}$ are unique, so the $i$-th coordinate of $f(\boldsymbol{v})$ is $\sum_j a_{ij}x_j = (A\boldsymbol{x})_i$, which is the assertion.

Observe that the definition of $A\boldsymbol{x}$ is nothing but a transcription of this computation. The product of a matrix and a vector is not an arbitrary rule handed down from above: it is the linear map written in coordinates.

2. Linearity: for $f, g : V \to W$ and $c \in K$ we have $(f + cg)(\boldsymbol{e}_j) = f(\boldsymbol{e}_j) + c\,g(\boldsymbol{e}_j)$, and the coefficients obtained by expanding the right-hand side in $\mathcal{C}$ are the sum of the respective coefficients and $c$ times them (by the linearity in part 1 of Proposition 2.1). Hence $M_{\mathcal{C}\mathcal{B}}(f + cg) = M_{\mathcal{C}\mathcal{B}}(f) + c\,M_{\mathcal{C}\mathcal{B}}(g)$.

Injectivity: if $M_{\mathcal{C}\mathcal{B}}(f) = O$ (the zero matrix), then $f(\boldsymbol{e}_j) = \sum_i 0 \cdot \boldsymbol{u}_i = \boldsymbol{0}$ for every $j$. The zero map satisfies the same condition, so the uniqueness in part 2 of Proposition 2.1 forces $f = 0$. A linear map with kernel $\{0\}$ is injective.

Surjectivity: take any $A = (a_{ij}) \in M_{m,n}(K)$ and put $\boldsymbol{w}_j := \sum_{i=1}^{m} a_{ij}\boldsymbol{u}_i \in W$. By part 2 of Proposition 2.1 there is a linear map $f$ with $f(\boldsymbol{e}_j) = \boldsymbol{w}_j$, and its representation matrix is exactly $A$.

Finally $\dim M_{m,n}(K) = mn$ (the $mn$ matrices having exactly one entry equal to $1$ form a basis), so the isomorphism gives $\dim \operatorname{Hom}(V,W) = mn$.

∎

Part 1 of Theorem 3.2 asserts that the following diagram commutes, that is, “going along the top and going along the bottom give the same result”. Replacing $V, W$ by $K^n, K^m$ via the coordinate isomorphisms turns the abstract map $f$ into multiplication by a matrix.

flowchart LR
V["V (basis B)"] -->|"f"| W["W (basis C)"]
V -->|"coordinate iso φ_B"| Kn["K^n"]
W -->|"coordinate iso φ_C"| Km["K^m"]
Kn -->|"x ↦ Ax"| Km

A representation matrix is the behaviour of f after transporting everything by the coordinate isomorphisms

Example 3.3（Rotation of the plane）

Let $V = W = \mathbb{R}^2$, let $\mathcal{E} = (\boldsymbol{e}_1, \boldsymbol{e}_2)$ be the standard basis, and let $f = R_\theta$ be the rotation about the origin through the angle $\theta$. To find the representation matrix it suffices to see where the basis vectors go. The vector $\boldsymbol{e}_1 = (1,0)^{\mathsf{T}}$ is the point of the unit circle at angle $0$, so after the rotation it becomes the point at angle $\theta$, namely $(\cos\theta, \sin\theta)^{\mathsf{T}}$. The vector $\boldsymbol{e}_2 = (0,1)^{\mathsf{T}}$ is the point at angle $\pi/2$, so it becomes the point at angle $\theta + \pi/2$, namely $(\cos(\theta + \pi/2), \sin(\theta+\pi/2))^{\mathsf{T}} = (-\sin\theta, \cos\theta)^{\mathsf{T}}$. Placing these in the columns,

$$M_{\mathcal{E}\mathcal{E}}(R_\theta) = \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix}.$$

What deserves to be memorised is not the matrix but the reading: “the first column is the image of $\boldsymbol{e}_1$”.

Example 3.4（Differentiation of polynomials is a matrix）

Let $P_n$ be the space of real polynomials of degree at most $n$. Take $\mathcal{B} = (1, x, x^2, x^3)$ as a basis of $P_3$ and $\mathcal{C} = (1, x, x^2)$ as a basis of $P_2$, and consider the differentiation map $D : P_3 \to P_2$, $D(p) = p'$. That $D$ is linear is exactly the linearity of differentiation. The basis vectors go to

$$D(1) = 0, \quad D(x) = 1, \quad D(x^2) = 2x, \quad D(x^3) = 3x^2 ,$$

so converting these to coordinates with respect to $\mathcal{C}$ and placing them in the columns gives

$$M_{\mathcal{C}\mathcal{B}}(D) = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 3 \end{pmatrix} \in M_{3,4}(\mathbb{R}).$$

Let us check this. The coordinates of $p(x) = 2 - x + 4x^2 + x^3$ are $(2, -1, 4, 1)^{\mathsf{T}}$, and

$$\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 3 \end{pmatrix} \begin{pmatrix} 2 \\ -1 \\ 4 \\ 1 \end{pmatrix} = \begin{pmatrix} -1 \\ 8 \\ 3 \end{pmatrix}$$

which represents $-1 + 8x + 3x^2$. On the other hand $p'(x) = -1 + 8x + 3x^2$, so the two agree. Differentiation, an infinitesimal operation, becomes a $3 \times 4$ table of numbers as soon as we choose bases. Matrices are not merely a tool for numerical computation; they are the common language of all linear operations.

4. The matrix product: representing composition

Let us compute, in the language of representation matrices, what happens when two linear maps are applied one after the other. This is where the definition of the product comes from.

Let $U, V, W$ be vector spaces over $K$ of dimensions $p, n, m$ respectively, with ordered bases $\mathcal{D} = (\boldsymbol{d}_1, \ldots, \boldsymbol{d}_p)$, $\mathcal{B} = (\boldsymbol{e}_1, \ldots, \boldsymbol{e}_n)$ and $\mathcal{C} = (\boldsymbol{u}_1, \ldots, \boldsymbol{u}_m)$. Let $f : U \to V$ and $g : V \to W$ be linear maps with representation matrices $A = (a_{kj}) = M_{\mathcal{B}\mathcal{D}}(f) \in M_{n,p}(K)$ and $B = (b_{ik}) = M_{\mathcal{C}\mathcal{B}}(g) \in M_{m,n}(K)$. The composite $g \circ f : U \to W$ is again linear and so has a representation matrix. Let us find it: following Definition 3.1, we compute the destinations of the basis vectors.

$$\begin{aligned} (g \circ f)(\boldsymbol{d}_j) &= g\bigl(f(\boldsymbol{d}_j)\bigr) = g\Bigl(\sum_{k=1}^{n} a_{kj}\boldsymbol{e}_k\Bigr) = \sum_{k=1}^{n} a_{kj}\, g(\boldsymbol{e}_k) \\ &= \sum_{k=1}^{n} a_{kj} \sum_{i=1}^{m} b_{ik}\,\boldsymbol{u}_i = \sum_{i=1}^{m} \Bigl(\sum_{k=1}^{n} b_{ik} a_{kj}\Bigr) \boldsymbol{u}_i . \end{aligned}$$

The third equality used the linearity of $g$. The upshot is that the $(i,j)$ entry of the representation matrix of $g\circ f$ is $\sum_k b_{ik}a_{kj}$. If we call this expression the “product”, the correspondence with representation matrices becomes compatible with composition.

Definition 4.1（Matrix product）

Let $B = (b_{ik}) \in M_{m,n}(K)$ and $A = (a_{kj}) \in M_{n,p}(K)$. When the number of columns of $B$ and the number of rows of $A$ agree, both being $n$, the product $BA \in M_{m,p}(K)$ is defined by

$$(BA)_{ij} = \sum_{k=1}^{n} b_{ik} a_{kj} \qquad (1 \le i \le m,\ 1 \le j \le p).$$

The case $p = 1$ is the matrix-vector product of Theorem 3.2. The definition also shows that the $j$-th column of $BA$ equals $B \cdot (\text{the } j\text{-th column of } A)$, since the $i$-th entry of either side is $\sum_k b_{ik}a_{kj}$. This “column by column” property will be used later.

Theorem 4.2（The product represents the composition）

With the notation above,

$$M_{\mathcal{C}\mathcal{D}}(g \circ f) = M_{\mathcal{C}\mathcal{B}}(g)\; M_{\mathcal{B}\mathcal{D}}(f)$$

holds.

Proof（Theorem 4.2）

The computation carried out above is already the proof. We found $(g\circ f)(\boldsymbol{d}_j) = \sum_{i} \bigl(\sum_k b_{ik}a_{kj}\bigr)\boldsymbol{u}_i$, and by part 1 of Proposition 2.1 the coefficients with respect to $\mathcal{C}$ are uniquely determined, so the $(i,j)$ entry of $M_{\mathcal{C}\mathcal{D}}(g\circ f)$ is $\sum_k b_{ik}a_{kj}$. By Definition 4.1 this equals $(BA)_{ij}$.

∎

Whatever is awkward about the matrix product is inherited from what is awkward about composing maps. In exchange, properties of maps translate directly into properties of matrices. The following corollary is the typical example: it can be proved without any computation with entries.

Corollary 4.3（Associativity of the product）

For $A \in M_{n,p}(K)$, $B \in M_{m,n}(K)$ and $C \in M_{l,m}(K)$ we have $(CB)A = C(BA)$.

Proof（Corollary 4.3）

To a matrix $A \in M_{n,p}(K)$ associate the linear map $f_A : K^p \to K^n$, $f_A(\boldsymbol{x}) = A\boldsymbol{x}$. The representation matrix of $f_A$ with respect to the standard bases of $K^p$ and $K^n$ is $A$ itself: indeed, for a standard basis vector $\boldsymbol{e}_j$ the $i$-th entry of $A\boldsymbol{e}_j$ is $\sum_k a_{ik}(\boldsymbol{e}_j)_k = a_{ij}$, that is, $A\boldsymbol{e}_j$ is the $j$-th column of $A$.

Applying Theorem 4.2 twice, $C(BA)$ is the representation matrix of $f_C \circ (f_B \circ f_A)$ and $(CB)A$ is that of $(f_C \circ f_B) \circ f_A$. But composition of maps is associative, and both are the same map $\boldsymbol{x} \mapsto f_C\bigl(f_B(f_A(\boldsymbol{x}))\bigr)$. Since the representation matrix is uniquely determined by the map (injectivity in part 2 of Theorem 3.2), we conclude $C(BA) = (CB)A$.

∎

Example 4.4（Composing rotations and the addition formulas）

For the rotation matrices of Example 3.3, the identity $R_\alpha \circ R_\beta = R_{\alpha + \beta}$ is geometrically obvious: rotating by $\beta$ and then by $\alpha$ is the same as rotating by $\alpha + \beta$. By Theorem 4.2 the same identity must hold on the side of representation matrices. Computing the left-hand side according to Definition 4.1,

$$\begin{pmatrix} \cos\alpha & -\sin\alpha \\ \sin\alpha & \cos\alpha \end{pmatrix} \begin{pmatrix} \cos\beta & -\sin\beta \\ \sin\beta & \cos\beta \end{pmatrix} = \begin{pmatrix} \cos\alpha\cos\beta - \sin\alpha\sin\beta & -(\cos\alpha\sin\beta + \sin\alpha\cos\beta) \\ \sin\alpha\cos\beta + \cos\alpha\sin\beta & \cos\alpha\cos\beta - \sin\alpha\sin\beta \end{pmatrix}$$

The right-hand side is $R_{\alpha+\beta}$, the matrix whose $(1,1)$ entry is $\cos(\alpha+\beta)$ and whose $(2,1)$ entry is $\sin(\alpha+\beta)$. Comparing entries,

$$\cos(\alpha+\beta) = \cos\alpha\cos\beta - \sin\alpha\sin\beta, \qquad \sin(\alpha+\beta) = \sin\alpha\cos\beta + \cos\alpha\sin\beta .$$

The addition formulas are nothing other than “composition of rotations” written in coordinates.

Remark 4.5（Why the product is not commutative）

Unlike multiplication of real numbers, the matrix product generally satisfies $AB \ne BA$. This too can be seen geometrically. Let $R = \begin{pmatrix} 0 & -1 \\ 1 & 0\end{pmatrix}$ be the rotation by $90^\circ$ and $S = \begin{pmatrix} 1 & 0 \\ 0 & -1\end{pmatrix}$ the reflection in the $x$-axis. Then

$$RS = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad SR = \begin{pmatrix} 0 & -1 \\ -1 & 0 \end{pmatrix}$$

(for instance $(RS)_{12} = 0\cdot 0 + (-1)\cdot(-1) = 1$ and $(SR)_{12} = 1\cdot(-1) + 0\cdot 0 = -1$). Here $RS$ is the reflection in the line $y = x$ and $SR$ the reflection in the line $y = -x$, which are different transformations. Just as turning a book cover-up and then rotating it $90^\circ$ to the right gives a different result from doing the two in the opposite order, non-commutativity reflects the fact that transformations depend on the order in which they are applied.

5. Changing the basis

The same linear map has different representation matrices for different bases. Leaving this point vague makes the meaning of diagonalisation incomprehensible later on. We first express the change of basis itself by a matrix.

Definition 5.1（Change-of-basis matrix）

Let $V$ be an $n$-dimensional vector space over $K$ and let $\mathcal{B} = (\boldsymbol{e}_1, \ldots, \boldsymbol{e}_n)$ and $\mathcal{B}' = (\boldsymbol{e}'_1, \ldots, \boldsymbol{e}'_n)$ be two ordered bases of $V$. Expanding each $\boldsymbol{e}'_j$ in $\mathcal{B}$,

$$\boldsymbol{e}'_j = \sum_{i=1}^{n} p_{ij}\,\boldsymbol{e}_i \qquad (j = 1, \ldots, n),$$

the matrix $P = (p_{ij}) \in M_n(K)$ is called the change-of-basis matrix from $\mathcal{B}'$ to $\mathcal{B}$. By definition $P = M_{\mathcal{B}\mathcal{B}'}(\mathrm{id}_V)$.

Since $P$ is the representation matrix of the identity map, applying part 1 of Theorem 3.2 to $f = \mathrm{id}_V$ gives, for every $\boldsymbol{v} \in V$,

$$\varphi_{\mathcal{B}}(\boldsymbol{v}) = P\,\varphi_{\mathcal{B}'}(\boldsymbol{v}).$$

Thus $P$ is the transformation that “takes new coordinates in and gives old coordinates out”. The change of bases $\mathcal{B} \to \mathcal{B}'$ and the change of coordinates $\mathcal{B}' \to \mathcal{B}$ run in opposite directions, which is a common source of confusion.

Caution

Let us check the direction in a one-dimensional example. Take $V = \mathbb{R}$ (lengths) with $\boldsymbol{e}_1 = 1\,\text{m}$ and $\boldsymbol{e}'_1 = 1\,\text{cm}$. Then $\boldsymbol{e}'_1 = 0.01\,\boldsymbol{e}_1$, so $P = (0.01)$. The new coordinate of “3 m” (in centimetres) is $300$ and the old one is $3$, and indeed $3 = 0.01 \times 300$. Making the basis finer makes the numerical coordinates larger.

Theorem 5.2（Transformation rule for representation matrices）

Let $f : V \to W$ be a linear map. Take two ordered bases $\mathcal{B}, \mathcal{B}'$ of $V$ and two ordered bases $\mathcal{C}, \mathcal{C}'$ of $W$, and let $P = M_{\mathcal{B}\mathcal{B}'}(\mathrm{id}_V)$ and $Q = M_{\mathcal{C}\mathcal{C}'}(\mathrm{id}_W)$ be the change-of-basis matrices. Then $P$ and $Q$ are invertible and

$$M_{\mathcal{C}'\mathcal{B}'}(f) = Q^{-1}\, M_{\mathcal{C}\mathcal{B}}(f)\, P$$

holds.

Proof（Theorem 5.2）

First, $M_{\mathcal{B}\mathcal{B}}(\mathrm{id}_V) = I_n$. Indeed $\mathrm{id}_V(\boldsymbol{e}_j) = \boldsymbol{e}_j$, so the coefficients in Definition 3.1 are $a_{ij} = \delta_{ij}$ (equal to $1$ when $i = j$ and $0$ otherwise).

Put $P^{\ast} := M_{\mathcal{B}'\mathcal{B}}(\mathrm{id}_V)$. Applying Theorem 4.2 to $\mathrm{id}_V \circ \mathrm{id}_V = \mathrm{id}_V$,

$$P P^{\ast} = M_{\mathcal{B}\mathcal{B}'}(\mathrm{id}_V)\, M_{\mathcal{B}'\mathcal{B}}(\mathrm{id}_V) = M_{\mathcal{B}\mathcal{B}}(\mathrm{id}_V) = I_n,$$

and similarly $P^{\ast} P = M_{\mathcal{B}'\mathcal{B}'}(\mathrm{id}_V) = I_n$. Hence $P$ is invertible with $P^{-1} = M_{\mathcal{B}'\mathcal{B}}(\mathrm{id}_V)$. The same argument applies to $Q$.

Next write $f = \mathrm{id}_W \circ f \circ \mathrm{id}_V$ and use Theorem 4.2 twice:

$$M_{\mathcal{C}'\mathcal{B}'}(f) = M_{\mathcal{C}'\mathcal{C}}(\mathrm{id}_W)\; M_{\mathcal{C}\mathcal{B}}(f)\; M_{\mathcal{B}\mathcal{B}'}(\mathrm{id}_V) = Q^{-1} M_{\mathcal{C}\mathcal{B}}(f)\, P .$$

In the last equality we used the identity $M_{\mathcal{C}'\mathcal{C}}(\mathrm{id}_W) = Q^{-1}$ just established.

∎

Remark 5.3（Similarity: another face of the same map）

When $V = W$ and the same basis is used in the domain and the codomain ($\mathcal{C} = \mathcal{B}$, $\mathcal{C}' = \mathcal{B}'$), we have $Q = P$ and the transformation rule takes the form

$$A' = P^{-1} A P .$$

Two square matrices related in this way are called similar (definition of similarity（Definition 2.1）［対角化とジョルダン標準形］). Similar matrices are “the same linear transformation viewed from different bases”. Consequently, any quantity invariant under similarity (the determinant, the trace, the eigenvalues, the rank, and so on in later chapters) is a property of the map itself, while any quantity that is not is an apparent property depending on the choice of basis. When working with a matrix, keep asking: is this a property of the map, or a property of the coordinates?

Example 5.4（A projection: diagonal in a good basis）

In $\mathbb{R}^2$, consider the projection $p$ onto the line $\ell = \operatorname{span}\{\boldsymbol{a}\}$ (with $\boldsymbol{a} = (2,1)^{\mathsf{T}}$) along the line $\operatorname{span}\{\boldsymbol{b}\}$ (with $\boldsymbol{b} = (-1,2)^{\mathsf{T}}$). Since $\boldsymbol{a}$ and $\boldsymbol{b}$ are orthogonal, hence linearly independent, $\mathcal{B}' = (\boldsymbol{a}, \boldsymbol{b})$ is a basis. By definition $p$ satisfies $p(\boldsymbol{a}) = \boldsymbol{a}$ and $p(\boldsymbol{b}) = \boldsymbol{0}$, and by part 2 of Proposition 2.1 these two conditions determine $p$ uniquely. The representation matrix with respect to $\mathcal{B}'$ is obtained just by listing the destinations of the basis vectors:

$$A' = M_{\mathcal{B}'\mathcal{B}'}(p) = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}.$$

The essence of a projection (keep one direction, crush the other) is visible at a glance.

What, then, is the representation matrix $A = M_{\mathcal{E}\mathcal{E}}(p)$ with respect to the standard basis $\mathcal{E}$? The change-of-basis matrix has the standard coordinates of the new basis vectors $\boldsymbol{a}, \boldsymbol{b}$ as its columns:

$$P = \begin{pmatrix} 2 & -1 \\ 1 & 2 \end{pmatrix}, \qquad P^{-1} = \frac{1}{5}\begin{pmatrix} 2 & 1 \\ -1 & 2 \end{pmatrix}$$

(the identity $P P^{-1} = I_2$ is verified by direct computation). Solving the formula $A' = P^{-1}AP$ of Remark 5.3 for $A$ gives $A = P A' P^{-1}$, so

$$A = \begin{pmatrix} 2 & -1 \\ 1 & 2\end{pmatrix}\begin{pmatrix} 1 & 0 \\ 0 & 0\end{pmatrix} \cdot \frac{1}{5}\begin{pmatrix} 2 & 1 \\ -1 & 2\end{pmatrix} = \begin{pmatrix} 2 & 0 \\ 1 & 0 \end{pmatrix}\cdot \frac{1}{5}\begin{pmatrix} 2 & 1 \\ -1 & 2\end{pmatrix} = \frac{1}{5}\begin{pmatrix} 4 & 2 \\ 2 & 1 \end{pmatrix}.$$

Let us verify. We get $A\boldsymbol{a} = \frac{1}{5}(4\cdot 2 + 2\cdot 1,\; 2\cdot 2 + 1\cdot 1)^{\mathsf{T}} = \frac{1}{5}(10, 5)^{\mathsf{T}} = (2,1)^{\mathsf{T}} = \boldsymbol{a}$ and $A\boldsymbol{b} = \frac{1}{5}(-4+4,\; -2+2)^{\mathsf{T}} = \boldsymbol{0}$, so this is indeed the representation matrix of $p$.

The same map became $\operatorname{diag}(1,0)$ in a good basis and a matrix full of fractions in the standard basis. The matrix is not complicated; the basis simply does not fit the map. Searching for a basis that fits the map is the subject of Eigenvalues and Eigenvectors and Diagonalization and Jordan Normal Form.

6. Reading a linear system as Ax = b

A system of $m$ linear equations in $n$ unknowns,

$$\begin{cases} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n = b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n = b_2 \\ \qquad\qquad\qquad \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n = b_m \end{cases}$$

can be written on one line as $A\boldsymbol{x} = \boldsymbol{b}$, using the matrix-vector product introduced in Theorem 3.2, where $A = (a_{ij}) \in M_{m,n}(K)$, $\boldsymbol{x} = (x_1,\ldots,x_n)^{\mathsf{T}}$ and $\boldsymbol{b} = (b_1,\ldots,b_m)^{\mathsf{T}}$. We call $A$ the coefficient matrix, and the $m \times (n+1)$ matrix $[A \mid \boldsymbol{b}]$ obtained by appending the column $\boldsymbol{b}$ to the right of $A$ the augmented matrix.

There are three ways to read this single line, and we switch between them according to the situation.

Reading	How the equation is seen	Geometric meaning
By rows	each row $\sum_j a_{ij}x_j = b_i$ is one equation	find the intersection of $m$ hyperplanes in $K^n$
By columns	$x_1 \boldsymbol{a}_1 + \cdots + x_n \boldsymbol{a}_n = \boldsymbol{b}$ (where $\boldsymbol{a}_j$ is the $j$-th column of $A$)	can $\boldsymbol{b}$ be written as a linear combination of the columns?
By maps	$f_A(\boldsymbol{x}) = \boldsymbol{b}$ with $f_A(\boldsymbol{x}) = A\boldsymbol{x}$	find the preimage $f_A^{-1}(\boldsymbol{b})$ under the linear map $f_A$

The “intersection of two lines” familiar from school is the reading by rows, but the last two are the powerful ones in theory. That the reading by columns is correct follows from the definition of the product: the $i$-th entry $\sum_j a_{ij}x_j$ of $A\boldsymbol{x}$ is the same as the $i$-th entry of $\sum_j x_j \boldsymbol{a}_j$. In other words

$$A\boldsymbol{x} = x_1\boldsymbol{a}_1 + x_2\boldsymbol{a}_2 + \cdots + x_n\boldsymbol{a}_n$$

holds for every $\boldsymbol{x}$. The product of a matrix and a vector is a linear combination of the columns. This single sentence is worth remembering.

In Vector Spaces and Linear Transformations we defined the kernel and image of a linear map. For a matrix $A \in M_{m,n}(K)$ we simply call the kernel and image of the linear map $f_A : K^n \to K^m$ the kernel and image of $A$, and write

$$\operatorname{Ker} A = \{\boldsymbol{x} \in K^n : A\boldsymbol{x} = \boldsymbol{0}\} \subseteq K^n, \qquad \operatorname{Im} A = \{A\boldsymbol{x} : \boldsymbol{x} \in K^n\} \subseteq K^m .$$

Both are subspaces (this is the special case of the basic properties of kernel and image（Proposition 7.2）［Vector Spaces and Linear Maps］). From the expression as a linear combination shown above,

$$\operatorname{Im} A = \operatorname{span}\{\boldsymbol{a}_1, \ldots, \boldsymbol{a}_n\},$$

that is, the image coincides with the subspace spanned by the columns of $A$ (the column space). In this language the question of solvability reduces to the single question “is $\boldsymbol{b} \in \operatorname{Im}A$?”.

Proposition 6.1（Structure of the solution set）

Let $A \in M_{m,n}(K)$ and $\boldsymbol{b} \in K^m$, and put $S = \{\boldsymbol{x} \in K^n : A\boldsymbol{x} = \boldsymbol{b}\}$.

1. If $\boldsymbol{b} \notin \operatorname{Im}A$, then $S = \varnothing$.
2. If some $\boldsymbol{x}_0 \in S$ exists, then $S = \boldsymbol{x}_0 + \operatorname{Ker}A := \{\boldsymbol{x}_0 + \boldsymbol{z} : \boldsymbol{z} \in \operatorname{Ker}A\}$.

Proof（Proposition 6.1）

1. This is the definition of $\operatorname{Im}A$ itself: if $S \ne \varnothing$, then for an element $\boldsymbol{x}$ of $S$ we get $\boldsymbol{b} = A\boldsymbol{x} \in \operatorname{Im}A$.

2. We first show $\supseteq$. For $\boldsymbol{z} \in \operatorname{Ker}A$, linearity of $f_A$ gives

$$A(\boldsymbol{x}_0 + \boldsymbol{z}) = A\boldsymbol{x}_0 + A\boldsymbol{z} = \boldsymbol{b} + \boldsymbol{0} = \boldsymbol{b},$$

so $\boldsymbol{x}_0 + \boldsymbol{z} \in S$.

Next we show $\subseteq$. Let $\boldsymbol{x} \in S$ and put $\boldsymbol{z} := \boldsymbol{x} - \boldsymbol{x}_0$. By linearity $A\boldsymbol{z} = A\boldsymbol{x} - A\boldsymbol{x}_0 = \boldsymbol{b} - \boldsymbol{b} = \boldsymbol{0}$, so $\boldsymbol{z} \in \operatorname{Ker}A$ and $\boldsymbol{x} = \boldsymbol{x}_0 + \boldsymbol{z} \in \boldsymbol{x}_0 + \operatorname{Ker}A$.

∎

Proposition 6.1 anticipates most of the theory. Unless it is empty, the solution set of an inhomogeneous system is the solution set of the homogeneous system (the kernel) translated by one particular solution. The kernel is a subspace through the origin, and the solution set is its translate (an affine subspace).

The solution set is the kernel translated by a particular solution

In the situation drawn, $\dim\operatorname{Ker}A = 1$, so the solutions have one dimension of freedom. If the kernel is just $\{\boldsymbol{0}\}$ there is at most one solution; if the kernel has positive dimension and there is at least one solution, then there are infinitely many (when $K$ is an infinite field). The school fact that “there are either zero, one, or infinitely many solutions” has been reduced to a question about the dimension of the kernel. What remains is a means of computing that dimension, namely Gaussian elimination.

7. Gaussian elimination

When solving a system of equations we multiply one equation by a constant and add it to another, or swap two equations. These operations are permitted because they do not change the solution set. Formulating the same operations as operations on the rows of the augmented matrix, and pushing them as far as they will go, gives the elimination method.

Definition 7.1（Elementary row operations and row equivalence）

The following three kinds of operations on a matrix $A$ are called elementary row operations.

1. (Type I) Interchange the $p$-th and $q$-th rows ($p \ne q$).
2. (Type II) Multiply the $p$-th row by $c \ne 0$.
3. (Type III) Add $c$ times the $q$-th row to the $p$-th row ($p \ne q$, $c \in K$).

If $A'$ is obtained from $A$ by finitely many elementary row operations, then $A$ and $A'$ are said to be row equivalent.

Lemma 7.2（Three properties of elementary row operations）

Let $A \in M_{m,n}(K)$ and write $o(A)$ for the matrix obtained by applying one elementary row operation $o$ to $A$.

1. Put $E_o := o(I_m)$, the matrix obtained by applying the same operation to the identity matrix; it is called an elementary matrix. Then $o(A) = E_o A$ for every $A \in M_{m,n}(K)$.
2. $E_o$ is invertible and its inverse is again an elementary matrix. Consequently, row equivalent matrices are carried into one another by left multiplication by an invertible matrix.
3. If $[A' \mid \boldsymbol{b}']$ is row equivalent to $[A \mid \boldsymbol{b}]$, then $A\boldsymbol{x} = \boldsymbol{b}$ and $A'\boldsymbol{x} = \boldsymbol{b}'$ have the same solution set.

Proof（Lemma 7.2）

1. The key is the following observation. For any $E \in M_m(K)$ and $A \in M_{m,n}(K)$, Definition 4.1 gives $(EA)_{ij} = \sum_{k=1}^{m} e_{ik}a_{kj}$, hence

$$\text{the } i\text{-th row of } EA = \sum_{k=1}^{m} e_{ik}\,\bigl(\text{the } k\text{-th row of } A\bigr).$$

That is, multiplying on the left replaces each row by a linear combination of the original rows, with the coefficients written in the rows of the left factor. It only remains to read off the rows of $E_o = o(I_m)$ for each of the three types.

For Type I, the $p$-th row of $o(I_m)$ is the $q$-th row of $I_m$ (only the $q$-th entry is $1$), so the $p$-th row of $E_oA$ is the $q$-th row of $A$, the $q$-th row is the $p$-th row of $A$, and the others are unchanged. For Type II, the $p$-th row has $c$ in the $p$-th slot, so the $p$-th row of $E_oA$ is $c$ times the $p$-th row of $A$. For Type III, the $p$-th row has $1$ in the $p$-th slot and $c$ in the $q$-th slot, so the $p$-th row of $E_oA$ is (the $p$-th row of $A$) $+ c \cdot$ (the $q$-th row of $A$). In each case the assertion holds.

2. Every elementary row operation has an inverse of the same type: the inverse of Type I is the same interchange, the inverse of Type II (multiplication by $c$) is multiplication by $c^{-1}$ (possible since $c \ne 0$), and the inverse of Type III (adding $c$ times the $q$-th row) is adding $-c$ times the $q$-th row. Calling this inverse operation $o'$ and putting $E_{o'} = o'(I_m)$, part 1 gives

$$E_{o'}E_o = E_{o'}\,\bigl(E_o I_m\bigr) = o'\bigl(o(I_m)\bigr) = I_m$$

(applying $o$ to $I_m$ and then $o'$ returns it to its original state). Similarly $E_oE_{o'} = I_m$, so $E_o$ is invertible with $E_o^{-1} = E_{o'}$. If two matrices are row equivalent we may write $A' = E_{o_s}\cdots E_{o_1}A$, and a product of invertible matrices is invertible ($(E_{o_s}\cdots E_{o_1})^{-1} = E_{o_1}^{-1}\cdots E_{o_s}^{-1}$), which gives the second statement.

3. It suffices to treat a single elementary row operation (finitely many repetitions follow by induction). By the remark made just after Definition 4.1, that the $j$-th column of a product is the left factor times the $j$-th column of the right factor, we have $E[A \mid \boldsymbol{b}] = [EA \mid E\boldsymbol{b}]$, so $A' = EA$ and $\boldsymbol{b}' = E\boldsymbol{b}$ with $E = E_o$. If $A\boldsymbol{x} = \boldsymbol{b}$, multiplying both sides on the left by $E$ gives $A'\boldsymbol{x} = E A\boldsymbol{x} = E\boldsymbol{b} = \boldsymbol{b}'$. Conversely, if $A'\boldsymbol{x} = \boldsymbol{b}'$, then by the invertibility established in part 2 we may multiply both sides by $E^{-1}$ to get $A\boldsymbol{x} = \boldsymbol{b}$. Hence the solution sets coincide.

∎

Part 3 is exactly the justification of the elimination method. However far we transform, the solution set does not move. Then we may as well transform all the way to a form from which the answer can be read off, which is what the next definition and theorem provide.

Definition 7.3（Row echelon form and reduced row echelon form）

A matrix $R$ is said to be in (row) echelon form if it satisfies the following two conditions.

1. Every nonzero row lies above every zero row.
2. For each nonzero row, the column index of the leftmost nonzero entry (called the leading entry, or pivot, of that row) increases strictly as one moves down the rows.

If in addition the following two conditions hold, $R$ is said to be in reduced row echelon form.

3. Every pivot is equal to $1$.
4. In a column containing a pivot, all entries other than that pivot are $0$.

Theorem 7.4（Gauss–Jordan elimination）

Every $A \in M_{m,n}(K)$ can be brought to reduced row echelon form by finitely many elementary row operations. Moreover, the reduced row echelon form row equivalent to $A$ is unique.

Proof（Theorem 7.4）

We prove existence here by an explicit procedure, Gauss–Jordan elimination. The proof of uniqueness is deferred to the Appendix.

Introduce a variable $r$ recording the working row, starting at $r = 1$. For the columns $j = 1, 2, \ldots, n$ in order, carry out the following.

• If $r > m$, stop.
• If all entries of the $j$-th column from the $r$-th row down are $0$, do nothing and move to the next column.
• Otherwise, choose some $i \ge r$ with $a_{ij} \ne 0$ and interchange the $i$-th and $r$-th rows (Type I). Next multiply the $r$-th row by $a_{rj}^{-1}$ so that the $(r,j)$ entry becomes $1$ (Type II). Then, from every row $i \ne r$, subtract $a_{ij}$ times the $r$-th row (Type III). Now the $j$-th column has $1$ in the $(r,j)$ entry and $0$ elsewhere. Increase $r$ by $1$ and move to the next column.

Each column is processed at most once, so there are at most $n$ stages, each consisting of at most $m+1$ elementary row operations.

Let us check that the output is in reduced row echelon form. Every time a pivot is set, both $r$ and $j$ increase strictly, so the column indices of the pivots increase strictly as one moves down (condition 2). What matters here is that when a pivot is set in the $j$-th column, the entries $1, \ldots, j-1$ of the $r$-th row are all $0$: had any of them been nonzero, a pivot would already have been set when that column was processed. Consequently, adding a multiple of the $r$-th row to another row in Type III does not destroy the part already arranged on the left. At termination the rows carrying pivots are lined up at the top and the rest are zero rows, giving condition 1; the normalisation gives condition 3; and the elimination gives condition 4.

∎

Remark 7.5（Where the uniqueness proof is）

The uniqueness in Theorem 7.4 is proved in the Appendix of this article. However, all that is needed in the next section, where rank is treated, is that the number of pivots is independent of how the elimination is carried out, and this is proved independently in Theorem 8.2 without using uniqueness.

Example 7.6（Elimination in practice）

Let us solve the following linear system.

$$\begin{cases} x_1 + 2x_2 - x_3 + 3x_4 = 1 \\ 2x_1 + 4x_2 - x_3 + 8x_4 = 5 \\ -x_1 - 2x_2 + 2x_3 - x_4 = 2 \end{cases}$$

The augmented matrix is as follows.

$$[A \mid \boldsymbol{b}] = \left(\begin{array}{cccc|c} 1 & 2 & -1 & 3 & 1 \\ 2 & 4 & -1 & 8 & 5 \\ -1 & -2 & 2 & -1 & 2 \end{array}\right)$$

The pivot in the first column is the entry $1$ in position $(1,1)$. Subtract twice the first row from the second row, and add the first row to the third row (Type III twice).

$$\longrightarrow \left(\begin{array}{cccc|c} 1 & 2 & -1 & 3 & 1 \\ 0 & 0 & 1 & 2 & 3 \\ 0 & 0 & 1 & 2 & 3 \end{array}\right)$$

In the second column everything from the second row down is $0$, so we skip it without setting a pivot. Moving to the third column and taking the entry $1$ in position $(2,3)$ as pivot, subtract the second row from the third row and add the second row to the first row.

$$\longrightarrow \left(\begin{array}{cccc|c} 1 & 2 & 0 & 5 & 4 \\ 0 & 0 & 1 & 2 & 3 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right)$$

This is in reduced row echelon form. The pivots lie in the first and third columns, so their number is $2$. The variables $x_1, x_3$ corresponding to the pivot columns are called dependent variables, and the remaining $x_2, x_4$ are called free variables. By part 3 of Lemma 7.2, the system represented by this matrix,

$$\begin{cases} x_1 + 2x_2 + 5x_4 = 4 \\ x_3 + 2x_4 = 3 \end{cases}$$

has the same solution set as the original one. Putting $x_2 = s$ and $x_4 = t$ we get $x_1 = 4 - 2s - 5t$ and $x_3 = 3 - 2t$, so

$$\boldsymbol{x} = \begin{pmatrix} 4 \\ 0 \\ 3 \\ 0\end{pmatrix} + s\begin{pmatrix} -2 \\ 1 \\ 0 \\ 0\end{pmatrix} + t\begin{pmatrix} -5 \\ 0 \\ -2 \\ 1 \end{pmatrix} \qquad (s, t \in \mathbb{R})$$

is the set of all solutions. Let us verify. Substituting $\boldsymbol{x}_0 = (4,0,3,0)^{\mathsf{T}}$ into the three original equations gives $4 - 3 = 1$, $8 - 3 = 5$, $-4 + 6 = 2$. For $\boldsymbol{z}_1 = (-2,1,0,0)^{\mathsf{T}}$ we get $-2+2 = 0$, $-4+4 = 0$, $2-2 = 0$, and for $\boldsymbol{z}_2 = (-5,0,-2,1)^{\mathsf{T}}$ we get $-5+2+3 = 0$, $-10+2+8 = 0$, $5-4-1 = 0$, so both belong to the kernel.

In the language of Proposition 6.1, $\boldsymbol{x}_0$ is a particular solution, $\{s\boldsymbol{z}_1 + t\boldsymbol{z}_2\}$ is the kernel, and the solution set is a two-dimensional affine subspace of $\mathbb{R}^4$. The number $2$ of free variables is the dimension of the kernel, and the number $2$ of pivots is the rank defined in the next section.

8. Rank and the structure of the solution set

In the example of the previous section, the number of pivots was $2$, the number of free variables was $2$, and $2 + 2 = 4 = n$. The goal of this section is to show that this is no accident. We first define the rank in a way that does not refer to any computational procedure.

Definition 8.1（Rank）

For $A \in M_{m,n}(K)$, the rank of $A$ is defined as the dimension of the image,

$$\operatorname{rank} A := \dim \operatorname{Im} A = \dim \operatorname{span}\{\boldsymbol{a}_1, \ldots, \boldsymbol{a}_n\}$$

(where $\boldsymbol{a}_j$ is the $j$-th column of $A$). The subspace of $K^n$ spanned by the $m$ row vectors of $A$ is called the row space and is written $\operatorname{Row}A$.

Why take the dimension of the image, rather than the number of pivots, as the definition? Because it is a definition that refers to no computational procedure, and because its geometric meaning is transparent. The map $f_A$ sends $K^n$ into an $\operatorname{rank}A$-dimensional subspace of $K^m$. The smaller the rank, the more strongly the map crushes space, and $\operatorname{rank}A$ may be read as the dimension of the information that survives passage through $f_A$. In what follows we write $\boldsymbol{\varepsilon}_1, \ldots, \boldsymbol{\varepsilon}_m$ for the standard basis of $K^m$.

Theorem 8.2（Rank equals the number of pivots and equals the row rank）

Let $A \in M_{m,n}(K)$, let $R$ be a reduced row echelon form row equivalent to $A$, and let $r$ be its number of pivots. Then

$$\operatorname{rank} A = r = \dim \operatorname{Row} A .$$

In particular $r$ does not depend on how the elimination is carried out, and the dimension of the span of the columns (the column rank) equals the dimension of the span of the rows (the row rank).

Proof（Theorem 8.2）

By part 2 of Lemma 7.2 there is an invertible matrix $P \in M_m(K)$ with $R = PA$.

Step 1 (the rank of $R$). Let the pivots of $R$ be in positions $(1, j_1), (2, j_2), \ldots, (r, j_r)$ with $j_1 < j_2 < \cdots < j_r$. By conditions 3 and 4 of Definition 7.3, the $j_t$-th column of $R$ is exactly $\boldsymbol{\varepsilon}_t$. Moreover the rows from the $(r+1)$-st down are zero rows, so every column of $R$ has zero entries from the $(r+1)$-st slot down and can be written as a linear combination of $\boldsymbol{\varepsilon}_1, \ldots, \boldsymbol{\varepsilon}_r$. Hence $\operatorname{Im}R = \operatorname{span}\{\boldsymbol{\varepsilon}_1, \ldots, \boldsymbol{\varepsilon}_r\}$, and since $\boldsymbol{\varepsilon}_1,\ldots,\boldsymbol{\varepsilon}_r$ are linearly independent, $\operatorname{rank}R = r$.

Step 2 (multiplying by an invertible matrix does not change the rank). We have $\operatorname{Im}(PA) = \{PA\boldsymbol{x} : \boldsymbol{x} \in K^n\} = P\bigl(\operatorname{Im}A\bigr)$. The map $\boldsymbol{y} \mapsto P\boldsymbol{y}$ is a linear isomorphism with inverse $\boldsymbol{y}\mapsto P^{-1}\boldsymbol{y}$, and isomorphisms preserve dimensions of subspaces. Indeed, if $(\boldsymbol{v}_1, \ldots, \boldsymbol{v}_k)$ is a basis of $\operatorname{Im}A$, then $P\boldsymbol{v}_1, \ldots, P\boldsymbol{v}_k$ span $P(\operatorname{Im}A)$ (because $P(\sum c_t\boldsymbol{v}_t) = \sum c_t P\boldsymbol{v}_t$) and are linearly independent (if $\sum_t c_t P\boldsymbol{v}_t = \boldsymbol{0}$ then $P(\sum_t c_t \boldsymbol{v}_t) = \boldsymbol{0}$, and since $P$ is injective $\sum_t c_t\boldsymbol{v}_t = \boldsymbol{0}$, whence $c_t = 0$ by linear independence of the basis). Therefore $\operatorname{rank}A = \operatorname{rank}(PA) = \operatorname{rank}R = r$. That $r$ does not depend on the elimination follows because $\operatorname{rank}A$ is a quantity determined by $A$ alone.

Step 3 (the row space). By part 1 of Lemma 7.2, each row of $EA$ is a linear combination of the rows of $A$, so $\operatorname{Row}(EA) \subseteq \operatorname{Row}(A)$. Since $E$ is invertible and $A = E^{-1}(EA)$, the same argument applied to $E^{-1}$ gives $\operatorname{Row}(A) \subseteq \operatorname{Row}(EA)$, so equality holds. Repeating this we obtain $\operatorname{Row}A = \operatorname{Row}R$.

Let $\boldsymbol{\rho}_1, \ldots, \boldsymbol{\rho}_r$ be the nonzero rows of $R$. Zero rows contribute nothing to a sum, so these span $\operatorname{Row}R$. We check linear independence. Suppose $\sum_{t=1}^{r} c_t \boldsymbol{\rho}_t = \boldsymbol{0}$ and take the $j_u$-th entry of this identity (for any $u$ between $1$ and $r$). As we saw in Step 1, the $j_u$-th column of $R$ is $\boldsymbol{\varepsilon}_u$, so the $j_u$-th entry of $\boldsymbol{\rho}_t$ is $1$ when $t = u$ and $0$ otherwise. Hence the $j_u$-th entry equals $c_u$, and $c_u = 0$ follows for every $u$. Therefore $\dim\operatorname{Row}A = \dim\operatorname{Row}R = r$.

∎

The equality of row rank and column rank is, on reflection, a surprising assertion. The columns of $A$ are vectors in $K^m$ and its rows are vectors in $K^n$; they live in different spaces. Nevertheless the dimensions of the spaces they span always agree. What connects them is a common intermediary: the number of pivots of the reduced row echelon form.

Theorem 8.3（Rank–nullity theorem）

For $A \in M_{m,n}(K)$,

$$\dim \operatorname{Ker} A + \operatorname{rank} A = n .$$

Proof（Theorem 8.3）

Let $R$ be a reduced row echelon form row equivalent to $A$, let the pivot column indices be $j_1 < \cdots < j_r$, and let $F$ be the set of the remaining column indices (the index set of the free variables), so that $|F| = n - r$. By Theorem 8.2 we have $\operatorname{rank}A = r$, so it suffices to prove $\dim\operatorname{Ker}A = n - r$.

First, $\operatorname{Ker}A = \operatorname{Ker}R$. This follows by applying part 3 of Lemma 7.2 with $\boldsymbol{b} = \boldsymbol{0}$ (elementary row operations leave $\boldsymbol{0}$ as $\boldsymbol{0}$).

Next consider the projection $\pi : K^n \to K^{n-r}$, $\pi(\boldsymbol{x}) = (x_k)_{k \in F}$, which extracts only the components of the free variables, restricted to $\operatorname{Ker}R$. As the restriction of a linear map, $\pi$ is linear. We show that it is an isomorphism.

By conditions 3 and 4 of Definition 7.3, the equation determined by the $t$-th row of $R$ (for $1 \le t \le r$) has the form

$$x_{j_t} + \sum_{k \in F,\; k > j_t} r_{tk}\,x_k = 0$$

(entries to the left of $j_t$ vanish by the echelon condition, and entries in the other pivot columns vanish by condition 4). Rows from the $(r+1)$-st down are zero rows and impose no condition.

Injectivity: if $\boldsymbol{x} \in \operatorname{Ker}R$ satisfies $\pi(\boldsymbol{x}) = \boldsymbol{0}$, that is, all components of the free variables are $0$, then the displayed equation gives $x_{j_t} = 0$ for every $t$, so $\boldsymbol{x} = \boldsymbol{0}$.

Surjectivity: take any $(c_k)_{k\in F} \in K^{n-r}$ and define $\boldsymbol{x}$ by $x_k = c_k$ for $k \in F$ and $x_{j_t} = -\sum_{k \in F, k > j_t} r_{tk}c_k$. Then every row equation of $R$ is satisfied, so $\boldsymbol{x} \in \operatorname{Ker}R$ and $\pi(\boldsymbol{x}) = (c_k)_{k\in F}$.

Hence $\operatorname{Ker}A = \operatorname{Ker}R \cong K^{n-r}$ and $\dim\operatorname{Ker}A = n - r$.

∎

The rank–nullity theorem can be read as “what is crushed plus what survives equals the original dimension” (it is the restatement in matrix language of the rank–nullity theorem（Theorem 7.3）［Vector Spaces and Linear Maps］ for abstract vector spaces). The map $f_A$ crushes a $\dim\operatorname{Ker}A$-dimensional part of $K^n$ to the origin and maps the rest faithfully onto the image. In Example 7.6 we had $n = 4$, $r = 2$ and two free variables, so $2 + 2 = 4$.

Theorem 8.4（Solvability criterion and the number of solutions）

Let $A \in M_{m,n}(K)$ and $\boldsymbol{b} \in K^m$.

1. The system $A\boldsymbol{x} = \boldsymbol{b}$ has a solution if and only if $\operatorname{rank}A = \operatorname{rank}[A \mid \boldsymbol{b}]$. When it has no solution, $\operatorname{rank}[A\mid\boldsymbol{b}] = \operatorname{rank}A + 1$.
2. When a solution exists, the solution set is the affine subspace $\boldsymbol{x}_0 + \operatorname{Ker}A$ of dimension $n - \operatorname{rank}A$. In particular the solution is unique if and only if $\operatorname{rank}A = n$.
3. A solution exists for every $\boldsymbol{b} \in K^m$ if and only if $\operatorname{rank}A = m$.

Proof（Theorem 8.4）

1. By definition, $A\boldsymbol{x} = \boldsymbol{b}$ has a solution if and only if $\boldsymbol{b} \in \operatorname{Im}A$. On the other hand the columns of $[A\mid\boldsymbol{b}]$ are $\boldsymbol{a}_1, \ldots, \boldsymbol{a}_n, \boldsymbol{b}$, so by Definition 8.1 we have $\operatorname{Im}[A\mid\boldsymbol{b}] = \operatorname{span}\{\boldsymbol{a}_1,\ldots,\boldsymbol{a}_n,\boldsymbol{b}\}$, the space spanned by $\operatorname{Im}A$ together with $\boldsymbol{b}$.

If $\boldsymbol{b} \in \operatorname{Im}A$, adjoining $\boldsymbol{b}$ does not enlarge the span, so $\operatorname{Im}[A\mid\boldsymbol{b}] = \operatorname{Im}A$ and the two dimensions are equal.

If $\boldsymbol{b} \notin \operatorname{Im}A$, then adjoining $\boldsymbol{b}$ to a basis $(\boldsymbol{v}_1,\ldots,\boldsymbol{v}_s)$ of $\operatorname{Im}A$ (where $s = \operatorname{rank}A$) yields a linearly independent family. Indeed, if $c\boldsymbol{b} + \sum_t c_t\boldsymbol{v}_t = \boldsymbol{0}$ with $c \ne 0$, then $\boldsymbol{b} = -c^{-1}\sum_t c_t \boldsymbol{v}_t \in \operatorname{Im}A$, contradicting the assumption; hence $c = 0$, and then $c_t = 0$ by linear independence of the basis. These $s+1$ vectors span $\operatorname{Im}[A\mid\boldsymbol{b}]$, so $\operatorname{rank}[A\mid\boldsymbol{b}] = s + 1 = \operatorname{rank}A + 1$.

Thus the case of having a solution and the case of equal ranks correspond exactly.

2. The first statement follows from part 2 of Proposition 6.1 together with Theorem 8.3. Uniqueness of the solution is equivalent to $\operatorname{Ker}A = \{\boldsymbol{0}\}$, that is, $\dim\operatorname{Ker}A = 0$, which by Theorem 8.3 is equivalent to $\operatorname{rank}A = n$.

3. Having a solution for every $\boldsymbol{b}$ is equivalent to $\operatorname{Im}A = K^m$. Since $\operatorname{Im}A \subseteq K^m$, this is equivalent to $\dim\operatorname{Im}A = m$. Indeed, a subspace of equal dimension coincides with the whole space: a basis of $\operatorname{Im}A$ is a linearly independent family of $m$ vectors in $K^m$, and in an $m$-dimensional space such a family is itself a basis.

∎

Let us summarise Theorem 8.4 in a table. In practice the test costs nothing extra: reducing the augmented matrix to reduced row echelon form once lets us read off $\operatorname{rank}A$ and $\operatorname{rank}[A\mid\boldsymbol{b}]$ simultaneously.

Comparison of ranks	Behaviour of the solutions
$\operatorname{rank}A < \operatorname{rank}[A \mid \boldsymbol{b}]$	no solution (inconsistent)
$\operatorname{rank}A = \operatorname{rank}[A \mid \boldsymbol{b}] = n$	exactly one solution
$\operatorname{rank}A = \operatorname{rank}[A \mid \boldsymbol{b}] < n$	the solutions have $n - \operatorname{rank}A$ degrees of freedom

Example 8.5（An inconsistent system）

Keep the coefficient matrix $A$ of Example 7.6 and change only the right-hand side to $\boldsymbol{b}' = (1, 5, 3)^{\mathsf{T}}$. Eliminating by the same steps,

$$\left(\begin{array}{cccc|c} 1 & 2 & -1 & 3 & 1 \\ 2 & 4 & -1 & 8 & 5 \\ -1 & -2 & 2 & -1 & 3 \end{array}\right) \longrightarrow \left(\begin{array}{cccc|c} 1 & 2 & -1 & 3 & 1 \\ 0 & 0 & 1 & 2 & 3 \\ 0 & 0 & 1 & 2 & 4 \end{array}\right) \longrightarrow \left(\begin{array}{cccc|c} 1 & 2 & -1 & 3 & 1 \\ 0 & 0 & 1 & 2 & 3 \\ 0 & 0 & 0 & 0 & 1 \end{array}\right)$$

The last row is the equation $0 = 1$, which no $\boldsymbol{x}$ satisfies. In terms of rank, the $A$ part has two pivots, so $\operatorname{rank}A = 2$, while the augmented matrix has three pivots, in columns 1, 3 and 5, so $\operatorname{rank}[A\mid\boldsymbol{b}'] = 3$. As part 1 of Theorem 8.4 predicts, the ranks disagree and there is no solution.

Geometrically, $\boldsymbol{b}'$ lies off the column space $\operatorname{Im}A$, a two-dimensional plane in $\mathbb{R}^3$. The vector $\boldsymbol{b} = (1,5,2)^{\mathsf{T}}$ lies on this plane, while $\boldsymbol{b}' = (1,5,3)^{\mathsf{T}}$ lies slightly off it. Solvability is decided by nothing more than whether the right-hand side sits on the plane.

Remark 8.6（More unknowns than equations）

If $n > m$, the homogeneous system $A\boldsymbol{x} = \boldsymbol{0}$ always has a nontrivial solution. Indeed $\operatorname{Im}A \subseteq K^m$ gives $\operatorname{rank}A \le m$, so Theorem 8.3 yields

$$\dim\operatorname{Ker}A = n - \operatorname{rank}A \ge n - m > 0,$$

and the kernel is larger than $\{\boldsymbol{0}\}$. The intuition that “more unknowns than equations leaves the solution undetermined” has been stated precisely as an inequality between dimensions.

Remark 8.7（A caution for numerical computation）

In theory any nonzero pivot may be chosen, but in floating-point arithmetic the choice affects the result. For instance, in

$$\begin{pmatrix} 10^{-20} & 1 \\ 1 & 1 \end{pmatrix}\begin{pmatrix} x_1 \\ x_2\end{pmatrix} = \begin{pmatrix} 1 \\ 2 \end{pmatrix}$$

choosing the $(1,1)$ entry as pivot forces us to subtract $10^{20}$ times the first row from the second, and as soon as $1 - 10^{20}$ and $2 - 10^{20}$ are evaluated in double precision the low-order information is lost and the answer goes badly wrong. Interchanging rows so as to take the entry of largest absolute value as pivot (partial pivoting) avoids this. Practical implementations use LU decomposition with this safeguard built in; for a square matrix of size $n$ the operation count is roughly $\frac{2}{3}n^3$ multiplications and divisions (Golub–Van Loan).

Remark 8.8（Connections with data science）

In the analysis of real data, overdetermined systems with more equations than unknowns ($m > n$) are the rule. There is no guarantee that $\boldsymbol{b}$ lies in the column space, so in the sense of Theorem 8.4 such a system usually has “no solution”. One therefore looks for the $\boldsymbol{x}$ minimising the residual $\lVert A\boldsymbol{x} - \boldsymbol{b}\rVert$, which is the method of least squares; it amounts to orthogonally projecting $\boldsymbol{b}$ onto the column space. Since lengths and orthogonality are needed, the stage shifts to Inner Product Spaces and Gram–Schmidt Orthogonalisation (least squares: fitting a line（Example 7.5）［内積空間とグラム・シュミット直交化］).

For a data matrix $X \in M_{N,d}(\mathbb{R})$ whose rows are $N$ samples and from which the mean of each feature has been subtracted, $\operatorname{rank}X$ is the dimension of the effective spread of the data. Principal component analysis is the procedure of choosing an orthonormal basis diagonalising the covariance matrix $\frac{1}{N}X^{\mathsf{T}}X$, so the slogan of Example 5.4, “in a basis fitted to the map the matrix becomes diagonal”, appears directly as an application. The supporting theory is in Eigenvalues and Eigenvectors and The Spectral Theorem (that a symmetric matrix can be diagonalised in an orthonormal basis is guaranteed by orthogonal diagonalisation of real symmetric matrices（Corollary 4.3）［スペクトル定理］), and the tool for deciding invertibility by a single number is in the next chapter, Determinants and Their Properties, in the criterion for invertibility（Theorem 7.1）［Determinants and Their Properties］.

9. Exercises

Exercise 9.1Easy

Let $P_2$ be the space of real polynomials of degree at most $2$ with basis $\mathcal{B} = (1, x, x^2)$, and define a linear map $T : P_2 \to P_2$ by $(Tp)(x) = p(x+1)$.

1. Find the representation matrix $A = M_{\mathcal{B}\mathcal{B}}(T)$ of $T$ with respect to $\mathcal{B}$.
2. Compute $A^2$ and verify that it is the representation matrix of $(T^2 p)(x) = p(x+2)$.

Solution

1. Following Definition 3.1, expand the destinations of the basis vectors in $\mathcal{B}$:

$$T(1) = 1, \qquad T(x) = x + 1 = 1 + x, \qquad T(x^2) = (x+1)^2 = 1 + 2x + x^2 .$$

Placing the coefficients in the columns,

$$A = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{pmatrix}.$$

2. Compute according to Definition 4.1. The first row is $(1,1,1)$ against each column, giving $(1,\; 1+1,\; 1+2+1) = (1,2,4)$; the second row is $(0,1,2)$ against each column, giving $(0,\; 1,\; 2 + 2) = (0,1,4)$; the third row is $(0,0,1)$ against each column, giving $(0,0,1)$. Hence

$$A^2 = \begin{pmatrix} 1 & 2 & 4 \\ 0 & 1 & 4 \\ 0 & 0 & 1\end{pmatrix}.$$

On the other hand $T^2 = T \circ T$ satisfies $(T^2p)(x) = (Tp)(x+1) = p(x+2)$, so the basis vectors go to $1 \mapsto 1$, $x \mapsto x + 2$, $x^2 \mapsto (x+2)^2 = 4 + 4x + x^2$. Placing these in the columns reproduces the matrix $A^2$ above, exactly as Theorem 4.2 asserts.

Exercise 9.2Standard

A linear transformation $f$ of $\mathbb{R}^2$ satisfies

$$f\begin{pmatrix} 1 \\ 1\end{pmatrix} = \begin{pmatrix} 3 \\ 1 \end{pmatrix}, \qquad f\begin{pmatrix} 1 \\ -1\end{pmatrix} = \begin{pmatrix} 1 \\ 3 \end{pmatrix}.$$

Put $\boldsymbol{p}_1 = (1,1)^{\mathsf{T}}$, $\boldsymbol{p}_2 = (1,-1)^{\mathsf{T}}$, $\mathcal{B}' = (\boldsymbol{p}_1, \boldsymbol{p}_2)$, and let $\mathcal{E}$ be the standard basis.

1. Find $A' = M_{\mathcal{B}'\mathcal{B}'}(f)$.
2. Find $A = M_{\mathcal{E}\mathcal{E}}(f)$ and verify that $A' = P^{-1}AP$, where $P$ is the change-of-basis matrix from $\mathcal{B}'$ to $\mathcal{E}$.

Solution

Since $\boldsymbol{p}_1, \boldsymbol{p}_2$ are linearly independent (neither is a scalar multiple of the other), $\mathcal{B}'$ is a basis, and by part 2 of Proposition 2.1 the two given conditions determine $f$ uniquely.

1. Expand the destinations in $\mathcal{B}'$. Writing $(3,1)^{\mathsf{T}} = a\boldsymbol{p}_1 + b\boldsymbol{p}_2$ gives $a + b = 3$ and $a - b = 1$, so $a = 2$, $b = 1$. Writing $(1,3)^{\mathsf{T}} = a\boldsymbol{p}_1 + b\boldsymbol{p}_2$ gives $a+b = 1$ and $a - b = 3$, so $a = 2$, $b = -1$. Hence

$$A' = \begin{pmatrix} 2 & 2 \\ 1 & -1 \end{pmatrix}.$$

2. Since $\boldsymbol{e}_1 = \frac{1}{2}(\boldsymbol{p}_1 + \boldsymbol{p}_2)$ and $\boldsymbol{e}_2 = \frac{1}{2}(\boldsymbol{p}_1 - \boldsymbol{p}_2)$, linearity gives

$$f(\boldsymbol{e}_1) = \tfrac{1}{2}\bigl((3,1)^{\mathsf{T}} + (1,3)^{\mathsf{T}}\bigr) = (2,2)^{\mathsf{T}}, \qquad f(\boldsymbol{e}_2) = \tfrac{1}{2}\bigl((3,1)^{\mathsf{T}} - (1,3)^{\mathsf{T}}\bigr) = (1,-1)^{\mathsf{T}} .$$

Hence $A = \begin{pmatrix} 2 & 1 \\ 2 & -1\end{pmatrix}$.

The change-of-basis matrix has the standard coordinates of $\boldsymbol{p}_1, \boldsymbol{p}_2$ as its columns, $P = \begin{pmatrix} 1 & 1 \\ 1 & -1\end{pmatrix}$, and $P^2 = 2I_2$ gives $P^{-1} = \frac{1}{2}P$. Computing explicitly,

$$AP = \begin{pmatrix} 2 & 1 \\ 2 & -1\end{pmatrix}\begin{pmatrix} 1 & 1 \\ 1 & -1\end{pmatrix} = \begin{pmatrix} 3 & 1 \\ 1 & 3\end{pmatrix}, \qquad P^{-1}(AP) = \frac{1}{2}\begin{pmatrix} 1 & 1 \\ 1 & -1\end{pmatrix}\begin{pmatrix} 3 & 1 \\ 1 & 3\end{pmatrix} = \frac{1}{2}\begin{pmatrix} 4 & 4 \\ 2 & -2\end{pmatrix} = \begin{pmatrix} 2 & 2 \\ 1 & -1\end{pmatrix}$$

which agrees with the $A'$ found in part 1. This confirms Theorem 5.2.

Exercise 9.3Standard

Consider the linear system with real constants $a, c$,

$$\begin{cases} x + y + z = 1 \\ x + 2y + 3z = 2 \\ x + 3y + az = c . \end{cases}$$

Determine the ranks of the coefficient matrix $A$ and of the augmented matrix, distinguishing cases according to $a$ and $c$, and classify the number of solutions. Where solutions exist, write them explicitly.

Solution

Apply elementary row operations to the augmented matrix: subtract the first row from the second, and the first row from the third.

$$\left(\begin{array}{ccc|c} 1&1&1&1 \\ 1&2&3&2 \\ 1&3&a&c\end{array}\right) \longrightarrow \left(\begin{array}{ccc|c} 1&1&1&1 \\ 0&1&2&1 \\ 0&2&a-1&c-1\end{array}\right) \longrightarrow \left(\begin{array}{ccc|c} 1&1&1&1 \\ 0&1&2&1 \\ 0&0&a-5&c-3\end{array}\right)$$

In the last step twice the second row was subtracted from the third. By part 3 of Lemma 7.2, the solution set has not changed.

(i) $a \ne 5$. A pivot appears at position $(3,3)$, so $\operatorname{rank}A = \operatorname{rank}[A\mid\boldsymbol{b}] = 3 = n$, and by part 2 of Theorem 8.4 there is exactly one solution. Solving from the bottom up, $z = \dfrac{c-3}{a-5}$, $y = 1 - 2z$, and $x = 1 - y - z = z$, so

$$(x, y, z) = \left(\frac{c-3}{a-5},\; 1 - \frac{2(c-3)}{a-5},\; \frac{c-3}{a-5}\right).$$

For instance $a = 6, c = 4$ gives $(1, -1, 1)$, and indeed $1 - 1 + 1 = 1$, $1 - 2 + 3 = 2$, $1 - 3 + 6 = 4$, so all three equations hold.

(ii) $a = 5$ and $c \ne 3$. The third row is $(0, 0, 0 \mid c - 3)$ with $c - 3 \ne 0$, so $\operatorname{rank}A = 2$ and $\operatorname{rank}[A\mid\boldsymbol{b}] = 3$. By part 1 of Theorem 8.4 there is no solution.

(iii) $a = 5$ and $c = 3$. The third row is a zero row, so $\operatorname{rank}A = \operatorname{rank}[A\mid\boldsymbol{b}] = 2 < 3 = n$ and the solutions have $3 - 2 = 1$ degree of freedom. Taking $z = t$ as the free variable, $y = 1 - 2t$ and $x = 1 - y - z = t$, so

$$(x,y,z) = (0,1,0) + t\,(1,-2,1) \qquad (t \in \mathbb{R}).$$

Checking in the third equation, $x + 3y + 5z = t + 3 - 6t + 5t = 3 = c$, as required. Here $(0,1,0)$ is a particular solution and $\operatorname{span}\{(1,-2,1)^{\mathsf{T}}\}$ is the kernel, exactly the shape given by Proposition 6.1.

Exercise 9.4Hard

Let $A \in M_{m,n}(K)$ and $B \in M_{n,p}(K)$. Prove

$$\operatorname{rank}(AB) \le \min\{\operatorname{rank}A,\; \operatorname{rank}B\},$$

and give an example in which equality fails.

Solution

$\operatorname{rank}(AB) \le \operatorname{rank}A$. For any $\boldsymbol{x} \in K^p$ we have $(AB)\boldsymbol{x} = A(B\boldsymbol{x})$ (by the associativity of Corollary 4.3, or from the definition of the product with $B\boldsymbol{x}$ regarded as a one-column matrix). Hence $\operatorname{Im}(AB) \subseteq \operatorname{Im}A$, and an inclusion of subspaces gives an inequality of dimensions, so $\operatorname{rank}(AB) \le \operatorname{rank}A$.

$\operatorname{rank}(AB) \le \operatorname{rank}B$. If $B\boldsymbol{x} = \boldsymbol{0}$ then $(AB)\boldsymbol{x} = A\boldsymbol{0} = \boldsymbol{0}$, so $\operatorname{Ker}B \subseteq \operatorname{Ker}(AB)$ and therefore $\dim\operatorname{Ker}B \le \dim\operatorname{Ker}(AB)$. Both $AB \in M_{m,p}(K)$ and $B \in M_{n,p}(K)$ have $p$ columns, so applying Theorem 8.3 to each gives

$$\operatorname{rank}(AB) = p - \dim\operatorname{Ker}(AB) \le p - \dim\operatorname{Ker}B = \operatorname{rank}B .$$

An example where equality fails. Take $A = \begin{pmatrix} 0 & 1 \\ 0 & 0\end{pmatrix}$ and $B = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$. Then $\operatorname{rank}A = \operatorname{rank}B = 1$ (both column spaces are $\operatorname{span}\{(1,0)^{\mathsf{T}}\}$), but $AB = O$, so $\operatorname{rank}(AB) = 0$. The image of $B$ is contained in the kernel of $A$, so everything is crushed at the second stage.

References

• M. Saito, Senkei Daisu Nyumon (Introduction to Linear Algebra), University of Tokyo Press, 1966 (in Japanese) — Chapters 1 and 2. A careful treatment of linear systems and elementary matrix operations in the standard Japanese style.
• I. Satake, Senkei Daisugaku (Linear Algebra), Shokabo, 1958 (reissued 2015) (in Japanese) — Chapters I and II. The standpoint of treating matrices as representations of linear maps is made explicit.
• S. Axler, Linear Algebra Done Right, 4th ed., Springer, 2024 — Chapter 3 (Linear Maps). Built up from linear maps without using determinants, which makes the roles of representation matrices and of the rank–nullity theorem especially clear. An open-access edition is available at linear.axler.net.
• G. Strang, Introduction to Linear Algebra, 5th ed., Wellesley-Cambridge Press, 2016 — Chapters 2 and 3. Rich in the “read it by columns” viewpoint and in the discussion of the four fundamental subspaces. The lectures are available at MIT OpenCourseWare 18.06.
• G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, 2013 — Chapter 3 (General Linear Systems). Pivoting strategies, numerical stability and operation counts are discussed here in detail.
• A. Cayley, “A Memoir on the Theory of Matrices”, Philosophical Transactions of the Royal Society of London 148 (1858), 17–37. The original paper defining the matrix product as the composition of linear substitutions.

Appendix: Uniqueness of the reduced row echelon form

We now prove the part of Theorem 7.4 left open, namely uniqueness. The claim is that the reduced row echelon form row equivalent to $A \in M_{m,n}(K)$ is unique. There is freedom in which rows are chosen during the elimination and in what order the columns are cleared, but the final form is determined by $A$ alone.

Strategy. Let $R$ and $R'$ both be reduced row echelon forms row equivalent to $A$. By part 3 of Lemma 7.2 (with $\boldsymbol{b} = \boldsymbol{0}$) we have $\operatorname{Ker}R = \operatorname{Ker}A = \operatorname{Ker}R'$. So it suffices to show that a matrix in reduced row echelon form can be reconstructed from its kernel alone, and then $R = R'$ follows. Below we write $N = \operatorname{Ker}R$, let $j_1 < \cdots < j_r$ be the pivot columns of $R$, and let $F$ be the index set of the free variables.

Step 1: the positions of the pivot columns are determined by the kernel. The $j$-th column fails to be a pivot column if and only if there exists $\boldsymbol{z} \in N$ with $z_j = 1$ whose entries from the $(j+1)$-st on are all $0$.

Indeed, if $j \in F$, then the vector $\boldsymbol{z} \in N$ obtained by the surjectivity construction in the proof of Theorem 8.3, prescribing $x_j = 1$ and $0$ for all other free variables, satisfies this condition. The entries to the right of $j$ vanish: those belonging to free variables are prescribed to be $0$, and for a pivot variable $x_{j_t}$ with $j_t > j$ the row equation $x_{j_t} + \sum_{k \in F,\, k > j_t} r_{tk}x_k = 0$ has all the free variables on its right-hand side equal to $0$, so $x_{j_t} = 0$. Conversely, suppose such a $\boldsymbol{z}$ exists and the $j$-th column were a pivot column, with its pivot in the $t$-th row. The $t$-th row of $R\boldsymbol{z} = \boldsymbol{0}$ reads $z_j + \sum_{k > j} r_{tk}z_k = 0$, but $z_j = 1$ and $z_k = 0$ for $k > j$, giving $1 = 0$, a contradiction. This condition is stated purely in terms of $N$, so if $\operatorname{Ker}R = \operatorname{Ker}R'$ the positions of the pivot columns agree completely.

Step 2: the entries too are determined by the kernel. Suppose the pivot columns agree. By conditions 3 and 4 of Definition 7.3, the $j_t$-th column of $R$ is $\boldsymbol{\varepsilon}_t$, and the same holds for $R'$. What remains are the columns of the free variables.

Let $j \in F$ and let $\boldsymbol{z} \in N$ satisfy ”$z_j = 1$ and all other free-variable entries are $0$”. Such a $\boldsymbol{z}$ is unique in $N$: if there were two, their difference would lie in $N$ with all free-variable entries $0$, and the injectivity part of the proof of Theorem 8.3 forces the difference to be $\boldsymbol{0}$. Thus $\boldsymbol{z}$ is determined by $N$ and $j$ alone. On the other hand, the $t$-th row of $R\boldsymbol{z} = \boldsymbol{0}$ reads $z_{j_t} + r_{tj}z_j = 0$, since the other free-variable entries are $0$ and the entries in the other pivot columns are $0$ by condition 4; that is, $r_{tj} = -z_{j_t}$. From the $(r+1)$-st entry on everything is $0$, the rows being zero rows. The same equations hold for $R'$ and $\boldsymbol{z}$ is common to both, so the $j$-th columns agree.

Both the pivot columns and the free-variable columns therefore agree, and $R = R'$ is proved. Because of this uniqueness, the reduced row echelon form is meaningful as a canonical form for matrices: two matrices are row equivalent if and only if their reduced row echelon forms coincide. Note that a non-reduced echelon form is not unique (multiplying the second row by $2$ keeps it in echelon form); uniqueness requires the normalisations in conditions 3 and 4.