# How do you determine the characteristic polynomial of a permutation matrix based on the cycle type of the corresponding permutation??

I read in a paper that you could use the following equation to find the characteristic polynomial of any permutation matrix using the cycle type of the corresponding permutation, but did not understand what $$n$$, $$k$$, or $$C_k$$ stand for in the context of the equation:

$$p(\lambda) = \det(M \sigma − λI) = (−1)^n \prod_{k=1}^{n}(\lambda^k − 1)^{C_k}$$

Could someone please explain to me using a simple example such as (1 2 3) what numbers to plug in for $$n$$, $$k$$, and $$C_k$$ to arrive at the correct characteristic polynomial for the corresponding matrix (in this case [[0 0 1], [1 0 0], [0 1 0]])?

Here is a link to the paper if this helps: https://www.math.arizona.edu/~ura-reports/003/blair-stahn/rpmevals.pdf

Thank you so much for your help!

The characteristic polynomial of a linear transformation does not depend on a choice of basis, so given any permutation matrix $$M_{\sigma}$$ we may as well reorder the standard basis to produce a basis with respect to which the corresponding permutation matrix is a direct sum $$\bigoplus_i P_{k_i}$$ of permutation matrices $$P_k = \pmatrix{&&&1\\1\\&\ddots\\&&1},$$ which respectively are $$k \times k$$; the variable $$i$$ indexes the cycles of $$\sigma$$. Of course $$P_k$$ is just the permutation matrix for the standard $$k$$-cycle, $$(1 \cdots k)$$. Computing using the cofactor expansion (most terms disappear, owing to the large number of zero entries) gives that the characteristic polynomial $$P_k$$ is $$p_{P_k}(\lambda) = \det (P_k - \lambda I) = (-1)^k (\lambda^k - 1).$$ The determinant of a direct sum of (square) matrices is the product of the determinants of those matrices, so the characteristic polynomial of $$\sigma$$ is $$\begin{multline}p(\lambda) = \det \left(\oplus_i P_{k_i} - \lambda I_n\right) = \det [\oplus_i (P_{k_i} - \lambda I_{k_i})] \\= \prod_i \det(P_{k_i} - \lambda I_{k_i}) = \prod_i [(-1)^{k_i} p_{P_k}(\lambda)] = (-1)^n \prod_i (\lambda^{k_i} - 1) . \end{multline}$$ If we instead index the product by cycle length, then if there are $$C_k$$ cycles of length $$k$$ (that is, if we declare $$C_k$$ to be the number of index values $$i$$ for which $$k_i = k$$), then their combined contribution to the last product is $$(\lambda^k - 1)^{C_k}$$. Thus, we can rewrite the above equation as $$\boxed{p(\lambda) = \prod_{k = 1}^n (\lambda^k - 1)^{C_k}}$$ as claimed.
• $$n$$ is the size of the set on which the permutations are acting,
• the variable $$k$$ indexes the sizes of the cycles in the given permutation $$\sigma$$,
• for each $$k$$, $$C_k$$ is the number of cycles of length $$k$$ in the cycle decomposition of $$\sigma$$.
In your example, where the permutation is $$(123)$$ (acting on a set of three elements), the permutation is a product of $$1$$ $$3$$-cycle (so that $$C_3 = 1$$), no $$2$$-cycles ($$C_2 = 0$$), and no trivial cycles (so $$C_1 = 0$$). So, our above formula gives that the characteristic polynomial of $$M_{(123)}$$ is $$p(\lambda) = \lambda^3 - 1 .$$
If instead $$(123)$$ is a permutation on a set of $$n > 3$$ elements, we have $$C_3 = 1$$, $$C_1 = n - 3$$, and $$C_k = 0$$ for all other $$k$$, and thus the characteristic polynomial is $$p(\lambda) = (\lambda^3 - 1)(\lambda - 1)^{n - 3} .$$