Exploring the Size of GL_n(Z2)

[Dragonfall]

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

 

[morphism]

Think in terms of linear independence.

 

[HallsofIvy]

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?

 

[Dragonfall]

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?

 

[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)$$

 

[HallsofIvy]

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

In fact, a matrix A, in Z₂ 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 Z_{2[/sup] are invertible?}

 

[morphism]

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

Yes!

In fact, a matrix A, in Z₂ 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 Z_{2[/sup] are invertible?}

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

 

[Dragonfall]

Yes!

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?

 

[morphism]

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

 

[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.

?