Recently, I got thinking about the material in Growing Linearly Independent Sets. I realized that because everything was finite one could essentially replace all the machinery of the dimension bound theorem with the pigeonhole principle. This realization, in turn, sent me down a rabbit hole of wondering whether these two theorems might be equivalent for finite vector spaces.
For the sake of being ultra-concrete here are the relevant definitions.
In the note below, we are going to show: The pigeon hole principle for finite sets is equivalent to the dimension bound theorem for finite vector spaces.
Consider a finite vector space $V = \mathbb{F}_p^d$ over a finite field $\mathbb{F}_p$. Fix a set of vectors $S = \{v_1, \dots, v_n\}$. We want to argue: if $n > d$ then $S$ is linearly dependent. Consider the function1 $L : \mathbb{F}_p^n \to V$ defined by \[ L(c_1, \dots, c_n) = c_1v_1 + \dots + c_nv_n. \] If $n > d$ then $|\mathbb{F}_p^n| = p^n > p^d = |V|$. Therefore, by the pigeonhole principle, $L$ is not injective. We get some $(a_1, \dots, a_n) \neq (b_1, \dots, b_n)$ such that: \[ a_1v_1 + \dots + a_nv_n = b_1v_1 + \dots + b_nv_n. \] It follows that: \[ (a_1 - b_1)v_1 + (a_2 - b_2)v_2 + \dots + (a_n - b_n)v_n = 0. \] We want to show that this is a non-trivial linear combination of the vectors $v_i$. To do so, we need to show that there is a non-zero coefficient somewhere on the left-hand side. And, indeed, there must be some non-zero coefficient $a_i - b_i$ because $(a_1, \dots, a_n) \neq (b_1, \dots, b_n)$.
This direction is weirder because we know so little about $f : X \to Y$. We don’t have linearity, continuity, or anything except $|X| > |Y|$. To apply the dimension bound theorem, we need to create a vector space $V$ and a set of vectors which somehow model the function $f$.
Without loss of generality2, we’ll assume $X = \{1, 2, \dots, n\}$ and $Y = \{1, 2, \dots, d\}$ where $n > d$. We will build a set of vectors in $V = \mathbb{F}_2^d$. We write $V = \operatorname{span}\{{e}_i : i = 1, \dots, d\}$ where the vectors ${e}_i$ are the usual standard basis vectors. The vector ${e}_i$ has 1 in position $i$ and $0$ elsewhere.
Now, we have $d$-dimensional finite vector space $V$. We need to build a set of vectors in $V$ based on $f : X \to Y$. Consider the following set3 of vectors. \[ S = \{ {e}_{f(i)} : i = 1, \dots, n \} \] $S$ has $n > d$ elements and so must contain a linear dependence by the dimension bound theorem. This implies that there are some coefficients, not all zero, such that:
\[ c_1 e_{f(1)} + c_2e_{f(2)} + \dots + c_n e_{f(n)} = 0. \]
On the right-hand side, we have the zero vector. All its coordinates are zero. On the left-hand side, we have basis vectors. The only way for the coordinates of the left-hand side to be zero is if there is an even4 number of summands in each coordinate. There must be some $c_i = 1$ non-zero because this is a non-trivial linear dependence. This implies there must be some other $c_j = 1$ non-zero somewhere. This means we have some some pair of terms $c_i e_{f(i)}$ and $c_j e_{f(j)}$ with $i \neq j$ which cancel out. Therefore, $f(i) = f(j)$ and $f$ is non-injective.
The construction above seems complicated but an example makes it immediately transparent. Consider the following function. \[ \begin{array}{c|ccc} x & 1 & 2 & 3 & 4\\ f(x) & 1 & 2 & 3 & 1\\ \end{array} \] This function maps $\{1,2,3,4\}$ to $\{1,2,3\}$. Our construction above will have $n=4$ and $d=3$. That means we’ll be working in $\mathbb{F}_2^3$. We build a set3 of four vectors out of the function $f$. \[ S = \{ e_{f(1)}, e_{f(2)}, e_{f(3)}, e_{f(4)} \} = \left\{ \begin{bmatrix} 1\\ 0\\ 0\\ \end{bmatrix}, \begin{bmatrix} 0\\ 1\\ 0\\ \end{bmatrix}, \begin{bmatrix} 0\\ 0\\ 1\\ \end{bmatrix}, \begin{bmatrix} 1\\ 0\\ 0\\ \end{bmatrix} \right\} \] The dimension bound theorem then produces the following non-trivial linear dependence. \[ 1 \cdot \begin{bmatrix} 1\\ 0\\ 0\\ \end{bmatrix} + 0 \cdot \begin{bmatrix} 0\\ 1\\ 0\\ \end{bmatrix} + 0 \cdot \begin{bmatrix} 0\\ 0\\ 1\\ \end{bmatrix} + 1 \cdot \begin{bmatrix} 1\\ 0\\ 0\\ \end{bmatrix} = \begin{bmatrix} 1 + 1\\ 0\\ 0\\ \end{bmatrix} = \begin{bmatrix} 0\\ 0\\ 0\\ \end{bmatrix} \] We see that $e_{f(1)} + e_{f(4)} = 0$ and so $f(1) = f(4)$. This is algebra-intensive way of saying: “The first and last vectors in $S$ are the same! There are two pigeons in the first hole!”
The name $L$ stands for “linear combination.” ↩︎
We’re dealing with finite sets, so we might as well assume they’re sets of natural numbers. If needed we can apply bijections to re-label $X$ and $Y$ as natural numbers. We can pre- and post-compose $f$ with bijections as well so that its inputs and outputs are natural numbers too. ↩︎
If we want to be really pedantic, we should note that $S$ is actually a multiset. Or, like, an $n$-tuple of vectors. ↩︎ ↩︎
This is because we’re working over $\mathbb{F}_2$. ↩︎
Published: Mar 31, 2026 @ 19:30.
Home / Now / Blog / Notes / Reading / Office Camera / Tags / Bookmarks / RSS Feeds / Top of Page
Thanks for reading! If you have any comments or questions about the content, please let me know. Anyone can contact me by email.
