0
$\begingroup$

I am looking at the automorphism group $G$ of a graph, represented as permutation matrices. The point in a proof I am trying to understand goes something like this:

"For any permutation matrix $P$ in $G$ there exists an orthogonal matrix $Q$ such that $Q^{-1}PQ=A$, where $A$ is a block-diagonal matrix representing a direct product of orthogonal groups. Hence there is an embedding of $G$ into this direct product."

Why is this? Is it always true that a morphism between two groups can be represented by a matrix $Q$ such that $Q^{-1}PQ=A$, where $P$ and $A$ are matrices representing elements of the domain and the image respectively? Or is this only the case for morphisms between two different representations of the same group?

If it is not true in general, why does it work in this specific case?

Improve this question
$\endgroup$
1
  • $\begingroup$ I don't know what is a "block-diagonal matrix representing a direct product of orthogonal groups", but there exists one fixed matrix Q which simultaneously block-diagonalizes all matrices of G. Sizes of the blocks are just dimensions of irreducible representations of G. In particular, if G=P then you are talking about a regular representation of $S_n$. $\endgroup$
    – Paul Yuryev
    Commented Oct 22, 2010 at 15:09

3 Answers 3

Reset to default
2
$\begingroup$

Isn't this just a fancy way of talking about the cycle decomposition of a permutation? The language you use is a little imprecise. But, firstly, by change of basis P can be made into a block matrix form, with each block corresponding to a cycle. And secondly one needs only to think of a cyclic permutation in matrix form, say with 1's mostly just above the diagonal, to see it as an orthogonal matrix.

Improve this answer
$\endgroup$
1
$\begingroup$

It sounds like you are decomposing the permutation into cycles and then translate this into linear algebra.

Improve this answer
$\endgroup$
0
$\begingroup$

Thanks for the answers. Just to clear things up: I don't think this is the same thing as a cycle decomposition. I'm afraid my language is imprecise because I am fairly new to this whole subject (hence the question).

As an example of what I'm talking about: there is a (supposedly!) well-known result that if the eigenvalues of the adjacency matrix of a graph are all simple, then the automorphism group of that graph is an abelian 2-group.

(Sketch of Proof)

Any permutation matrix $P$ representing an automorphism of the graph commutes with the adjacency matrix $A$. If $Q$ is the matrix with columns eigenvectors of $A$, then this implies that $Q^{-1}PQ$ is a block-diagonal matrix, where each block $P_n$ of dimension $n$ fixes a block of the eigendecomposition of $A$, that is, ${P_n}^{-1}(\lambda I_n)P_n=\lambda I_n$ for some eigenvalue $\lambda$ with multiplicity $n$.

So if the eigenvalues are all simple, then each block of $Q^{-1}PQ$ has dimension $1$, ie. $Q^{-1}PQ$ is embedded in the group $O(1)\times O(1)\times \ldots$

$O(1)={ \pm 1 }$, so we have that $P^2=1$, ie. it is an element of a 2-group. $\Box$

What I am taking from your answers is that the operation $Q^{-1}PQ$ is a change of basis to a direct sum of irreducible representations. So we are just representing $P$ in such a way that we can see it is an element of $O(1)\times O(1)\times \ldots$

Is this right? I will assume so unless some kind soul is patient enough to read the above and tell me otherwise!

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Let's see: A is a symmetric matrix, P a permutation matrix, and they commute with each other. Each is a normal matrix, so they are simultaneously diagonalisable over the complex numbers. Now the obvious way to diagonalise P is to take the cycle decomposition first, and then to diagonalise the matrix of a cyclic permutation using the fact that it is a circulant (has roots of unity as eigenvalues and eigenvectors you can write down). You seem to want to diagonalise A first ... but it must all come out the same in the end. $\endgroup$
    – Charles Matthews
    Commented Oct 22, 2010 at 20:09
  • $\begingroup$ Thanks Charles! I'm going to have to think about this, but I'm pretty sure you've convinced me. $\endgroup$
    – Adam
    Commented Oct 22, 2010 at 20:39
  • $\begingroup$ Not quite myself. Because if there is more than one cycle the eigenvalues of P are not distinct (1 will have multiplicity equal to the number of cycles), there is a little bit more to say. $\endgroup$
    – Charles Matthews
    Commented Oct 22, 2010 at 20:45
  • $\begingroup$ Coming at this again: if A had an orthogonal group (which would be the case if we knew that A was non-singular) then P would be in it, because the transpose of P is the inverse of P, and P commutes with A. (This is the adjacency matrix, not the notation of the original post). So one part is to try to isolate the eigenspace for 0 for A. On the complement of that, there can be orthogonal blocks. $\endgroup$
    – Charles Matthews
    Commented Oct 23, 2010 at 8:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .