# Dimension theorem for vector spaces

In mathematics, the dimension theorem for vector spaces states that all bases of a vector space have equally many elements. This number of elements may be finite, or given by an infinite cardinal number, and defines the dimension of the space.

Formally, the dimension theorem for vector spaces states that

Given a vector space V, any two linearly independent generating sets (in other words, any two bases) have the same cardinality.

If V is finitely generated, then it has a finite basis, and the result says that any two bases have the same number of elements.

While the proof of the existence of a basis for any vector space in the general case requires Zorn's lemma and is in fact equivalent to the axiom of choice, the uniqueness of the cardinality of the basis requires only the ultrafilter lemma,[1] which is strictly weaker (the proof given below, however, assumes trichotomy, i.e., that all cardinal numbers are comparable, a statement which is also equivalent to the axiom of choice). The theorem can be generalized to arbitrary R-modules for rings R having invariant basis number.

The theorem for finitely generated case can be proved with elementary arguments of linear algebra, and requires no forms of the axiom of choice.

## Proof

Assume that { ai: iI } and { bj: jJ } are both bases, with the cardinality of I bigger than the cardinality of J. From this assumption we will derive a contradiction.

### Case 1

Assume that I is infinite.

Every bj can be written as a finite sum

${\displaystyle b_{j}=\sum _{i\in E_{j}}\lambda _{i,j}a_{i}}$, where ${\displaystyle E_{j}}$ is a finite subset of ${\displaystyle I}$.

Since the cardinality of I is greater than that of J and the Ej's are finite subsets of I, the cardinality of I is also bigger than the cardinality of ${\displaystyle \bigcup _{j\in J}E_{j}}$. (Note that this argument works only for infinite I.) So there is some ${\displaystyle i_{0}\in I}$ which does not appear in any ${\displaystyle E_{j}}$. The corresponding ${\displaystyle a_{i_{0}}}$ can be expressed as a finite linear combination of ${\displaystyle b_{j}}$'s, which in turn can be expressed as finite linear combination of ${\displaystyle a_{i}}$'s, not involving ${\displaystyle a_{i_{0}}}$. Hence ${\displaystyle a_{i_{0}}}$ is linearly dependent on the other ${\displaystyle a_{i}}$'s.

### Case 2

Now assume that I is finite and of cardinality bigger than the cardinality of J. Write m and n for the cardinalities of I and J, respectively. Every ai can be written as a sum

${\displaystyle a_{i}=\sum _{j\in J}\mu _{i,j}b_{j}}$

The matrix ${\displaystyle (\mu _{i,j}:i\in I,j\in J)}$ has n columns (the j-th column is the m-tuple ${\displaystyle (\mu _{i,j}:i\in I)}$), so it has rank at most n. This means that its m rows cannot be linearly independent. Write ${\displaystyle r_{i}=(\mu _{i,j}:j\in J)}$ for the i-th row, then there is a nontrivial linear combination

${\displaystyle \sum _{i\in I}\nu _{i}r_{i}=0}$

But then also ${\displaystyle \sum _{i\in I}\nu _{i}a_{i}=\sum _{i\in I}\nu _{i}\sum _{j\in J}\mu _{i,j}b_{j}=\sum _{j\in J}{\biggl (}\sum _{i\in I}\nu _{i}\mu _{i,j}{\biggr )}b_{j}=0,}$ so the ${\displaystyle a_{i}}$ are linearly dependent.

#### Alternative proof

The proof above uses several non-trivial results. If these results are not carefully established in advance, the proof may give rise to circular reasoning. Here is a proof of the finite case which requires less prior development.

Theorem 1: If ${\displaystyle A=(a_{1},\dots ,a_{n})\subseteq V}$ is a linearly independent tuple in a vector space ${\displaystyle V}$, and ${\displaystyle B_{0}=(b_{1},...,b_{r})}$ is a tuple that spans ${\displaystyle V}$, then ${\displaystyle n\leq r}$.[2]

The argument is as follows:

Since ${\displaystyle B_{0}}$ spans ${\displaystyle V}$, the tuple ${\displaystyle (a_{1},b_{1},\dots ,b_{r})}$ also spans. Since ${\displaystyle a_{1}\neq 0}$ (because ${\displaystyle A}$ is linearly independent), there is at least one ${\displaystyle t\in \{1,\ldots ,r\}}$ such that ${\displaystyle b_{t}}$ can be written as a linear combination of ${\displaystyle B_{1}=(a_{1},b_{1},\dots ,b_{t-1},b_{t+1},...b_{r})}$. To see this, write ${\displaystyle a_{1}}$ as a linear combination of the ${\displaystyle b_{i}}$, and note that because ${\displaystyle a_{i}\neq 0}$, at least one of the coefficients of the ${\displaystyle b_{i}}$ must be non-zero. Isolating this term on one side of the equation and dividing by its coefficient - here we make critical use of the assumption that a vector space is always defined over a field - yields the result. Thus, ${\displaystyle B_{1}}$ is a spanning tuple, and its length is the same as ${\displaystyle B_{0}}$'s.

Repeat this process. Because ${\displaystyle A}$ is linearly independent, we can always remove an element from the list ${\displaystyle B_{i}}$ which is not one of the ${\displaystyle a_{j}}$'s that we prepended to the list in a prior step (because ${\displaystyle A}$ is linearly independent, and so there must be some nonzero coefficient in front of one of the ${\displaystyle b_{i}}$'s). Thus, after ${\displaystyle n}$ iterations, the result will be a tuple ${\displaystyle B_{n}=(a_{1},\ldots ,a_{n},b_{m_{1}},\ldots ,b_{m_{k}})}$ (possibly with ${\displaystyle k=0}$) of length ${\displaystyle r}$. In particular, ${\displaystyle A\subseteq B_{n}}$, so ${\displaystyle |A|\leq |B_{n}|}$, i.e., ${\displaystyle n\leq r}$.

To prove the finite case of the dimension theorem from this, suppose that ${\displaystyle V}$ is a vector space and ${\displaystyle S=\{v_{1},\ldots ,v_{n}\}}$ and ${\displaystyle T=\{w_{1},\ldots ,w_{m}\}}$ are both bases of ${\displaystyle V}$. Since ${\displaystyle S}$ is linearly independent and ${\displaystyle T}$ spans, we can apply Theorem 1 to get ${\displaystyle m\geq n}$. And since ${\displaystyle T}$ is linearly independent and ${\displaystyle S}$ spans, we get ${\displaystyle n\geq m}$. From these, we get ${\displaystyle m=n}$.

## Kernel extension theorem for vector spaces

This application of the dimension theorem is sometimes itself called the dimension theorem. Let

T: UV

be a linear transformation. Then

dim(range(T)) + dim(kernel(T)) = dim(U),

that is, the dimension of U is equal to the dimension of the transformation's range plus the dimension of the kernel. See rank–nullity theorem for a fuller discussion.

## References

1. ^ Howard, P., Rubin, J.: "Consequences of the axiom of choice" - Mathematical Surveys and Monographs, vol 59 (1998) ISSN 0076-5376.
2. ^ S. Axler, "Linear Algebra Done Right," Springer, 2000.