Algebra

Vector spaces

Sets of objects that can be added and scaled, the setting for all of linear algebra.

IntuitionIntuition: add and scale — that is all you need

Arrows in the plane can be placed tip-to-tail to add them, and stretched or shrunk by a number. That is already enough structure to do a surprising amount of mathematics — and the surprise is that the exact same two operations, addition and scalar multiplication, also make sense for polynomials (add two polynomials, multiply one by a number), for matrices of the same size, and for functions (add two functions pointwise, scale a function by a constant). A vector space is any set equipped with these two operations obeying the same handful of sensible rules that arrows in the plane already obey; once a set is recognized as a vector space, every theorem proved once for "vectors in general" applies immediately to arrows, polynomials, matrices, and functions alike.

Two column vectors

\mathbf{v}_1 = (a_{11}, a_{21})

and

\mathbf{v}_2 = (a_{12}, a_{22})

form a basis of

\mathbb{R}^2

whenever they are not collinear (

\det A \neq 0

), spanning the coordinate grid shown.

SchoolDefinition: vector space axioms

Definition: Vector space

A vector space over $\mathbb{R}$ is a set $V$ together with an addition $\mathbf{u}+\mathbf{v}\in V$ and a scalar multiplication $\alpha\mathbf{u}\in V$ (for $\alpha\in\mathbb{R}$ ) such that addition is commutative and associative, there is a zero vector $\mathbf{0}$ with $\mathbf{u}+\mathbf{0}=\mathbf{u}$ , every $\mathbf{u}$ has an additive inverse $-\mathbf{u}$ , scalar multiplication is compatible with real-number multiplication and distributes over both vector addition and scalar addition, and $1\cdot\mathbf{u}=\mathbf{u}$ . Concretely, the two distributive laws are $\alpha(\mathbf{u}+\mathbf{v})=\alpha\mathbf{u}+\alpha\mathbf{v},\quad (\alpha+\beta)\mathbf{u}=\alpha\mathbf{u}+\beta\mathbf{u}$ . Familiar examples include $\mathbb{R}^n$ , the space $P_n$ of polynomials of degree at most $n$ , the space $M_{m\times n}$ of matrices, and the space $C[a,b]$ of continuous functions on an interval.

\alpha(\mathbf{u}+\mathbf{v})=\alpha\mathbf{u}+\alpha\mathbf{v},\quad (\alpha+\beta)\mathbf{u}=\alpha\mathbf{u}+\beta\mathbf{u}

These distributive laws say that scaling a sum of vectors is the same as scaling each vector separately and adding the results, and that adding two scalars before multiplying is the same as multiplying separately and adding — these two rules are exactly what make "linear" combinations of vectors well-behaved, and every theorem about vector spaces is ultimately built from just these axioms.

Definition: Basis and dimension

A set of vectors $\{v_1,\dots,v_k\}$ is linearly independent if no nontrivial combination $c_1v_1+\cdots+c_kv_k$ equals $\mathbf{0}$ (equivalently, no vector in the set is a combination of the others), and it spans $V$ if every vector of $V$ is a combination of them, i.e. $\operatorname{span}(v_1,\dots,v_k)=\Big\{\textstyle\sum_{i=1}^k c_iv_i : c_i\in\mathbb{R}\Big\}$ equals all of $V$ . A basis of $V$ is a set that is both linearly independent and spanning $V$ ; the dimension $\dim(V)$ is the number of vectors in a basis — well defined precisely because, as the next theorem shows, every basis of $V$ has the same size.

\operatorname{span}(v_1,\dots,v_k)=\Big\{\textstyle\sum_{i=1}^k c_iv_i : c_i\in\mathbb{R}\Big\}

For example, the standard basis $e_1=(1,0,\dots,0),\dots,e_n=(0,\dots,0,1)$ of $\mathbb{R}^n$ has exactly $n$ vectors, so $\dim(\mathbb{R}^n)=n$ ; and $1,x,x^2,\dots,x^n$ is a basis of $P_n$ with $n+1$ vectors, so $\dim(P_n)=n+1$ .

Dimension of familiar vector spaces
Vector space	A basis	Dimension
$\mathbb{R}^n$	$e_1,\dots,e_n$	$n$
$P_n$ (polynomials of degree $\leq n$ )	$1,x,\dots,x^n$	$n+1$
$M_{m\times n}$ (matrices)	matrices $E_{ij}$ with a single $1$	$mn$
$C[a,b]$ (continuous functions)	no finite basis	$\infty$

UndergraduateTheorems: every basis has the same size

Theorem: Steinitz exchange lemma

If $\{v_1,\dots,v_m\}$ spans a vector space $V$ and $\{w_1,\dots,w_k\}\subseteq V$ is linearly independent, then $k\leq m$ : an independent set can never be larger than a spanning set. Moreover, $k$ of the $v_i$ can be replaced by $w_1,\dots,w_k$ so that the resulting set still spans $V$ .

Why is it true?

Independent vectors cannot outnumber a spanning set, because each new independent vector can always be "traded in" for one of the spanning vectors without breaking the spanning property — the trade is only blocked once every spanning vector has already been used up, and at that point there is no room left to add another independent vector without contradiction, which is exactly what pins down $k\leq m$ .

Proof

Argue by induction on $k$ , the number of $w$ 's exchanged in so far. For $k=0$ the inequality $0\leq m$ is trivial, and no exchange is needed. Suppose inductively that $w_1,\dots,w_{k-1}$ have already been exchanged in for $k-1$ of the original $v_i$ 's (relabel so these are $v_1,\dots,v_{k-1}$ ), so that $\{w_1,\dots,w_{k-1},v_k,\dots,v_m\}$ still spans $V$ .

If $k-1$ already equals $m$ , every $v_i$ has been used up, so $\{w_1,\dots,w_{k-1}\}$ alone spans $V$ ; but then $w_k\in V$ would be a linear combination of $w_1,\dots,w_{k-1}$ , contradicting the linear independence of $\{w_1,\dots,w_k\}$ . So this case cannot occur while $k\leq m$ is still to be shown for the current $k$ — precisely, it shows $k-1<m$ , i.e. $k\leq m$ , immediately.

Otherwise $k-1<m$ , so at least one $v_j$ (among $v_k,\dots,v_m$ ) remains. Since $\{w_1,\dots,w_{k-1},v_k,\dots,v_m\}$ spans $V$ , write $w_k$ as a combination $w_k=\lambda_1w_1+\cdots+\lambda_{k-1}w_{k-1}+\mu_1v_{j_1}+\cdots+\mu_{m-k+1}v_{j_{m-k+1}}$ . If every coefficient $\mu_1,\dots$ on the remaining $v$ 's were $0$ , then $w_k$ would be a combination of $w_1,\dots,w_{k-1}$ alone, again contradicting independence — so some remaining $v_j$ has a nonzero coefficient.

Solve that equation for $v_j$ (dividing by its nonzero coefficient), expressing $v_j$ as a combination of $w_1,\dots,w_k$ and the other remaining $v$ 's. Substituting this expression for $v_j$ wherever it appears shows that $\{w_1,\dots,w_k\}$ together with the remaining $v$ 's (minus $v_j$ ) still spans $V$ — one more $v$ has been successfully exchanged for $w_k$ , completing the inductive step and confirming $k\leq m$ .

Theorem: Dimension theorem

Any two finite bases of the same vector space $V$ have the same number of elements: if $B_1$ has $m$ vectors and $B_2$ has $k$ vectors, then $\dim(V)=m=k$ . Hence $\dim(V)$ is a well-defined invariant of $V$ , not an artifact of which basis was chosen.

Why is it true?

A basis is simultaneously a spanning set and an independent set, so applying the exchange lemma once in each direction — once treating $B_1$ as the spanning set and $B_2$ as independent, once the other way around — squeezes the two sizes between each other until they must be equal.

Proof

Let $B_1=\{v_1,\dots,v_m\}$ and $B_2=\{w_1,\dots,w_k\}$ both be bases of $V$ . Since $B_1$ spans $V$ (it is a basis) and $B_2$ is linearly independent (it is a basis), the exchange lemma proved above applies directly with $B_1$ playing the role of the spanning set and $B_2$ the independent set, giving $k\leq m$ .

Symmetrically, since $B_2$ spans $V$ and $B_1$ is linearly independent, apply the exchange lemma again with the roles swapped — $B_2$ as the spanning set, $B_1$ as the independent set — giving $m\leq k$ .

Combining the two inequalities $k\leq m$ and $m\leq k$ forces $k=m$ : the two bases have exactly the same number of vectors.

Since this argument places no restriction on which particular finite bases $B_1,B_2$ were chosen, every finite basis of $V$ has this same common size. This justifies defining $\dim(V)$ to be that common size — it is an invariant of the space $V$ itself, never depending on which basis was used to compute it.

UndergraduateReal-World Applications and Worked Examples

Vector spaces are the common language behind digital signal compression (representing a signal in a cleverer basis than the "obvious" one), and behind the solution sets of linear differential equations that describe oscillators, circuits, and structures in physics and engineering — in both cases, recognizing a set of objects as a vector space with a specific finite dimension is what makes an otherwise infinite-looking problem tractable with finitely many numbers.

Example: Computer science: changing basis to compress a signal

A short digital signal is stored as the vector $(3,1)\in\mathbb{R}^2$ in the standard basis $\{e_1,e_2\}$ . A compression scheme instead uses the basis $\{u_1,u_2\}=\{(1,1),(1,-1)\}$ , which turns out to concentrate most signals into the first coordinate. Express $(3,1)$ in the new basis $\{u_1,u_2\}$ .

Solution

First check $\{u_1,u_2\}=\{(1,1),(1,-1)\}$ is really a basis of $\mathbb{R}^2$ : it has $2=\dim(\mathbb{R}^2)$ vectors, and they are not multiples of each other (one has equal coordinates, the other has opposite coordinates), so they are linearly independent — two independent vectors in a $2$ -dimensional space automatically span it as well.

Write $(3,1)=c_1u_1+c_2u_2=c_1(1,1)+c_2(1,-1)$ for unknown scalars $c_1,c_2$ . This gives the linear system $c_1+c_2=3$ (first coordinate) and $c_1-c_2=1$ (second coordinate).

Adding the two equations: $2c_1=4$ , so $c_1=2$ . Subtracting the second from the first: $2c_2=2$ , so $c_2=1$ .

So $(3,1)=2u_1+1u_2$ , i.e. the coordinates of the signal in the new basis $\{u_1,u_2\}$ are $(2,1)$ ; the compression scheme can now discard or quantize the smaller second coordinate more aggressively than the first, which is exactly why changing basis is useful for compression.

Example: Physics: the solution space of an oscillator equation

The differential equation $y''+y=0$ describing a simple harmonic oscillator has solution set exactly $\{c_1\cos x+c_2\sin x : c_1,c_2\in\mathbb{R}\}$ , a $2$ -dimensional vector space with basis $\{\cos x,\sin x\}$ . Find the specific solution satisfying the initial conditions $y(0)=2$ and $y'(0)=3$ .

Solution

Because the solution set is a vector space with basis $\{\cos x,\sin x\}$ , every solution is uniquely determined by its two coordinates $c_1,c_2$ in that basis — finding the solution reduces to finding these two numbers, exactly as in the compression example above.

The general solution is $y(x)=c_1\cos x+c_2\sin x$ . Evaluate at $x=0$ : $y(0)=c_1\cos 0+c_2\sin 0=c_1$ . The initial condition $y(0)=2$ immediately gives $c_1=2$ .

Differentiate: $y'(x)=-c_1\sin x+c_2\cos x$ . Evaluate at $x=0$ : $y'(0)=-c_1\sin 0+c_2\cos 0=c_2$ . The initial condition $y'(0)=3$ immediately gives $c_2=3$ .

So the specific solution is $y(x)=2\cos x+3\sin x$ — the coordinates $(c_1,c_2)=(2,3)$ of this particular solution in the basis $\{\cos x,\sin x\}$ of the $2$ -dimensional solution space were pinned down completely by the two initial conditions, matching the dimension of the space exactly.

Which of these sets is NOT a vector space under the usual operations?

What is $\dim(P_3)$ , where $P_3$ is the space of polynomials of degree at most $3$ ?

$\{v_1,\dots,v_5\}$ spans $V$ and $\{w_1,w_2,w_3,w_4,w_5,w_6\}\subseteq V$ . What does the Steinitz exchange lemma tell us?

A digital audio compressor represents each short signal frame in a special basis instead of the standard basis. Why does this require the frame's vector space to have a well-defined, basis-independent dimension?

References

Sheldon Axler (2015). Linear Algebra Done Right
Eric W. Weisstein (MathWorld) (2024). Vector Space