Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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. –  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
1  
Add that information on the body of the question. –  Mariano Suárez-Alvarez Apr 3 '12 at 2:35
2  
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
1  
See mathoverflow.net/questions/18636/… –  alex Apr 3 '12 at 8:17
show 3 more comments

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
    
It definitely helps. –  Sunni Apr 3 '12 at 2:37
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.