Question Statement

Let $K$ be a finite field of $q$ elements. Let $U$, $V$ be vector spaces over $K$ with $\dim(U) = k$, $\dim(V) = l$. How many linear maps $U \rightarrow V$ are there?

I'm struggling to answer this question. Given that a linear map is uniquely determined by its action on a basis we may as well consider the mappings of the standard basis. Even with this restriction, each of the $k$ basis vectors can map to not only $q$ distinct elements but also into $l$ different positions (or none, or into multiple positions).

What easy thing am I missing?


The answer (if I actually got it right), for anyone still wondering:

Let $\mathbf{e}_1,\mathbf{e}_2,\ldots,\mathbf{e}_k$ be a basis of $U$, $\mathbf{f}_1,\ldots,\mathbf{f}_l$ be a basis of $V$ and $T:U\rightarrow V$ be a linear map.

Then $$T(\mathbf{e}_1) = \alpha_{11}\mathbf{f}_1 + \alpha_{12}\mathbf{f}_2 + \cdots + \alpha_{1l}\mathbf{f}_{l}$$ $$T(\mathbf{e}_2) = \alpha_{21}\mathbf{f}_1 + \alpha_{22}\mathbf{f}_2 + \cdots + \alpha_{2l}\mathbf{f}_l$$ $$\vdots $$ $$ T(\mathbf{e}_k) = \alpha_{k1}\mathbf{f}_1 + \alpha_{k2}\mathbf{f}_2 + \cdots + \alpha_{kl}\mathbf{f}_l$$

defines $T$. The number of different linear transformations is then just the number of different combinations of $\alpha_{ij}$'s. There are a finite number of combinations as there are only $q$ choices for each one.

I found two similar methods, each with a slightly different focus, that lead to the answer:

More algebraic

As there are $q$ different choices for each $\alpha_{ij}$ and they are chosen independently, so on each row there are $q^l$ different choices. Now over $k$ independently chosen rows we have $$\underbrace{q^l \cdot q^l \cdot \cdots \cdot q^l}_{k\text{ times}}=(q^l)^k=q^{kl}$$ different choices

More combinatorial

we may write the linear transformation as a matrix of the coefficients ($\alpha_{ij}$'s) in the following way

$$ \pmatrix{ \alpha_{11} & \cdots & \alpha_{1l}\\ \\ \vdots & \ddots & \vdots\\ \\ \alpha_{k1} & \cdots & \alpha_{kl} } $$

You can now look at the number of ways of choosing combinations of non-zero $\alpha_{ij}$'s, which is every possible matrix and therefore every possible linear transformation (note that choosing no $\alpha_{ij}$ non-zero gives us the zero matrix).

There are

  • $\binom{kl}{0} \cdot (q-1)^0 = 1$ ways of choosing no non-zero coefficients. We are choosing zero of the $k \times l$ coefficients.

  • $\binom{kl}{1} \cdot (q-1)^1 = (q-1)$ ways of choosing one $\alpha_{ij}$ non-zero. 1 of the $k\times l$ coefficients and $q-1$ different choices for it

  • $\binom{kl}{2} \cdot (q-1)^2$ ways of choosing two $\alpha_{ij}$ non-zero. There are $q-1$ non-zero choices for each of the 2 coefficients, so $(q-1)^2$ different combinations

In general there are $\binom{kl}{i} \cdot (q-1)^i$ ways of choosing $i\ \alpha_{ij}$ non-zero. The total number of linear transformations is the number of different matrices, which is the sum of all the numbers above:

$$\sum_{i=0}^{kl} \binom{kl}{i} \cdot (q-1)^i = \sum_{i=0}^{kl} \binom{kl}{i} \cdot (q-1)^i \cdot 1^{kl-i}= (q-1+1)^{kl}=q^{kl}$$


Hint: The space of all linear maps from $U\to V$ is isomorphic to $\text{Mat}_{l\times k}(K).$

  • $\begingroup$ So there are $q^{lxk}$ different ways? $\endgroup$
    – Asa Cremin
    Feb 6 '14 at 1:32
  • $\begingroup$ @AsaCremin: Right you're. $\endgroup$ Feb 6 '14 at 1:50

All such linear maps are of the form $c_1y_1+..c_ky_k$ where $y_1,..y_k$ is the image of the basis vectors of $U$, and $c_i$ are scalars. Note that you can have $q$ different choices for each $y_i$

Hope you can finish the problem now.

  • $\begingroup$ The $x_1, \ldots, x_K$ are basis vectors of $U$, but $V$ is just one dimensional, so you need to specify more carefully what you mean by the linear map being of the "form" $c_1 x_1 + \ldots $. $\endgroup$ Feb 4 '14 at 1:30
  • $\begingroup$ @ChristopherA.Wong: Yah right- I am editing the answer now. $\endgroup$
    – voldemort
    Feb 4 '14 at 1:34
  • $\begingroup$ V is of dimension l, not dimension 1. Sorry for the ambiguity of the font $\endgroup$
    – Asa Cremin
    Feb 4 '14 at 14:52
  • $\begingroup$ thats the letter l (again, sorry for any confusion) $\endgroup$
    – Asa Cremin
    Feb 4 '14 at 15:04

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.