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
-
2It 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. – 2012-04-03
-
0the matrices considered are with entries from real field. – 2012-04-03
-
1Add that information on the body of the question. – 2012-04-03
-
0Dear Sunni, your answe to my question in the comment above is contradicted by your acceptance of Daniel's answer below... – 2012-04-03
-
2Sunni, please note that if matrices are over $\mathbb{Z}_2$ then $S_n$ is essentially the [general linear group](http://en.wikipedia.org/wiki/General_linear_group#Over_finite_fields): $\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. – 2012-04-03
-
1See http://mathoverflow.net/questions/18636/number-of-invertible-0-1-real-matrices – 2012-04-03
-
0Also: http://math.stackexchange.com/questions/54246/probability-that-a-random-binary-matrix-is-invertible – 2012-04-03
-
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.
-
0It definitely helps. – 2012-04-03
-
1This is incorrect; it addresses invertibility over $\mathbb{F}_2$ when the OP wants invertibility over $\mathbb{R}$. – 2012-04-03
-
0Downvoter: timestamps reveal that this answer was posted **before** OP posted a comment about invertibility over $\mathbb R.$ – 2012-04-03
-
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