# number of invertible 0-1 matrices

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})$.

-
It would not hurt if you were explicit about whether you want invertibility of the matrix as real matrices or over some other field (possibly the field with two elements) The answer will depend in this. – Mariano Suárez-Alvarez Apr 3 '12 at 2:32
the matrices considered are with entries from real field. – Sunni Apr 3 '12 at 2:34
Add that information on the body of the question. – Mariano Suárez-Alvarez Apr 3 '12 at 2:35
Sunni, please note that if matrices are over $\mathbb{Z}_2$ then $S_n$ is essentially the general linear group: $\mathsf{GL}(n, \mathbb{Z}_2),$ which has size $\displaystyle\prod_{i=0}^{n-1} (2^n- 2^i).$ But if matrices are over $\mathbb{R},$ then you're looking at $S_n \subset \mathsf{GL}(n, \mathbb{R}).$ The accepted answer by Daniel M. addresses the former case not the latter case. – user2468 Apr 3 '12 at 3:57
– alexx Apr 3 '12 at 8:17

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.
This is incorrect; it addresses invertibility over $\mathbb{F}_2$ when the OP wants invertibility over $\mathbb{R}$. – Qiaochu Yuan Apr 3 '12 at 2:59
Downvoter: timestamps reveal that this answer was posted before OP posted a comment about invertibility over $\mathbb R.$ – user2468 Apr 3 '12 at 6:17
Yeah. I did not read that the problem it was over $\mathbb{R}$, I assumed it was over $F_2$ by his guess. – Daniel Montealegre Apr 3 '12 at 21:34