様々な行列の分解

バイオインフォ基礎

1. LU分解

LU分解（Lower–Upper 分解）は、正方行列 $A\in\mathbb{R}^{n\times n}$ を下三角行列 $L$（対角成分を $1$ とする）と上三角行列 $U$ の積
$$
A=LU
$$
として表す方法である。実装では部分ピボット（行の入れ替え）を行うことが多く、その場合は置換行列 $P$ を用いて
$$
PA=LU
$$
とする（$P$ は単位行列の行を並べ替えた行列）。

(1) 手順（ガウス消去に基づく構成）

  • 第 $k$ 列のピボット $a_{kk}$ を用い、$i=k+1,\dots,n$ について消去係数 $m_{ik}=a_{ik}/a_{kk}$ を求め、行 $i$ から $m_{ik}$ 倍の行 $k$ を引く。
  • 得られる上三角が $U$、係数 $m_{ik}$ を下三角に並べ、対角を $1$ としたものが $L$。

(2) 例

行列
$$
A=\begin{pmatrix}
2&3&1\\
4&7&7\\
6&18&22
\end{pmatrix}
$$
に対し、ピボット無しで進める。

  1. 列1の消去：$m_{21}=4/2=2,\ m_{31}=6/2=3$。
    $r_2\leftarrow r_2-2r_1,\ r_3\leftarrow r_3-3r_1$ で
    $$
    \begin{pmatrix}
    2&3&1\\
    0&1&5\\
    0&9&19
    \end{pmatrix}
    $$
  2. 列2の消去：$m_{32}=9/1=9$。$r_3\leftarrow r_3-9r_2$ で
    $$
    U=\begin{pmatrix}
    2&3&1\\
    0&1&5\\
    0&0&-26
    \end{pmatrix}
    $$
  3. 消去係数を $L$ に配置（対角は $1$）
    $$
    L=\begin{pmatrix}
    1&0&0\\
    2&1&0\\
    3&9&1
    \end{pmatrix}
    $$
    検算として $LU$ を掛けると $A$ に戻る。

注意：ピボットが $0$ になる／数値的に小さい場合は部分ピボット $P$ を導入して $PA=LU$ とする。

2. QR分解

QR分解は、任意の（長方も可）行列 $A\in\mathbb{R}^{m\times n}\ (m\ge n)$ を、列直交（$Q^\top Q=I_n$）な $Q\in\mathbb{R}^{m\times n}$ と上三角 $R\in\mathbb{R}^{n\times n}$ で
$$
A=QR
$$
と表す分解である。最も基本的な構成法は（修正）グラム–シュミット正規直交化。

(1) グラム–シュミットによる計算法（具体例つき）

次の $3\times2$ 行列を QR 分解する：
$$
A=\begin{pmatrix}
1&1\\
1&0\\
0&1
\end{pmatrix}
,\quad
a_1=\begin{pmatrix}1\\1\\0\end{pmatrix},\ a_2=\begin{pmatrix}1\\0\\1\end{pmatrix}
$$

  1. 1本目の正規化：
    $$
    r_{11}=|a_1|=\sqrt{1^2+1^2+0^2}=\sqrt{2},\quad
    q_1=\frac{a_1}{r_{11}}=\frac{1}{\sqrt{2}}\begin{pmatrix}1\\1\\0\end{pmatrix}
    $$
  2. 2本目を $q_1$ に直交化：
    $$
    r_{12}=q_1^\top a_2=\frac{1}{\sqrt{2}}(1\cdot1+1\cdot0+0\cdot1)=\frac{1}{\sqrt{2}}
    $$
    $$
    u_2=a_2-r_{12}q_1=\begin{pmatrix}1\\0\\1\end{pmatrix}-\frac{1}{\sqrt{2}}\cdot\frac{1}{\sqrt{2}}\begin{pmatrix}1\\1\\0\end{pmatrix}
    =\begin{pmatrix}1\\0\\1\end{pmatrix}-\frac{1}{2}\begin{pmatrix}1\\1\\0\end{pmatrix}
    =\begin{pmatrix}\frac{1}{2}\\-\frac{1}{2}\\1\end{pmatrix}
    $$
  3. 2本目の正規化：
    $$
    r_{22}=|u_2|=\sqrt{\left(\frac{1}{2}\right)^2+\left(-\frac{1}{2}\right)^2+1^2}=\sqrt{\frac{3}{2}}=\frac{\sqrt{6}}{2}
    $$
    $$
    q_2=\frac{u_2}{r_{22}}=\frac{2}{\sqrt{6}}\begin{pmatrix}\frac{1}{2}\\-\frac{1}{2}\\1\end{pmatrix}
    =\begin{pmatrix}\frac{1}{\sqrt{6}}\\-\frac{1}{\sqrt{6}}\\ \frac{2}{\sqrt{6}}\end{pmatrix}
    $$
  4. まとめ：
    $$
    Q=\begin{pmatrix}
    \frac{1}{\sqrt{2}}&\frac{1}{\sqrt{6}}\\
    \frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{6}}\\
    0&\frac{2}{\sqrt{6}}
    \end{pmatrix}
    ,\quad
    R=\begin{pmatrix}
    \sqrt{2}&\frac{1}{\sqrt{2}}\\
    0&\frac{\sqrt{6}}{2}
    \end{pmatrix}
    $$
    直ちに $QR=A$ を確認できる（列毎に $Q$ の直交性と $R$ の上三角性も確認可能）。

コメント：数値計算では修正グラム–シュミットやハウスホルダー変換の QR が安定。理論理解には上の手計算が有効。

3. 極分解（Polar decomposition）

任意の $A\in\mathbb{R}^{m\times n}$ に対し、列フルランクの場合
$$
A=UP
$$
と分解できる。ここで $U$ は列直交（$U^\top U=I_n$）、$P$ は対称半正定値で
$$
P=\sqrt{A^\top A},\quad U=A\,P^{-1}.
$$
（正方正則なら $U$ は直交行列。一般の場合にも $U$ は部分等長で、$A$ の回転（等長）と伸縮（半正定値）に分解される。）

(1) 具体例

$$
A=\begin{pmatrix}3&1\\0&2\end{pmatrix}
$$

  1. $A^\top A$ と固有分解：
    $$
    A^\top A=\begin{pmatrix}9&3\\3&5\end{pmatrix}
    $$
    特性方程式
    $$
    \lambda^2-14\lambda+36=0\ \Rightarrow\ \lambda_{1,2}=7\pm\sqrt{13}
    $$
    特異値（$P$ の固有値）は
    $$
    \sigma_1=\sqrt{7+\sqrt{13}}\approx3.303,\quad \sigma_2=\sqrt{7-\sqrt{13}}\approx1.213
    $$
    固有ベクトル（右特異ベクトルに一致）を正規化して
    $$
    v_1\propto\begin{pmatrix}3\\-2+\sqrt{13}\end{pmatrix}\approx\begin{pmatrix}3\\1.606\end{pmatrix},\quad
    v_2\propto\begin{pmatrix}3\\-2-\sqrt{13}\end{pmatrix}\approx\begin{pmatrix}3\\-5.606\end{pmatrix}
    $$
    正規化して $V=[\hat v_1\ \hat v_2]$ を得る（数値は省略可能）。
  2. $P=\sqrt{A^\top A}$ の構成（スペクトル写像）：
    $$
    P=V\begin{pmatrix}\sigma_1&0\\0&\sigma_2\end{pmatrix}V^\top
    $$
    （$V$ は直交なので $V^{-1}=V^\top$。）
  3. $U=A\,P^{-1}$：
    $$
    U=A\left(V\begin{pmatrix}\sigma_1&0\\0&\sigma_2\end{pmatrix}V^\top\right)^{-1}
    =A\,V\begin{pmatrix}\frac{1}{\sigma_1}&0\\0&\frac{1}{\sigma_2}\end{pmatrix}V^\top
    $$
    数値的に計算すると
    $$
    U\approx\begin{pmatrix}0.957&0.290\\-0.290&0.957\end{pmatrix},\quad
    P\approx\begin{pmatrix}3.130&0.915\\0.915&2.376\end{pmatrix}
    $$
    （検算）$U^\top U\approx I,\ P$ は対称半正定値、かつ $UP\approx A$。

ポイント：$P$ は「長さ（伸縮）」、$U$ は「回転（等長）」を表す。SVD $A=U_\ell\,\Sigma\,V^\top$ を使えば $P=V\Sigma V^\top,\ U=U_\ell V^\top$ と一気に求まる。

4. テープリッツの定理（Toeplitz の定理）

ここでは可換な行列族の同時三角化・同時対角化について扱う。以下、体は $\mathbb{C}$ とする（固有値が必ず存在するため議論が簡潔）。

(1) 同時固有ベクトル

主張　$A,B\in\mathbb{C}^{n\times n}$ が可換（$AB=BA$）とする。このとき、$A$ の任意の固有値 $\lambda$ に対し、その固有空間
$$
E_\lambda(A)=\ker(A-\lambda I)
$$
は $B$ によって不変（$B(E_\lambda(A))\subseteq E_\lambda(A)$）である。したがって $E_\lambda(A)\ne{0}$ なら、その中に $A$ と $B$ の共通固有ベクトルが存在する（$B$ を $E_\lambda(A)$ に制限して固有ベクトルを取ればよい）。

証明（丁寧）
$v\in E_\lambda(A)$、すなわち $(A-\lambda I)v=0$ とする。可換性 $AB=BA$ から
$$
(A-\lambda I)(Bv)=ABv-\lambda Bv=BA v-\lambda Bv=B(Av-\lambda v)=B\cdot 0=0
$$
よって $Bv\in E_\lambda(A)$。すなわち $E_\lambda(A)$ は $B$-不変。$\mathbb{C}$ 上では $B|{E_\lambda(A)}$ は必ず固有ベクトルを持つので、それが $A$ と $B$ の共通固有ベクトルになる。$\square$

(2) 同時上三角化

主張　可換な行列族 $\mathcal{F}={A_1,\dots,A_m}\subset\mathbb{C}^{n\times n}$ は同時に上三角化できる。すなわち可逆行列 $S$ が存在して、全ての $j$ について
$$
S^{-1}A_j S\ \text{が上三角}
$$
となる。

証明（$n$ に関する帰納法）
$n=1$ は自明。$n>1$ とし、$A_1$ の固有値 $\lambda$ と固有ベクトル $v\ne 0$ を取る（$\mathbb{C}$ 上なので存在）。(1) より $E_\lambda(A_1)$ は全ての $A_j$ で不変。よって $\mathbb{C}^n$ は $A_j$-不変部分空間
$$
V_1=\mathrm{span}{v}\quad\text{と}\quad V_1^\perp\ \text{（適当な補空間）}
$$
に分解できる（実際には基底を $v$ で始めて拡張すればよい）。この基底で各 $A_j$ はブロック上三角
$$
\begin{pmatrix}
\ast&\ast\\
0&\ast
\end{pmatrix}
$$
の形になる。右下の $(n-1)\times(n-1)$ ブロックは、もとの可換性から互いに可換のまま。帰納法の仮定でこの下右ブロックは同時上三角化できる。ブロック上の変換を元の基底に持ち上げると、全体として同時上三角化が得られる。$\square$

直感：可換なら「同じフラグ（鎖状の部分空間）」を保つ。一次元の不変部分空間を一つ見つけ、次元を一つずつ減らしていけば、同時に上三角まで持って行ける。

(3) テープリッツの定理（可換な正規行列族の同時ユニタリ対角化）

主張（Toeplitz の定理）
$\mathcal{N}={N_1,\dots,N_m}\subset\mathbb{C}^{n\times n}$ を互いに可換な正規行列の族（$N_k^\ast N_\ell=N_\ell N_k^\ast$ を含意）とする。このとき、あるユニタリ行列 $U$ が存在して、全ての $k$ について
$$
U^\ast N_k\,U=\text{対角行列}
$$
すなわち $\mathcal{N}$ は同時にユニタリ対角化可能である。

証明（初学者向けの道筋）

  1. まず一つ取り出して $N_1$ をユニタリ対角化する（正規行列は常に可能）：
    $$
    N_1=U_1\Lambda_1 U_1^\ast,\quad \Lambda_1=\mathrm{diag}(\lambda_1,\dots,\lambda_n)
    $$
    基底変換で $\tilde N_k:=U_1^\ast N_k U_1$ とおくと、可換性から
    $$
    \tilde N_k\,\Lambda_1=\Lambda_1\,\tilde N_k
    $$
    が成り立つ。すなわち $\tilde N_k$ は $\Lambda_1$（＝$N_1$ の固有値）ごとの固有空間を保存する。したがって $\tilde N_k$ は、同じ固有値に対応する添字をまとめたブロック対角になる。
  2. 各固有値 $\lambda$ の固有空間 $E_\lambda(N_1)$ に $\tilde N_k$ を制限すると、依然として正規かつ互いに可換（制限・直和は正規性と可換性を保つ）。よって各ブロック内で再びユニタリ同時対角化できる（$N_1$ はそこでは $\lambda I$ なので邪魔をしない）。
  3. それぞれのブロックで得たユニタリを直和で組み合わせると、全体としてあるユニタリ $U$ が得られ、全ての $N_k$ が同時に対角化される。

直感：正規行列は「互いに直交する固有空間の直和」に分解でき、可換性はその直和構造を全員が壊さないことを意味する。各固有空間内でも正規かつ可換なので、そこでも同時対角化が可能。結果として全空間で同時対角化が成立する。$\square$

スポンサーリンク