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.

In summary, in this last display equation,

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