Counting matrices over a finite field. Let $ \mathcal{M}^{k \times n} = \{ A \in \mathbb{F}_q^{k \times n} \mid A \text{ is full rank and every } \; k \times k \; \text{submatrix of }\; A \;\text{is invertible}\}$. I want to know $|\mathcal{M}^{k \times n}| $. I know that since $\mathcal{M}^{k \times n}$ is subset of the full rank matrices then the number I'm looking for is less than $(q^n-1)(q^n-q)\cdots (q^n-q^{k-1})$ (the number of full rank matrices) but if you make the count for $ k=1$ this seems to be false:
When $ k=1$ every sub matrix having determinant distinct to zero is equivalent to being full rank, so one has to count only the number of vectors with non zero entries: $ (q^n-1)^n > q^n-1$.
I know that I might be wrong but I can't see how
Thank you all in advance
Edit
I forgot to add that $n>k $, this will implie that in $k=1 $ being full rank only means not to be the zero vector i.e we are only looking for the vectors with non zero entries (there are $ (q^n-1)^n > q^n-1$ many of them ) but hte equivalence I state does not holds.
 A: Here are two methods:


*

*Blind computation: $A$ has maximal rank $k$ iff any one $k\times k$ submatrix is invertible. So it's enough to ask that every $k\times k$ submatrix is invertible. Break $A$ into the top $k\times k$ box and the bottom $(n-k)\times k$ rectangle. There are 
$$(q^k-1)(q^k-q)\cdots(q^k-q^{k-1})$$
ways of filling in the top box invertibly, as you said. 
What about the next row? That row vector $v$ must lie outside all the $k-1$ dimensional spaces $\Pi_1,...,\Pi_k\subseteq V$ spanned by row vectors of the top box. Thus there are 
$$q^k-1- |\Pi_1\cup \cdots \cup \Pi_k|$$
possible $v$'s. We compute using inclusion-exclusion
$$|\Pi_1\cup \cdots \cup \Pi_k|=k|\Pi_1|-\binom{k}{2}|\Pi_1\cap \Pi_2|+\cdots \pm |\Pi_1\cap \cdots \cap \Pi_k|$$
Each intersection has dimension one less than the last, so 
$$|\Pi_1\cup \cdots \cup \Pi_k|=kq^{k-1}-\binom{k}{2}q^{k-2}+\cdots \pm q^0=(-q+1)^k=q^k-(q-1)^k$$
and there are this many chocies for $v$:
$$(q-1)^k-1$$
What about the next row after that? There are now $k+1$ spaces $\Pi_1,...,\Pi_{k+1}\subseteq V$ to avoid, and
$$|\Pi_1\cup \cdots \cup \Pi_{k+1}|=(k+1)q^{k-1}-\binom{k}{2}q^{k-2}+\cdots \pm \binom{k+1}{1}q^0$$
is 
$$\frac{1}{q}\left(q^{k+1}-(q-1)^{k+1}+(-1)^{k+1}\right)$$
And these are the number of choices for the row vector:
$$\frac{1}{q}\left((q-1)^{k+1}-(-1)^{k+1}\right)-1$$
The general term is 
$$\alpha_{m+1}=\frac{1}{q^m}\left((q-1)^{k+m} \text{ with the last }m\text{ summands cut off }\right)-1$$
and the number of such matrices is thus
$$(q^k-1)(q^k-q)\cdots (q^k-q^{k-1}) \  \alpha_1 \cdots \alpha_{n-k}$$

*Computation: Let $V,W$ have dimensions $k$ and $n$, and $\alpha: V\to W$ be a linear map between them. Pick a basis $e_1,...,e_n$ of $W$. Then the matrix of $\alpha$ satisfies your property iff 
$$V\stackrel{\alpha}{\longrightarrow}W\stackrel{\pi_i}{\longrightarrow}W_i$$
is invertible for each $W_i\subseteq W$ generated by some $k$ of the $e_i$, and $\pi_i$ is the projection using the basis. Equivalently, $\pi_i\cdot \alpha$ is injective, i.e.
$$\text{im }\alpha \ \cap \ \ker \pi_i \ = \ 0.$$
We now count how many possible $\alpha$ there are by looking how it acts on a basis $v_1,...,v_k$ of $V$. First, what are the conditions on $\alpha(v_1)$? The above gives
$$\alpha(v_1) \ \not \in \ \ker \pi_1 \cup \ker \pi_2 \cup \cdots \ \ \ = \Omega$$
Then there are $q^n-|\Omega|$ choices for $\alpha(v_1)$.  
What about $\alpha(v_2)$? Not only $\alpha(v_2)\not \in \Omega$, but also $\alpha(av_1+bv_2)\not \in \Omega$, which is equivalent to $\alpha(v_2)\not \in \Omega +a\alpha(v_1)$ for all $a$. Now, 
$$|\{ \Omega +a\alpha(v_1) : a \in \mathbb{F}_q\}\ = \ q|\Omega|$$
so there are $q|\Omega|$ choices for $\alpha(v_2)$. 
Similarly, having chosen $\alpha(v_1),...,\alpha(v_r)$, there are $q^r|\Omega|$ choices for $\alpha(v_{r+1})$. Thus in total, there are
$$q^{\frac{k(k-1)}{2}} |\Omega|^k$$ 
possible such $\alpha$.
The second method is more useful in smaller dimensions, because $\Omega$, the union of the $n-k$ dimensional standard hyperplanes in $\mathbb{F}_q^n$, has $|\Omega|$ easily computible. In general I think it will be as much of a mess as the first method.
