24
$\begingroup$

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.

$\endgroup$

2 Answers 2

41
$\begingroup$

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.

enter image description here

$\endgroup$
18
$\begingroup$

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.

$\endgroup$
7
  • 2
    $\begingroup$ [+1] thorough analysis. $\endgroup$
    – Jean Marie
    Mar 2, 2017 at 11:17
  • $\begingroup$ @H.H.Rugh Can we find out minimal polynomial of given permutation matrix with this information? $\endgroup$ Jul 17, 2020 at 15:30
  • $\begingroup$ @Ibs Note sure. But testing on examples it looks as if it is the product of $(1-t^{|c_i|})$ over distinct cycle lengths. $\endgroup$
    – H. H. Rugh
    Jul 17, 2020 at 17:26
  • $\begingroup$ @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! $\endgroup$ Jul 17, 2020 at 17:40
  • $\begingroup$ @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) $\endgroup$
    – H. H. Rugh
    Jul 17, 2020 at 18:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .