# Vector Spaces and Linear Maps: From the Eight Axioms to the Rank-Nullity Theorem > Starting from the eight axioms, we build subspaces, bases and dimension, prove the exchange lemma and the rank-nullity theorem, and test them on projections, differentiation and PCA. > https://rikai.mugen-giken.com/en/mathematics/linear-algebra/vector-spaces ## 0. Key points - A vector is not "an arrow with a direction and a length". A vector is an element of a set on which **an addition and a scalar multiplication are defined and satisfy eight axioms**. Thanks to this abstraction, tuples of numbers, matrices, polynomials, functions and sequences are all covered by one and the same theorem. - A subspace is a subset that "contains the origin and never escapes under addition and scalar multiplication". There is no need to recheck the eight axioms: three conditions suffice. - A basis is a family that spans the space "with nothing missing and nothing redundant", and choosing a basis is the same as installing coordinates. The number of vectors in a basis does not depend on which basis we choose, and that number is the dimension. The heart of this uniqueness is the exchange lemma. - A linear map is a map that preserves addition and scalar multiplication. Rotations, projections, dilations and differentiation are all linear maps, and a matrix is nothing but a coordinate representation of one. - The rank-nullity theorem $\dim V = \dim \operatorname{Ker} f + \dim \operatorname{Im} f$ is a conservation law: the image thins out by exactly as much as was collapsed. The number of degrees of freedom in the solutions of a system of linear equations, and the amount of information discarded by principal component analysis, are both explained by this single identity. ## 1. Motivation: what comes into view once we drop the arrows Up to high school, a vector was "an arrow with a direction and a length". That definition works perfectly well in the plane and in space, but a little further on it runs into three questions. First, what is the $n$ in "$n$-dimensional"? Nobody has ever seen a four-dimensional arrow. Yet we speak of four-dimensional and hundred-dimensional spaces. Unless "dimension" can be defined without reference to pictures of arrows, such talk is empty. Second, the collection of polynomials $a_0 + a_1 x + a_2 x^2$, or the collection of continuous functions on the interval $[0,1]$, are plainly not arrows. Nevertheless they can be added, they can be multiplied by constants, and they obey exactly the same computational rules as vectors in the plane. Why? Is it a coincidence? Third, the number of degrees of freedom of the solutions of a system of linear equations is often explained as "the number of unknowns minus the number of independent equations". Where does that subtraction come from? These questions have a common answer: **what matters is not what the objects are made of, but only the structure of how they are added to one another and how they are multiplied by constants**. So we forget entirely about arrows and take as our starting point "a set equipped with an addition and a scalar multiplication satisfying a few rules". The first person to write this down clearly was Giuseppe Peano, who in his 1888 book reorganised Grassmann's theory of extension and gave axioms almost identical to the modern ones. Peano even listed function spaces among his examples, but this formulation came into wide use only after Weyl and Banach began to employ linear spaces as a tool in the twentieth century. The abstraction pays off in a very concrete way. Once a theorem is proved from the axioms alone, it may be used free of charge for every object satisfying those axioms. The labour of proving something in $\mathbb{R}^3$, then reproving it for polynomials, then reproving it for functions, disappears. Indeed, the rank-nullity theorem proved in this article applies verbatim to projections in the plane, to differentiation of polynomials, and to dimension reduction in machine learning. If you are unsure about how proofs are written (contradiction, contraposition, induction) or about the handling of "for all" and "there exists", read [The grammar of mathematics: sets and logic](/en/mathematics/foundations/sets-and-logic) (in particular ) and [Techniques of proof: induction and contradiction](/en/mathematics/foundations/proof-techniques) (in particular ) first. This article is a consumer of those tools.
B["Subspaces"] A --> C["Linear combinations and spans"] C --> D["Linear independence"] C --> E["Spanning sets"] D --> F["Bases"] E --> F F --> G["Exchange lemma"] G --> H["Dimension is independent of the basis"] A --> I["Linear maps"] I --> J["Kernel Ker f and image Im f"] H --> K["Rank-nullity: dim V = dim Ker f + dim Im f"] J --> K K --> L["Degrees of freedom of linear systems / compression rate of PCA"]`} />
## 2. Preliminaries: the set of scalars and the language of maps When we multiply a vector by a "constant", where does that constant come from? It need not be a real number. With complex coefficients we get a complex vector space; with the field of just $0$ and $1$ we get the vector spaces of coding theory. So we fix the set of coefficients first. A set $K$ equipped with an addition and a multiplication is called a **field** when the following hold. Addition is associative and commutative, there is a zero element $0$, and every element has an additive inverse. Multiplication is associative and commutative, there is an identity $1 \ne 0$, and every element $a \ne 0$ has a multiplicative inverse $a^{-1}$. Finally the distributive law $a(b+c) = ab+ac$ holds. In short, a field is a set in which the four arithmetic operations may be performed freely. The sets $\mathbb{Q}$, $\mathbb{R}$ and $\mathbb{C}$ are fields, whereas $\mathbb{Z}$ is not, since it lacks the reciprocal of $2$. In this article $K$ may be any field; if in doubt, read $K = \mathbb{R}$. Elements of the field are called **scalars**. Let us also fix the vocabulary for maps. A map $f : X \to Y$ is **injective** if $f(x_1) = f(x_2)$ implies $x_1 = x_2$, and **surjective** if for every $y \in Y$ there is an $x \in X$ with $f(x) = y$. A map that is both is called **bijective**. Reading "injective" as "loses no information" and "surjective" as "leaves no part of the target uncovered" makes the correspondence with the later discussion clear. Notation is as follows. Vectors are $\boldsymbol{u}, \boldsymbol{v}, \boldsymbol{w}$, scalars are $a, b, c$, and $\mathbb{N} = \{1, 2, \ldots\}$ does not contain $0$. A sum of $n$ terms is written $\sum_{i=1}^{n} a_i \boldsymbol{v}_i$. ## 3. The axioms of a vector space ### 3.1. The definition Let $K$ be a field. Suppose a set $V$ is equipped with two maps $$ + \colon V \times V \to V, \qquad \cdot \colon K \times V \to V $$ satisfying the following eight conditions. Then $V$ is called a **vector space over $K$** (a linear space), and the elements of $V$ are called **vectors**. Below, $\boldsymbol{u}, \boldsymbol{v}, \boldsymbol{w}$ denote arbitrary elements of $V$, $a, b$ arbitrary elements of $K$, and $a \cdot \boldsymbol{v}$ is abbreviated to $a\boldsymbol{v}$. - **(V1) Associativity of addition**: $(\boldsymbol{u} + \boldsymbol{v}) + \boldsymbol{w} = \boldsymbol{u} + (\boldsymbol{v} + \boldsymbol{w})$ - **(V2) Commutativity of addition**: $\boldsymbol{u} + \boldsymbol{v} = \boldsymbol{v} + \boldsymbol{u}$ - **(V3) Existence of a zero vector**: there is a $\boldsymbol{0} \in V$ such that $\boldsymbol{v} + \boldsymbol{0} = \boldsymbol{v}$ for every $\boldsymbol{v} \in V$ - **(V4) Existence of additive inverses**: for each $\boldsymbol{v} \in V$ there is a $\boldsymbol{v}' \in V$ with $\boldsymbol{v} + \boldsymbol{v}' = \boldsymbol{0}$ - **(V5) Distributivity over vector sums**: $a(\boldsymbol{u} + \boldsymbol{v}) = a\boldsymbol{u} + a\boldsymbol{v}$ - **(V6) Distributivity over scalar sums**: $(a + b)\boldsymbol{v} = a\boldsymbol{v} + b\boldsymbol{v}$ - **(V7) Associativity of scalar multiplication**: $(ab)\boldsymbol{v} = a(b\boldsymbol{v})$ - **(V8) Action of the identity**: $1\boldsymbol{v} = \boldsymbol{v}$ (here $1$ is the multiplicative identity of $K$) Two points are easy to overlook. The first is that **closure is built into the definition**. By writing addition as "a map from $V \times V$ to $V$" we have already demanded that $\boldsymbol{u} + \boldsymbol{v}$ be an element of $V$; the same goes for scalar multiplication. When checking whether a set satisfies the axioms, closure is the first thing to verify. The second is that **(V1)–(V4) merely say that $V$ is an abelian group under addition**; what makes the subject linear algebra is the scalar multiplication in (V5)–(V8). In particular (V8) is often felt to be too obvious to be worth stating, but as we shall see it does not follow from the other seven. The additive inverse of $\boldsymbol{v}$ is unique, as we verify next, so we write it $-\boldsymbol{v}$ and set $\boldsymbol{u} - \boldsymbol{v} := \boldsymbol{u} + (-\boldsymbol{v})$. ### 3.2. Elementary consequences of the axioms The axioms say nothing about "obvious facts" such as $0\boldsymbol{v} = \boldsymbol{0}$. Since they are not stated, they must be proved. The proofs below are also good practice in tracking which axiom is used where. Let $V$ be a vector space over a field $K$, let $\boldsymbol{v} \in V$ and $a \in K$. Then the following hold. 1. The vector $\boldsymbol{0}$ of (V3) is unique. 2. The additive inverse of each $\boldsymbol{v}$ is unique. 3. $0\boldsymbol{v} = \boldsymbol{0}$ (the $0$ on the left is the zero of $K$, the right-hand side is the zero vector of $V$). 4. $a\boldsymbol{0} = \boldsymbol{0}$. 5. $(-1)\boldsymbol{v} = -\boldsymbol{v}$. 6. If $a\boldsymbol{v} = \boldsymbol{0}$ then $a = 0$ or $\boldsymbol{v} = \boldsymbol{0}$. **(1)** Suppose $\boldsymbol{0}$ and $\boldsymbol{0}'$ both satisfy (V3). Applying the property of $\boldsymbol{0}'$ to $\boldsymbol{v} = \boldsymbol{0}$ gives $\boldsymbol{0} + \boldsymbol{0}' = \boldsymbol{0}$, and applying the property of $\boldsymbol{0}$ to $\boldsymbol{v} = \boldsymbol{0}'$ gives $\boldsymbol{0}' + \boldsymbol{0} = \boldsymbol{0}'$. By (V2) the two left-hand sides agree, so $\boldsymbol{0} = \boldsymbol{0}'$. **(2)** Suppose $\boldsymbol{v} + \boldsymbol{v}' = \boldsymbol{0}$ and $\boldsymbol{v} + \boldsymbol{v}'' = \boldsymbol{0}$. Then $$ \boldsymbol{v}' = \boldsymbol{v}' + \boldsymbol{0} = \boldsymbol{v}' + (\boldsymbol{v} + \boldsymbol{v}'') = (\boldsymbol{v}' + \boldsymbol{v}) + \boldsymbol{v}'' = (\boldsymbol{v} + \boldsymbol{v}') + \boldsymbol{v}'' = \boldsymbol{0} + \boldsymbol{v}'' = \boldsymbol{v}'' + \boldsymbol{0} = \boldsymbol{v}'' $$ where we used, in order, (V3), the hypothesis, (V1), (V2), the hypothesis, (V2) and (V3). **(3)** Since $0 + 0 = 0$ in $K$, axiom (V6) gives $$ 0\boldsymbol{v} + 0\boldsymbol{v} = (0 + 0)\boldsymbol{v} = 0\boldsymbol{v}. $$ Add the additive inverse of $0\boldsymbol{v}$ (which exists by (V4)) to both sides. By (V1), (V4) and (V3) the left-hand side becomes $0\boldsymbol{v} + (0\boldsymbol{v} + (-(0\boldsymbol{v}))) = 0\boldsymbol{v} + \boldsymbol{0} = 0\boldsymbol{v}$, while by (V4) the right-hand side becomes $\boldsymbol{0}$. Hence $0\boldsymbol{v} = \boldsymbol{0}$. **(4)** By (V3) we have $\boldsymbol{0} + \boldsymbol{0} = \boldsymbol{0}$, so (V5) gives $a\boldsymbol{0} + a\boldsymbol{0} = a(\boldsymbol{0} + \boldsymbol{0}) = a\boldsymbol{0}$. Cancelling as in (3) yields $a\boldsymbol{0} = \boldsymbol{0}$. **(5)** By (V8), (V6) and (3), $$ \boldsymbol{v} + (-1)\boldsymbol{v} = 1\boldsymbol{v} + (-1)\boldsymbol{v} = (1 + (-1))\boldsymbol{v} = 0\boldsymbol{v} = \boldsymbol{0}. $$ Hence $(-1)\boldsymbol{v}$ is an additive inverse of $\boldsymbol{v}$, and by the uniqueness in (2) we get $(-1)\boldsymbol{v} = -\boldsymbol{v}$. Note that (V8) was used here. **(6)** Suppose $a \ne 0$. Since $K$ is a field, $a^{-1}$ exists and $$ \boldsymbol{v} = 1\boldsymbol{v} = (a^{-1}a)\boldsymbol{v} = a^{-1}(a\boldsymbol{v}) = a^{-1}\boldsymbol{0} = \boldsymbol{0}, $$ using in order (V8), arithmetic in $K$, (V7), the hypothesis and (4). So $a \ne 0$ forces $\boldsymbol{v} = \boldsymbol{0}$, which is the assertion. ### 3.3. Examples and counterexamples Equip $K^n = \{(x_1, \ldots, x_n) \mid x_i \in K\}$ with the componentwise operations $$ (x_1, \ldots, x_n) + (y_1, \ldots, y_n) := (x_1 + y_1, \ldots, x_n + y_n), \qquad a(x_1, \ldots, x_n) := (ax_1, \ldots, ax_n). $$ All eight conditions follow componentwise from the arithmetic of $K$. For instance, comparing $i$-th components, (V6) is exactly the distributive law $(a+b)x_i = ax_i + bx_i$ in $K$. The zero vector is $\boldsymbol{0} = (0, \ldots, 0)$ and the inverse of $(x_1,\ldots,x_n)$ is $(-x_1, \ldots, -x_n)$. The cases $n = 2, 3$ with $K = \mathbb{R}$ correspond to the arrows of high school. The "sum" of arrows was the diagonal of a parallelogram, and written in components this agrees with the definition above. Let $X$ be a non-empty set and let $K^X$ be the set of all maps from $X$ to $K$. For $f, g \in K^X$ and $a \in K$ set $$ (f + g)(x) := f(x) + g(x), \qquad (af)(x) := a \cdot f(x) \quad (x \in X). $$ The zero vector is the function identically equal to $0$, and the inverse of $f$ is $x \mapsto -f(x)$. All eight conditions reduce, at each point $x$, to the arithmetic laws of $K$. For example (V1) holds because $((f+g)+h)(x) = (f(x)+g(x))+h(x) = f(x)+(g(x)+h(x)) = (f+(g+h))(x)$ for every $x$, so the two maps agree at every point and hence are equal. This single example contains many spaces at once. | Choice of $X$ | Resulting space | |---|---| | $X = \{1, 2, \ldots, n\}$ | the coordinate space $K^n$ (read $f$ as $(f(1), \ldots, f(n))$) | | $X = \mathbb{N}$ | the space $K^{\mathbb{N}}$ of all sequences | | $X = \{1,\ldots,m\} \times \{1,\ldots,n\}$ | the space $M_{m,n}(K)$ of all $m \times n$ matrices | | $X = [0,1]$, $K = \mathbb{R}$ | all real-valued functions on the interval | The reason matrix addition and scalar multiplication are componentwise is that a matrix is a function of a pair of indices. **(a) The first quadrant is not a space.** The set $W = \{(x,y) \in \mathbb{R}^2 \mid x \ge 0,\ y \ge 0\}$ is closed under addition. However, $(1,1) \in W$ while $(-1)(1,1) = (-1,-1) \notin W$, so scalar multiplication is not a map into $W$. Additive inverses are missing as well, so (V4) fails too. "Directions can be freely reversed" is a demand of the axioms. **(b) (V8) does not follow from the other seven.** On $V = \mathbb{R}^2$ keep the usual addition but redefine scalar multiplication by $$ a \odot (x, y) := (ax, 0). $$ Since the addition is the ordinary one, (V1)–(V4) hold. Let us check the rest. $$ \begin{aligned} a \odot ((x_1,y_1) + (x_2,y_2)) &= (a(x_1+x_2),\, 0) = (ax_1, 0) + (ax_2, 0) = a \odot (x_1,y_1) + a \odot (x_2,y_2), \\ (a+b) \odot (x,y) &= ((a+b)x,\, 0) = (ax, 0) + (bx, 0) = a \odot (x,y) + b \odot (x,y), \\ (ab) \odot (x,y) &= (abx,\, 0), \qquad a \odot (b \odot (x,y)) = a \odot (bx, 0) = (abx, 0). \end{aligned} $$ So (V5), (V6) and (V7) hold. But $1 \odot (0,1) = (0,0) \ne (0,1)$, so (V8) alone fails. In this $V$, part (5) of fails as well: indeed $(-1) \odot (0,1) = (0,0)$, whereas the additive inverse of $(0,1)$ is $(0,-1)$. Dropping (V8) destroys the compatibility between scalar multiplication and additive inverses. ## 4. Subspaces and spans Verifying all eight conditions every time we build a new space would be tedious. Fortunately, when we investigate the inside of a space already known to be a vector space, far less needs to be checked. Let $V$ be a vector space over $K$. A subset $W \subseteq V$ is called a **subspace** of $V$ if it becomes a vector space over $K$ under the addition and scalar multiplication of $V$ restricted to $W$. Let $V$ be a vector space over $K$ and let $W \subseteq V$. Then $W$ is a subspace of $V$ if and only if all three of the following hold. 1. $\boldsymbol{0} \in W$ (in particular $W \ne \emptyset$). 2. $\boldsymbol{u} + \boldsymbol{v} \in W$ for all $\boldsymbol{u}, \boldsymbol{v} \in W$. 3. $a\boldsymbol{v} \in W$ for all $a \in K$ and $\boldsymbol{v} \in W$. **Necessity.** If $W$ is a subspace, then addition and scalar multiplication are defined inside $W$, so conditions 2 and 3 hold. Also $W$ is non-empty (it has a zero vector), and picking any $\boldsymbol{v} \in W$, condition 3 gives $0\boldsymbol{v} \in W$, which by part (3) of equals the zero vector $\boldsymbol{0}$ of $V$; hence condition 1 holds. Along the way we have also seen that the zero vector of $W$ itself coincides with the zero vector of $V$. **Sufficiency.** Conditions 2 and 3 say precisely that addition and scalar multiplication define maps $W \times W \to W$ and $K \times W \to W$. Axioms (V1), (V2), (V5), (V6), (V7) and (V8) are identities valid for all elements of $V$, hence in particular for elements of $W$. Axiom (V3) follows from condition 1. As for (V4), given $\boldsymbol{v} \in W$, condition 3 with $a = -1$ gives $(-1)\boldsymbol{v} \in W$, and by part (5) of this is $-\boldsymbol{v}$. So inverses lie in $W$ as well, and $W$ satisfies all eight conditions. For instance, inside $\mathbb{R}^3$ both the line $\{t(1,2,3) \mid t \in \mathbb{R}\}$ through the origin and the plane $\{(x,y,z) \mid x + y + z = 0\}$ through the origin are subspaces. Checking the latter: $(0,0,0)$ satisfies $0+0+0=0$; if $x_1+y_1+z_1 = 0$ and $x_2+y_2+z_2=0$ then the components of the sum satisfy $(x_1+x_2)+(y_1+y_2)+(z_1+z_2) = 0$; and multiplying by $a$ gives $ax+ay+az = a\cdot 0 = 0$. Likewise the polynomial space $P_n$ is a subspace of a function space, and the set of all continuous functions is a subspace of $\mathbb{R}^{[0,1]}$ (because continuity is preserved by sums and constant multiples). Next we define the operation that builds a space out of a few vectors. Let $V$ be a vector space over $K$, let $\boldsymbol{v}_1, \ldots, \boldsymbol{v}_m \in V$ and $a_1, \ldots, a_m \in K$. An element of the form $$ a_1 \boldsymbol{v}_1 + a_2 \boldsymbol{v}_2 + \cdots + a_m \boldsymbol{v}_m $$ is called a **linear combination** of $\boldsymbol{v}_1, \ldots, \boldsymbol{v}_m$. For a subset $S \subseteq V$, the set of all linear combinations of **finitely many** elements of $S$ is written $\operatorname{span}(S)$ and called the **span** of $S$. For $S = \emptyset$ we agree that $\operatorname{span}(\emptyset) := \{\boldsymbol{0}\}$. The span $\operatorname{span}(S)$ is the smallest subspace containing $S$. Indeed, that $\operatorname{span}(S)$ is a subspace follows from : the vector $\boldsymbol{0}$ is included as the empty sum (or as the linear combination with all coefficients $0$), a sum of linear combinations is again a linear combination, and $a$ times a linear combination is the linear combination with all coefficients multiplied by $a$. Moreover, if $W$ is a subspace containing $S$, then $W$ is closed under addition and scalar multiplication and therefore contains every linear combination of elements of $S$, so $\operatorname{span}(S) \subseteq W$. It matters that we allow only **finitely many** terms, even when $S$ is infinite: infinite sums require a notion of limit, which algebra alone cannot supply. ## 5. Linear independence, bases and dimension ### 5.1. Linear independence With $\operatorname{span}$ we can build as many spaces as we like, but redundancy creeps in. The plane $\mathbb{R}^2$ is spanned by the three vectors $(1,0), (0,1), (1,1)$, yet the third is superfluous because it is built from the first two. Linear independence is the notion that measures this redundancy. Let $V$ be a vector space over $K$. 1. A tuple $(\boldsymbol{v}_1, \ldots, \boldsymbol{v}_m)$ is **linearly independent** if, for $a_1, \ldots, a_m \in K$, $$ a_1\boldsymbol{v}_1 + \cdots + a_m\boldsymbol{v}_m = \boldsymbol{0} \implies a_1 = a_2 = \cdots = a_m = 0. $$ Otherwise it is **linearly dependent**; that is, there exist coefficients $a_1,\ldots,a_m$, not all $0$, with $\sum_i a_i \boldsymbol{v}_i = \boldsymbol{0}$. An infinite subset $S \subseteq V$ is called linearly independent when every tuple of finitely many distinct elements of $S$ is linearly independent. 2. If $\operatorname{span}(S) = V$, we say $S$ **generates** $V$ and call $S$ a **spanning set** of $V$. 3. A linearly independent spanning set is called a **basis** of $V$. In the finite case we write it as an ordered tuple $(\boldsymbol{v}_1, \ldots, \boldsymbol{v}_n)$. A word on how to read the definition. The relation $\sum_i a_i \boldsymbol{v}_i = \boldsymbol{0}$ always holds when all coefficients are $0$ (by part (3) of ). This is called the **trivial relation**. Linear independence says that there is no relation other than the trivial one. Geometrically, linear dependence is the same as "one of the vectors lies in the span of the others". Indeed, if $\sum_i a_i \boldsymbol{v}_i = \boldsymbol{0}$ with $a_k \ne 0$, multiplying by $a_k^{-1}$ and rearranging gives $$ \boldsymbol{v}_k = -a_k^{-1} \sum_{i \ne k} a_i \boldsymbol{v}_i, $$ so $\boldsymbol{v}_k$ is a linear combination of the others; the converse is checked in the same way. The vectors $(1,0), (0,1), (1,1)$ in $\mathbb{R}^2$ satisfy the non-trivial relation $1\cdot(1,0) + 1\cdot(0,1) + (-1)\cdot(1,1) = (0,0)$ and are therefore linearly dependent. ### 5.2. Bases and coordinates Let $V$ be a vector space over $K$ and $\boldsymbol{v}_1, \ldots, \boldsymbol{v}_n \in V$. Then $(\boldsymbol{v}_1, \ldots, \boldsymbol{v}_n)$ is a basis of $V$ if and only if for every $\boldsymbol{x} \in V$ there is exactly one tuple of scalars $(x_1, \ldots, x_n) \in K^n$ with $$ \boldsymbol{x} = x_1\boldsymbol{v}_1 + \cdots + x_n\boldsymbol{v}_n. $$ **Necessity.** Let $(\boldsymbol{v}_1,\ldots,\boldsymbol{v}_n)$ be a basis. Since it spans, every $\boldsymbol{x}$ has at least one expansion $\boldsymbol{x} = \sum_i x_i \boldsymbol{v}_i$. If there were another expansion $\boldsymbol{x} = \sum_i x_i' \boldsymbol{v}_i$, subtracting term by term gives $$ \boldsymbol{0} = \sum_{i=1}^{n} (x_i - x_i')\boldsymbol{v}_i. $$ By linear independence, $x_i - x_i' = 0$ for every $i$, that is $x_i = x_i'$. So the expansion is unique. **Sufficiency.** Every $\boldsymbol{x}$ has an expansion, so the tuple spans. For linear independence, suppose $\sum_i a_i \boldsymbol{v}_i = \boldsymbol{0}$. One expansion of $\boldsymbol{x} = \boldsymbol{0}$ is the one with all coefficients $0$, and by hypothesis it is the only one. Hence $a_i = 0$ for every $i$. This unique tuple $(x_1, \ldots, x_n)$ is called the **coordinate vector** of $\boldsymbol{x}$ with respect to the basis $B = (\boldsymbol{v}_1,\ldots,\boldsymbol{v}_n)$, written $[\boldsymbol{x}]_B$. **Choosing a basis is the same as installing a coordinate system**, and it is what makes an abstract vector computable as a tuple of numbers in $K^n$. As we shall see, a matrix is simply a linear map written out in such coordinates. Let $P_n := \{a_0 + a_1x + \cdots + a_nx^n \mid a_i \in \mathbb{R}\}$ be the set of functions defined by real polynomials of degree at most $n$ (the zero polynomial included). **First, it is a subspace.** $P_n$ is a subset of the function space $\mathbb{R}^{\mathbb{R}}$ (). The zero function belongs to $P_n$, being the polynomial with all $a_i = 0$; the sum of two polynomials of degree at most $n$ is computed coefficientwise and so again has degree at most $n$; and the same holds for constant multiples. Hence $P_n$ is a vector space by . **Next, $(1, x, x^2, \ldots, x^n)$ is a basis.** That it spans is the definition of $P_n$. For linear independence, suppose $a_0 + a_1x + \cdots + a_nx^n = 0$ for every real $x$. Substituting $x = 0$ gives $a_0 = 0$. Differentiating the remaining identity $a_1x + \cdots + a_nx^n = 0$ gives $a_1 + 2a_2x + \cdots + na_nx^{n-1} = 0$ for every $x$, and substituting $x = 0$ gives $a_1 = 0$. Repeating the procedure, each time we differentiate $k$ times and substitute $x = 0$ we obtain $k!\,a_k = 0$, that is $a_k = 0$, one after another. So all coefficients vanish and the family is linearly independent. Therefore a basis of $P_n$ has $n+1$ elements. The coordinate vector of the polynomial $3 - 2x + x^3$ with respect to the basis $(1,x,x^2,x^3)$ is $(3, -2, 0, 1)$. ### 5.3. The exchange lemma and the invariance of dimension Besides $((1,0),(0,1))$, the plane $\mathbb{R}^2$ has the basis $((1,1),(1,-1))$, and infinitely many others. Yet every basis has two elements. This is no accident; it follows from the next lemma, the single most important lemma at this stage of linear algebra. Let $V$ be a vector space over $K$. If $\boldsymbol{u}_1, \ldots, \boldsymbol{u}_m \in V$ are linearly independent and $$ \boldsymbol{u}_1, \ldots, \boldsymbol{u}_m \in \operatorname{span}(\boldsymbol{w}_1, \ldots, \boldsymbol{w}_n), $$ then $m \le n$. That is, **the size of a linearly independent family never exceeds the size of a spanning family**. Put $W := \operatorname{span}(\boldsymbol{w}_1, \ldots, \boldsymbol{w}_n)$. We prove the following claim by induction on $r$. **Claim.** For each $r$ with $0 \le r \le m$, after renumbering $\boldsymbol{w}_1, \ldots, \boldsymbol{w}_n$ we have $r \le n$ and $$ W \subseteq \operatorname{span}(\boldsymbol{u}_1, \ldots, \boldsymbol{u}_r, \boldsymbol{w}_{r+1}, \ldots, \boldsymbol{w}_n). $$ For $r = 0$ the right-hand side is $W$ itself, so the claim clearly holds. Assume the claim for some $r < m$ and prove it for $r+1$. By hypothesis $\boldsymbol{u}_{r+1} \in W \subseteq \operatorname{span}(\boldsymbol{u}_1, \ldots, \boldsymbol{u}_r, \boldsymbol{w}_{r+1}, \ldots, \boldsymbol{w}_n)$, so there are scalars $a_1,\ldots,a_r, b_{r+1},\ldots,b_n$ with $$ \boldsymbol{u}_{r+1} = \sum_{i=1}^{r} a_i \boldsymbol{u}_i + \sum_{j=r+1}^{n} b_j \boldsymbol{w}_j. $$ Suppose all the $b_j$ were $0$ (this includes the case $r = n$, where no $\boldsymbol{w}$ is left). Then $$ 1 \cdot \boldsymbol{u}_{r+1} - \sum_{i=1}^{r} a_i \boldsymbol{u}_i = \boldsymbol{0}, $$ and since the coefficient of $\boldsymbol{u}_{r+1}$ is $1 \ne 0$ this is a non-trivial relation. As $r + 1 \le m$, it contradicts the linear independence of $\boldsymbol{u}_1, \ldots, \boldsymbol{u}_m$. Hence $b_j \ne 0$ for some $j$; in particular at least one $\boldsymbol{w}$ remains, that is $r + 1 \le n$. Renumbering, we may assume $b_{r+1} \ne 0$, and solving the displayed equation for $\boldsymbol{w}_{r+1}$ gives $$ \boldsymbol{w}_{r+1} = b_{r+1}^{-1}\left( \boldsymbol{u}_{r+1} - \sum_{i=1}^{r} a_i \boldsymbol{u}_i - \sum_{j=r+2}^{n} b_j \boldsymbol{w}_j \right). $$ The right-hand side is a linear combination of $\boldsymbol{u}_1, \ldots, \boldsymbol{u}_{r+1}, \boldsymbol{w}_{r+2}, \ldots, \boldsymbol{w}_n$, so $\boldsymbol{w}_{r+1} \in \operatorname{span}(\boldsymbol{u}_1, \ldots, \boldsymbol{u}_{r+1}, \boldsymbol{w}_{r+2}, \ldots, \boldsymbol{w}_n)$. Consequently $$ \operatorname{span}(\boldsymbol{u}_1, \ldots, \boldsymbol{u}_r, \boldsymbol{w}_{r+1}, \ldots, \boldsymbol{w}_n) \subseteq \operatorname{span}(\boldsymbol{u}_1, \ldots, \boldsymbol{u}_{r+1}, \boldsymbol{w}_{r+2}, \ldots, \boldsymbol{w}_n) $$ (because every generator on the left lies in the right-hand side, which is a subspace; we used ), and together with the induction hypothesis the claim holds for $r+1$. Carrying the induction through to $r = m$ produces, along the way, the inequality $m \le n$. The name "exchange" comes from the procedure in the proof: we discard $\boldsymbol{w}_{r+1}$ and insert $\boldsymbol{u}_{r+1}$, one vector at a time. Since the spanning side has only $n$ vectors, the exchanges run out after $n$ steps. Let $V$ be a vector space over $K$ and suppose $V$ has both a basis with $m$ elements and a basis with $n$ elements ($m, n$ finite). Then $m = n$. Call the two bases $(\boldsymbol{u}_1, \ldots, \boldsymbol{u}_m)$ and $(\boldsymbol{w}_1, \ldots, \boldsymbol{w}_n)$. The first is linearly independent and the second spans, so $\boldsymbol{u}_i \in V = \operatorname{span}(\boldsymbol{w}_1,\ldots,\boldsymbol{w}_n)$. By we get $m \le n$. Now swap the roles. The second is linearly independent and the first spans, so $\boldsymbol{w}_j \in V = \operatorname{span}(\boldsymbol{u}_1,\ldots,\boldsymbol{u}_m)$. Again gives $n \le m$. Hence $m = n$. If a vector space $V$ has a basis with finitely many elements, $V$ is called **finite-dimensional**, and the number of elements of such a basis is the **dimension** of $V$, written $\dim V$ (or $\dim_K V$ when the field must be made explicit). By , this value does not depend on the choice of basis. If $V$ has no finite basis, it is called **infinite-dimensional**. For $V = \{\boldsymbol{0}\}$ we regard the empty set as a basis and set $\dim \{\boldsymbol{0}\} = 0$. Let us compute a few values. We have $\dim K^n = n$. Indeed, let $\boldsymbol{e}_i$ be the vector whose $i$-th component is $1$ and whose other components are $0$. Every $\boldsymbol{x} = (x_1,\ldots,x_n)$ can be written $\boldsymbol{x} = \sum_i x_i \boldsymbol{e}_i$, so these vectors span; and $\sum_i a_i\boldsymbol{e}_i = (a_1, \ldots, a_n) = \boldsymbol{0}$ immediately forces $a_i = 0$ for every $i$, so they are linearly independent. The family $(\boldsymbol{e}_1,\ldots,\boldsymbol{e}_n)$ is called the **standard basis**. By we have $\dim P_n = n + 1$. Also $M_{m,n}(K)$ has as a basis the matrices $E_{ij}$ whose only non-zero entry is a $1$ in position $(i,j)$, so $\dim M_{m,n}(K) = mn$. By contrast, the space $K[x]$ of all polynomials is infinite-dimensional. If it were generated by $N$ polynomials, then the $N+1$ linearly independent elements $1, x, \ldots, x^{N}$ would lie in the span of those $N$ polynomials, and would give $N + 1 \le N$, a contradiction. More directly, for every $n$ there are $n+1$ linearly independent elements $1, x, \ldots, x^n$, so no finite basis can exist. ### 5.4. Basic properties of finite-dimensional spaces Here we assemble the tools needed for the proof of the rank-nullity theorem. Each is a corollary of the exchange lemma. Let $V$ be a finite-dimensional vector space with $\dim V = n$. 1. Any family of $n+1$ or more vectors of $V$ is linearly dependent. 2. Any linearly independent family $(\boldsymbol{u}_1, \ldots, \boldsymbol{u}_k)$ in $V$ can be extended to a basis of $V$ by adjoining suitable vectors. 3. Every subspace $U$ of $V$ is finite-dimensional with $\dim U \le n$, and $\dim U = n$ holds only when $U = V$. Fix a basis $(\boldsymbol{w}_1, \ldots, \boldsymbol{w}_n)$ of $V$. **(1)** If $(\boldsymbol{u}_1,\ldots,\boldsymbol{u}_m)$ is linearly independent, then, since the basis spans, each $\boldsymbol{u}_i$ is a linear combination of $\boldsymbol{w}_1,\ldots,\boldsymbol{w}_n$, and gives $m \le n$. Taking the contrapositive, any family with $m \ge n+1$ is linearly dependent. **(2)** First an auxiliary fact: if $(\boldsymbol{u}_1,\ldots,\boldsymbol{u}_k)$ is linearly independent and $\boldsymbol{v} \notin \operatorname{span}(\boldsymbol{u}_1,\ldots,\boldsymbol{u}_k)$, then $(\boldsymbol{u}_1,\ldots,\boldsymbol{u}_k,\boldsymbol{v})$ is linearly independent as well. Indeed, suppose $\sum_i a_i\boldsymbol{u}_i + b\boldsymbol{v} = \boldsymbol{0}$. If $b \ne 0$ then $\boldsymbol{v} = -b^{-1}\sum_i a_i \boldsymbol{u}_i \in \operatorname{span}(\boldsymbol{u}_1,\ldots,\boldsymbol{u}_k)$, contrary to hypothesis; hence $b = 0$, and the remaining relation $\sum_i a_i \boldsymbol{u}_i = \boldsymbol{0}$ forces all $a_i = 0$ by the independence of the $\boldsymbol{u}_i$. Now take a linearly independent family containing $(\boldsymbol{u}_1,\ldots,\boldsymbol{u}_k)$ with as many elements as possible. By (1) the number of elements is bounded by $n$, so a maximal one exists. Write it as $(\boldsymbol{u}_1,\ldots,\boldsymbol{u}_k,\boldsymbol{z}_1,\ldots,\boldsymbol{z}_s)$. If this family did not span $V$, we could pick $\boldsymbol{v} \in V$ outside its span, and the auxiliary fact would produce a longer linearly independent family, contradicting maximality. So the family spans and is linearly independent, hence is a basis. **(3)** A linearly independent family inside $U$ is also linearly independent inside $V$, so by (1) it has at most $n$ elements. Take a linearly independent family in $U$ with the largest possible number of elements, say $(\boldsymbol{u}_1,\ldots,\boldsymbol{u}_k)$ with $k \le n$. For any $\boldsymbol{u} \in U$, the family $(\boldsymbol{u}_1,\ldots,\boldsymbol{u}_k,\boldsymbol{u})$ is linearly dependent by maximality, so the contrapositive of the auxiliary fact in (2) gives $\boldsymbol{u} \in \operatorname{span}(\boldsymbol{u}_1,\ldots,\boldsymbol{u}_k)$. Hence this family is a basis of $U$ and $\dim U = k \le n$. Now suppose $\dim U = n$. A basis of $U$ is a linearly independent family of $n$ vectors in $V$, so by (2) it extends to a basis of $V$. By the extended family must have $n$ elements, so in fact nothing was adjoined. That is, a basis of $U$ is already a basis of $V$, and $U = \operatorname{span}(\text{that basis}) = V$. Conversely, if $U = V$ then $\dim U = n$ trivially. ## 6. Linear maps ### 6.1. Definition and geometric examples Having defined the spaces themselves, we turn to the maps between them. Since the structure of a vector space consists of addition and scalar multiplication only, the notion of a "structure-preserving map" is determined automatically. Let $V, W$ be vector spaces over the same field $K$. A map $f : V \to W$ is called a **linear map** if it satisfies the following two conditions. - **Additivity**: $f(\boldsymbol{u} + \boldsymbol{v}) = f(\boldsymbol{u}) + f(\boldsymbol{v})$ for all $\boldsymbol{u}, \boldsymbol{v} \in V$ - **Homogeneity**: $f(a\boldsymbol{v}) = a f(\boldsymbol{v})$ for all $a \in K$ and $\boldsymbol{v} \in V$ When $V = W$ we call $f$ a **linear transformation** of $V$. The two conditions can be combined into one: for all $a, b \in K$ and $\boldsymbol{u}, \boldsymbol{v} \in V$, $$ f(a\boldsymbol{u} + b\boldsymbol{v}) = a f(\boldsymbol{u}) + b f(\boldsymbol{v}). $$ That this follows from additivity and homogeneity is the computation $f(a\boldsymbol{u}+b\boldsymbol{v}) = f(a\boldsymbol{u}) + f(b\boldsymbol{v}) = af(\boldsymbol{u}) + bf(\boldsymbol{v})$. Conversely, putting $a = b = 1$ in the combined identity gives additivity, and putting $b = 0$ gives $f(a\boldsymbol{u}) = af(\boldsymbol{u}) + 0\cdot f(\boldsymbol{v}) = af(\boldsymbol{u})$, which is homogeneity (we used part (3) of ). By induction, $f(\sum_i a_i \boldsymbol{v}_i) = \sum_i a_i f(\boldsymbol{v}_i)$ holds for any finite linear combination. Every linear map satisfies $f(\boldsymbol{0}) = \boldsymbol{0}$: simply compute $f(\boldsymbol{0}) = f(0 \cdot \boldsymbol{0}) = 0 \cdot f(\boldsymbol{0}) = \boldsymbol{0}$, again using part (3) of . This one remark is immediately useful for recognising counterexamples. Let us examine several maps on $\mathbb{R}^2$. **(a) Rotation about the origin** $R_\theta(x, y) = (x\cos\theta - y\sin\theta,\ x\sin\theta + y\cos\theta)$. We check linearity: $$ \begin{aligned} R_\theta\bigl(a(x_1,y_1) + b(x_2,y_2)\bigr) &= R_\theta(ax_1 + bx_2,\ ay_1 + by_2) \\ &= \bigl((ax_1+bx_2)\cos\theta - (ay_1+by_2)\sin\theta,\ (ax_1+bx_2)\sin\theta + (ay_1+by_2)\cos\theta\bigr) \\ &= a\bigl(x_1\cos\theta - y_1\sin\theta,\ x_1\sin\theta + y_1\cos\theta\bigr) + b\bigl(x_2\cos\theta - y_2\sin\theta,\ x_2\sin\theta + y_2\cos\theta\bigr) \\ &= a R_\theta(x_1,y_1) + b R_\theta(x_2,y_2). \end{aligned} $$ The only thing that matters is that each component is homogeneous of degree one in $x$ and $y$. **(b) Projection onto the $x$-axis** $P(x,y) = (x, 0)$. Since $P(a(x_1,y_1)+b(x_2,y_2)) = (ax_1+bx_2, 0) = a(x_1,0) + b(x_2,0)$, this map is linear. It throws away the information in the $y$ direction. **(c) Axis-aligned scaling** $S(x,y) = (c_1 x, c_2 y)$ and **(d) shear** $T(x,y) = (x + ky, y)$. In both cases the components are homogeneous of degree one, so the same computation as in (a) proves linearity. Here are their matrix representations with respect to the standard basis. The matrix $A$ is the one for which $f(x,y)$, viewed as a column vector, equals $A\begin{pmatrix} x \\ y\end{pmatrix}$. | Transformation | Formula | Matrix | Kernel | Image | |---|---|---|---|---| | rotation | $(x\cos\theta - y\sin\theta,\ x\sin\theta+y\cos\theta)$ | $\begin{pmatrix}\cos\theta & -\sin\theta \\ \sin\theta & \cos\theta\end{pmatrix}$ | $\{\boldsymbol{0}\}$ | $\mathbb{R}^2$ | | projection onto the $x$-axis | $(x, 0)$ | $\begin{pmatrix}1 & 0 \\ 0 & 0\end{pmatrix}$ | the $y$-axis | the $x$-axis | | scaling | $(c_1x, c_2y)$ | $\begin{pmatrix}c_1 & 0 \\ 0 & c_2\end{pmatrix}$ | $\{\boldsymbol{0}\}$ if $c_1c_2 \ne 0$ | $\mathbb{R}^2$ if $c_1c_2 \ne 0$ | | shear | $(x + ky,\ y)$ | $\begin{pmatrix}1 & k \\ 0 & 1\end{pmatrix}$ | $\{\boldsymbol{0}\}$ | $\mathbb{R}^2$ | **Maps that are not linear.** The translation $T_{\boldsymbol{b}}(x,y) = (x+1, y)$ is not linear because $T_{\boldsymbol{b}}(\boldsymbol{0}) = (1,0) \ne \boldsymbol{0}$. A linear map plus a constant vector is called an affine map, and is to be distinguished from a linear map. Likewise $g(x,y) = (x^2, y)$ is not linear: $g(2,0) = (4,0)$ while $2g(1,0) = (2,0)$, so homogeneity fails. ### 6.2. A linear map is determined by the images of a basis Let $(\boldsymbol{v}_1, \ldots, \boldsymbol{v}_n)$ be a basis of $V$. Then a linear map $f : V \to W$ is completely determined by $f(\boldsymbol{v}_1), \ldots, f(\boldsymbol{v}_n)$. Indeed, every $\boldsymbol{x} \in V$ can be written uniquely as $\boldsymbol{x} = \sum_i x_i \boldsymbol{v}_i$ by , so linearity forces $f(\boldsymbol{x}) = \sum_i x_i f(\boldsymbol{v}_i)$. Conversely, choose $\boldsymbol{w}_1, \ldots, \boldsymbol{w}_n \in W$ arbitrarily and define $f(\boldsymbol{x}) := \sum_i x_i \boldsymbol{w}_i$, where $(x_i)$ is the coordinate vector of $\boldsymbol{x}$. Then $f$ is a linear map with $f(\boldsymbol{v}_i) = \boldsymbol{w}_i$. The definition is unambiguous because coordinates are unique, and linearity follows because the coordinates of $\boldsymbol{x} + \boldsymbol{y}$ and $a\boldsymbol{x}$ are the componentwise sum and the componentwise multiple. This fact, restated as the isomorphism given by the coordinate map, is . In other words, constructing a linear map is the same as prescribing $n$ destinations for the basis vectors. Choosing a basis of $W$ as well, expressing each $f(\boldsymbol{v}_j)$ in coordinates and arranging these as columns gives a **matrix**. A matrix is not the linear map itself but its representation once bases are fixed; change the bases and the same map acquires a different matrix. This correspondence and the associated computations are treated in [Matrices and systems of linear equations](/en/mathematics/linear-algebra/matrices-and-linear-systems), in , while the problem of choosing bases so as to make the matrix as simple as possible is treated in [Eigenvalues and eigenvectors](/mathematics/linear-algebra/eigenvalues) and [Diagonalisation and the Jordan normal form](/mathematics/linear-algebra/diagonalization-and-jordan-form). ## 7. Kernel, image and the rank-nullity theorem ### 7.1. Kernel and image When studying a linear map there are two subspaces to look at first: "what gets crushed" and "how far it reaches". Let $f : V \to W$ be a linear map between vector spaces over $K$. The sets $$ \operatorname{Ker} f := \{\boldsymbol{v} \in V \mid f(\boldsymbol{v}) = \boldsymbol{0}\}, \qquad \operatorname{Im} f := \{f(\boldsymbol{v}) \mid \boldsymbol{v} \in V\} $$ are called the **kernel** and the **image** of $f$ respectively. When $\operatorname{Im} f$ is finite-dimensional, $\operatorname{rank} f := \dim \operatorname{Im} f$ is called the **rank** of $f$. Let $f : V \to W$ be a linear map. 1. $\operatorname{Ker} f$ is a subspace of $V$, and $\operatorname{Im} f$ is a subspace of $W$. 2. $f$ is injective if and only if $\operatorname{Ker} f = \{\boldsymbol{0}\}$. **(1)** We check the three conditions of . For the kernel: $f(\boldsymbol{0}) = \boldsymbol{0}$, so $\boldsymbol{0} \in \operatorname{Ker} f$. If $\boldsymbol{u}, \boldsymbol{v} \in \operatorname{Ker} f$ then $f(\boldsymbol{u}+\boldsymbol{v}) = f(\boldsymbol{u}) + f(\boldsymbol{v}) = \boldsymbol{0} + \boldsymbol{0} = \boldsymbol{0}$, and for $a \in K$ we get $f(a\boldsymbol{v}) = af(\boldsymbol{v}) = a\boldsymbol{0} = \boldsymbol{0}$ (the last step is part (4) of ). For the image: $\boldsymbol{0} = f(\boldsymbol{0}) \in \operatorname{Im} f$. If $\boldsymbol{y}_1 = f(\boldsymbol{x}_1)$ and $\boldsymbol{y}_2 = f(\boldsymbol{x}_2)$ then $\boldsymbol{y}_1 + \boldsymbol{y}_2 = f(\boldsymbol{x}_1 + \boldsymbol{x}_2) \in \operatorname{Im} f$ and $a\boldsymbol{y}_1 = f(a\boldsymbol{x}_1) \in \operatorname{Im} f$. **(2)** Suppose $f$ is injective. If $\boldsymbol{v} \in \operatorname{Ker} f$ then $f(\boldsymbol{v}) = \boldsymbol{0} = f(\boldsymbol{0})$, so injectivity gives $\boldsymbol{v} = \boldsymbol{0}$. Hence $\operatorname{Ker} f = \{\boldsymbol{0}\}$. Conversely suppose $\operatorname{Ker} f = \{\boldsymbol{0}\}$. If $f(\boldsymbol{u}) = f(\boldsymbol{v})$ then linearity gives $f(\boldsymbol{u} - \boldsymbol{v}) = f(\boldsymbol{u}) - f(\boldsymbol{v}) = \boldsymbol{0}$, so $\boldsymbol{u} - \boldsymbol{v} \in \operatorname{Ker} f = \{\boldsymbol{0}\}$, that is $\boldsymbol{u} = \boldsymbol{v}$. Part (2) is a useful reformulation. For a general map, injectivity must be tested "for every pair of points", whereas for a linear map it suffices to examine **only the points sent to the origin**. In the language of linear systems: to decide uniqueness of solutions, one need only look at the case where the right-hand side is $\boldsymbol{0}$, that is, the homogeneous equation. ### 7.2. The rank-nullity theorem Let $V, W$ be vector spaces over a field $K$ and let $f : V \to W$ be a linear map. If $V$ is finite-dimensional, then $\operatorname{Ker} f$ and $\operatorname{Im} f$ are both finite-dimensional and $$ \dim V = \dim \operatorname{Ker} f + \dim \operatorname{Im} f. $$ Put $n := \dim V$. By the kernel $\operatorname{Ker} f$ is a subspace of $V$, hence finite-dimensional by part (3) of . Put $k := \dim \operatorname{Ker} f \le n$ and choose a basis $(\boldsymbol{u}_1, \ldots, \boldsymbol{u}_k)$ of $\operatorname{Ker} f$ (the empty family when $k = 0$). This is also a linearly independent family in $V$, so by part (2) of it extends to a basis of $V$. Write the extended basis as $$ (\boldsymbol{u}_1, \ldots, \boldsymbol{u}_k, \boldsymbol{z}_1, \ldots, \boldsymbol{z}_r). $$ By we have $k + r = n$. **Claim: $(f(\boldsymbol{z}_1), \ldots, f(\boldsymbol{z}_r))$ is a basis of $\operatorname{Im} f$.** *It spans.* Take any $\boldsymbol{y} \in \operatorname{Im} f$ and write $\boldsymbol{y} = f(\boldsymbol{x})$. Expanding $\boldsymbol{x}$ in the above basis as $\boldsymbol{x} = \sum_{i=1}^{k} a_i \boldsymbol{u}_i + \sum_{j=1}^{r} b_j \boldsymbol{z}_j$, linearity of $f$ gives $$ \boldsymbol{y} = f(\boldsymbol{x}) = \sum_{i=1}^{k} a_i f(\boldsymbol{u}_i) + \sum_{j=1}^{r} b_j f(\boldsymbol{z}_j) = \sum_{j=1}^{r} b_j f(\boldsymbol{z}_j), $$ the first sum vanishing because $\boldsymbol{u}_i \in \operatorname{Ker} f$ gives $f(\boldsymbol{u}_i) = \boldsymbol{0}$. Hence $\operatorname{Im} f = \operatorname{span}(f(\boldsymbol{z}_1), \ldots, f(\boldsymbol{z}_r))$; in particular $\operatorname{Im} f$ is finite-dimensional. *It is linearly independent.* Suppose $\sum_{j=1}^{r} c_j f(\boldsymbol{z}_j) = \boldsymbol{0}$. By linearity $f\left(\sum_j c_j \boldsymbol{z}_j\right) = \boldsymbol{0}$, so $\sum_j c_j \boldsymbol{z}_j \in \operatorname{Ker} f$. Since the $\boldsymbol{u}_i$ form a basis of the kernel, there are scalars $d_1, \ldots, d_k$ with $$ \sum_{j=1}^{r} c_j \boldsymbol{z}_j = \sum_{i=1}^{k} d_i \boldsymbol{u}_i, \qquad \text{that is} \qquad \sum_{i=1}^{k} d_i \boldsymbol{u}_i - \sum_{j=1}^{r} c_j \boldsymbol{z}_j = \boldsymbol{0}. $$ The equation on the right is a relation among the basis $(\boldsymbol{u}_1,\ldots,\boldsymbol{u}_k,\boldsymbol{z}_1,\ldots,\boldsymbol{z}_r)$ of $V$, so by its linear independence all coefficients vanish; in particular $c_1 = \cdots = c_r = 0$. Therefore $\dim \operatorname{Im} f = r = n - k = \dim V - \dim \operatorname{Ker} f$, and rearranging gives the asserted identity. When $k = n$ (so $r = 0$), we have $\operatorname{Im} f = \operatorname{span}(\emptyset) = \{\boldsymbol{0}\}$ and $\dim \operatorname{Im} f = 0$, so the identity reads $n = n + 0$ and still holds. The content of the proof can be drawn as follows. Split a basis of $V$ into "a basis of the kernel" and "the rest"; the rest is carried bijectively onto a basis of the image.
V (dimension n) the remaining n-k dimensions Ker f (dimension k) W Im f (dimension n-k) 0 one-to-one correspondence all sent to 0
Let $D : P_3 \to P_3$ be differentiation, $D(p) = p'$. By we have $\dim P_3 = 4$. **Linearity.** For $p = \sum_{i=0}^{3} a_i x^i$ and $q = \sum_{i=0}^{3} b_i x^i$, the coefficients of $ap + bq$ are $a a_i + b b_i$, and $$ D(ap + bq) = \sum_{i=1}^{3} i(a a_i + b b_i)x^{i-1} = a\sum_{i=1}^{3} i a_i x^{i-1} + b \sum_{i=1}^{3} i b_i x^{i-1} = aD(p) + bD(q), $$ so $D$ is linear. The values stay inside $P_3$ because the degree drops by one. **Kernel.** Suppose $D(a_0 + a_1x + a_2x^2 + a_3x^3) = a_1 + 2a_2x + 3a_3x^2 = 0$. The linear independence of $1, x, x^2$ established in gives $a_1 = 2a_2 = 3a_3 = 0$, that is $a_1 = a_2 = a_3 = 0$. Hence $\operatorname{Ker} D = \{a_0 \mid a_0 \in \mathbb{R}\}$ consists of the constant polynomials, with basis $(1)$, so $\dim \operatorname{Ker} D = 1$. **Image.** The values of $D$ always have degree at most $2$, so $\operatorname{Im} D \subseteq P_2$. Conversely, given any $b_0 + b_1 x + b_2 x^2 \in P_2$, $$ D\left(b_0 x + \frac{b_1}{2}x^2 + \frac{b_2}{3}x^3\right) = b_0 + b_1 x + b_2 x^2, $$ and the polynomial in brackets belongs to $P_3$. Hence $\operatorname{Im} D = P_2$ and $\dim \operatorname{Im} D = 3$. **Check.** We get $\dim P_3 = 4 = 1 + 3 = \dim\operatorname{Ker} D + \dim\operatorname{Im} D$, exactly as predicts. Differentiation is the map that discards "only the information carried by the constant term", and the image thins out by precisely that one dimension. Let $V, W$ be finite-dimensional vector spaces over a field $K$ with $\dim V = \dim W = n$, and let $f : V \to W$ be a linear map. Then the following three conditions are equivalent. 1. $f$ is injective. 2. $f$ is surjective. 3. $f$ is bijective. It suffices to prove $(1) \Leftrightarrow (2)$; the equivalence with $(3)$ then follows from the definitions. By , $f$ is injective if and only if $\operatorname{Ker} f = \{\boldsymbol{0}\}$, that is $\dim \operatorname{Ker} f = 0$. By this is equivalent to $\dim \operatorname{Im} f = \dim V = n$. On the other hand, $\operatorname{Im} f$ is a subspace of $W$, so applying part (3) of to $W$ shows that $\dim \operatorname{Im} f = n = \dim W$ is equivalent to $\operatorname{Im} f = W$. And $\operatorname{Im} f = W$ is precisely the surjectivity of $f$. Chaining these gives $(1) \Leftrightarrow (2)$. This corollary may be read as: "in finite dimensions, a map that loses no information necessarily fills up its target". It is the real reason why, for a system of $n$ linear equations in $n$ unknowns, "there is always at most one solution" and "there is always at least one solution" are equivalent. As shows, the statement fails in infinite dimensions. Finite-dimensionality is used essentially, through . A system of linear equations $A\boldsymbol{x} = \boldsymbol{b}$ (with $A$ an $m \times n$ matrix) can be rewritten as $f_A(\boldsymbol{x}) = \boldsymbol{b}$ using the linear map $f_A : K^n \to K^m$, $f_A(\boldsymbol{x}) = A\boldsymbol{x}$. Then a solution exists exactly when $\boldsymbol{b} \in \operatorname{Im} f_A$, the number of degrees of freedom of the solutions is $\dim \operatorname{Ker} f_A$, and gives $$ \dim \operatorname{Ker} f_A = n - \operatorname{rank} f_A. $$ The rule of thumb quoted in the motivating section, "the number of unknowns minus the number of independent equations", is a restatement of this identity. The true meaning of "the number of independent equations" is $\operatorname{rank} f_A$, and how to compute it by is treated in [Matrices and systems of linear equations](/en/mathematics/linear-algebra/matrices-and-linear-systems). ### 7.3. How to read the theorem in data science A data point with $p$ features is a vector in $\mathbb{R}^p$. Principal component analysis (PCA) first centres the data by subtracting the mean, then chooses directions $\boldsymbol{u}_1, \ldots, \boldsymbol{u}_k \in \mathbb{R}^p$ of length $1$ that are mutually orthogonal, and compresses $p$ dimensions into $k$ by $$ f(\boldsymbol{x}) = \bigl(\langle \boldsymbol{u}_1, \boldsymbol{x}\rangle, \ldots, \langle \boldsymbol{u}_k, \boldsymbol{x}\rangle\bigr) \in \mathbb{R}^k. $$ The inner product is linear in its second argument, so $f$ is a linear map. If the $\boldsymbol{u}_j$ are orthonormal then $f(\boldsymbol{u}_j) = \boldsymbol{e}_j$ (the standard basis of $\mathbb{R}^k$), so $\operatorname{Im} f = \mathbb{R}^k$ and $\operatorname{rank} f = k$. Hence gives $$ \dim \operatorname{Ker} f = p - k. $$ These $p - k$ dimensions are exactly "the information thrown away by the compression". However cleverly the directions $\boldsymbol{u}_j$ are chosen, $p-k$ dimensions are inevitably lost. What PCA answers is the optimisation problem "which $k$ dimensions should be kept so that the loss of variance is smallest", and the answer is the eigenvectors of the covariance matrix, as guaranteed by . This thread continues in [Eigenvalues and eigenvectors](/mathematics/linear-algebra/eigenvalues), [Inner product spaces and Gram-Schmidt orthogonalisation](/mathematics/linear-algebra/inner-product-spaces) and [The spectral theorem](/mathematics/linear-algebra/spectral-theorem). Here is one more practical example. In linear regression, when one explanatory variable is a linear combination of the others (multicollinearity), the kernel of the linear map defined by the data matrix is no longer $\{\boldsymbol{0}\}$. By part (2) of the map is no longer injective, so infinitely many coefficient vectors give the same predictions. The phenomenon known as "unstable coefficients" is a consequence of the kernel failing to vanish. ## 8. Exercises Decide whether each of the following subsets of $\mathbb{R}^2$ is a subspace, and justify your answer. 1. $W_1 = \{(x,y) \in \mathbb{R}^2 \mid 2x - 3y = 0\}$ 2. $W_2 = \{(x,y) \in \mathbb{R}^2 \mid xy = 0\}$ **1. It is a subspace.** We check the three conditions of . Since $2\cdot 0 - 3\cdot 0 = 0$, we have $(0,0) \in W_1$. If $(x_1,y_1), (x_2,y_2) \in W_1$ then $$ 2(x_1+x_2) - 3(y_1+y_2) = (2x_1 - 3y_1) + (2x_2 - 3y_2) = 0 + 0 = 0, $$ so the sum lies in $W_1$. For $a \in \mathbb{R}$ we have $2(ax_1) - 3(ay_1) = a(2x_1 - 3y_1) = a \cdot 0 = 0$, so scalar multiples lie in $W_1$ too. Note that $W_1 = \operatorname{span}((3,2))$, a line through the origin. **2. It is not a subspace.** The equation $xy = 0$ means "$x = 0$ or $y = 0$", so $W_2$ is the union of the two coordinate axes. We have $(1,0) \in W_2$ (since $y=0$) and $(0,1) \in W_2$ (since $x=0$), but their sum is $(1,1)$ and $1 \cdot 1 = 1 \ne 0$, so the sum is not in $W_2$. Thus $W_2$ is not closed under addition and condition 2 fails. Since it does contain the zero vector and is closed under scalar multiplication, this is an example where exactly one of the three conditions fails. In the vector space $\mathbb{R}^{\mathbb{R}}$ of all real-valued functions on the reals (), consider $f_1(x) = 1$, $f_2(x) = \cos^2 x$ and $f_3(x) = \cos 2x$. 1. Show that $(f_1, f_2, f_3)$ is linearly dependent. 2. Show that $(f_1, f_2)$ is linearly independent. 3. Determine the dimension of $\operatorname{span}(f_1, f_2, f_3)$. **1.** By the double angle formula $\cos 2x = 2\cos^2 x - 1$, for every $x$ we have $$ 1 \cdot f_1(x) - 2 \cdot f_2(x) + 1 \cdot f_3(x) = 1 - 2\cos^2 x + \cos 2x = 0. $$ As functions, $f_1 - 2f_2 + f_3 = 0$, and the coefficients $(1,-2,1)$ are not all $0$, so this is a non-trivial relation. Hence the family is linearly dependent. **2.** Suppose $a f_1 + b f_2 = 0$, that is $a + b\cos^2 x = 0$ for every $x$. Substituting $x = \pi/2$ and using $\cos(\pi/2) = 0$ gives $a = 0$. Substituting $x = 0$ and using $\cos 0 = 1$ gives $a + b = 0$, and with $a = 0$ this yields $b = 0$. Hence the family is linearly independent. **3.** By part 1 we have $f_3 = 2f_2 - f_1$, so $\operatorname{span}(f_1,f_2,f_3) = \operatorname{span}(f_1,f_2)$ (every linear combination involving $f_3$ can be rewritten as a linear combination of $f_1$ and $f_2$). By part 2 these two are linearly independent, so $(f_1,f_2)$ is a basis and the dimension is $2$. Let $M_2(\mathbb{R})$ be the vector space of all real $2 \times 2$ matrices and consider the trace $$ \operatorname{tr} \begin{pmatrix} a & b \\ c & d \end{pmatrix} := a + d. $$ Show that $\operatorname{tr} : M_2(\mathbb{R}) \to \mathbb{R}$ is a linear map, determine a basis and the dimension of $\operatorname{Ker}(\operatorname{tr})$ and the dimension of $\operatorname{Im}(\operatorname{tr})$, and verify . **Linearity.** For $X = \begin{pmatrix} a_1 & b_1 \\ c_1 & d_1\end{pmatrix}$, $Y = \begin{pmatrix} a_2 & b_2 \\ c_2 & d_2\end{pmatrix}$ and $s, t \in \mathbb{R}$, the $(1,1)$ entry of $sX + tY$ is $sa_1 + ta_2$ and the $(2,2)$ entry is $sd_1 + td_2$, so $$ \operatorname{tr}(sX + tY) = (sa_1 + ta_2) + (sd_1 + td_2) = s(a_1+d_1) + t(a_2+d_2) = s\operatorname{tr}(X) + t\operatorname{tr}(Y). $$ Hence the trace is linear. **Image.** By , $\operatorname{Im}(\operatorname{tr})$ is a subspace of $\mathbb{R}$, and it is not $\{0\}$ because $\operatorname{tr}\begin{pmatrix}1&0\\0&0\end{pmatrix} = 1 \ne 0$. Since $\dim \mathbb{R} = 1$, part (3) of gives $\operatorname{Im}(\operatorname{tr}) = \mathbb{R}$ and $\dim \operatorname{Im}(\operatorname{tr}) = 1$. More directly, any $\lambda \in \mathbb{R}$ is obtained as $\operatorname{tr}\begin{pmatrix}\lambda & 0\\ 0 & 0\end{pmatrix} = \lambda$, so the map is surjective. **Kernel.** The condition $a + d = 0$ means $d = -a$, so $$ \operatorname{Ker}(\operatorname{tr}) = \left\{ \begin{pmatrix} a & b \\ c & -a\end{pmatrix} \;\middle|\; a,b,c \in \mathbb{R} \right\} = \operatorname{span}\left( \begin{pmatrix}1&0\\0&-1\end{pmatrix}, \begin{pmatrix}0&1\\0&0\end{pmatrix}, \begin{pmatrix}0&0\\1&0\end{pmatrix} \right). $$ These three matrices are linearly independent: a linear combination has the form $\begin{pmatrix} \alpha & \beta \\ \gamma & -\alpha \end{pmatrix}$, which is the zero matrix only when $\alpha = \beta = \gamma = 0$. Hence they form a basis and $\dim \operatorname{Ker}(\operatorname{tr}) = 3$. **Check.** We have $\dim M_2(\mathbb{R}) = 4$ (with basis $E_{11}, E_{12}, E_{21}, E_{22}$), and indeed $4 = 3 + 1$. Let $V = \mathbb{R}^{\mathbb{N}}$ be the vector space of all real sequences and let $$ S(a_1, a_2, a_3, \ldots) := (0, a_1, a_2, \ldots), \qquad T(a_1, a_2, a_3, \ldots) := (a_2, a_3, a_4, \ldots) $$ be the right shift and the left shift. 1. Verify that $S$ and $T$ are linear maps. 2. Show that $S$ is injective but not surjective, and that $T$ is surjective but not injective. 3. Show that $V$ is infinite-dimensional, and explain why the finite-dimensionality hypothesis in cannot be dropped. **1.** Sums and scalar multiples of sequences are defined componentwise. Let $\boldsymbol{a} = (a_i)$, $\boldsymbol{b} = (b_i)$ and $s,t \in \mathbb{R}$. The first component of $S(s\boldsymbol{a} + t\boldsymbol{b})$ is $0 = s\cdot 0 + t \cdot 0$ and its $(i+1)$-st component is $sa_i + tb_i$, which agree with the corresponding components of $sS(\boldsymbol{a}) + tS(\boldsymbol{b})$. For $T$, the $i$-th component of $T(s\boldsymbol{a}+t\boldsymbol{b})$ is $sa_{i+1} + tb_{i+1}$, which agrees with the $i$-th component of $sT(\boldsymbol{a}) + tT(\boldsymbol{b})$. **2.** If $S(\boldsymbol{a}) = \boldsymbol{0}$ then, reading off the $(i+1)$-st component, $a_i = 0$ for every $i$, so $\boldsymbol{a} = \boldsymbol{0}$. Hence $S$ is injective by . On the other hand, every element of $\operatorname{Im} S$ has first component $0$, so $(1,0,0,\ldots) \notin \operatorname{Im} S$ and $S$ is not surjective. As for $T$, given any $\boldsymbol{b} = (b_1,b_2,\ldots)$ we have $T(0, b_1, b_2, \ldots) = \boldsymbol{b}$, so $T$ is surjective. But $T(1,0,0,\ldots) = (0,0,\ldots) = \boldsymbol{0}$, so $\operatorname{Ker} T \ne \{\boldsymbol{0}\}$ and $T$ is not injective. Note also that $T \circ S = \mathrm{id}_V$, whereas $S \circ T(\boldsymbol{a}) = (0, a_2, a_3, \ldots)$, so $S \circ T \ne \mathrm{id}_V$ for any sequence with $a_1 \ne 0$. A one-sided inverse of this kind cannot occur in finite dimensions. **3.** For each $n$ let $\boldsymbol{e}_n$ be the sequence whose $n$-th term is $1$ and whose other terms are $0$. If $\sum_{i=1}^{N} c_i \boldsymbol{e}_i = \boldsymbol{0}$ then reading off the $i$-th component gives $c_i = 0$, so $(\boldsymbol{e}_1, \ldots, \boldsymbol{e}_N)$ is linearly independent for every $N$. If $V$ were finite-dimensional with $\dim V = n$, then by part (1) of no linearly independent family of $n+1$ vectors could exist, yet $(\boldsymbol{e}_1,\ldots,\boldsymbol{e}_{n+1})$ is one. Hence $V$ is infinite-dimensional. Now $S$ is a linear map from $V$ to $V$ that is injective but not surjective, so the conclusion of fails and its finite-dimensionality hypothesis cannot be dropped. Looking back at where finite-dimensionality was used: in deducing $\operatorname{Im} f = W$ from $\dim \operatorname{Im} f = \dim W$ (part (3) of ), and in the fact that itself assumes finite dimension. For $S$ we have $\operatorname{Ker} S = \{\boldsymbol{0}\}$ and $\operatorname{Im} S \subsetneq V$: the situation, peculiar to infinite dimensions, in which a proper subspace is "just as large" as the whole space. ## References - Masahiko Saito, *Senkei Daisu Nyumon*, University of Tokyo Press, 1966 (in Japanese) — the chapters on linear spaces, bases, dimension and linear maps. A standard Japanese textbook. - Ichiro Satake, *Senkei Daisugaku*, Shokabo, new edition 2015 (original 1958) (in Japanese) — the chapters on vector spaces and linear maps. The level of abstraction is high and the axiomatic development is careful. - Sheldon Axler, *Linear Algebra Done Right*, 4th ed., Springer, 2024 — Chapter 1 (Vector Spaces), Chapter 2 (Finite-Dimensional Vector Spaces), Chapter 3 (Linear Maps). Builds the structure without determinants, and is close in spirit to the organisation of this article. An open access edition is available at [linear.axler.net](https://linear.axler.net/). - Gilbert Strang, *Introduction to Linear Algebra*, 6th ed., Wellesley-Cambridge Press, 2023 — the chapters on vector spaces and subspaces, and on the four fundamental subspaces. The emphasis is on numerical computation and data analysis. - Giuseppe Peano, *Calcolo geometrico secondo l'Ausdehnungslehre di H. Grassmann*, Fratelli Bocca, Torino, 1888 — Chapter IX gives the axioms for a "linear system", known as the prototype of the modern definition of a vector space. - I. T. Jolliffe, *Principal Component Analysis*, 2nd ed., Springer, 2002 — the standard reference on principal component analysis, and the background to the discussion of compression in §7.3. ## Appendix: What changes in infinite dimensions **Existence of bases.** For finite-dimensional spaces we proved the existence of a basis in . The statement "every vector space has a basis" is true for general vector spaces as well, but its proof requires Zorn's lemma (equivalent to the axiom of choice). Conversely, it is known that the axiom of choice can be derived from that statement. So the existence of a basis is a proposition depending on the axiom system of set theory, out of reach of the kind of constructive argument available in the finite-dimensional case. **Bases that cannot be written down.** A basis whose existence is guaranteed by the axiom of choice need not be explicitly describable. The famous example is a basis of $\mathbb{R}$ regarded as a vector space over $\mathbb{Q}$ (a Hamel basis). It exists, yet not a single one of its elements can be exhibited. This is why "take a basis" is a far less casual operation in infinite dimensions than in finite ones. **The limits of algebraic bases.** As we saw in , a linear combination is always a finite sum. Consequently an infinite sum such as a Fourier series is not a linear combination in the algebraic sense. Functional analysis introduces a notion of convergence and uses a complete orthonormal system to give meaning to an infinite sum $f = \sum_{n} c_n e_n$ as a limit. This is a different object from an algebraic basis. For complete orthonormal systems in Hilbert spaces, [Inner product spaces and Gram-Schmidt orthogonalisation](/mathematics/linear-algebra/inner-product-spaces) is the entry point, and its finite-dimensional counterpart is . **What replaces dimension.** In infinite dimensions an identity such as is unavailable. As the right shift of shows, injectivity and surjectivity also come apart. Instead, more delicate quantities take the leading role: whether the image of an operator is closed, and whether the difference between the dimensions of the kernel and the cokernel (the index) is finite. On the care needed even in comparing the "sizes" of infinite sets, see [Cardinality and infinity: infinities come in different sizes](/mathematics/foundations/cardinality-and-infinity) and . **Where finiteness was used in this article.** Looking back, finite-dimensionality mattered only in the step of where "the spanning family is finite, so the exchanges run out", and in the three assertions of derived from it. Everything else — , , , — holds without any assumption on dimension.