# 3x3 Diagonalizable Matrices over GF(2)

1. May 9, 2013

### ArcanaNoir

Does anyone know where I can find or how I can compute (without checking all 512) the 8 diagonalizable 3x3 matrices over GF(2)? GF(2) means the entries are 0's and 1's. I'm working on some graph polynomial research and to check out a formula I'm working with I would have to take a sum over these 8 little guys but I don't know what they are. I'm not too up on my linear algebra, but I believe diagonalizable implies there will be 3 distinct eignenvalues. Not sure if that helps narrow the possible forms of the matrices down. Is there some way I can cut the possibilities down from 512 to something I could more reasonably check by hand? Or some maple code? Thanks for any help :)

2. May 9, 2013

### I like Serena

Hey Arcana!

A diagonal matrix has only non-zero entries on its main diagonal.
The main diagonal has 3 entries, each of which can either be 0 or 1.
That makes 8 possible diagonal matrices.
If the ordering of eigenvalues is not relevant, that leaves 4 diagonal matrices.
Note that the eigenvalues cannot be distinct, since you have 3 entries on the diagonal but only 2 possible eigenvalues.

According to the spectral theorem, a real matrix is diagonalizable if and only if it is symmetric.
I think it also holds for matrices over the field GF(2).
That means that you have a free choice for the upper triangular matrix for 2^6=64 choices. After that the remaining part of the lower triangle is fixed.

3. May 9, 2013

### micromass

Staff Emeritus
No, this is false. There are plenty of matrices which are diagonalizable but not symmetric.

4. May 9, 2013

### I like Serena

From the link I provided:
"Another way to phrase the spectral theorem is that a real n×n matrix A is symmetric if and only if there is an orthonormal basis of consisting of eigenvectors for A."

5. May 9, 2013

### micromass

Staff Emeritus
A diagonalizable matrix need not have an orthonormal basis of eigenvectors.

6. May 9, 2013

### I like Serena

Good point. I'll take the time to digest that.

7. May 9, 2013

### Office_Shredder

Staff Emeritus
There are definitely more than 8 diagonalizable matrices because there are 8 diagonal matrices. Because you're in F(2) the only eigenvalues are 0 or 1 - this is nice because it means that all diagonal matrices are projections (and hence all diagonalizable matrices are projections as well, and vice versa of course). This means that P is diagonalizable if and only if P = P2 which gives a ton of algebraic relations - it might be possible to solve directly but you only have 512 matrices so you could write some code to output all matrices such that P = P2 pretty fast if you know how to program

I Like Serena: All you need is a basis of eigenvectors, doesn't matter if they're orthogonal to each other.

8. May 9, 2013

### WannabeNewton

The spectral theorem states that a matrix is orthogonally diagonalizable (i.e. has an orthogonal eigenbasis) with real eigenvalues if and only if it is self-adjoint. However as noted above, there of course exist diagonalizable matrices whose eigenbasis is not orthogonal and whose eigenvalues are not all real.

Also, a matrix doesn't have to have distinct eigenvalues to be diagonalizable. The converse is true of course but the original statement is false (take the identity matrix for example). All you need is for the geometric multiplicities of the eigenspaces to add up to the dimension of the original space.

9. May 9, 2013

### Office_Shredder

Staff Emeritus
So I just realized I have a bit of a disconnect with the notation in the OP. Do you want diaogonalizable matrices, or diagonalizable invertible matrices? Because there is only one of the latter

10. May 9, 2013

### micromass

Staff Emeritus
I'm not seeing the connection between orthogonal and having determinant 1.

How would you define "orthogonal" in $\mathbb{F}_2$ anyway. There is no inner product on that space. At most, there is a symmetric bilinear form.

$$\left(\begin{array} 1 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 1\end{array}\right)$$

Counterexample:

$$\left(\begin{array} 1 & 0 & 1\\ 0 & 1 & 0\\ 0 & 0 & 0\end{array}\right)$$

11. May 9, 2013

### I like Serena

Still, you make good points.

So I wrote a program to count the invertible matrices, and to count the diagonalizable matrices.
I got the surprising result that there are 168 invertible matrices and 58 diagonalizable matrices.

It turns out that for instance the following symmetric matrix is not diagonalizable:
$$\begin{bmatrix}0&1&0 \\ 1&0&0 \\0&0&0\end{bmatrix}$$

12. May 9, 2013

### ArcanaNoir

They need not be invertible.

I'm confused about this, first you say the main diagonal can only have non-zero entries, but then you say the main diagonal can have 0's or 1's. Also, diagonalizable is not the same as diagonal, right?

13. May 9, 2013

### ArcanaNoir

58? Crap! They must have started at n=0... :(:(:( Well in that case there is no way I'm going to do this sum over 58 matrices.

14. May 9, 2013

### I like Serena

Sorry for the confusion.
A diagonal matrix can have zeroes on its diagonal.
It's just that all other entries have to be zero.

And yes, diagonalizable is not the same as diagonal.

15. May 9, 2013

### ArcanaNoir

:surprised I just checked the paper again and it is diagonal matrices, not diagonalizable. The world is saved again :)

16. May 9, 2013

### ArcanaNoir

And thanks to everybody for all your input :)

17. May 9, 2013

### I like Serena

Ah well, just for the record, the sum of those 58 matrices is the identity matrix!

18. May 9, 2013

### ArcanaNoir

Oh thats interesting :) I don't suppose you've seen my post in the precalc forum about an associative function... *my hero* ;)

19. May 9, 2013

### I like Serena

Yeah, I saw it... but I do not consider it precalc.
With my first couple of attempts I couldn't prove associativity, although I could verify with a couple of examples that it does seem to be associative.
So for now I decided not to add to the zero-count of the thread.
Perhaps someone else is more creative than I am.

20. May 9, 2013

### ArcanaNoir

Do you mean I'm allowed to post in the big-people sections now?