特殊矩陣 (7)：循環矩陣

本文的閱讀等級：高級

具有以下形式的 $n\times n$ 階矩陣稱為循環矩陣 (circulant matrix)：

$C=\begin{bmatrix} c_0&c_1&c_2&\cdots&c_{n-1}\\ c_{n-1}&c_0&c_1&\cdots&c_{n-2}\\ c_{n-2}&c_{n-1}&c_0&\cdots&c_{n-3}\\ \vdots&\vdots&\ddots&\ddots&\vdots\\ c_1&c_2&\cdots&c_{n-1}&c_0 \end{bmatrix}$

例如，

$C=\begin{bmatrix} 2&3&4&5\\ 5&2&3&4\\ 4&5&2&3\\ 3&4&5&2 \end{bmatrix}$

循環矩陣 $C$ 的每一列即為上一列往右循環移動一元，因此各列不過就是第一列的循環排列。根據這項觀察，我們定義下面的基本循環排列矩陣 (也稱為主要排列矩陣)

$P=\begin{bmatrix} 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ 1&0&0&0 \end{bmatrix}$

抽出循環矩陣 $C$ 相同的元， $C$ 可分解為

$C=2\begin{bmatrix} 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix}+3\begin{bmatrix} 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ 1&0&0&0 \end{bmatrix}+4\begin{bmatrix} 0&0&1&0\\ 0&0&0&1\\ 1&0&0&0\\ 0&1&0&0 \end{bmatrix}+5\begin{bmatrix} 0&0&0&1\\ 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0 \end{bmatrix}$

不難驗證 $C$ 為 $I$ ， $P$ ， $P^2$ 和 $P^3$ 的線性組合：

$C=2I+3P+4P^2+5P^3$

推廣至一般情況，任一 $n\times n$ 階循環矩陣 $C$ 可表示為

$C=c_0I+c_1P+c_2P^2+\cdots+c_{n-1}P^{n-1}$

反之，可表示為上述形式的矩陣必為循環矩陣。這裡 $P$ 是 $n\times n$ 階基本循環排列矩陣，注意 $P^{0}=I=P^{n}$ ， $C$ 的組合係數 $c_0,c_1,\ldots,c_{n-1}$ 正是第一列的元。因為有這個簡單的表示形式，循環矩陣存在一些優美的性質。

判別方法

若 $C$ 是一 $n\times n$ 階循環矩陣，則 $C=PCP^T$ ，反之亦然。因為循環矩陣 $C$ 可唯一表示成 $C=\sum_{i=0}^{n-1}c_iP^i$ 。使用 $P^T=P^{-1}$ ，

$\displaystyle PCP^T=P\left(\sum_{i=0}^{n-1}c_iP^i\right)P^T=\sum_{i=0}^{n-1}c_iPP^iP^T=\sum_{i=0}^{n-1}c_iP^i=C$

特徵值與特徵向量

假設基本循環矩陣 $P$ 的特徵值為 $\rho$ ，對應的特徵向量為 $\mathbf{x}$ ，特徵方程式是 $P\mathbf{x}=\rho\mathbf{x}$ ，也就有 $P^k\mathbf{x}=\rho^k\mathbf{x}$ 。計算

$\begin{aligned} C\mathbf{x}&=c_0I\mathbf{x}+c_1P\mathbf{x}+c_2P^2\mathbf{x}+\cdots+c_{n-1}P^{n-1}\mathbf{x}\\ &=\left(c_0+c_1\rho+c_2\rho^2+\cdots+c_{n-1}\rho^{n-1}\right)\mathbf{x}\end{aligned}$

這說明 $C$ 的特徵值為

$\displaystyle\lambda= c_0+c_1\rho+c_2\rho^2+\cdots+c_{n-1}\rho^{n-1}=\sum_{k=0}^{n-1}c_k\rho^k$

其特徵向量同樣是 $P$ 的特徵向量 $\mathbf{x}$ 。所以我們只要知道基本循環矩陣 $P$ 的特徵值便很容易求得任何循環矩陣 $C$ 的特徵值。

以 $4\times 4$ 基本循環矩陣為例，考慮其特徵多項式

$\mathrm{det}(P-\rho I)=\left|\!\!\begin{array}{rrrr} -\rho&1&0&0\\ 0&-\rho&1&0\\ 0&0&-\rho&1\\ 1&0&0&-\rho \end{array}\!\!\right|$

以餘因子展開，並利用三角矩陣的行列式性質，可得

$\det(P-\rho I)=(-\rho)\left|\!\!\begin{array}{rrr} -\rho&1&0\\ 0&-\rho&1\\ 0&0&-\rho \end{array}\!\!\right|+(-1)\left|\!\!\begin{array}{rrc} 1&0&0\\ -\rho&1&0\\ 0&-\rho&1 \end{array}\!\!\right|=\rho^4-1$

利用歸納法可以證明 $n\times n$ 階基本循環矩陣 $P$ 的特徵多項式為

$\det(P-\rho I)=(-\rho)^n-(-1)^n$

也就是說， $P$ 的特徵值為 $\rho^n=1$ 的 $n$ 個複數根：

$\rho_m=e^{-2\pi im/n},~~m=0,1,2,\ldots,n-1$

其中 $i=\sqrt{-1}$ 。直接計算可驗證對應特徵值 $\rho_m$ 的特徵向量 $\mathbf{x}_m$ 為

$\displaystyle\mathbf{x}_m=\frac{1}{\sqrt{n}}\begin{bmatrix} 1\\ \rho_m\\ \rho_m^2\\ \vdots\\ \rho_m^{n-1} \end{bmatrix}$

引入常數 $1/\sqrt{n}$ 的目的是為使 $\mathbf{x}_m$ 為單位向量，即 $\Vert\mathbf{x}_m\Vert=1$ ，證明於下：

$\displaystyle \begin{aligned} \Vert\mathbf{x}_m\Vert^2&=\mathbf{x}_m^\ast\mathbf{x}_m\\ &=\frac{1}{n}\left(1+\overline{\rho_m}\rho_m+\overline{\rho_m^2}\rho_m^2+\cdots+\overline{\rho^{n-1}_m}{\rho_m^{n-1}}\right)\\ &=\frac{1}{n}\left(1+\vert\rho_m\vert^2+\vert\rho_m^2\vert^2+\cdots+\vert\rho^{n-1}_m\vert^2\right)\\ &=\frac{1}{n}(\underbrace{1+1+1+\cdots+1}_{n\text{ terms}})=1 \end{aligned}$

將基本循環矩陣 $P$ 的特徵值代入循環矩陣 $C$ 的展開式得到 $C$ 的特徵值：

$\displaystyle\lambda_m=\sum_{k=0}^{n-1}c_ke^{-2\pi imk/n},~~m=0,1,\ldots,n-1$

對應的單位特徵向量為

$\displaystyle\mathbf{x}_m=\frac{1}{\sqrt{n}}\begin{bmatrix} 1\\ e^{-2\pi im/n}\\ \vdots\\ e^{-2\pi im(n-1)/n} \end{bmatrix},~~m=0,1,\ldots,n-1$

由於 $\mathbf{x}_0,\mathbf{x}_1,\ldots,\mathbf{x}_{n-1}$ 是線性獨立的特徵向量，循環矩陣 $C$ 是可對角化，表示為

$C=U\Lambda U^{\ast}$

其中 $\Lambda$ 和 $U^{\ast}$ 皆為複矩陣，如下所示：

$\Lambda=\begin{bmatrix} \lambda_0&~&~&~&~\\ ~&\lambda_1&~&~&~\\ ~&~&\lambda_2&~&~\\ ~&~&~&\ddots&~\\ ~&~&~&~&\lambda_{n-1} \end{bmatrix}$

$\displaystyle U=\frac{1}{\sqrt{n}}F=\frac{1}{\sqrt{n}}\begin{bmatrix} 1&1&1&\cdots&1\\ 1&w&w^2&\cdots&w^{n-1}\\ 1&w^2&w^4&\cdots&w^{2(n-1)}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&w^{n-1}&w^{2(n-1)}&\cdots&w^{(n-1)^2} \end{bmatrix}$

上式中 $w=e^{-2\pi i/n}$ 。使用複數指數的正交關係可證明 $U$ 為么正矩陣 (unitary matrix，滿足

$\displaystyle \sum_{m=0}^{n-1}e^{2\pi imk/n}=n\delta_{k\mod n}=\left\{\begin{matrix} n,&k\mod n=0\\ 0,&\mathrm{otherwise} \end{matrix}\right.$

其中 $\delta$ 是 Kronecker 記號，若 $m=0$ ，則 $\delta_m=1$ ，否則 $\delta_m=0$ 。矩陣 $U$ 滿足 $UU^{\ast}=I$ ， $U^{\ast}U=I$ (參見“特殊矩陣 (3)：么正矩陣 (酉矩陣)”)。

性質

由循環矩陣的對角化形式可推論以下性質。若 $C$ 和 $B$ 為同階循環矩陣，設 $C=U\Lambda U^{\ast}$ ， $B=U\Psi U^{\ast}$ ，則

(1) $C$ 和 $B$ 符合乘法交換律：

$CB=U\Lambda U^{\ast}U\Psi U^{\ast}=U\Lambda\Psi U^{\ast}=U\Psi\Lambda U^{\ast}=BC$

(2) $C+B$ 是循環矩陣：

$C+B=U(\Lambda+\Psi)U^{\ast}$

(3) 若 $\Lambda$ 是可逆的，就有 $C^{-1}=U\Lambda^{-1}U^{\ast}$ ，因此 $C^{-1}$ 也是循環矩陣。

離散傅立葉轉換

令人震驚的是循環矩陣 $C$ 的特徵值公式

$\displaystyle \lambda_m=\sum_{k=0}^{n-1}c_ke^{-2\pi imk/n}$

就是數列 $\{c_k\}$ 的離散傅立葉轉換 (discrete Fourier transform)，簡稱 DFT。先前定義的 $U=\frac{1}{\sqrt{n}}F$ ，其中 $F$ 稱為傅立葉矩陣，矩陣乘法 $F\mathbf{y}$ 即為 $\mathbf{y}$ 所表示數列之傅立葉轉換，因此

$\begin{bmatrix} \lambda_0\\ \lambda_1\\ \vdots\\ \lambda_{n-1} \end{bmatrix}=F\begin{bmatrix} c_0\\ c_1\\ \vdots\\ c_{n-1} \end{bmatrix}$

利用傅立葉轉換的逆轉換 (IDFT) 可由特徵值 $\{\lambda_m\}$ 回復數列 $\{c_k\}$ ，即

$\begin{bmatrix} c_0\\ c_1\\ \vdots\\ c_{n-1} \end{bmatrix}=F^{-1}\begin{bmatrix} \lambda_0\\ \lambda_1\\ \vdots\\ \lambda_{n-1} \end{bmatrix}$

因為 $U^{-1}=U^{\ast}=\frac{1}{\sqrt{n}}F^{\ast}$ ，可知 $F^{-1}=\frac{1}{n}F^{\ast}$ ，IDFT 常以下面的算式表示

$\displaystyle c_l=\frac{1}{n}\sum_{m=0}^{n-1}\lambda_me^{2\pi ilm/n}$

讀者可察覺以矩陣運算表示 DFT 和 IDFT 比傳統訊號處理使用的 $\sum$ 符號更為簡潔易懂。

考慮線性方程 $C\mathbf{x}=\mathbf{b}$ ，令 $C$ 是可逆循環矩陣，則

$\displaystyle \mathbf{x}=C^{-1}\mathbf{b}=U\Lambda^{-1}U^{\ast}\mathbf{b}=F\Lambda^{-1}\frac{1}{n}F^{\ast}\mathbf{b}$

快速傅立葉轉換 (fast Fourier transform)，簡稱 FFT，是一種計算 DFT 和 IDFT的快速演算法，使用它來解方程式的運算量遠比高斯消去法少，步驟如下：

$\mathbf{y}=\mathrm{IDFT}(\mathbf{b})$ ，亦即 $\mathbf{y}=\frac{1}{n}F^{\ast}\mathbf{b}$ 。
$\mathbf{z}=\mathrm{DFT}(\mathbf{c})$ ， $\mathbf{c}$ 為係數矩陣 $C$ 的第一列所構成的向量， $\mathbf{z}$ 的各元即為特徵值 $\lambda_m$ 。
計算 $w_i=y_i/z_i$ ， $i=1,2,\ldots,n$ ，並組成向量 $\mathbf{w}$ 。
$\mathbf{x}=\mathrm{DFT}(\mathbf{w})$ ，此即 $\mathbf{x}=F\mathbf{w}$ 。

繼續閱讀：

13 Responses to 特殊矩陣 (7)：循環矩陣

Anonymous says:

04/27/2011 at 1:46 am

$\sum_{m=0}^{n-1}e^{2\pi imk/n}=n\delta_{k\mathrm{mod}n}=\left\{\begin{matrix} n&k\mathrm{mod}n=0\\ 0&\mathrm{otherwise} \end{matrix}\right.$
这个式子从何而来？

ccjou says:

04/27/2011 at 9:16 am

請參閱以下連結

Click to access dsp_n02_chapter2.pdf

頁20(2.6)式之後解釋了你的問題。

簡短補充於下，我們稱一複數 $\omega$ 是第 $n$ 個單位基本根若 $\omega^n=1$ 但 $\omega^k\neq 1$ ，對於任一正整數 $k<n$ 。不難確認 $\omega^k$ ， $0<k<n$ ，是 $x^n-1=0$ 的一根，因為
$\sum_{i=0}^{n-1}\omega^{ik}=\frac{(\omega^k)^n-1}{\omega^k-1}=0$

張志瑋 (@jrweizhang) says:

03/26/2012 at 10:33 pm

不知道可不可以請您再多說一點 FT、DFT、以及 FFT 的相關討論呢
謝謝！

- ccjou says:
  
  03/27/2012 at 8:17 am
  
  好的，我再找時間動筆。
  
illiteracyxia says:

05/19/2015 at 6:59 pm

您好请问 https://s0.wp.com/latex.php?latex=%5Cdisplaystyle%5Cmathbf%7Bx%7D_m%3D%5Cfrac%7B1%7D%7B%5Csqrt%7Bn%7D%7D%5Cbegin%7Bbmatrix%7D++++1%5C%5C++++%5Crho_m%5C%5C++++%5Crho_m%5E2%5C%5C++++%5Cvdots%5C%5C++++%5Crho_m%5E%7Bn-1%7D++++%5Cend%7Bbmatrix%7D&bg=ffffff&fg=000000&s=0&zoom=2
这里怎么知道乘上根号n分之一就可以得到单位矩阵的？

- ccjou says:
  
  05/19/2015 at 8:18 pm
  
  事實上，不需要使用等比級數公式。我已將推導過程貼入上文。
  
  - illiteracyxia says:
    
    05/21/2015 at 11:50 pm
    
    谢谢老师！是我看得不够仔细！看到那里不懂就卡住没继续往下看，后来才发现推导就在后面！
    
    - ccjou says:
      
      05/22/2015 at 8:22 am
      
      並非你看的不仔細，推導過程是我在你留言後才補上去的。
      
Lin says:

03/17/2017 at 1:04 am

打搅下周老师，有一个小小的疑惑,为什么基本循环排列矩阵P的所有特征值都不相同呢？如果只是要求满足\rho^n=1的话，会出现特征值相同的情况么？

- ccjou says:
  
  03/17/2017 at 7:41 am
  
  這是 De Moivre’s formula
  https://zh.wikipedia.org/wiki/%E6%A3%A3%E8%8E%AB%E5%BC%97%E5%85%AC%E5%BC%8F#.E7.94.A8.E6.A3.A3.E8.8E.AB.E5.BC.97.E5.85.AC.E5.BC.8F.E6.B1.82.E6.A0.B9
  
Chirs says:

11/03/2018 at 6:34 pm

老師您好~想請問一下在求循環矩陣P的特徵值時
寫到p^n=1的n個複數根為: p_m=exp(-2*pi*i*m/n)

想說為什麼 p_m不會是exp(2*pi*i*m/n) ? 因為p^n=1
還是說應該是p^n=-1，這樣p_m求出來才會是exp(-2*pi*i*m/n) ?

- Megan says:
  
  03/13/2019 at 4:49 pm
  
  p_m=exp(-2*pi*i*m/n)和exp(2*pi*i*m/n)应该是等价的，只是根的取法前者是顺时针，后者是逆时针。
  
Mu says:

03/19/2019 at 10:39 pm

請問老師，可以教學循環矩陣的逆矩陣的推導過程嗎?

	陳倍恩 on 線性代數的第一堂課──矩陣乘法的定義
	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨