3x3 Diagonalizable Matrices over GF(2)

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

 

[I like Serena]

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.

 

[micromass]

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.

 

[I like Serena]

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

 

[micromass]

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.

 

[I like Serena]

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

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

 

[Office_Shredder]

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 = P² 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 = P² 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.

 

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

 

[Office_Shredder]

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

 

[micromass]

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.

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

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

Counterexample:

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

 

[I like Serena]

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}$$

 

[ArcanaNoir]

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?

 

[ArcanaNoir]

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.

 

[I like Serena]

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.

 

[ArcanaNoir]

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

 

[ArcanaNoir]

And thanks to everybody for all your input :)

 

[I like Serena]

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!

 

[ArcanaNoir]

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

 

[I like Serena]

Oh that's 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.
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.

 

[ArcanaNoir]

Yeah, I saw it... but I do not consider it precalc.

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

 

[micromass]

I would say the post is precalculus, since it's just an algebraic manipulation.

 

[I like Serena]

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.

 

[micromass]

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.

 

[ArcanaNoir]

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.

 

[I like Serena]

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.

 

[ArcanaNoir]

It appears to turn into a higher order polynomial expression.
It may not be possible to solve that.
At any rate, Wolfram doesn't.

Neither will maple. Although maple sucks at algebraic manipulation.

 

[I like Serena]

I just noticed that this sub forum for abstract algebra is now moderated by Mark44 and Fredrik.
... but neither of those two is high up into abstract algebra.
It seems micromass has left some sort of vacuum here...

 

[micromass]

Mark44 and Fredrik certainly know their abstract algebra. Mark44 has a masters in math (and maybe more), so he's more than capable. And I've seen Fredrik make some very good abstract algebra posts.

Besides, you don't need to be an expert in a subject to be able to moderate something well. I'm certainly no expert in abstract algebra related things, but I did feel like I had no trouble moderating it.

 

[I like Serena]

Mark44 and Fredrik certainly know their abstract algebra. Mark44 has a masters in math (and maybe more), so he's more than capable. And I've seen Fredrik make some very good abstract algebra posts.

Besides, you don't need to be an expert in a subject to be able to moderate something well. I'm certainly no expert in abstract algebra related things, but I did feel like I had no trouble moderating it.

I'm sorry.
I didn't mean to criticize you or Mark44 or Fredrik.
My remark was more intended as a compliment to you, since I do consider you to be high up.

 

[ArcanaNoir]

I just noticed that this sub forum for abstract algebra is now moderated by Mark44 and Fredrik.
... but neither of those two is high up into abstract algebra.
It seems micromass has left some sort of vacuum here...

Mark44 and Fredrik certainly know their abstract algebra. Mark44 has a masters in math (and maybe more), so he's more than capable. And I've seen Fredrik make some very good abstract algebra posts.

Besides, you don't need to be an expert in a subject to be able to moderate something well. I'm certainly no expert in abstract algebra related things, but I did feel like I had no trouble moderating it.

Yeah I don't think who the moderator is makes much difference, it seems like everyone tries to answer whatever they can. It's not like only moderators answer questions and only in their own forums. Besides, I didn't even put it in the algebra forum. As micro said, it feels like I might be able to solve it with "the math we used to call algebra before we learned about abstract algebra and which now seems to lack an appropriate designation".

 

[HallsofIvy]

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?

IlikeSerena made a slight grammatical error.

He/she said "the main diagonal can only have non-zero entries". What he/she meant to say was "only the main diagonal can have non-zero entries". The position of the word "only" is crucial!

 

[ArcanaNoir]

IlikeSerena made a slight grammatical error.

He/she said "the main diagonal can only have non-zero entries". What he/she meant to say was "only the main diagonal can have non-zero entries". The position of the word "only" is crucial!

thanks for the clarification :)