Posted by: JBL | August 5, 2015

Permutation cycle type puzzle

Suppose that $w$ is a permutation with 8 cycles, all of whose lengths divide 12.  If $w^2$ has 13 cycles, $w^3$ has 16, $w^4$ has 15, $w^6$ has 25, and $w^{12}$ has 27, what is the cycle type of w?
What can we say if we drop the guarantee that all cycle lengths divide 12?

Responses

1. Hm, say there are A 1s, B 2s, C 3s, D 4s, E 6s, F 12s.

A+B+C+D+E+F = 8
A+2B+C+2D+2E+2F = 13
A+B+3C+D+3E+3F = 16
A+2B+C+4D+2E+4F = 15
A+2B+3C+2D+6E+6F = 25
A+2B+3C+4E+6E+12F = 27

This has a unique solution (1,1,2,2,3,-1). What did I do wrong?

I bet row-reducing this matrix amounts to computing the standard Mobius function…

2. Just arithmetic, probably: your proposed solution doesn’t satisfy the last equation.

I had thought it was going to be just the usual Moebius function (or a simple twist), but it seems a little bit more complicated. I believe you would get mu if I gave you data on number of fixed points instead of number of cycles.

3. Oh, I understand your last comment now. Yes, that’s exactly what’s going on; the matrix in question is the product of the zeta matrix for divisibility relation, a diagonal matrix, and the transpose of the zeta matrix, so when you row-reduce you’re exactly doing some Möbius inversion