2
$\begingroup$

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

  • 2
    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.2012-04-03
  • 0
    the matrices considered are with entries from real field.2012-04-03
  • 1
    Add that information on the body of the question.2012-04-03
  • 0
    Dear Sunni, your answe to my question in the comment above is contradicted by your acceptance of Daniel's answer below...2012-04-03
  • 2
    Sunni, 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
  • 1
    See http://mathoverflow.net/questions/18636/number-of-invertible-0-1-real-matrices2012-04-03
  • 0
    Also: http://math.stackexchange.com/questions/54246/probability-that-a-random-binary-matrix-is-invertible2012-04-03
  • 0
    Sorry all... so the conclusion is that my guess in the question is wrong and there is no known formula.2012-04-03

1 Answers 1

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.

  • 0
    It definitely helps.2012-04-03
  • 1
    This is incorrect; it addresses invertibility over $\mathbb{F}_2$ when the OP wants invertibility over $\mathbb{R}$.2012-04-03
  • 0
    Downvoter: timestamps reveal that this answer was posted **before** OP posted a comment about invertibility over $\mathbb R.$2012-04-03
  • 0
    Yeah. 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