Householder 矩陣乘積的特徵值

本文的閱讀等級:中級

考慮下面的 n\times n 階實 Householder 矩陣:

H=I-2\mathbf{u}\mathbf{u}^T

其中 In 階單位矩陣,\mathbf{u}\in\mathbb{R}^n 為任意單位向量,亦即 \Vert\mathbf{u}\Vert^2=\mathbf{u}^T\mathbf{u}=1。Householder 矩陣也稱為基本鏡射 (反射) 矩陣,鏡射超平面的法向量即為 \mathbf{u} (見“特殊矩陣(4):Householder 矩陣”)。由 Householder 矩陣的幾何意義很容易推論其特徵值,考慮 \mathbf{u} 的鏡射結果:

H\mathbf{u}=(I-2\mathbf{u}\mathbf{u}^T)\mathbf{u}=\mathbf{u}-2\mathbf{u}(\mathbf{u}^T\mathbf{u})=\mathbf{u}-2\mathbf{u}=-\mathbf{u}

上式說明 H 有特徵值 -1\mathbf{u} 為對應的特徵向量。令 \mathcal{U}=\mathrm{span}\{\mathbf{u}\},鏡射超平面即為 \mathcal{U} 的正交補餘 \mathcal{U}^{\perp}。明顯地,\mathrm{dim}\mathcal{U}^{\perp}=n-1,令 \mathcal{U}^{\perp} 的任意 n-1 個線性獨立向量為 \mathbf{x}_1,\ldots,\mathbf{x}_{n-1},則 \mathbf{u}^T\mathbf{x}_i=0i=1,\ldots,n-1。利用這個結果可算出

H\mathbf{x}_i=(I-2\mathbf{u}\mathbf{u}^T)\mathbf{x}_i=\mathbf{x}_i-2\mathbf{u}(\mathbf{u}^T\mathbf{x}_i)=\mathbf{x}_i,~~~i=1,\ldots,n-1

鏡射超平面也就是對應特徵值 1 的特徵空間。綜合以上結果,我們知道 Householder 矩陣 Hn-1 個相重特徵值 1 以及特徵值 -1。設

\begin{aligned}  H_1&=I-2\mathbf{u}_1\mathbf{u}_1^T\\    H_2&=I-2\mathbf{u}_2\mathbf{u}_2^T\end{aligned}

本文所要討論的問題是,如何計算 Householder 矩陣乘積 H_2H_1 的特徵值?(此問題由網友 jockey5566 於交流園地提出)。

 
我們先回想 Householder 矩陣 H 擁有的一些基本性質:很明顯,H 是對稱矩陣,而且是正交矩陣,H^TH=H^2=I,原因是任何向量經過連續兩次鏡射又得回原向量,稱為對合 (involutory)。注意,H_2H_1 雖未必對稱,但 H_2H_1 也是正交矩陣,因為

(H_2H_1)^T(H_2H_1)=H_1^TH_2^TH_2H_1=H_1^TH_1=I

對於任意向量 \mathbf{x}

\Vert H_2H_1\mathbf{x}\Vert^2=\mathbf{x}^T(H_2H_1)^T(H_2H_1)\mathbf{x}=\mathbf{x}^T\mathbf{x}=\Vert\mathbf{x}\Vert^2

Householder 矩陣乘積 H_2H_1 不改變向量長度,故其特徵值滿足 \vert\lambda\vert=1。不過,這個訊息仍不足以確定特徵值為何,因此我們轉而從 Householder 矩陣的幾何性質下手。

 
若單位向量 \mathbf{u}_1\mathbf{u}_2 共線,\mathbf{u}_1=\pm\mathbf{u}_2,就有 H_1=H_2,推知 H_2H_1=H_1^2=IH_2H_1n 個重複特徵值 1。以下我們針對 \mathbf{u}_1\mathbf{u}_2 不共線的情況說明。計算 H_2H_1 特徵值的方法類似於上述由特徵向量計算單一 Householder 矩陣 H 的特徵值,H_2H_1 的特徵向量也可以根據 H_1H_2 的鏡射超平面與法向量區分為兩類。令 \mathcal{U}_1=\mathrm{span}\{\mathbf{u}_1\}\mathcal{U}_2=\mathrm{span}\{\mathbf{u}_2\},對應 H_1H_2 的鏡射超平面分別為 \mathcal{U}_1^{\perp}\mathcal{U}_2^{\perp},而 \mathcal{U}_1^{\perp}\cap\mathcal{U}_2^{\perp} 同時正交於 \mathbf{u}_1\mathbf{u}_2\mathcal{U}_1^{\perp}\cap\mathcal{U}_2^{\perp}\mathrm{span}\{\mathbf{u}_1,\mathbf{u}_2\} 的正交補餘。因為 \mathbf{u}_1\mathbf{u}_2 不共線,\mathrm{dim}\left(\mathcal{U}_1^{\perp}\cap\mathcal{U}_2^{\perp}\right)=n-2。設 \mathbf{x}_1,\ldots,\mathbf{x}_{n-2}\mathcal{U}_1^{\perp}\cap\mathcal{U}_2^{\perp} 的一組基底,因為所有的 \mathbf{x}_i 都屬於 H_1H_2 的鏡射超平面,H_1\mathbf{x}_i=\mathbf{x}_iH_2\mathbf{x}_i=\mathbf{x}_i,接著可以得到

H_2H_1\mathbf{x}_i=H_2\mathbf{x}_i=\mathbf{x}_i

推知 H_2H_1n-2 次重複的特徵值 1

 
另外兩個特徵值的特徵空間為何?既然已經在 \mathcal{U}_1^{\perp}\cap\mathcal{U}_2^{\perp} 找到了 n-2 個特徵向量,沒有別的選擇,我們只能在 \mathrm{span}\{\mathbf{u}_1,\mathbf{u}_2\} 設法找出剩下的兩個特徵向量。設 \mathbf{y}=c_1\mathbf{u}_1+c_2\mathbf{u}_2 滿足 H_2H_1\mathbf{y}=\lambda\mathbf{y}c_1c_2 不都為零。整理出主要的變換結果:

\begin{aligned}  H_1\mathbf{u}_1&=-\mathbf{u}_1\\    H_2\mathbf{u}_2&=-\mathbf{u}_2\\    H_1\mathbf{u}_2&=(I-2\mathbf{u}_1\mathbf{u}_1^T)\mathbf{u}_2=\mathbf{u}_2-2k\mathbf{u}_1\\    H_2\mathbf{u}_1&=(I-2\mathbf{u}_2\mathbf{u}_2^T)\mathbf{u}_1=\mathbf{u}_1-2k\mathbf{u}_2\end{aligned}

上面我們令 k=\mathbf{u}_1^T\mathbf{u}_2=\mathbf{u}_2^T\mathbf{u}_1。現在開始計算工作,過程如下:

\begin{aligned}  H_2H_1\mathbf{y}&=H_2H_1\left(c_1\mathbf{u}_1+c_2\mathbf{u}_2\right)\\    &=H_2\left(-c_1\mathbf{u}_1+c_2\mathbf{u}_2-2kc_2\mathbf{u}_1\right)\\    &=H_2\left(-(c_1+2kc_2)\mathbf{u}_1+c_2\mathbf{u}_2\right)\\    &=-(c_1+2kc_2)(\mathbf{u}_1-2k\mathbf{u}_2)-c_2\mathbf{u}_2\\    &=-(c_1\mathbf{u}_1+c_2\mathbf{u}_2)-2k(c_2\mathbf{u}_1-(c_1+2kc_2)\mathbf{u}_2)\\    &=-\mathbf{y}-2k(c_2\mathbf{u}_1-(c_1+2kc_2)\mathbf{u}_2)\end{aligned}

明顯地,右項 c_2\mathbf{u}_1-(c_1+2kc_2)\mathbf{u}_2 必定與特徵向量 \mathbf{y}=c_1\mathbf{u}_1+c_2\mathbf{u}_2 共線,可得下面的重要關係式:

\displaystyle\frac{c_2}{c_1}=-\frac{c_1+2kc_2}{c_2}

c_1+2kc_2=-c_2^2/c_1 代回前面的推導式,即得

H_2H_1\mathbf{y}=\displaystyle\left(-1-2k\frac{c_2}{c_1}\right)\mathbf{y}=\lambda\mathbf{y}

上述重要關係式也可以改寫為

\displaystyle\left(\frac{c_2}{c_1}\right)^2+2k\left(\frac{c_2}{c_1}\right)+1=0

解出

\displaystyle\frac{c_2}{c_1}=-k\mp\sqrt{k^2-1}

\mathbf{u}_1\mathbf{u}_2 的夾角為 \theta。因為 \mathbf{u}_1\mathbf{u}_2 同為單位向量,k=\mathbf{u}_1^T\mathbf{u}_2=\cos\theta\neq \pm 1。所以

\displaystyle\frac{c_2}{c_1}=-\cos\theta\mp i\sin\theta

其中 i=\sqrt{-1}。再將此結果代入特徵值算式,可得

\begin{aligned}  \displaystyle\lambda&=-1-2k\frac{c_2}{c_1}\\    &=-1-2\cos\theta(-\cos\theta\mp i\sin\theta)\\    &=-1+2\cos^2\theta\pm 2i\sin\theta\cos\theta\\    &=\cos(2\theta)\pm i\sin(2\theta)\end{aligned}

最後一個步驟使用了倍角公式。

 
整理推演得到的結果。若 \mathbf{u}_1\mathbf{u}_2 共線,H_2H_1n 個特徵值 1;當 \mathbf{u}_1\mathbf{u}_1 不共線時,H_2H_1n-2 個特徵值 1,以及絕對值為 1 的共軛複數特徵值,\cos(2\theta)\pm i\sin(2\theta)。對於 n\ge 2H_2H_1 是一旋轉矩陣,詳見“旋轉與鏡射”與“高階旋轉矩陣”。

相關閱讀:
廣告
本篇發表於 特徵分析, 線性代數專欄 並標籤為 , , 。將永久鏈結加入書籤。

6 Responses to Householder 矩陣乘積的特徵值

  1. ccjou 說道:

    原文有錯,已經更正,順便稍加補充改寫。

  2. vtriplev 說道:

    在清華開放課程上,有看到根本主體類似的文章
    http://moodle.nthu.edu.tw/mod/resource/view.php?id=11858
    http://moodle.nthu.edu.tw/file.php/6833/CH3_Linear_Algebra/Linear_operators/AP1-Operator.pdf
    在文章內的rotation and reflection 的討論中
    2D平面旋轉矩陣以R(theta)表示, y方向parity operator 以 Py表示
    那麼,任何2D平面上的鏡射,基本上都可以用 R(theta)*Py來表示
    而且
    Py*R(theta)=R(-theta)*Py=inverse of R(theta)*Py
    Py*Py=I

    所以也就是說,任意平面上的兩個reflection 矩陣 H1, H2分別可表示為
    H1=Py*R(theta1)
    H2=Py*R(theta2)
    H1*H2=Py*R(theta1)*Py*R(theta2)=R(-theta1)*Py*Py*R(theta2)=R(theta2-theta1)
    在2D平面上,連續作用兩次鏡射的作用會等效於1個旋轉

    感覺跟本主題有些神似,在3D空間上,連續兩次作用鏡射,似乎也等效於對某個旋轉軸做旋轉 (旋轉軸是特徵值為1的eigenspace, 其dimension=n-2=3-2=1)

    所以,感覺好像可以推論,作用兩次鏡射,要麼回到I,不然就會變成旋轉

  3. vtriplev 說道:

    對平面上的兩個鏡射來說
    H1=Py*R(theta1),及H2=Py*R(theta2)
    H1的映射軸L1為極座標之角度=1/2*theta1
    H2的映射軸L2為極座標之角度=1/2*theta2
    L1與L2的夾角=1/2*(theta1-theta2)
    而H2*H1=R(theta1-theta2)所對應的旋轉矩陣的旋轉角度,是L1與L2夾角的兩倍
    剛好可以做驗證.

  4. ccjou 說道:

    任何 \mathbb{R}^n 向量都可以經過 n-1 次平面旋轉使其指向第一軸(或任何軸),使用 Givens 旋轉即可:
    https://ccjou.wordpress.com/2010/02/18/givens-%E6%97%8B%E8%BD%89%E6%96%BC-qr-%E5%88%86%E8%A7%A3%E7%9A%84%E6%87%89%E7%94%A8/

  5. Meiyue Shao 說道:

    我觉得vtriplev的评论比较本质——两个镜像变换的复合是平面旋转,反之亦然。这是一个简单而深刻的结论,Coxeter曾撰文以此推导空间旋转的四元数表示。虽然几何直观并不能代替代数演算,不过如果在大段的计算下面配上一张图说明上述原理能帮助读者更好地理解。

發表迴響

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

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s