Where "a form" for some RRE matrix is its description in terms of the number of all-zero rows it has and the position of pivots in the non-zero rows.
I've tried using induction, the base case is obvious enough:
$$ \left[
\begin{array}{c}
0
\end{array}
\right],
\left[
\begin{array}{c}
1
\end{array}
\right] \rightarrow 2^1$$
After that, I assume that the total number of forms for the $n$ step is $2^n$, which has to be the sum of the different number of forms for each number $0 ,…, n$ of zero rows, the specifics of which I ignore for now (really, because I couldn't prove it myself).
Then, for each $n \times n$ form with given number of zero rows $Z$, I can embed it in a $(n+1) \times (n+1)$ matrix where the first zero row $z$ from the embedded matrix can be extended to have an $z_{n+1}$ entry in $\{1, 0\}$. If $z_{n+1} = 0$, there is a one-to-one correspondence with the sets of $n\times n$ forms indexed by $Z$, except when $Z=0$. The same argument applies to $z_{n+1} = 1$. Notice that for the $Z=0$ case, the smaller matrix can be embedded in a matrix where the last entry is either $0$ or $1$, which results in two RRE additional forms for the larger matrix.
Finally, the two one-to-one mappings contribute $2^n -1$ forms each. Adding the last two cases, we have $2^n – 1 + 2^n -1 +2 = 2^{n+1}$ forms and the induction is complete.
I feel my reasoning is somewhat convoluted, so I'd appreciate it if any flaws could be pointed out. My textbook had a hint about using Pascal's triangle, and I did notice that the number of forms linked to each $Z$ follows the pattern, but I was unable to set up a counting scheme for all possible pivot positions to show that this applies generally, so I would appreciate guidance in that regard.
Best Answer
A form with $k$ non-zero rows will have $k$ pivots which can be in columns $1,...,n$. Since the pivots must be ordered so that each one is to the right of the previous one, they can only be picked in increasing order, that is, only one ordering matters and this is equivalent to picking a combination of $k$ in $n$ elements.
Therefore, for a given $n \times n$ matrix, we have $\sum_{k=0}^n {n \choose k} = 2^n$ forms.