# Find the number of surjective linear maps from an $n$-dimensional vector space over the field with 2 elements to itself.

Find the number of surjective linear maps from an $n$-dimensional vector space over the field with 2 elements to itself.

Here's my attempt:

So let's say I have this vector space $V$ with a basis $\{v_1, v_2, \dots, v_n\}$, and I want the number of surjective maps from V to itself. So $T \in \mathcal{L}(V)$ can map $v_1$ to any of the other $n$ vectors, $v_2$ to any of the other $n-1$....

I'm confused as to where the "two elements" parts comes into play. I'm missing something very obvious here....

• This is the number of nonsingular matrices over the field $\Bbb F_2$. It's a well-known problem... Aug 13, 2017 at 7:31
• Your reasoning makes no sense. A surjective linear map doesn't have to send a basis vector to a basis vector. (For a concrete example, tho it should be very easy for you to construct one: consider in a two-dimensional space the map that sends the first basis vector to itself and the second basis vector to the sum of the first and the second.) Aug 13, 2017 at 7:39
• Lord Shark - while I recognize it's a well known problem, can you help me understand when you comment rather than just pointing that out? Why is that problem equivalent? Aug 13, 2017 at 7:42
• Symplectomorphic - thanks for clearing that up. makes sense. Aug 13, 2017 at 7:42
• Where is the problem from? What is your mathematical background? What other thoughts do you have? You ought to know that a linear endomorphism is surjective iff it's injective, which in turn holds iff the map is nonsingular. Aug 13, 2017 at 7:45

## 1 Answer

It's easier to transform the question to a question about matrices. Once you choose a basis for your vector space $V$, a linear map $T$ is represented uniquely by an $n \times n$ matrix $A$ whose entries are elements of $\mathbb{F}_2$ ($0$ or $1$). The linear map will be surjective iff it is injective iff it has full rank. In terms of matrices, this means that the matrices that represent surjective matrices are matrices $A$ for which $\operatorname{rank}(A) = n$.

Let's start with some basic observations. The number of $n \times 1$ column vectors with entries in $\mathbb{F}_2$ is $2^n$ (each entry can be either $0$ or $1$). The number of elements in a vector space of dimension $k$ over $\mathbb{F}_2$ is $2^k$ because once you choose a basis $e_1,\dots,e_k$ for $V$, each element is a unique linear combination $a_1 e_1 + \dots + a_k e_k$ where $a_i \in \mathbb{F}_2$.

A matrix $A \in M_n(\mathbb{F}_2)$ has full rank if and only if its columns are linearly independent. This means that a matrix $A$ has full rank if and only if the first column is non-zero and the $k$-th column of the matrix doesn't belong to the span of the $1,\dots,k-1$ columns for $2 \leq k \leq n$. Having this in mind, we have $2^n - 1$ options for the first column (any non-zero vector in $\mathbb{F}_2^n$), $2^n - 2$ options for the second column (any vector that doesn't belong to the span of the first column), $2^n - 2^2$ options for the third column and so on. Hence, the number of full rank $n \times n$ matrices over $\mathbb{F}_2$ is

$$(2^n - 1)(2^n - 2) \cdots (2^n - 2^{n-1}).$$

• It is not necessary to go to matrices. The first basis vector can map to anything non-zero. The second to anything not in the one-dimensional subspace spanned by the image of the first etc. It is the same calculation. (NB you should have $2^n-1$ as the first factor in your calculation). Aug 13, 2017 at 9:31
• @MarkBennet: That's true, one can get away only by choosing some basis. Thanks for the correct, I've edited the answer. Aug 13, 2017 at 9:34
• @MarkBennet - this is the answer I was looking for. thanks so much. Aug 14, 2017 at 3:16