3
$\begingroup$

How can I determine the number of $k\times n$ matrices with entries in $\mathbb F_p$ with rank $k$ (of course $k<n$)

The formula if $k=n$ is $(p^n-1)(p^n-p)\dots(p^n-p^{n-1})$, now how can I modify this ?

If I pick any $k$ columns of $n$, and apply the formula, and let the $n-k$ columns be arbitrary, then this causes multiple counting, but I don't know how many times I count.

$\endgroup$
5
$\begingroup$

The matrix has $k$ rows and $n$ columns. Considering $k \le n$, it has rank $k$ if and only if the $k$ rows are linearly independent. So:

  • There are $p^n - 1$ choices for the first row (it can't be $0$)

  • There are $p^n - p$ choices for the second row (it can't be in the span of the first row)

  • There are $p^n - p^2$ choices for the third row (it can't be in the span of the first two rows)

and so on. So the number of matrices total is simply $$ \prod_{i=0}^{k-1} (p^n - p^i) = (p^n - 1)(p^n - p)(p^n - p^2) \cdots (p^n - p^{k-1}). $$

You will also notice this agrees (and is the exact same argument) with the case $n = k$.

Things would become a bit more complicated if we wanted to count matrices with rank $j$, where potentially $j < k$.

$\endgroup$
2
$\begingroup$

A supplementary answer to 6005's answer is given here. Let $q=p^k$ for some prime natural number $p$ and for some positive integer $k$. Fix two positive integers $m$ and $n$. The number of $m$-by-$n$ matrices over $\mathbb{F}_q$ of rank $r$, where $r$ is a nonnegative integer less than or equal to both $m$ and $n$, is given by $$\left(\prod_{j=1}^r\,\left(q^m-q^{j-1}\right)\right)\,\left(\sum_{\substack{{j_1,\ldots,j_r\in\mathbb{Z}_{\geq 0}}\\{j_1+j_2+\ldots+j_r\leq n-r}}}\,q^{\sum_{i=1}^r\,i\,j_i}\right)\,.\tag{1}$$ which is also equal to $$\left(\prod_{j=1}^r\,\left(q^n-q^{j-1}\right)\right)\,\left(\sum_{\substack{{j_1,\ldots,j_r\in\mathbb{Z}_{\geq 0}}\\{j_1+j_2+\ldots+j_r\leq m-r}}}\,q^{\sum_{i=1}^r\,i\,j_i}\right)\,.\tag{2}$$ According to Marko Riedel in this post, (1) and (2) are equal to $$\prod_{j=1}^r\,\frac{\left(q^m-q^{j-1}\right)\,\left(q^n-q^{j-1}\right)}{q^{j-1}\left(q^j-1\right)}=\prod_{j=1}^r\,\frac{q^{j-1}\,\left(q^{m-j+1}-1\right)\,\left(q^{n-j+1}-1\right)}{\left(q^j-1\right)}\,.$$

If $r=m$ and $m\leq n$, then the second expression is precisely $\displaystyle \prod_{j=1}^m\,\left(q^n-q^{j-1}\right)$, as 6005 has stated. In the extreme case, $r=0$, both expressions evaluate to $1$ (since the number of $0$-subsets of $\mathbb{Z}_{\geq 0}$ whose sum is less than or equal to $m-r$ or $n-r$ is $1$, which counts only the empty set). In the case $r=1$, the answer is $$\displaystyle\left(q^m-1\right)\,\left(\sum_{j=0}^{n-1}\,q^j\right)=\frac{\left(q^m-1\right)\left(q^n-1\right)}{q-1}=\left(q^n-1\right)\,\left(\sum_{j=0}^{m-1}\,q^j\right)\,.$$ It is an interesting question whether there is an algebraic or analytic argument that proves that (1) and (2) are equal (by treating $q$ as a variable, and proving that these two polynomials in $q$ are identical, for example, via balancing the coefficients).

$\endgroup$

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.