3x3 Diagonalizable Matrices over GF(2)

  • Thread starter ArcanaNoir
  • Start date
  • #1
768
4
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 :)
 

Answers and Replies

  • #2
I like Serena
Homework Helper
6,577
176
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 :)
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
22,089
3,293
According to the spectral theorem, a real matrix is diagonalizable if and only if it is symmetric.
No, this is false. There are plenty of matrices which are diagonalizable but not symmetric.
 
  • #4
I like Serena
Homework Helper
6,577
176
No, this is false. There are plenty of matrices which are diagonalizable but not symmetric.
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
22,089
3,293
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."
A diagonalizable matrix need not have an orthonormal basis of eigenvectors.
 
  • #6
I like Serena
Homework Helper
6,577
176
A diagonalizable matrix need not have an orthonormal basis of eigenvectors.
Good point. I'll take the time to digest that.
 
  • #7
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,109
278
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
WannabeNewton
Science Advisor
5,800
534
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
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,109
278
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
22,089
3,293
Over GF(2) all 3x3 matrices that are invertible have determinant 1.
So all invertible matrices are orthogonal.
I'm not seeing the connection between orthogonal and having determinant 1.

Therefore each basis of independent eigenvectors has an associated matrix that is orthogonal.
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.

[tex]\left(\begin{array} 1 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 1\end{array}\right)[/tex]



It means that in this particular case, each diagonalizable matrix is symmetric.
Counterexample:

[tex]\left(\begin{array} 1 & 0 & 1\\ 0 & 1 & 0\\ 0 & 0 & 0\end{array}\right)[/tex]
 
  • #11
I like Serena
Homework Helper
6,577
176
I had already deleted my post.
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
768
4
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
They need not be invertible.

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.
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
768
4
I had already deleted my post.
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}$$
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
I like Serena
Homework Helper
6,577
176
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?
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
768
4
:surprised I just checked the paper again and it is diagonal matrices, not diagonalizable. The world is saved again :)
 
  • #16
768
4
And thanks to everybody for all your input :)
 
  • #17
I like Serena
Homework Helper
6,577
176
:surprised I just checked the paper again and it is diagonal matrices, not diagonalizable. The world is saved again :)
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.
Ah well, just for the record, the sum of those 58 matrices is the identity matrix! :smile:
 
  • #18
768
4
Oh thats interesting :) I don't suppose you've seen my post in the precalc forum about an associative function... *my hero* ;)
 
  • #19
I like Serena
Homework Helper
6,577
176
Oh thats interesting :) I don't suppose you've seen my post in the precalc forum about an associative function... *my hero* ;)
Yeah, I saw it... but I do not consider it precalc. :wink:
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
768
4
Yeah, I saw it... but I do not consider it precalc. :wink:
Do you mean I'm allowed to post in the big-people sections now?
 
  • #21
22,089
3,293
I would say the post is precalculus, since it's just an algebraic manipulation.
 
  • #22
I like Serena
Homework Helper
6,577
176
Do you mean I'm allowed to post in the big-people sections now?
Dunno.
Until now no one has corrected me for posting in the big-people section.
So I guess that makes it okay.

As for your associativity problem, it seems to me that mere algebraic manipulation is not going to cut it.
Moreover, I'd consider associativity problems part of abstract algebra.
 
  • #23
22,089
3,293
As for your associativity problem, it seems to me that mere algebraic manipulation is not going to cut it.
It will. But it's tedious.
 
  • #24
768
4
I would say the post is precalculus, since it's just an algebraic manipulation.
That's what I thought too.

Moreover, I'd consider associativity problems part of abstract algebra.
It is, it's actually a group theory thing I'm working on.

It will. But it's tedious.
It will? Are you sure? Any hints would be greatly appreciated.
 
  • #25
I like Serena
Homework Helper
6,577
176
It will. But it's tedious.
It appears to turn into a higher order polynomial expression.
It may not be possible to solve that.
At any rate, Wolfram doesn't.
 

Related Threads on 3x3 Diagonalizable Matrices over GF(2)

  • Last Post
Replies
8
Views
2K
Replies
6
Views
15K
Replies
7
Views
3K
  • Last Post
Replies
5
Views
563
Replies
5
Views
3K
Replies
4
Views
6K
  • Last Post
Replies
3
Views
2K
Replies
2
Views
2K
Top