- #1

- 1,030

- 4

## Main Question or Discussion Point

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

- Thread starter Dragonfall
- Start date

- #1

- 1,030

- 4

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

- #2

morphism

Science Advisor

Homework Helper

- 2,015

- 4

Think in terms of linear independence.

- #3

HallsofIvy

Science Advisor

Homework Helper

- 41,833

- 955

- #4

- 1,030

- 4

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?Think in terms of linear independence.

- #5

- 21

- 0

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

In fact, a matrix A, in Z

- #7

morphism

Science Advisor

Homework Helper

- 2,015

- 4

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

In fact, a matrix A, in Z_{2}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?}

- #8

- 1,030

- 4

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?Yes!

- #9

morphism

Science Advisor

Homework Helper

- 2,015

- 4

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

?

(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:

- 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

- Replies
- 1

- Views
- 1K