$page_title       = "Exhibit: How many row reduced echelon matrices?";
$page_description = "Exhibit page on row reduction in Math 21b, Linear Algebra and Applications";
${base}           = "../../";
$robots = "all";

sub main_page {
print OUTPUT<<"EOF"

<h2> Number of Row Reduced 0-1 matrices </h2> 

In one of the homework problems you looked for the number of 0-1 matrices which 
are row reduced. The general problem is very interesting. The answer is 
explicitly known for any nxn matrix. 

<br><br><center><table cellpadding="10" width="90%" bgcolor="#000000"><tr><td>
The number of row reduced n x n matrices is given by the sequence
<a href="https://oeis.org/A006116">A006116</a>, a sum of Gaussian Binomial coefficients.
It is the number of subspaces of a vector space over the field Z</sub>2</sup>
or the number of distinct binary linear codes of length n
or the number of Abelian groups in C<sub>2</sub><sup>n</sup>.
The sequence starts as follows: 

<pre>
1, 2, 5, 16, 67, 374, 2825, 29212, 417199, 8283458, ...
</pre>

Here are all 15 nonzero 3x3 cases: 

<center>
<img src="3.png">
</center>

Here are all 66 nonzero 4x4 cases. Would be nice homework problem....

<center>
<img src="4.png">
</center> 

And counting all the 5x5 cases would be a nice exam problem...


<center>
<img src="5.png">
</center>


Here is how one can compute that with brute force: 

<pre>
(* How many row reduced 0-1 matrices are there of size n x n ?            *)
F[n_]:=Module[{i,u,m=n^2},
 i[x_]:=Partition[PadLeft[IntegerDigits[x,2],m],n];
 u=Map[i,Range[0,2^m-1]];    (* produces list of all 0-1 matrices         *)
 v=Union[Table[RowReduce[u[[k]]],{k,2^m-1}]];
 w={}; Do[If[Sort[Union[Flatten[v[[k]]]]]=={0,1},
       w=Append[w,v[[k]]]],{k,Length[v]}]; 1+Length[w]];
F[4] 
</pre>

When first computing this, I (Oliver) had not checked that the row reduced matrices
are still 0-1 matrices. Actually, they are not in general. Thanks to <b>Jun Hou Fou</b>
(whom you know from teaching 21a last semester) for pointing this out to me 
and telling about the connection to the subspace problem and the sequence A006116.


EOF
}

1;