# Size of GLn

1. Oct 12, 2008

### Dragonfall

What is the size of $GL_n(\mathbb{Z}_2)$?

2. Oct 13, 2008

### morphism

Think in terms of linear independence.

3. Oct 13, 2008

### HallsofIvy

Staff Emeritus
You could also think of this as n by n matrices whose entries must be either 1 or 0. How many entries are then in an n by n matrix? And if there are only two possible values for each?

4. Oct 13, 2008

### Dragonfall

Well non-invertible matrices are not in GLn(Z_2), so it's NOT 2^(n^2). Rather it's that minus all the matrices with determinant 0, and I don't know how to count those.

Is it true that an nxn matrix is invertible iff the column space has n dimensions?

5. Oct 16, 2008

### Jang Jin Hong

$$Z_2= \{0,1\}$$ and $$Z_2$$ has only one unit {1}.
so matrix A which satisfy det A = 1 will be element of $$GL_n ( Z_2)$$

6. Oct 16, 2008

### HallsofIvy

Staff Emeritus
Yes, and the whole question is "how many of them are there"!

In fact, a matrix A, in Z2 is invertible if det(A)= 1 and not invertible if det(A)= 0. Does that imply that exactly half of all n by n matrices in Z2[/sup] are invertible?

7. Oct 16, 2008

### morphism

Yes!

No. In fact, this is only true if n=1.

8. Oct 16, 2008

### Dragonfall

I still don't know how to count them. So you have $2^n-1$ choices for the first vector. $2^n-2$ for the second. But how many vectors are linearly independent wrt to the first two?

9. Oct 17, 2008

### morphism

How many linear combinations are there of the first two columns? Remember, there are only two elements in our field.

10. Oct 17, 2008

### Tiger99

I think it's
(2^n -1)(2^n - 2) (2^n - 2^2 ) .... (2^n - 2^{n-1}).

the reason is: you just have to make sure all the rows are linearly independent and non-zero.
For the first row there are (2^n - 1) choices.

For the second row there's (2^n-1) minus 1 (the number of rows already used).

For the third row there's (2^n-1) minus 2 (the number of rows already used) minus another 1 for the number of sums of those rows.

For the kth row, there's (2^n-1) minus (k choose 1) minus (k choose 2), etc., minus (k choose (k-1)). You can tell that none of these conditions are redundant because that would imply that some of the previous rows were linearly dependent.

But
k choose 1 + k choose 2 + ... + k choose (k-1) = 2^{k} -1.

?

Last edited: Oct 17, 2008