# What are the properties of eigenvalues of permutation matrices?

Up till now, the only things I was able to come up/prove are the following properties:

• $\prod\lambda_i = \pm 1$
• $0 \leq \sum \lambda_i \leq n$, where $n$ is the size of the matrix
• eigenvalues of the permutation matrix lie on the unit circle

I am curious whether there exist some other interesting properties.

A permutation matrix is an orthogonal matrix (orthogonality of column vectors and norm of column vectors = 1).

As such, because an orthogonal matrix "is" an isometry

$$\tag{1}\|PV\|=\|V\|$$

If $$V$$ is an eigenvector associated with eigenvalue $$\lambda$$, substituting $$PV=\lambda V$$ in (1) we deduce

$$|\lambda|=1.$$

Moreover, as $$P^p=I_n$$ ($$p$$ is the order of the permutation) these eigenvalues are such that $$\lambda^p=1$$; therefore

$$\lambda=e^{i k 2\pi/p}$$

for some $$k \in \mathbb{Z}$$.

Let us take an example: consider the following permutation decomposed into the product of two disjoint support cycles

a cycle $$\color{red}{(5 4 3 2 1)}$$ of order $$5$$ and a cycle $$\color{blue}{(6 7 8)}$$ of order $$3$$.

Its associated matrix is:

$$\left(\begin{array}{ccccc|ccc} 0 & \color{red}{1} & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & \color{red}{1} & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & \color{red}{1} & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & \color{red}{1} & 0 & 0 & 0\\ \color{red}{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & \color{blue}{1}\\ 0 & 0 & 0 & 0 & 0 & \color{blue}{1} & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & \color{blue}{1} & 0\end{array}\right)$$

Its cycle structure is reflected (see picture) into the five eigenvalues $$\color{red}{e^{2i k\pi/5}}$$ and the three eigenvalues $$\color{blue}{e^{2i k\pi/3}}$$.

Please note that eigenvalue $$1$$ is - in a natural way - a double eigenvalue, and more generally with multiplicity $$m$$ if the permutation can be decomposed into $$m$$ disjoint cycles.

A permutation may be written as a unique product of primitive cycles $\pi = (c_1)\cdots(c_k)$. This corresponds to writing the matrix in block form with each cycle representing a block. Each cycle of length $|c_i|$ has precisely the $|c_i|$'th roots of unity as eigenvalues. This tells you at least precisely when a collection of eigenvalues (with multiplicity) may correspond to a permutation matrix.

• [+1] thorough analysis. Mar 2, 2017 at 11:17
• @H.H.Rugh Can we find out minimal polynomial of given permutation matrix with this information? Jul 17, 2020 at 15:30
• @Ibs Note sure. But testing on examples it looks as if it is the product of $(1-t^{|c_i|})$ over distinct cycle lengths. Jul 17, 2020 at 17:26
• @H.H.Rugh can you please tell me the name of book where I can find these properties of Permutation matrix,I will be thankful to you! Jul 17, 2020 at 17:40
• @Ibs You may have a look at math.stackexchange.com/questions/3265988/… for a bit more explanations. I don't really have any book which gives these properties of permutation matrices. I personally fancy P.M.Cohn Algebra vol 1 (end 2) but it doesn't describe the above (and the books are on a bit advanced level) Jul 17, 2020 at 18:36