Determinant of a permutation matrix plus identity

Question

Let $A$ be a permutation matrix. Calculate $\det(I + A)$.

---

I tried with the definition of the determinant but couldn't find it. I also tried to use the decomposition of permutations as products of disjoint cycles.

Answer 1

Here's a reasonable approach. First, consider the case in which $A$ is the size $n$ matrix of a single cycle of length $n$. We find that the associated characteristic polynomial is $$ \det(A - \lambda I) = (-1)^n(\lambda^n - 1). $$ To calculate $\det(A + I)$, it suffices to plug in $\lambda = -1$. We find that $$ \det(A + I) = (-1)^n((-1)^n - 1) = \begin{cases}2 & n \text{ is odd,}\\ 0 & n \text{ is even.}\end{cases} $$ For the general case, let $A_1,\dots,A_k$ denote the matrices associated with each of the disjoint cycles in the cycle decomposition of $A$. We see that $A$ is similar (permutation similar, in fact) to the block diagonal matrix $$ PAP^{-1} = \pmatrix{A_1\\ & \ddots \\ && A_k}. $$ It follows that $\det(A + I) = \det(PAP^{-1} + I) = \det(A_1 + I) \cdots \det(A_k + I)$.

Thus, we reach the following conclusion: suppose that the permutation associated with $A$ can be decomposed into a product of $k$ cycles. If one of those cycles has even length, then $\det(A + I) = 0$. Otherwise, we find that $\det(A + I) = 2^k$.

Answer 2

For the readers who want more, the question that follows is as the following : Considering $T_n=\sum_{\sigma \in S_n}^{} det(I+P_{\sigma})$, prove that $T_{n+1}=2T_{n}+n(n-1)T_n$ to determine a simple formula for $T_n$