21
$\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

31
$\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$
17
$\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.