Size of GLn

  • Thread starter Dragonfall
  • Start date
  • #1
1,030
4

Main Question or Discussion Point

What is the size of [itex]GL_n(\mathbb{Z}_2)[/itex]?
 

Answers and Replies

  • #2
morphism
Science Advisor
Homework Helper
2,015
4
Think in terms of linear independence.
 
  • #3
HallsofIvy
Science Advisor
Homework Helper
41,833
955
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
1,030
4
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?
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.

Think in terms of linear independence.
Is it true that an nxn matrix is invertible iff the column space has n dimensions?
 
  • #5
[tex]Z_2= \{0,1\}[/tex] and [tex]Z_2[/tex] has only one unit {1}.
so matrix A which satisfy det A = 1 will be element of [tex]GL_n ( Z_2) [/tex]
 
  • #6
HallsofIvy
Science Advisor
Homework Helper
41,833
955
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
morphism
Science Advisor
Homework Helper
2,015
4
Is it true that an nxn matrix is invertible iff the column space has n dimensions?
Yes!

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?

No. In fact, this is only true if n=1.
 
  • #8
1,030
4
Yes!
I still don't know how to count them. So you have [itex]2^n-1[/itex] choices for the first vector. [itex]2^n-2[/itex] for the second. But how many vectors are linearly independent wrt to the first two?
 
  • #9
morphism
Science Advisor
Homework Helper
2,015
4
How many linear combinations are there of the first two columns? Remember, there are only two elements in our field.
 
  • #10
41
0
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:

Related Threads on Size of GLn

  • Last Post
Replies
5
Views
6K
  • Last Post
Replies
12
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
1K
Replies
3
Views
2K
  • Last Post
Replies
6
Views
3K
Replies
12
Views
3K
Replies
1
Views
2K
Top