Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

3x3 Diagonalizable Matrices over GF(2)

  1. May 9, 2013 #1
    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. jcsd
  3. May 9, 2013 #2

    I like Serena

    User Avatar
    Homework Helper

    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.
     
  4. May 9, 2013 #3

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    No, this is false. There are plenty of matrices which are diagonalizable but not symmetric.
     
  5. May 9, 2013 #4

    I like Serena

    User Avatar
    Homework Helper

    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."
     
  6. May 9, 2013 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    A diagonalizable matrix need not have an orthonormal basis of eigenvectors.
     
  7. May 9, 2013 #6

    I like Serena

    User Avatar
    Homework Helper

    Good point. I'll take the time to digest that.
     
  8. May 9, 2013 #7

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  9. May 9, 2013 #8

    WannabeNewton

    User Avatar
    Science Advisor

    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.
     
  10. May 9, 2013 #9

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
     
  11. May 9, 2013 #10

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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.

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



    Counterexample:

    [tex]\left(\begin{array} 1 & 0 & 1\\ 0 & 1 & 0\\ 0 & 0 & 0\end{array}\right)[/tex]
     
  12. May 9, 2013 #11

    I like Serena

    User Avatar
    Homework Helper

    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}$$
     
  13. May 9, 2013 #12
    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?
     
  14. May 9, 2013 #13
    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.
     
  15. May 9, 2013 #14

    I like Serena

    User Avatar
    Homework Helper

    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.
     
  16. May 9, 2013 #15
    :surprised I just checked the paper again and it is diagonal matrices, not diagonalizable. The world is saved again :)
     
  17. May 9, 2013 #16
    And thanks to everybody for all your input :)
     
  18. May 9, 2013 #17

    I like Serena

    User Avatar
    Homework Helper

    Ah well, just for the record, the sum of those 58 matrices is the identity matrix! :smile:
     
  19. May 9, 2013 #18
    Oh thats interesting :) I don't suppose you've seen my post in the precalc forum about an associative function... *my hero* ;)
     
  20. May 9, 2013 #19

    I like Serena

    User Avatar
    Homework Helper

    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.
     
  21. May 9, 2013 #20
    Do you mean I'm allowed to post in the big-people sections now?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: 3x3 Diagonalizable Matrices over GF(2)
Loading...