# Conjugacy class of a permutation from its matrix representation

Apologies if this is too basic, but given a permutation matrix $M$, is there any parameter or formula based on $M$ that gives the disjoint cycle decomposition, or at least the conjugacy class, of the corresponding permutation?

-
If you actually want to find a cycle decomposition, this probably isn't the way to do it. What is the intended application? – Qiaochu Yuan Feb 15 '11 at 21:40
@Qiaochu Yuan: I know. I'm not actually interested in finding the dcd, I just want to prove a relation between two different constructions and it seems that expressing permutations as matrices may make things easier in this case. – Anthony Labarre Feb 15 '11 at 21:55

## 1 Answer

I don't really see what exactly you expect, as «parameter or formula based on $M$» is a pretty vague description. Here is one option...

You can compute the number of cycles of a specific length from the multiplicities of other eigenvalues---which are all roots of unity. For example, the multiplicity of $1$ as an eigenvalue is the number of cycles.

More generally, if we call $c_\ell$ the number of cycles of length $\ell$ in the permutation, and $\mu_n$ the multiplicity of $e^{2\pi i/n}$ as an eigenvalue of the matrix, then $$\mu_n = \sum_{n\mid\ell}c_\ell.$$ This relation be inverted using Moebius inversion to a formula exactly expressing the $c_\ell$ in terms of the multiplicities $\mu_n$.

-
@Mariano: I guess the multiplicity of 1 as an eigenvalue is the number of fixed points (and not the number of cycles). If I am correct, I will delete this comment after you modify your answer. – Did Feb 15 '11 at 21:14
@Didier: pick an $n$-cycle in $S_n$ and compute the eigenvalues of its corresponding permutation matrix. What is the multiplicity of $1$? – Mariano Suárez-Alvarez Feb 15 '11 at 21:16
An example is the shortest way from a guess to a statement :) – Mariano Suárez-Alvarez Feb 15 '11 at 21:18
@Mariano: Touché. What is more, this also stems from the formula for $\mu_1$ you provide next. Well, I guess the hour is too late for me... – Did Feb 15 '11 at 21:21
Thanks, I actually started thinking about the characteristic polynomial shortly after submitting the question. This seems to fit my purposes, but I still need to verify it. – Anthony Labarre Feb 15 '11 at 21:29