Amount of elements in finite vector space.

Question

I'm trying to resolve two exercises from Kostrikin's book.

Ex. 1

How many elements contains vector space $\mathbb{F}_p^n$ (vectors $(x_1,x_2,\dots,x_n)$ of length $n$) over a field $\mathbb{F}_p$ with $p$ elements? How many solutions has equation $a_1x_1+a_2x_2+\dots+a_nx_n=0$ (not all $a_i=0$)?

Ex. 2

How many $k$-dimmension subspaces ($1\le k\le n$) contains $n$-dimension vector space $V$ over a field $F_q$ with $q$ elements.

I think, I resolve first exercise:

$$\left|\mathbb{F}_p^n\right|=p^n$$ because I need to create vector of length $n$. I can choose first element on $p$ ways, second too.... so $p\cdot p\cdot p\cdots p$. Number of solutions is an amount of linear dependent vectors in this space. Dimension of this space is equal $n$, so a maximum set of independent vectors contains $n$ vectors. Number of solution is equal $p^n-n$?

In case of second exercise I have two solutions.

First:

There is only one $k$-dimension subspace? Because all spaces with dimension $k$ are isomorphic.

Second:

Base of $V$ space contains $n$ vectors. So I can choose ${n \choose k}$ vectors from $V$ base and create $k$-dimension subspace. So there is ${n \choose k}$ subspaces.

Are any of my solutions correct?

Thanks.

Answer 1

Your answer to the first exercise is correct.

For the second exercise, first note that they ask for the number of $k$-dimensional subspaces, not the number of isomorphism classes of $k$-dimensional subspaces. If they were asking for isomorphism classes, then yes you're right there would only be 1. Also, you make the incorrect assumption that every $k$-dim subspace can be obtained as the span of a subset of your basis. This is not true. For example, in $F^2$ (let $F := \mathbb{F}_p$), you can take the basis $\{(1,0),(0,1)\}$, but here subsets of the basis yield only two distinct 1-dim subspaces, even though there are many more. For example, what about the subspace generated by $(1,1)$? In this example, $F^2$ should be thought of as a plane, and 1-dim subspaces are just lines in the plane going through the origin, which are classified by their slope (which may be infinity for the vertical line).

To correctly count the number of $k$-dim subspaces, note that any such subspace has a basis of $k$ vectors, and thus we can begin by counting the number of sets of $k$ linearly independent vectors in $V$, which we will identify with $F^n$. For the first vector you have $p^n-1$ choices (anything but $0$). For the second, you have $p^n-p$ choices (anything but a vector in the span of the first), and so on. Thus, you have $$\prod_{j=0}^{k-1}(p^n-p^j)$$ possible ordered sets of $k$ linearly independent vectors in $V$. Thus we have a map (of sets): $$f : \{\text{ordered lists of $k$ linearly independent vectors in $V$}\}\longrightarrow \{\text{$k$-dim subspaces of $V$}\}$$ (where $f(v_1,\ldots,v_k) = \text{Span}\{v_1,\ldots,v_k\}$) which is surjective, but not injective. We would like to count the size of $f^{-1}(U)$, where $U\le V$ is a $k$-dim subspace. Since $f^{-1}(U)$ is just the set of ordered bases of $U$, we find that $$|f^{-1}(U)| = \text{the number of ordered bases of $U$}$$ Identifying $U$ with $F^k$, we find that the number of ordered bases of $U$ are in bijection with matrices in $GL_k(F)$ (this group acts freely and transitively on the set of such ordered bases, or alternatively, any such ordered basis gives you a matrix in $GL_k(F)$ with elements of the basis as columns). Thus, $|f^{-1}(U)| = |GL_k(F)|$. Since this doesn't depend on $U$, we find that the number of $k$-dim subspaces of $V$ is precisely: $$\frac{\prod_{j=0}^{k-1}(p^n-p^j)}{|GL_k(F)|}$$ By the same reasoning as above, the size of $GL_k(F)$ is $$|GL_k(F)| = \prod_{j=0}^{k-1}(p^k-p^j)$$ so: $$\frac{\prod_{j=0}^{k-1}(p^n-p^j)}{|GL_k(F)|} = \frac{\prod_{j=0}^{k-1}(p^n-p^j)}{\prod_{j=0}^{k-1}(p^k-p^j)} = \prod_{j=0}^{k-1}\frac{p^{n-j}-1}{p^{k-j}-1}$$

Answer 2

After 4 years I faced this exercise again and I found that first exercise is not solved properly. First part is ok and $\left|\mathbb{F}_p^n\right|=p^n$. Second part is wrong. Number of solutions is not equal $p^n-n$.

My new solution:

Let's begin on count how many solution has this equation: $$ a_1x_1+a_2x_2=0\;\;\;\;\;\; a_i,x_i\in\mathbb{F}_p $$ Let's assume that $a_1\not =0$ (For $a_2$ result will be the same). Let's assign any value for $x_2$ (we have $p$ possibilities). Then $a_2x_2'=r$ ($x_2'$ is assigned value). $\mathbb{F}_p$ is a field, so $r$ has additive inverse element $-r$. $$a_1x_1=-r$$ Basing on the same reason (and $a_1\not=0)$ $a_1$ has multiplicative inverse element $a_1^{-1}$, so we have solution. $$ x_1=-ra_1^{-1}$$ We have $p$ solutions for this equation.

Let's start with general solution right now. $$ a_1x_1+a_2x_2+a_3x_3+\cdots+a_nx_n=0$$ Let's assume that $a_1\not =0$ (We could did it for any $a_i$) and let's assign any values for $x_2,x_3,x_4,\cdots x_n$ (We have $p^{n-1}$ possibilities). Then let's evaluate this expression. Result: $$ a_1x_1+k=0\;\;\;\;\;\;k=a_2x_2'+a_3x_3'+\cdots+a_nx_n' $$ Where $x_i'$ is assigned value. This equation has only one solution, so general equation has $p^{n-1}$ solutions, not $p^n-n$.

Is there any other way to find this value? On is my solution OK?

Thanks

---

Thanks @ancientmathematician I tried with rank-nullity theorem. Here is my result:

$A$ is linear transformation $A:\mathbb{F}_p^n\rightarrow\mathbb{F}_p$. $$ A(x)=\sum_{i=1}^na_ix_i $$ Domain of $A$ is whole $\mathbb{F}_p^n$, so $$ \mathrm{dom}{A}=\mathbb{F}_p^n\;\Rightarrow\; \mathrm{dim}\,\mathrm{dom}{A}=n $$ Image of $A$ is whole $\mathbb{F}_p$, so $$ \mathrm{im}{A}=\mathbb{F}_p\;\Rightarrow\; \mathrm{dim}\,\mathrm{im}{A}=1 $$ From rank-nullity theorem $$ \mathrm{dim}\,\mathrm{dom}{A}=\mathrm{dim}\,\mathrm{ker}{A}+\mathrm{dim}\,\mathrm{im}{A} $$ i can figure out value of kernel dimension $$ n=\mathrm{dim}\,\mathrm{ker}{A}+1\Rightarrow\mathrm{dim}\,\mathrm{ker}{A}=n-1 $$ Kernel of transformation is set of vectors which value is 0. So i understand i'm looking for $|\mathrm{ker}{A}|$. I'm not sure how to find amount of elements in kernel. Here is my try:

I know dimension of kernel and I know that kernel is linear space, so base of this set has $n-1$ elements. I can take any base so i'll take 'default' $$ (1,0,0,\cdots,0)\;(0,1,0,\cdots,0)\;(0,0,1,\cdots,0)\cdots(0,0,0,\cdots,1) $$ All vectors has $n-1$ coordinates. I can generate $p^{n-1}$ vectors basing on this set, so equation from begging of exercise has $p^{n-1}$ solutions.

Is that correct?