Eigenvalues and eigenvectors of permutation matrices
How the spectrum of a permutation matrix is related to permutation cycles.
We use the permutation matrix corresponding to the following permutation: \(
\begin{bmatrix}
a \\ b \\ c \\ d \\ e
\end{bmatrix}
\)\(\xrightarrow{P} \) \(
\begin{bmatrix}
c \\ a \\ b \\ e \\ d
\end{bmatrix}
\) as an example. Note that this permutation has one cycle of order 3 and one cycle of order 2.
The corresponding permutation matrix is:\( \text{P=} \)\(
\begin{bmatrix}
0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0
\end{bmatrix}
\)
0. Finding the eigenvalues
Construct a vector \( \text{x = } \)\(
\begin{bmatrix}
a \\ b \\ c \\ 0 \\ 0
\end{bmatrix}
\). Now observe that \( P^3 \text{x = } \text{x} \):\(
\begin{bmatrix}
a \\ b \\ c \\ 0 \\ 0
\end{bmatrix}
\)\( \xrightarrow{P} \)\(
\begin{bmatrix}
c \\ a \\ b \\ 0 \\ 0
\end{bmatrix}
\)\( \xrightarrow{P} \)\(
\begin{bmatrix}
b \\ c \\ a \\ 0 \\ 0
\end{bmatrix}
\)\( \xrightarrow{P} \)\(
\begin{bmatrix}
a \\ b \\ c \\ 0 \\ 0
\end{bmatrix}
\)Thus the eigenvalues \( \lambda \) of \( P \) satisfy \( P^3x = \lambda^3 x = x \Rightarrow \amber{\lambda^3 = 1} \). Thus three of the eigenvalues are the cubic roots of unity.
Similarly, construct a vector \( \text{y = } \)\(
\begin{bmatrix}
0 \\ 0 \\ 0 \\ d \\ e
\end{bmatrix}
\). Now observe that \( P^2 \text{y = } \text{y} \):\(
\begin{bmatrix}
0 \\ 0 \\ 0 \\ d \\ e
\end{bmatrix}
\)\( \xrightarrow{P} \)\(
\begin{bmatrix}
0 \\ 0 \\ 0 \\ e \\ d
\end{bmatrix}
\)\( \xrightarrow{P} \)\(
\begin{bmatrix}
0 \\ 0 \\ 0 \\ d \\ e
\end{bmatrix}
\)Thus the eigenvalues \( \lambda \) of \( P \) satisfy \( P^2y = \lambda^2 y = y \Rightarrow \amber{\lambda^2 = 1} \). Thus the other two eigenvalues are the square roots of unity.
0.1. Generalizing the result
The above result generalizes to any permutation matrix.
If a permutation matrix has a cycle of length k, then the eigenvalues of the permutation matrix are the k-th roots of unity.
For the matrix \( P \) from the example above, the eigenvalues are the cubic roots of unity and the square roots of unity. This can also be verified programmatically:
import torch
P = torch.Tensor([
[0,0,1,0,0],
[1,0,0,0,0],
[0,1,0,0,0],
[0,0,0,0,1],
[0,0,0,1,0]
])
eig = torch.linalg.eig(P)
print(eig.eigenvalues)
### Output: ###
tensor([-0.5000+0.8660j, -0.5000-0.8660j, 1.0000+0.0000j, # cubic roots of unity
1.0000+0.0000j, -1.0000+0.0000j]) # square roots of unity1. Finding the eigenvectors
This part is pretty straightforward:\(
\begin{bmatrix}
a \\ b \\ c \\ 0 \\ 0
\end{bmatrix}
\)\( \xrightarrow{P} \)\(
\begin{bmatrix}
c \\ a \\ b \\ 0 \\ 0
\end{bmatrix}
\)\( = \)\(
\begin{bmatrix}
λa \\ λb \\ λc \\ λ0 \\ λ0
\end{bmatrix}
\)\( \amber{\Rightarrow c = \lambda a, b = \lambda^2 a} \)Thus the eigenvector corresponding to \( \lambda \) is \(
\begin{bmatrix}
a \\ λ^2a \\ λa \\ 0 \\ 0
\end{bmatrix}
\)\( = \)\(
\begin{bmatrix}
λ \\ 1 \\ λ^2 \\ 0 \\ 0
\end{bmatrix}
\) by setting \( a = λ \) (it can be set to any non-zero complex number). This can also be verified programmatically:
print(-eig.eigenvectors[:,0] * 1.73205) # scaled by square root of 3 since the eigenvector is scaled down to norm 1
### Output: ###
tensor([-0.5000+0.8660j, 1.0000+0.0000j, -0.5000-0.8660j, 0.0000-0.0000j,
0.0000-0.0000j])The eigenvectors corresponding to the square roots of unity can be found in similar fashion. For instance, the eigenvector corresponding to the eigenvalue \( -1 \) is:
print(eig.eigenvectors[:,-1] * 1.41425)
### Output: ###
tensor([ 0.0000+0.j, 0.0000+0.j, 0.0000+0.j, -1.0000+0.j, 1.0000+0.j])1.1. Generalizing the result
The above result generalizes to any permutation matrix.
A cycle \( i_1, i_2, ... i_k \) of length \( k \) has the eigenvector with values \( λ, λ^2, ... λ^k \) at those indices and zeros elsewhere corresponding to the eigenvalue \( λ \).
What is the permutation only has one cycle? There is a particular class of permutation matrices with only one cycle which we will look into next.