1
$\begingroup$

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....

$\endgroup$
7
  • 1
    $\begingroup$ This is the number of nonsingular matrices over the field $\Bbb F_2$. It's a well-known problem... $\endgroup$ Aug 13 '17 at 7:31
  • 2
    $\begingroup$ 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.) $\endgroup$ Aug 13 '17 at 7:39
  • $\begingroup$ 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? $\endgroup$
    – tastykakes
    Aug 13 '17 at 7:42
  • $\begingroup$ Symplectomorphic - thanks for clearing that up. makes sense. $\endgroup$
    – tastykakes
    Aug 13 '17 at 7:42
  • $\begingroup$ 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. $\endgroup$ Aug 13 '17 at 7:45
1
$\begingroup$

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}).$$

$\endgroup$
3
  • 2
    $\begingroup$ 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). $\endgroup$ Aug 13 '17 at 9:31
  • $\begingroup$ @MarkBennet: That's true, one can get away only by choosing some basis. Thanks for the correct, I've edited the answer. $\endgroup$
    – levap
    Aug 13 '17 at 9:34
  • $\begingroup$ @MarkBennet - this is the answer I was looking for. thanks so much. $\endgroup$
    – tastykakes
    Aug 14 '17 at 3:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.