Define the set $S_n=\{A_n| A_n \hbox{is invertible 0-1 matrix}\}$. What is the size of $S_n$? When $n=2$, it is easy to see $\sharp S_2=6$. I guess $\sharp S_n=\prod_{k=1}^n(2^n-2^{k-1})$.
Number of invertible 0-1 matrices
2
$\begingroup$
linear-algebra
combinatorics
matrices
-
0Sorry all... so the conclusion is that my guess in the question is wrong and there is no known formula. – 2012-04-03
1 Answers
6
Your guess is almost right ($k$ should start at $0$). This is a particular case of the order of the general linear group over a field $F$.
In your case here is how the proof goes. You first want a non-zero column for your matrix. You have $2^n-1$ options to pick such first column. Then, you want to pick a column that is linearly independent from your first column, so you have a total of $2^n$ possible options for this entry minus the multiples of the first column, in this case $2$. For the third column you again have to substract the linear combinations of the first two columns in this case is $2^2$. Doing so you obtain: $(2^n-1)(2^n-2)(2^n-2^2)...(2^n-2^{n-1})$Hope this helps.
-
0Yeah. I did not read that the problem it was over $\mathbb{R}$, I assumed it was over $F_2$ by his guess. – 2012-04-03