Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

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

share|improve this answer
    
@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
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.