特殊矩陣 (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}

不難驗證 CIPP^2P^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}

反之,可表示為上述形式的矩陣必為循環矩陣。這裡 Pn\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=1n 個複數根:

\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}

其中 \LambdaU^{\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}=IU^{\ast}U=I (參見“特殊矩陣 (3):么正矩陣 (酉矩陣)”)。

 
性質

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

(1) CB 符合乘法交換律:

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的快速演算法,使用它來解方程式的運算量遠比高斯消去法少,步驟如下:

  1. \mathbf{y}=\mathrm{IDFT}(\mathbf{b}),亦即 \mathbf{y}=\frac{1}{n}F^{\ast}\mathbf{b}
  2. \mathbf{z}=\mathrm{DFT}(\mathbf{c})\mathbf{c} 為係數矩陣 C 的第一列所構成的向量,\mathbf{z} 的各元即為特徵值 \lambda_m
  3. 計算 w_i=y_i/z_ii=1,2,\ldots,n,並組成向量 \mathbf{w}
  4. \mathbf{x}=\mathrm{DFT}(\mathbf{w}),此即 \mathbf{x}=F\mathbf{w}
繼續閱讀:
This entry was posted in 特殊矩陣, 線性代數專欄 and tagged , , , , , . Bookmark the permalink.

8 則回應給 特殊矩陣 (7):循環矩陣

  1. 訪客 說:

    \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.
    这个式子从何而来?

  2. ccjou 說:

    請參閱以下連結
    http://licos.epfl.ch/courses/dsp0607/dsp_n02_chapter2.pdf
    頁20(2.6)式之後解釋了你的問題。

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

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

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s