8.1 Vector Spaces, Bases and Dimension
Arrows in the plane, polynomials, matrices, sequences and functions all obey the same eight rules for adding and scaling. Once a set obeys them it has a dimension — the size of any basis — and that one number controls subspaces, sums, quotients and even how many subspaces a finite space has.
Solve a homogeneous system of linear equations, a homogeneous linear differential equation $y''+y=0$, or a linear recurrence $x_{n+2}=x_{n+1}+x_n$, and the same thing happens every time: sums of solutions are solutions, multiples of solutions are solutions, and every solution is a combination of a few special ones ($\cos x$ and $\sin x$; the Fibonacci-type sequences starting $1,0$ and $0,1$). The common structure is a vector space, and the "few special solutions" form a basis. The number of vectors in a basis — the dimension — turns out not to depend on which basis we choose, and it is the single most useful invariant in linear algebra: two subspaces of $\mathbb{R}^7$ of dimensions $4$ and $5$ must meet in a plane; a space of $3\times3$ matrices described by four independent conditions has dimension $5$; a $4$-dimensional space over a field with $3$ elements has exactly $130$ planes through the origin.
This section builds the theory from the axioms: subspaces and the subspace test, span and linear independence, the Steinitz exchange theorem (the reason dimension is well defined), extension of independent sets to bases, sums and direct sums with the dimension formula $\dim(U+W)=\dim U+\dim W-\dim(U\cap W)$, quotient spaces, and counting subspaces over finite fields. CSIR NET examines these ideas constantly in Part B ("the dimension of the space of all … is") and Part C ("which of the following are subspaces / are linearly independent / must intersect"). Throughout, $\mathbb{F}$ is a field — usually $\mathbb{R}$ or $\mathbb{C}$, sometimes $\mathbb{Q}$ or the finite field $\mathbb{F}_q$ with $q$ elements ($\mathbb{F}_p=\mathbb{Z}_p$ for a prime $p$; fields themselves are studied in Unit 2).
Vector Spaces and Subspaces
A vector space over $\mathbb{F}$ is a set $V$ with an addition $V\times V\to V$, $(u,v)\mapsto u+v$, and a scalar multiplication $\mathbb{F}\times V\to V$, $(a,v)\mapsto av$, such that for all $u,v,w\in V$ and $a,b\in\mathbb{F}$:
Elements of $V$ are vectors, elements of $\mathbb{F}$ are scalars. When the field matters we say "$\mathbb{F}$-vector space" or "vector space over $\mathbb{F}$".
The standard examples, which will reappear all through Chapters 8–10:
- $\mathbb{F}^n$, the column vectors $(x_1,\dots,x_n)^{T}$ with entrywise operations; $\mathbb{F}^{\mathbb{N}}$, all sequences $(x_1,x_2,\dots)$.
- $M_{m\times n}(\mathbb{F})$, the $m\times n$ matrices; $M_n(\mathbb{F})=M_{n\times n}(\mathbb{F})$.
- $\mathbb{F}[x]$, all polynomials, and $P_n(\mathbb{F})$, the polynomials of degree at most $n$ (the zero polynomial included).
- $\mathbb{F}^X$, all functions $X\to\mathbb{F}$ on a set $X$, with $(f+g)(x)=f(x)+g(x)$ and $(af)(x)=af(x)$; inside $\mathbb{R}^{[a,b]}$ live $C[a,b]$, $C^k[a,b]$ and the Riemann integrable functions (Chapter 4).
- Restriction of scalars: a vector space over $\mathbb{C}$ is also one over $\mathbb{R}$, and one over $\mathbb{R}$ is also one over $\mathbb{Q}$. So $\mathbb{C}$ is a vector space over $\mathbb{C}$, over $\mathbb{R}$ and over $\mathbb{Q}$ — three different vector spaces on the same set.
Proof. (a) If $0$ and $0'$ are both zero vectors, $0=0+0'=0'$ by (V3) applied twice and (V1). If $w$ and $w'$ are negatives of $v$, then $w=w+(v+w')=(w+v)+w'=w'$. (e) Add $-w$ to both sides and use (V2), (V4), (V3). (b) $0v=(0+0)v=0v+0v$ by (V8), so $0v+0=0v+0v$ and cancellation gives $0v=0$. Likewise $a0=a(0+0)=a0+a0$ gives $a0=0$. (c) $v+(-1)v=1v+(-1)v=(1+(-1))v=0v=0$, so $(-1)v$ is the (unique) negative of $v$. (d) If $av=0$ and $a\ne0$, then $v=1v=(a^{-1}a)v=a^{-1}(av)=a^{-1}0=0$. ∎
Part (d) uses that nonzero scalars are invertible. It is exactly what fails for "modules" over $\mathbb{Z}$: in $\mathbb{Z}_6$ we have $2\cdot3=0$ with neither factor zero, which is why $\mathbb{Z}_6$ is not a vector space over any field.
Proof. (a) A subspace contains a zero vector $0_W$, and $0_W+0_W=0_W$ in $V$ forces $0_W=0$ by cancellation; it is closed under the operations, so $au+v\in W$. Conversely, suppose $0\in W$ and $W$ is closed under $(a,u,v)\mapsto au+v$. Taking $a=1$ gives closure under addition; taking $v=0$ gives closure under scaling; $-u=(-1)u\in W$ by Theorem 8.1(c). Axioms (V1), (V2), (V5)–(V8) hold in $W$ because they hold in $V$, and (V3), (V4) hold because $0$ and the negatives lie in $W$. (b) If every $W_i$ contains $0$ and is closed under $au+v$, so is $\bigcap_iW_i$. (c) If $U\subseteq W$ the union is $W$. Conversely, suppose neither contains the other: choose $u\in U\setminus W$ and $w\in W\setminus U$. If $U\cup W$ were a subspace, $u+w$ would lie in $U$ or in $W$. If $u+w\in U$ then $w=(u+w)-u\in U$; if $u+w\in W$ then $u=(u+w)-w\in W$. Both are contradictions. ∎
Part (c) has a far-reaching extension, a favourite of Part C problems.
Proof. Suppose, for a contradiction, that $V$ is a union of $k$ proper subspaces, and choose such a union with $k$ as small as possible; $k\ge2$ since $U_1\ne V$. By minimality $U_1\not\subseteq U_2\cup\cdots\cup U_k$, so there is $u\in U_1$ lying in no other $U_i$; and since $U_1\ne V$ there is $v\notin U_1$. Consider the vectors $v+tu$, $t\in\mathbb{F}$. None of them lies in $U_1$: otherwise $v=(v+tu)-tu\in U_1$. So each lies in one of $U_2,\dots,U_k$. There are infinitely many $t$ and only $k-1$ subspaces, so two different scalars $s\ne t$ give vectors $v+su$, $v+tu$ in the same $U_i$ ($i\ge2$). Then $(s-t)u\in U_i$, hence $u=(s-t)^{-1}(s-t)u\in U_i$ — contradicting the choice of $u$. For the finite case: every nonzero $x\in\mathbb{F}_q^2$ lies on the line $\mathbb{F}_qx$, and there are $(q^2-1)/(q-1)=q+1$ such lines (Theorem 8.15). ∎
Span, Linear Independence, Bases and Dimension
Proof. $0$ is the empty combination, and $a\sum a_iv_i+\sum b_jw_j$ is again a finite linear combination of vectors of $S$; by Theorem 8.2(a) the span is a subspace, and it contains each $s=1s$. A subspace containing $S$ is closed under linear combinations, so it contains $\operatorname{span}S$. Hence $\operatorname{span}S$ is the smallest such subspace, which is the intersection of all of them (a subspace by Theorem 8.2(b)). ∎
Proof. (a) A dependence relation among a subset is one for the whole set (put zero coefficients on the other vectors); and $1\cdot0=0$ is a dependence relation. (b) Let $av+\sum a_is_i=0$ with distinct $s_i\in S$. If $a\ne0$, then $v=-a^{-1}\sum a_is_i\in\operatorname{span}S$, which is excluded; so $a=0$, and then all $a_i=0$ because $S$ is independent. (c) If $v_j=\sum_{i\ne j}b_iv_i$, then $v_j-\sum_{i\ne j}b_iv_i=0$ is a dependence relation (the coefficient of $v_j$ is $1$). Conversely, let $\sum a_iv_i=0$ with not all $a_i=0$, and let $j$ be the largest index with $a_j\ne0$. If $j=1$, then $a_1v_1=0$ forces $v_1=0$ by Theorem 8.1(d); so if $v_1\ne0$ then $j\ge2$ and $$v_j=-a_j^{-1}(a_1v_1+\cdots+a_{j-1}v_{j-1}).$$ Any linear combination of $v_1,\dots,v_k$ can then be rewritten without $v_j$ by substituting this expression, so the span is unchanged. ∎
Proof. "Spans" is precisely "at least one way". If the list is independent and $\sum c_ib_i=\sum d_ib_i$, then $\sum(c_i-d_i)b_i=0$ gives $c_i=d_i$: at most one way. Conversely, uniqueness for $v=0$ (whose obvious representation has all coefficients $0$) is exactly independence. Adding or scaling representations gives representations of $u+v$ and $av$, and uniqueness identifies them with the coordinate vectors. ∎
The next result is the heart of the section: it is why "dimension" makes sense.
Proof. We prove by induction on $j=0,1,\dots,\min(k,m)$ that, after renumbering, $$V=\operatorname{span}\{u_1,\dots,u_j,w_{j+1},\dots,w_m\}.$$ For $j=0$ this is the hypothesis. Suppose it holds for some $j\lt k$. Then $u_{j+1}$ is a linear combination $$u_{j+1}=a_1u_1+\cdots+a_ju_j+b_{j+1}w_{j+1}+\cdots+b_mw_m.$$ If all $b_i$ were $0$ (in particular, if no $w$'s were left, i.e. $j=m$), then $u_{j+1}$ would be a combination of $u_1,\dots,u_j$, contradicting independence. Hence $j\lt m$ and some $b_i\ne0$; renumber so that $b_{j+1}\ne0$. Solving for $w_{j+1}$ shows $w_{j+1}\in\operatorname{span}\{u_1,\dots,u_{j+1},w_{j+2},\dots,w_m\}$, so this new list still spans $V$ (its span contains every vector of the old spanning list). This completes the induction step. The argument shows that whenever $j\lt k$ we have $j\lt m$; applying it for $j=0,1,\dots,k-1$ gives $k-1\lt m$, i.e. $k\le m$, and the case $j=k$ is the exchange statement. ∎
Proof. (a) Let $V=\operatorname{span}\{v_1,\dots,v_m\}$. Discard zero vectors; then go through the list and discard each $v_j$ that lies in the span of the vectors kept before it. By Theorem 8.5(c) the span never changes, and the vectors kept are independent: a dependence relation among them would, by Theorem 8.5(c), produce a kept vector lying in the span of earlier kept vectors. (b) If $\mathcal{B}$ and $\mathcal{B}'$ are bases with $n$ and $n'$ elements, then $\mathcal{B}$ is independent and $\mathcal{B}'$ spans, so $n\le n'$ by Theorem 8.7; exchanging roles gives $n'\le n$. (An infinite independent set cannot exist in $V$ either: its first $m+1$ vectors would contradict Theorem 8.7.) ∎
Standard values (each with its standard basis): $\dim\mathbb{F}^n=n$ (basis $e_1,\dots,e_n$); $\dim M_{m\times n}(\mathbb{F})=mn$ (the matrix units $E_{ij}$, with $1$ in place $(i,j)$); $\dim P_n(\mathbb{F})=n+1$ (basis $1,x,\dots,x^n$); $\dim_{\mathbb{R}}\mathbb{C}=2$ (basis $1,i$) while $\dim_{\mathbb{C}}\mathbb{C}=1$; $\mathbb{F}[x]$, $\mathbb{F}^{\mathbb{N}}$ and $C[a,b]$ are infinite-dimensional (the monomials $1,x,x^2,\dots$ are independent in each). And $\dim_{\mathbb{Q}}\mathbb{R}=\infty$: a $\mathbb{Q}$-space of finite dimension $n$ is in bijection with $\mathbb{Q}^n$ by coordinates, hence countable (§1.1), while $\mathbb{R}$ is not.
- every independent set has at most $n$ vectors, and every spanning set has at least $n$;
- $n$ independent vectors form a basis, and $n$ vectors that span form a basis;
- every independent set can be extended to a basis, and every spanning set contains a basis;
- every subspace $W$ is finite-dimensional with $\dim W\le n$, and $\dim W=n$ if and only if $W=V$.
Proof. Fix a basis $\mathcal{B}$ of $V$ with $n$ vectors. (1) Theorem 8.7 with the spanning set $\mathcal{B}$ bounds independent sets by $n$; with the independent set $\mathcal{B}$ it shows every spanning set has at least $n$ vectors. (3) Let $S$ be independent. If $\operatorname{span}S\ne V$, choose $v\notin\operatorname{span}S$; then $S\cup\{v\}$ is independent by Theorem 8.5(b). By (1) this can happen at most $n-|S|$ times, so the process stops at an independent spanning set — a basis containing $S$. A finite spanning set contains a basis by Theorem 8.8(a). (2) If $n$ independent vectors did not span, (3) would extend them to a basis with more than $n$ vectors, contradicting Theorem 8.8(b). If $n$ vectors span, they contain a basis by (3), which has exactly $n$ vectors — so it is the whole list. (4) Independent subsets of $W$ are independent in $V$, so they have at most $n$ vectors; choose one, $S$, of the largest possible size. For $w\in W\setminus\operatorname{span}S$, $S\cup\{w\}$ would be a larger independent subset of $W$ (Theorem 8.5(b)), so $S$ spans $W$: it is a basis of $W$ and $\dim W=|S|\le n$. If $\dim W=n$, then $S$ is $n$ independent vectors of $V$, a basis of $V$ by (2), and $W=\operatorname{span}S=V$. ∎
Proof (sketch). Order the independent subsets containing a given independent set $S_0$ by inclusion. The union of a chain of independent sets is independent (a dependence relation involves finitely many vectors, all of which lie in one member of the chain). By Zorn's lemma there is a maximal independent set $S\supseteq S_0$, and by Theorem 8.5(b) maximality forces $\operatorname{span}S=V$. The equality of cardinalities for infinite bases is a counting argument: each vector of one basis is a finite combination of the other. ∎
No Hamel basis of $\mathbb{R}$ over $\mathbb{Q}$ or of $C[0,1]$ over $\mathbb{R}$ can be written down explicitly; in analysis one uses "bases" that allow infinite sums instead (Fourier series, orthonormal bases in §10.1). For CSIR purposes the finite-dimensional statements of Theorem 8.9 are what matter.
- A span in $\mathbb{F}^n$. Put the vectors as rows of a matrix and row-reduce; row operations do not change the span of the rows, and the nonzero rows of an echelon form are a basis. (To keep a basis made of the original vectors, put them as columns instead and keep the pivot columns — §8.3.)
- A solution space $\{x:Ax=0\}$. Solve for the pivot variables in terms of the free ones; setting one free variable equal to $1$ and the others to $0$ gives one basis vector per free variable.
- Polynomials and matrices. Replace each vector by its coordinate vector in the standard basis and use 1–2: coordinates turn $P_n$ into $\mathbb{F}^{n+1}$ and $M_{m\times n}$ into $\mathbb{F}^{mn}$ without changing independence (Theorem 8.6).
- "Dimension of the space of all … with conditions". Count the free parameters after the conditions are imposed, and check that the conditions are independent (four conditions on a $9$-dimensional space give dimension $5$ only if none of them follows from the others).
- Functions. To prove $f_1,\dots,f_k$ independent, evaluate a supposed relation $\sum a_if_i=0$ at well-chosen points, differentiate it, or integrate it against suitable functions. To prove them dependent, exhibit a relation.
Sums, Direct Sums and the Dimension Formula
- the sum $W_1+\cdots+W_k$ is direct;
- if $w_1+\cdots+w_k=0$ with $w_i\in W_i$, then every $w_i=0$;
- $W_j\cap\left(\sum_{i\ne j}W_i\right)=\{0\}$ for every $j$;
- (when each $W_i$ is finite-dimensional) putting together bases of $W_1,\dots,W_k$ gives a basis of the sum;
- (when each $W_i$ is finite-dimensional) $\dim\sum_iW_i=\sum_i\dim W_i$.
Proof. (1)⇒(2): $0=0+\cdots+0$ is one representation of $0$, so it is the only one. (2)⇒(1): if $\sum w_i=\sum w_i'$ then $\sum(w_i-w_i')=0$ with $w_i-w_i'\in W_i$, so $w_i=w_i'$. (2)⇒(3): if $w_j=\sum_{i\ne j}w_i$ lies in the intersection, then $w_j-\sum_{i\ne j}w_i=0$ forces $w_j=0$. (3)⇒(2): if $\sum w_i=0$ and some $w_i\ne0$, let $j$ be such an index; then $w_j=-\sum_{i\ne j}w_i$ is a nonzero vector of $W_j\cap\sum_{i\ne j}W_i$. (2)⇔(4): the combined list always spans the sum. A linear relation among the combined basis vectors groups as $w_1+\cdots+w_k=0$, where $w_i$ is the part using the basis of $W_i$. Under (2) each $w_i=0$, so (each $W_i$-basis being independent) all coefficients vanish; conversely, under (4), writing each $w_i$ in its basis turns $\sum w_i=0$ into a relation, whose coefficients are all $0$. (4)⇒(5) is immediate. (5)⇒(4): the combined list has length $\sum\dim W_i$ and spans the sum; under (5) this length equals $\dim(W_1+\cdots+W_k)$, and a spanning list whose length equals the dimension is a basis (Theorem 8.9(2)). ∎
Notice what condition 3 does not say: for $k\ge3$ it is not enough that the subspaces meet pairwise in $\{0\}$. Three different lines through the origin in $\mathbb{R}^2$ meet pairwise in $\{0\}$, but their sum is $\mathbb{R}^2$, of dimension $2\ne1+1+1$.
Proof. $U\cap W$ is a subspace of $U$, hence finite-dimensional; let $z_1,\dots,z_r$ be a basis. By Theorem 8.9(3) extend it to a basis $z_1,\dots,z_r,u_1,\dots,u_s$ of $U$ and, separately, to a basis $z_1,\dots,z_r,w_1,\dots,w_t$ of $W$. We claim that $$z_1,\dots,z_r,\ u_1,\dots,u_s,\ w_1,\dots,w_t$$ is a basis of $U+W$; then $\dim(U+W)=r+s+t=(r+s)+(r+t)-r$, which is the formula. Spanning: each $u+w$ is a combination of the two bases, hence of the list. Independence: suppose $$\sum a_iz_i+\sum b_ju_j+\sum c_kw_k=0.$$ Then $x=\sum c_kw_k$ lies in $W$, and $x=-\sum a_iz_i-\sum b_ju_j$ lies in $U$; so $x\in U\cap W$ and $x=\sum d_iz_i$ for some scalars $d_i$. Now $\sum d_iz_i-\sum c_kw_k=0$ is a relation in the basis $z,w$ of $W$, so all $c_k=0$ (and $d_i=0$). The original relation becomes $\sum a_iz_i+\sum b_ju_j=0$, a relation in the basis $z,u$ of $U$, so all $a_i=b_j=0$. The final inequality follows from $\dim(U+W)\le n$ (Theorem 8.9(4)). ∎
Proof. Extend a basis $u_1,\dots,u_k$ of $U$ to a basis $u_1,\dots,u_k,v_1,\dots,v_m$ of $V$ (Theorem 8.9(3)) and let $W=\operatorname{span}\{v_1,\dots,v_m\}$. The combined list is a basis of $V=U+W$, so the sum is direct by Theorem 8.11(4), and $\dim W=m=\dim V-\dim U$. For non-uniqueness, take $u=u_1$ and $v=v_1$ and replace $v_1$ by $v_1+tu_1$ for a scalar $t$: the list $u_1,\dots,u_k,v_1+tu_1,v_2,\dots,v_m$ is still a basis, so $W_t=\operatorname{span}\{v_1+tu_1,v_2,\dots,v_m\}$ is a complement for every $t$. These are different subspaces for different $t$: if $v_1+tu_1\in W_s$ with $s\ne t$, then $(t-s)u_1=(v_1+tu_1)-(v_1+su_1)$ lies in $W_s\cap U=\{0\}$, which is false. ∎
Quotient Spaces and Counting over Finite Fields
Proof. (a) $u+W=v+W$ iff $u\sim v$ iff $u-v\in W$, since cosets are equivalence classes. If $u+W=u'+W$ and $v+W=v'+W$, then $(u+v)-(u'+v')=(u-u')+(v-v')\in W$ and $au-au'=a(u-u')\in W$, so the sum and the scalar multiple do not depend on the representatives chosen. Each axiom for $V/W$ follows from the same axiom in $V$, e.g. $a\big((u+W)+(v+W)\big)=a(u+v)+W$, which equals $(au+av)+W=a(u+W)+a(v+W)$; the zero is $0+W=W$ and $-(v+W)=(-v)+W$. (b) Spanning: write $v=\sum a_iw_i+\sum b_jv_j$; since $\sum a_iw_i\in W$, $v+W=\sum b_j(v_j+W)$. Independence: if $\sum b_j(v_j+W)=0+W$, then $\sum b_jv_j\in W$, so $\sum b_jv_j=\sum c_iw_i$; this is a relation in the basis of $V$, so every $b_j=0$. Thus $\dim V/W=m=\dim V-\dim W$. ∎
Two illustrations. In $V=P_n(\mathbb{R})$ with $W=\{p:p(0)=0\}$ (dimension $n$), two polynomials are congruent modulo $W$ iff they have the same constant term, so $V/W$ is a line, $\dim=(n+1)-n=1$. In the infinite-dimensional space $C[0,1]$ with $W=\{f:f(0)=0\}$, the same reasoning gives $\dim C[0,1]/W=1$ even though both $C[0,1]$ and $W$ are infinite-dimensional — the formula "$\dim V-\dim W$" would read $\infty-\infty$. Quotients reappear in §8.2 as $V/\ker T\cong\operatorname{im}T$.
Over a finite field everything can be counted, and Part B problems love the answers.
- $|V|=q^n$;
- the number of ordered lists $(v_1,\dots,v_k)$ of $k$ linearly independent vectors is $(q^n-1)(q^n-q)\cdots(q^n-q^{k-1})$; for $k=n$ this counts the ordered bases of $V$;
- the number of $k$-dimensional subspaces of $V$ is the Gaussian binomial coefficient $$\binom nk_q=\frac{(q^n-1)(q^n-q)\cdots(q^n-q^{k-1})}{(q^k-1)(q^k-q)\cdots(q^k-q^{k-1})};$$
- $\binom nk_q=\binom n{n-k}_q$; in particular the number of lines (1-dimensional subspaces) and of hyperplanes ($(n-1)$-dimensional subspaces) are both $\dfrac{q^n-1}{q-1}$.
Proof. (1) By Theorem 8.6, $v\mapsto[v]_{\mathcal{B}}$ is a bijection $V\to\mathbb{F}_q^n$, and $\mathbb{F}_q^n$ has $q^n$ elements. (2) Choose the vectors one at a time. $v_1$ may be any nonzero vector: $q^n-1$ choices. If $v_1,\dots,v_j$ are independent, then $v_1,\dots,v_j,v_{j+1}$ is independent iff $v_{j+1}\notin\operatorname{span}\{v_1,\dots,v_j\}$ (Theorem 8.5(b), (c)); that span has dimension $j$, hence $q^j$ elements by (1), leaving $q^n-q^j$ choices. Multiply. (3) Count the set of pairs $(W,(v_1,\dots,v_k))$ in which $W$ is a $k$-dimensional subspace and $(v_1,\dots,v_k)$ is an ordered basis of $W$, in two ways. Each independent $k$-list spans exactly one $k$-dimensional subspace, so the number of pairs is the number in (2). Each $k$-dimensional $W$ has, by (2) applied to $W$ itself, $(q^k-1)\cdots(q^k-q^{k-1})$ ordered bases. Dividing gives (3). (4) Divide the $i$-th factor of the numerator and of the denominator by $q^i$: $$\frac{q^n-q^i}{q^k-q^i}=\frac{q^{n-i}-1}{q^{k-i}-1}.$$ So with $[m]!=(q-1)(q^2-1)\cdots(q^m-1)$ we get $\binom nk_q=\dfrac{[n]!}{[k]!\,[n-k]!}$, which is symmetric in $k$ and $n-k$. For $k=1$ the formula gives $\tfrac{q^n-1}{q-1}$. ∎
Letting $q\to1$ in $\frac{q^m-1}{q-1}=1+q+\cdots+q^{m-1}\to m$ turns $\binom nk_q$ into the ordinary binomial coefficient $\binom nk$ — subspaces of $\mathbb{F}_q^n$ behave like "$q$-analogues" of subsets of an $n$-element set.
- A union of subspaces is rarely a subspace: the two axes in $\mathbb{R}^2$; $U\cup W$ is a subspace only if one contains the other (Theorem 8.2(c)). The sum $U+W$ is the right replacement.
- Finite fields are different: $\mathbb{F}_2^2$ is the union of its three proper subspaces $\{0,e_1\}$, $\{0,e_2\}$, $\{0,e_1+e_2\}$; over an infinite field no finite union of proper subspaces is the whole space (Theorem 8.3).
- Pairwise independent is not independent: $(1,0),(0,1),(1,1)$ — any two are independent, all three are not.
- Pairwise trivial intersections do not make a sum direct: three distinct lines through $0$ in $\mathbb{R}^2$. Use Theorem 8.11(3) or (5).
- The lattice of subspaces is not distributive: for three distinct lines $U,W,X$ in $\mathbb{R}^2$, $U\cap(W+X)=U$ but $(U\cap W)+(U\cap X)=\{0\}$. Only $\supseteq$ holds in general.
- Complements are not unique, and "complement" is not the set complement: every line other than the $x$-axis is a complement of the $x$-axis in $\mathbb{R}^2$; the set $V\setminus W$ never contains $0$, so it is never a subspace.
- Dimension depends on the field: $\dim_{\mathbb{C}}\mathbb{C}^n=n$, $\dim_{\mathbb{R}}\mathbb{C}^n=2n$, $\dim_{\mathbb{Q}}\mathbb{R}=\infty$ (in fact the cardinality of a Hamel basis is $\mathfrak{c}$).
- Edge cases: a set containing $0$ is dependent; a single nonzero vector is independent; $\varnothing$ is independent with $\operatorname{span}\varnothing=\{0\}$, so $\dim\{0\}=0$.
- Infinite dimension breaks the counting rules: $xP$ ($=\{xp:p\in\mathbb{R}[x]\}$) is a proper subspace of $\mathbb{R}[x]$ "of the same size"; $\dim W=\dim V\Rightarrow W=V$ and $\dim V/W=\dim V-\dim W$ make no sense when $\dim V=\infty$.
- $e_1,e_2,e_3,\dots$ is not a basis of $\mathbb{R}^{\mathbb{N}}$: they are independent, but finite combinations give only the sequences with finitely many nonzero terms; $(1,1,1,\dots)$ is not in their span. Linear algebra allows only finite sums.
- $\operatorname{Sym}\oplus\operatorname{Skew}$ needs $2\ne0$: over $\mathbb{F}_2$ symmetric and skew-symmetric matrices coincide (Example 5(c)).
- Independence of functions depends on the domain, and a vanishing Wronskian proves nothing: $x$ and $|x|$ are independent on $[-1,1]$ but equal on $[0,1]$; $x^2$ and $x|x|$ have Wronskian $x^2\cdot2|x|-2x\cdot x|x|=0$ everywhere, yet are independent on $\mathbb{R}$ (evaluate at $\pm1$).
- Conditions may be dependent: the $2n$ conditions "all row and column sums are $0$" cut the dimension by $2n-1$, not $2n$ (Example 4(d)).
Exercises
- 1 Using only the axioms, prove that $-(-v)=v$ and $a(u-v)=au-av$ in every vector space.
- 2 On $V=(0,\infty)$ define $x\oplus y=xy$ and $a\odot x=x^a$ ($a\in\mathbb{R}$). Show that $V$ is a real vector space. What are its zero vector and the negative of $x$?
- 3 Which of these are subspaces of $\mathbb{R}^3$? (a) $\{x:x_1=2x_2\}$; (b) $\{x:x_1\ge0\}$; (c) $\{x:x_1^2=x_2^2\}$; (d) $\{x:x_1+x_2+x_3=0=x_1-x_3\}$.
- 4 Which of these are subspaces of $M_n(\mathbb{R})$ ($n\ge2$)? (a) upper triangular matrices; (b) matrices of trace $0$; (c) $\{A:A^2=0\}$; (d) $\{A:AB=BA\}$ for a fixed $B$; (e) singular matrices.
- 5 Which of these are subspaces of $C[0,1]$? (a) $\{f:f(0)=2f(1)\}$; (b) $\{f:f(\tfrac12)=1\}$; (c) the differentiable functions; (d) the monotone functions; (e) $\{f:|f(x)|\le1\text{ for all }x\}$.
- 6 Prove that $\mathbb{R}^2$ is not the union of finitely many lines through the origin, and list three proper subspaces of $\mathbb{F}_2^2$ whose union is $\mathbb{F}_2^2$. What is the smallest number of proper subspaces whose union is $\mathbb{F}_3^2$?
- 7 Show that the real sequences satisfying $x_{n+2}=3x_{n+1}-2x_n$ for all $n$ form a subspace of $\mathbb{R}^{\mathbb{N}}$, of dimension $2$, with basis $(1,1,1,\dots)$ and $(2^n)_{n\ge1}$.
- 8 Let $U,W\le V$. Prove that $U+W=\operatorname{span}(U\cup W)$ and that $U+W=U$ iff $W\subseteq U$.
- 1 Are $(1,2,3),(4,5,6),(7,8,9)$ linearly independent in $\mathbb{R}^3$? If not, find a dependence relation.
- 2 For which real $t$ are $(1,1,t),(1,t,1),(t,1,1)$ a basis of $\mathbb{R}^3$?
- 3 Show that $1,\ x-1,\ (x-1)^2,\ (x-1)^3$ is a basis of $P_3(\mathbb{R})$ and find the coordinates of $x^3$ in it.
- 4 Prove that $\sin x,\sin2x,\sin3x$ are linearly independent in $C[0,\pi]$.
- 5 Find the dimension of the space of real $n\times n$ symmetric matrices with zero diagonal, and of the space of upper triangular $n\times n$ matrices.
- 6 Let $v_1=(1,2,0,1)$, $v_2=(2,4,1,1)$, $v_3=(0,0,1,-1)$, $v_4=(1,2,1,0)$. Find a basis of $\operatorname{span}\{v_1,\dots,v_4\}$ and extend it to a basis of $\mathbb{R}^4$.
- 7 Prove that $v_1,\dots,v_n$ are independent if and only if $v_1,\ v_1+v_2,\ \dots,\ v_1+v_2+\cdots+v_n$ are independent.
- 8 Show that $\dim_{\mathbb{R}}\mathbb{C}^n=2n$ and write down a basis. Is $\{(1,i),(i,-1)\}$ independent over $\mathbb{C}$? Over $\mathbb{R}$?
- 9 Prove, using countability, that $\dim_{\mathbb{Q}}\mathbb{R}$ is not finite. Why does this not follow merely from the existence of infinitely many irrational numbers?
- 10 Show that $x$ and $|x|$ are independent in $C[-1,1]$ but their restrictions to $[0,1]$ are dependent in $C[0,1]$.
- 1 In $\mathbb{R}^4$ let $U=\{x:x_1+x_2=0\}$ and $W=\{x:x_3+x_4=0\}$. Find $\dim U$, $\dim W$, $\dim(U\cap W)$ and $\dim(U+W)$, and check the dimension formula.
- 2 Write $A=\begin{pmatrix}2&5\\-1&0\end{pmatrix}$ as a symmetric plus a skew-symmetric matrix.
- 3 Prove that two distinct $3$-dimensional subspaces of $\mathbb{R}^4$ meet in a subspace of dimension exactly $2$.
- 4 Let $\dim V=n$ and $U,W\le V$ with $\dim U+\dim W\gt n$. Prove that $U\cap W$ contains a nonzero vector.
- 5 Give three subspaces $W_1,W_2,W_3$ of $\mathbb{R}^3$, each meeting the others pairwise only in $0$, whose sum is not direct.
- 6 Find all complements of the line $L=\operatorname{span}\{(1,1)\}$ in $\mathbb{R}^2$, and show that the line $\operatorname{span}\{(1,1,0)\}$ has infinitely many complements in $\mathbb{R}^3$.
- 7 Let $U=\{p\in P_3(\mathbb{R}):p(1)=0\}$ and $W=\{p\in P_3(\mathbb{R}):p(-1)=0\}$. Find $\dim U$, $\dim W$, $\dim(U\cap W)$, and decide whether $U+W=P_3(\mathbb{R})$.
- 8 Prove that $V=U\oplus W$ if and only if $V=U+W$ and $\dim V=\dim U+\dim W$ ($V$ finite-dimensional).
- 1 Let $W=\{p\in P_5(\mathbb{R}):p(1)=p(2)=0\}$. Find $\dim W$ and $\dim P_5(\mathbb{R})/W$.
- 2 Describe the cosets of $W=\operatorname{span}\{(1,1,1)\}$ in $\mathbb{R}^3$ geometrically and find a basis of $\mathbb{R}^3/W$.
- 3 Let $W\le V$ and $U$ a complement of $W$. Prove that $u\mapsto u+W$ is a bijection from $U$ onto $V/W$ preserving sums and scalar multiples.
- 4 How many vectors does $\mathbb{F}_3^4$ have? How many ordered bases does $\mathbb{F}_3^2$ have?
- 5 How many $1$-dimensional subspaces does $\mathbb{F}_5^3$ have?
- 6 How many $2$-dimensional subspaces does $\mathbb{F}_2^5$ have? How many $3$-dimensional ones?
- 7 Find the total number of subspaces of $\mathbb{F}_2^4$.
- 8 Show that a line $L$ in $\mathbb{F}_q^2$ has exactly $q$ complements, and that the quotient $\mathbb{F}_q^n/W$ by a $k$-dimensional subspace has $q^{n-k}$ elements.
- 9 Applied. A binary linear code of length $7$ and dimension $4$ is a $4$-dimensional subspace of $\mathbb{F}_2^7$; its vectors are the codewords that may be transmitted. How many codewords does each such code have, and how many different such codes are there?
E1. CSIR Part B GATE MA Let $V$ be the space of real $3\times3$ matrices whose three row sums and three column sums are all equal to one another. Then $\dim V$ is (A) $4$; (B) $5$; (C) $6$; (D) $9$.
E2. CSIR Part B The number of $2$-dimensional subspaces of the vector space $\mathbb{F}_3^4$ over the field with three elements is (A) $40$; (B) $120$; (C) $130$; (D) $1040$.
E3. CSIR Part B Let $U$ and $W$ be subspaces of $\mathbb{R}^7$ with $\dim U=4$ and $\dim W=5$. Which statement is true? (A) $\dim(U\cap W)$ can be $1$; (B) $\dim(U\cap W)\ge2$ always; (C) $\dim(U\cap W)=2$ always; (D) $\dim(U\cap W)$ can be $5$.
E4. CSIR Part C GATE MA Let $V=P_4(\mathbb{R})$, the real polynomials of degree at most $4$. Which of the following are true? (One or more options may be correct.) (A) $\{p:p(1)=p(-1)\}$ is a subspace of dimension $4$; (B) $\{p:p(0)=1\}$ is a subspace of dimension $4$; (C) $\{p:p(x)=p(-x)\text{ for all }x\}$ is a subspace of dimension $2$; (D) $\{p:p(1)=p'(1)=0\}$ is a subspace of dimension $3$.
E5. CSIR Part C Which of the following are true? (A) $\mathbb{R}$ is an infinite-dimensional vector space over $\mathbb{Q}$. (B) $1,\sqrt2,\sqrt3$ are linearly independent over $\mathbb{Q}$. (C) Every vector space over $\mathbb{Q}$ that is countable as a set is finite-dimensional. (D) The real sequences with $x_{n+2}=x_{n+1}+x_n$ for all $n$ form a $2$-dimensional subspace of $\mathbb{R}^{\mathbb{N}}$.
E6. CSIR Part C Let $U,W,X$ be subspaces of a finite-dimensional vector space $V$ over $\mathbb{R}$. Which of the following are necessarily true? (A) $U\cup W$ is a subspace if and only if $U\subseteq W$ or $W\subseteq U$. (B) If $U+W=V$ and $\dim U+\dim W=\dim V$, then $V=U\oplus W$. (C) If $U\cap W=U\cap X=W\cap X=\{0\}$, then the sum $U+W+X$ is direct. (D) $U\cap(W+X)=(U\cap W)+(U\cap X)$.
Suggested plan — 2 lectures × 60 min (a third if the class has not seen abstract vector spaces).
- Spaces, subspaces, independence. Axioms quickly (Definition 8.1) with the zoo of examples; Theorem 8.1(d) and why $\mathbb{Z}_6$ fails. Subspace test and Example 1 as a class poll — insist on (h), "subspace over which field?". Theorem 8.2(c) and Theorem 8.3 with its four-line proof (a CSIR favourite). Span, independence, the dependence lemma; then the Steinitz exchange theorem in full on the board — it is the only genuinely clever proof of the section. Project Interactive 1: let it play through the dependent position, then choose $v=2b_1$ to show that $v$ survives the collapse because it lies on the line.
- Dimension at work. Theorem 8.9 (extension of independent sets), Examples 2 and 4 — Example 4(d) is the model for "dimension of the space of all matrices with…" questions. Direct sums (Theorem 8.11), the dimension formula with its proof, Examples 5–6. Quotients in ten minutes (Theorem 8.14). Finish with Theorem 8.15 and Interactive 2 at $q=3$: count the four lines, then switch to cosets; then use the Gaussian-binomial readout to check E2.
Discussion questions. (1) Why does the Steinitz argument need the $u$'s to be independent but not the $w$'s? What is the analogous statement for finite sets and injective/surjective maps? (2) $\mathbb{F}_2^2$ is a union of three proper subspaces. What is the least number of proper subspaces whose union is $\mathbb{F}_q^n$, and where does the proof of Theorem 8.3 use that $\mathbb{F}$ is infinite? (3) Which statements of this section survive in infinite dimension, and which need $\dim V\lt\infty$?
Misconceptions to watch for. Confusing span with union; believing pairwise independence (or pairwise zero intersection) is enough; counting conditions without checking their independence; forgetting that $0$ must lie in a subspace; treating $\dim$ as independent of the field; writing infinite linear combinations; thinking a complement is unique or is the set-theoretic complement.
Suggested homework. I(2, 4, 6, 7), II(2, 3, 6, 8, 10), III(1, 3, 5, 7), IV(1, 5, 6, 9); Exam corner E1, E4, E6.
Research question. Among the $11811$ four-dimensional subspaces of $\mathbb{F}_2^7$ (Exercise IV.9), which ones can protect four data bits against any single transmission error — and why are there exactly that many?
Why it matters. Error-correcting codes are subspaces over finite fields. Memory chips in servers (ECC RAM), deep-space probes, mobile networks, QR codes and data storage all add redundant bits chosen by linear algebra, so that a receiver can detect and repair errors caused by noise or cosmic rays. Richard Hamming invented the simplest such code at Bell Labs in 1950 after his weekend computer jobs kept failing on single bit errors.
What to do.
- Let $H$ be the $3\times7$ matrix over $\mathbb{F}_2$ whose columns are the seven nonzero vectors of $\mathbb{F}_2^3$, and let $C=\{x\in\mathbb{F}_2^7:Hx=0\}$. Show that $C$ is a $4$-dimensional subspace (find a basis), so it has $16$ codewords.
- The weight of $x$ is its number of $1$s, and the minimum distance of a code is the least weight of a nonzero codeword. Show that $C$ has minimum distance $3$: no codeword of weight $1$ or $2$ exists because the columns of $H$ are nonzero and distinct. Explain why minimum distance $3$ lets the receiver correct one flipped bit (the syndrome $Hy$ of a received word $y$ names the position of the error).
- By computer, run through all $11811$ four-dimensional subspaces of $\mathbb{F}_2^7$ (or, more cleverly, through all $3\times7$ matrices $H$ of rank $3$) and count those with minimum distance $3$. Is any of them better (distance $4$)?
- Explain your count with Theorem 8.15: two orderings of the columns of $H$ give the same code exactly when their row spaces agree, i.e. when they differ by one of the $168$ invertible $3\times3$ matrices.
Tools: Python with itertools (vectors as tuples of $0$s and $1$s, arithmetic mod $2$); or any computer algebra system that works over finite fields.
Hand in: A one-page note: a basis of $C$, the decoding rule with one worked example, your count of single-error-correcting codes, and the formula that explains it.
Going further. Read about the Hamming bound and perfect codes, about Reed–Solomon codes (subspaces of $\mathbb{F}_{256}^{n}$ used in QR codes and CDs), or about the extended Hamming code of length $8$, which detects double errors.
🧪 Self-check quiz
Q1. The dimension of the space of real $3\times3$ skew-symmetric matrices is
Q2. Which subset of $\mathbb{R}^2$ is a subspace?
Q3. If $U,W\le\mathbb{R}^5$ with $\dim U=3$ and $\dim W=4$, the smallest possible value of $\dim(U\cap W)$ is
Q4. The number of $1$-dimensional subspaces of $\mathbb{F}_2^3$ is
Q5. Let $V=P_4(\mathbb{R})$ and $W=\{p\in V:p(0)=0\}$. Then $\dim V/W$ is