置换矩阵的特征值

hbghlyj

math.stackexchange.com/questions/1970702
置换矩阵是正交矩阵（易验证列向量为单位向量且正交）。所以
$$\tag{1}\|PV\|=\|V\|$$
如果 $V$ 是与特征值 $\lambda$ 相关联的特征向量，则在 (1) 中代入 $PV=\lambda V$ 我们推导出
$$|\lambda|=1.$$
此外，设 $p$ 是置换阶（order），由于 $P^p=I_n$ 这些特征值满足 $\lambda^p=1$； 所以
$$\lambda=e^{i k 2\pi/p}$$
对某个 $k \in \mathbb{Z}$.
让我们举个例子：考虑以下置换，它分解为两个不相交的循环之积

5阶循环$\color{red}{(5 4 3 2 1)}$ 和 3阶循环$\color{blue}{(6 7 8)}$

置换矩阵为
$$\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.

hbghlyj

en.wikipedia.org/wiki/Permutation_matrix#Linear_algebraic_properties

To calculate the eigenvalues of a permutation matrix \(P_{\sigma}\), write \(\sigma\) as a product of cycles, say, \(\sigma= C_{1}C_{2} \cdots C_{t}\). Let the corresponding lengths of these cycles be \(l_{1},l_{2}...l_{t}\), and let \(R_{i}  (1 \le i \le t)\) be the set of complex solutions of \(x^{l_{i}}=1\). The union of all \(R_{i}\)s is the set of eigenvalues of the corresponding permutation matrix. The geometric multiplicity of each eigenvalue equals the number of \(R_{i}\)s that contain it.

hbghlyj

置换矩阵\[P={\begin{bmatrix}0&0&\cdots &0&1\\1&0&\cdots &0&0\\0&\ddots &\ddots &\vdots &\vdots \\\vdots &\ddots &\ddots &0&0\\0&\cdots &0&1&0\end{bmatrix}}.\]的多项式称为circulant matrix(循环矩阵)\[C=c_{0}I+c_{1}P+c_{2}P^{2}+\dots +c_{n-1}P^{n-1}=f(P),\]根据1楼, $C$的特征值为
\[\lambda _{j}=c_{0}+c_{n-1}\omega ^{j}+c_{n-2}\omega ^{2j}+\dots +c_{1}\omega ^{(n-1)j},\quad j=0,1,\dots ,n-1.\]
单位特征向量为(与$P$相同)
\[v_{j}={\frac {1}{\sqrt {n}}}\left(1,\omega ^{j},\omega ^{2j},\ldots ,\omega ^{(n-1)j}\right),\quad j=0,1,\ldots ,n-1,\]
其中 $\omega=\exp \left(i{\tfrac {2\pi }{n}}\right)$。
特征向量矩阵是同样维数的离散傅立叶变换矩阵，因此循环矩阵的特征值很容易通过快速傅立叶变换计算出来。
特征向量可以视为Fourier mode, 特征值是频率, 见Normal mode(简正模)