Engineering / Mathematics — Modules, Vector Spaces and Matrices
Linear Independence and Bases
Linear independence, spanning sets and bases, and the conditions under which a basis exists.
Executive summary
A basis is a set that is both linearly independent and spanning, so every element has a unique representation. Over a field every vector space has one; over a general ring most modules do not.
The existence of a basis is what makes coordinates possible and what reduces linear algebra to matrix computation.
Learning objectives
- Define independence, spanning and basis.
- State the existence theorem over a field.
- Identify why existence fails over a general ring.
01The definitions
Independence, spanning, basis
A set S is linearly independent if no non-trivial finite linear combination of its elements is zero.
S spans M if every element is a finite linear combination of elements of S.
S is a basis if it is both.
Unique representation
S is a basis if and only if every element of M has exactly one representation as a finite linear combination of elements of S.
Spanning gives existence of a representation; independence gives uniqueness. The two conditions are exactly what is needed for coordinates to be well defined.
02Existence over a field
Basis existence
Every vector space over a field has a basis. Moreover, every linearly independent set extends to a basis and every spanning set contains one.
For finitely generated spaces the proof is a finite exchange argument. For arbitrary spaces it requires Zorn's lemma, and is in fact equivalent to the axiom of choice.
Exchange lemma
If M is spanned by n elements, then every linearly independent subset has at most n elements.
03Failure over a ring
| Module | Ring | Basis? |
|---|---|---|
| F^n | Field F | Yes, the standard basis |
| Z^n | Z | Yes, free of rank n |
| Z_n | Z | No — every element is torsion |
| Q | Z | No — not finitely generated, and any two elements are dependent |
| An ideal I ⊆ R | R | Only if I is principal and R is a domain |
The general obstruction is torsion. A module with a non-zero torsion element cannot be free, because a basis element b would satisfy rb = 0 for some non-zero r, contradicting independence.
Over a principal ideal domain the situation is as good as it can be: every finitely generated module is a direct sum of a free part and a torsion part, and this classification is the structure theorem that specialises to finitely generated abelian groups.
04Frequently asked questions
Does every module have a maximal independent set?
Yes, by Zorn's lemma, but such a set need not span. Over a field maximality forces spanning; over a general ring it does not, which is precisely why bases can fail to exist.
Can a module have bases of different sizes?
Not over a commutative ring — the rank of a free module is well defined there. Over certain non-commutative rings it can fail, and such rings are said to lack the invariant basis number property.
Is Q finitely generated over Z?
No. Any finite set of rationals has a common denominator, and the subgroup they generate cannot contain rationals with larger denominators. Q is a standard example of a torsion-free module that is not free.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 306-309.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.