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?



Morphisms between representations
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.


