We use the permutation matrix corresponding to the following permutation, , as an example. Note that this permutation has one cycle of order 3 (the elements ) and one cycle of order 2 (the elements ). The corresponding permutation matrix is:

The spectrum of a permutation matrix is directly related to its cycles: the order-3 cycle contributes the cubic roots of unity and the order-2 cycle contributes the square roots of unity .

The whole story of this section fits in one flow diagram. Start from the permutation we want to understand.

It decomposes into two disjoint cycles: the order-3 cycle and the order-2 cycle .

Each cycle contributes its roots of unity: the cubic roots and the square roots .

Finally each set of roots is placed at its cycle's indices with zeros elsewhere to give the eigenvector layouts: and .

---

0. Finding the eigenvalues

Construct a vector . Now observe that :

Thus the eigenvalues of satisfy . Thus three of the eigenvalues are the cubic roots of unity.

Similarly, construct a vector . Now observe that :

Thus the eigenvalues of satisfy . 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 , then the eigenvalues of the permutation matrix are the -th roots of unity.

For the matrix from the example above, the eigenvalues are the cubic roots of unity and the square roots of unity. This can also be verified programmatically:

Verification using Python

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 unity

---

1. Finding the eigenvectors

This part is pretty straightforward:

Thus the eigenvector corresponding to is by setting (it can be set to any non-zero complex number, and here ). This can also be verified programmatically:

Verification using Python

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 is:

Verification using Python

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 of length has the eigenvector with values at those indices and zeros elsewhere corresponding to the eigenvalue .

What if the permutation only has one cycle? There is a particular class of permutation matrices with only one cycle which we will look into next.

---

← Overview and permutation cycles · Circulant matrices →