Counting echelon form matrices

Question

Can somebody explain me how to count the number of matrices $A ∈ M_m,_n(\mathbb Z_2)$ in reduced (that is, each column containing a leading 1 has zeros everywhere else) echelon form? For example the number of matrices $A ∈ M_2,_3(\mathbb Z_2)$ in reduced echelon form is $15$.

Answer 1

I suggest to define first the number $k$ of rows having a leading $1$. This number is in $[0, \min(m, n)]$ and the $k$ first rows of the matrix have a leading $1$. Then suppose that there are $\alpha_0$ columns before the first leading 1, then $\alpha_1$ columns between the first leading 1 and the second, etc. The total number of columns is $n = k + \sum_{i=0}^k \alpha_i$. It follows that the total number of matrices should be \begin{equation} \nu(m, n) = \sum_{k=0}^{\min(m, n)}\sum_{\sum_{p=0}^k\alpha_p = n-k}2^{\sum_{p=0}^k p\ \alpha_p} \end{equation} In the example of $\nu(2, 3)$, the above formula gives \begin{equation}\nu(2, 3) = (2^0) + (2^2+2^1+2^0) + (2^2+2^1+2^0)=15 \end{equation}