様々な行列の分解

ガウス消去（前進消去）を行交換なしで進めるには、各段階のピボットが 0 でない必要があります。$\Delta_k\neq0$ は「その段階までの左上 $k\times k$ ブロックが可逆」を意味し、ピボットが常に非零＝消去を行交換なしで最後まで進められることを保証します。

(1) 十分性（$\Delta_k\neq0\Rightarrow LU$ が存在）

帰納法（分割とシュール補行列）で示します。$A$ を $$ A=\begin{pmatrix} a_{11} & a^\top\\[2pt] b & B \end{pmatrix},\qquad a_{11}=\Delta_1\neq0 $$ と分け、$\ell:=b/a_{11}$、シュール補行列 $$ S:=B-\frac{1}{a_{11}}\,b\,a^\top $$ を定義すると $$ A= \underbrace{\begin{pmatrix}1&0\\ \ell&I\end{pmatrix}}_{L_1} \underbrace{\begin{pmatrix}a_{11}&a^\top\\ 0&S\end{pmatrix}}_{U_1}. $$ ここで重要なのは、仮定 $\Delta_k\neq0$ から $S$ の先頭主小行列式もすべて非零になること（$\det S_{1:(k-1),1:(k-1)}=\Delta_k/\Delta_1\neq0$）。よって帰納法の仮定により $S=L_SU_S$（$L_S$ 単位下三角、$U_S$ 上三角）。まとめると $$ A=\underbrace{L_1\begin{pmatrix}1&0\\ 0&L_S\end{pmatrix}}_{L\ \text{単位下三角}} \underbrace{\begin{pmatrix}a_{11}&a^\top\\ 0&U_S\end{pmatrix}}_{U\ \text{上三角}}, $$ つまり $A=LU$ が構成できます。

直観：各段階で「列の下側をピボットで割って係数を作る→その列を消去→右下ブロックに進む」を、行交換せず最後まで続けられる、ということです。

(2) 必要性（$A=LU\Rightarrow \Delta_k\neq0$）

もし $A=LU$（$L$ 単位下三角、$U$ 上三角）なら、 $$ A_{1:k,1:k}=L_{1:k,1:k}\,U_{1:k,1:k}. $$ よって $$ \Delta_k=\det(L_{1:k,1:k})\det(U_{1:k,1:k})=1\cdot \prod_{i=1}^k u_{ii}, $$ 上三角の対角の積なので $\Delta_k\neq0$。
（逆に $\Delta_k=0$ なら、行交換なしの消去はどこかで止まります。）

(3) 一意性（$L$ を単位下三角に固定した場合）

$A=L_1U_1=L_2U_2$ とすると $$ L_2^{-1}L_1 = U_2U_1^{-1}. $$ 左辺は単位下三角、右辺は上三角。両者が等しい行列は恒等行列しかありえないため、$L_1=L_2$, $U_1=U_2$。一意性が従います。

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

ガウス消去では、各ステップでピボット（現在の先頭位置の対角要素）が 0 でないことが必要です。
行交換を許せば、現在の列の中から非零の成分を上に持ってくることができ、消去を必ず進められます（その列がすべて 0 の場合は、そもそも消去不要で次の列へ進める）。

$n=1$ は自明。$n>1$ について示す。行列を

$$ A=\begin{pmatrix} a_{11} & a^\top\\[2pt] b & B \end{pmatrix}, \quad a^\top\in\mathbb{F}^{1\times(n-1)},\ b\in\mathbb{F}^{(n-1)\times 1},\ B\in\mathbb{F}^{(n-1)\times(n-1)} $$

の形に分けて議論する（1 行 1 列を“現在の位置”とみなす）。

ケース1：第1列に非零がある（標準的な場合）

第1列のどこかに非零成分があるので、置換行列 $P_1$ を選び、その非零成分を先頭（行1）に持ってくる。$\tilde A:=P_1A$ とおくと、$\tilde a_{11}\neq0$ で

$$ \tilde A=\begin{pmatrix} \tilde a_{11} & \tilde a^\top\\ \tilde b & \tilde B \end{pmatrix}. $$

このとき、乗数（multiplier） $\ell:=\tilde b/\tilde a_{11}$ と シュール補行列

$$S:=\tilde B-\ell\,\tilde a^\top$$

を定めると、ブロック三角分解

$$ \tilde A = \underbrace{\begin{pmatrix}1&0\\ \ell & I\end{pmatrix}}_{=:L_1\ \text{単位下三角}} \underbrace{\begin{pmatrix}\tilde a_{11} & \tilde a^\top\\ 0 & S\end{pmatrix}}_{=:U_1\ \text{上三角ブロック}} \tag{1} $$

が成り立つ（1 列目の消去を行った形）。

ここで帰納法の仮定を $S$ に適用：ある置換行列 $P_2$、単位下三角 $L_S$、上三角 $U_S$ が存在して

$$P_2 S=L_S U_S.$$

(1) に代入し、左から $\mathrm{diag}(1,P_2)$ を掛けると

$$ \underbrace{\begin{pmatrix}1&0\\ 0&P_2\end{pmatrix}}_{=:P’} \tilde A = \begin{pmatrix}1&0\\ 0&P_2\end{pmatrix} L_1 \begin{pmatrix}\tilde a_{11} & \tilde a^\top\\ 0 & S\end{pmatrix} = \underbrace{\Bigl(\begin{pmatrix}1&0\\ 0&P_2\end{pmatrix}L_1\begin{pmatrix}1&0\\ 0&P_2^\top\end{pmatrix}\Bigr)}_{=:L\ \text{単位下三角}} \underbrace{\begin{pmatrix}\tilde a_{11} & \tilde a^\top\\ 0 & L_S U_S\end{pmatrix}}_{=:U’}. $$

ここで $L$ は単位下三角、$U’=\begin{pmatrix}\tilde a_{11} & \tilde a^\top\\ 0 & L_S U_S\end{pmatrix}$ は下ブロックをさらに $U_S$ に吸収すれば上三角（の形）になる。結局

$$ (P’P_1)A=L\,U,\qquad \text{すなわち}\quad PA=LU $$

が得られる（$P:=P’P_1$ は置換行列）。

要するに：
1) その列に非零があれば行を入れ替えて非零を先頭へ（$P_1$）、
2) 乗数 $\ell$ で下を消してシュール補 $S$ を作る、
3) 右下の $S$ に同じことを再帰（帰納）適用、
4) 全体をまとめると $PA=LU$。

ケース2：第1列がすべて 0

この場合は行交換すら不要（どの行を先頭にしてもピボットは 0）。第1列はすでに上三角の形になっているので、そのまま

$$ A=\underbrace{\begin{pmatrix}1&0\\ 0&I\end{pmatrix}}_{L_1} \underbrace{\begin{pmatrix}0 & a^\top\\ 0 & B\end{pmatrix}}_{U_1} $$

とみなせる。右下ブロック $B$ に帰納法を適用し、$P_2 B=L_S U_S$。すると

$$ \begin{pmatrix}1&0\\ 0&P_2\end{pmatrix}A = \underbrace{\begin{pmatrix}1&0\\ 0&P_2\end{pmatrix}L_1}_{L} \underbrace{\begin{pmatrix}0 & a^\top\\ 0 & L_SU_S\end{pmatrix}}_{U}, $$

でやはり $PA=LU$（$P=\mathrm{diag}(1,P_2)$）が得られる。
この場合は $U$ の対角（第1対角）に 0 が立つだけで、分解自体は問題なく成立する。

以上より存在が示せた

両ケースを併せると、任意の $A$ に対して帰納的に $P,L,U$ を構成できるため、

$$PA=LU$$

が常に成立する。

• 一般に $P$ は一意ではありません（同じ列に複数の非零があれば、どれをピボットに選ぶかで $P$ が変わる）。
• ただし $P$ を固定し、かつ $L$ の対角を 1 に固定すれば、 $$PA=L_1U_1=L_2U_2 \;\Rightarrow\; L_2^{-1}L_1=U_2U_1^{-1}$$ で左辺は単位下三角、右辺は上三角。両方を満たすのは恒等行列のみなので $L_1=L_2, U_1=U_2$。つまり 与えられた $P$ のもとで $L,U$ は一意です。

• 実装では安定性のため 部分ピボット（その列で絶対値最大の行を選ぶ）を用いるのが標準。
• 長方行列にも拡張でき、$PA=LU$ で $U$ を上台形にする形が使われます。

$A=[a_1\ \cdots\ a_n]$ と列で書く。列フルランクより $\{a_1,\dots,a_n\}$ は一次独立で，以下の手続きで直交化・正規化ができる。

ステップ1
$r_{11}:=\|a_1\|>0$, $q_1:=a_1/r_{11}$。
各 $j\ge2$ について $r_{1j}:=q_1^{\top}a_j$, 残差 $a_j^{(2)}:=a_j-r_{1j}q_1$。

ステップk ($2\le k\le n$)
（すでに $q_1,\dots,q_{k-1}$ 構成済みとする）
$r_{kk}:=\bigl\|a_k^{(k)}\bigr\|>0$, $q_k:=a_k^{(k)}/r_{kk}$。
各 $j\ge k+1$ について $r_{kj}:=q_k^{\top}a_j^{(k)}$, $a_j^{(k+1)}:=a_j^{(k)}-r_{kj}q_k$。

すると各列 $a_j$ は

$$a_j=\sum_{i=1}^{j} q_i\, r_{ij}\qquad (j=1,\dots,n)$$

と展開される。列を並べると

$$ A = [q_1\ \cdots\ q_n]\, \begin{pmatrix} r_{11} & r_{12} & \cdots & r_{1n}\\ 0 & r_{22} & \cdots & r_{2n}\\ \vdots & \ddots & \ddots & \vdots\\ 0 & \cdots & 0 & r_{nn} \end{pmatrix} =: QR, $$

ここで $Q^{\top}Q=I_n$, $R$ は上三角，対角 $r_{ii}>0$。よって存在が示された。■

一意性（対角を正に規約した場合）

$A=Q_1R_1=Q_2R_2$（$Q_i^{\top}Q_i=I,\ R_i$ 上三角，$\operatorname{diag}(R_i)>0$）とすると

$$Q_1^{\top}Q_2 = R_1 R_2^{-1}.$$

左辺は直交行列，右辺は上三角行列。直交かつ上三角で対角正な行列は恒等行列しかないので， $Q_1^{\top}Q_2=I\Rightarrow Q_1=Q_2,\ R_1=R_2$。■

複素数体の場合

$\mathbb{C}$ 上では $Q^\ast Q=I$（ユニタリ），$R$ 上三角，対角 $\operatorname{diag}(R)$ を正の実数に取れば同様に存在・一意。

参考：ランク落ちや列ピボット

列が一次独立でない場合でも，列ピボット付き QR で

$$ AP = Q \begin{pmatrix} R_{11} & R_{12}\\ 0 & 0 \end{pmatrix} $$

（$P$ 置換，$\operatorname{rank}A=r=\dim R_{11}$）が取れる。

まとめ

• 列フルランクの $A$ は必ず $A=QR$（$Q$ 直交／ユニタリ，$R$ 上三角）。
• 対角を正に取れば一意。
• 構成法はグラム–シュミット（理論・概念），ハウスホルダー（実装・数値安定）の二本柱。

1. $A^\ast A\succeq0$ なので，唯一の正の平方根 $$H=(A^\ast A)^{1/2}\succeq0$$ が存在する。
2. 線形写像 $U$ を $$U(Hy):=Ay\quad(\forall\,y),\qquad U|_{\ker H}:=0$$ で定義する。よく定まること：もし $Hy_1=Hy_2$ なら $H(y_1-y_2)=0\Rightarrow y_1-y_2\in\ker H=\ker(A^\ast A)\subseteq\ker A$，ゆえに $Ay_1=Ay_2$。
3. 等長性：任意の $y$ に対し $$\|Hy\|^2=\langle y,A^\ast Ay\rangle=\|Ay\|^2=\|U(Hy)\|^2.$$ よって $U$ は $\operatorname{Im}H$ 上でノルム保存，$(\operatorname{Im}H)^\perp=\ker H$ では 0。すなわち部分等長で $$U^\ast U=P_{\operatorname{Im}H},\quad UU^\ast=P_{\overline{\operatorname{Im}A}}.$$
4. 定義より $$(U H)y=U(Hy)=Ay\quad(\forall y)\ \Rightarrow\ UH=A.$$
5. 一意性：$H$ は $A^\ast A$ の正の平方根として一意。$A=U_1H=U_2H$ なら $(U_1-U_2)$ は $\operatorname{Im}H$ 上で 0 なので，$\operatorname{Im}H$ 上では $U_1=U_2$（通常 $U|_{\ker H}=0$ を採用する）。

薄い SVD を $$A=U_r\,\Sigma_r\,V_r^\ast,\quad U_r\in\mathbb{C}^{m\times r},\ \Sigma_r=\mathrm{diag}(\sigma_1,\dots,\sigma_r)>0,\ V_r\in\mathbb{C}^{n\times r}$$ （$r=\operatorname{rank}A$）とする。このとき $$H=(A^\ast A)^{1/2}=V_r\,\Sigma_r\,V_r^\ast\ (+\ 0\ \text{on }(\operatorname{Im}V_r)^\perp),$$ $$\boxed{\,U=U_r\,V_r^\ast\,}$$ と置けば $$U\,H=(U_rV_r^\ast)\,(V_r\Sigma_rV_r^\ast)=U_r\Sigma_rV_r^\ast=A.$$

さらに $$U^\ast U=V_rV_r^\ast=P_{\operatorname{Im}(A^\ast)},\qquad UU^\ast=U_rU_r^\ast=P_{\operatorname{Im}(A)}$$ で，$U$ が部分等長であることも一目瞭然。

まとめ

• $H=(A^\ast A)^{1/2}$ を取り，$U$ を「$\operatorname{Im}H$ 上で $Hy\mapsto Ay$，$\ker H$ を 0」によって定めると $A=U H$。
• 計算には $U=A\,H^{+}$（列フルなら $U=A\,(A^\ast A)^{-1/2}$）。
• 幾何学的には SVD $A=U_r\Sigma_rV_r^\ast$ から $U=U_rV_r^\ast$ を使うと分かりやすい。

具体例として、次の $4\times3$ 行列 $$ A=\begin{pmatrix} 1&1&1\\ 1&-1&0\\ 0&0&1\\ 0&0&0 \end{pmatrix} \quad(\operatorname{rank}A=3) $$ の左極分解 $A=U\,H$を、SVD を用いて具体的に求めます（実数体。随伴 $^{\ast}$ は転置 $^{\top}$ と同じ）。

下準備：SVD

$A$ の（薄い）SVD は $$A=U_r\,\Sigma_r\,V_r^{\top}$$ で、（小数は約6桁） $$ U_r= \begin{pmatrix} -0.923880&\;\;0&-0.382683\\ \;\;0&-1&\;\;0\\ -0.382683&\;\;0&\;\;0.923880\\ \;\;0&\;\;0&\;\;0 \end{pmatrix}, \quad \Sigma_r=\operatorname{diag}(1.847759,\;1.414214,\;0.765367), $$ $$ V_r= \begin{pmatrix} -0.500000&-0.707107&-0.500000\\ -0.500000&\;\;0.707107&-0.500000\\ -0.707107&\;\;0&\;\;0.707107 \end{pmatrix}. $$ 特異値は $\sigma_1\approx1.847759,\ \sigma_2=\sqrt2,\ \sigma_3\approx0.765367$。

参考のための行列： $$ A^{\top}A=\begin{pmatrix}2&0&1\\0&2&1\\1&1&2\end{pmatrix},\qquad AA^{\top}=\begin{pmatrix}3&0&1&0\\0&2&0&0\\1&0&1&0\\0&0&0&0\end{pmatrix}. $$

左極分解 $A=U\,H$（$H=(A^{\top}A)^{1/2}$）

SVD の性質から $$H=(A^{\top}A)^{1/2}=V_r\,\Sigma_r\,V_r^{\top},\qquad U=U_r\,V_r^{\top}.$$

計算結果

$$ H\approx \begin{pmatrix} \;1.360388&-0.053825&\;0.382683\\ -0.053825&\;1.360388&\;0.382683\\ \;0.382683&\;0.382683&\;1.306563 \end{pmatrix} \quad(\text{対称・半正定値},\ H^2=A^{\top}A), $$ $$ U\approx \begin{pmatrix} \;0.653281&\;0.653281&\;0.382683\\ \;0.707107&-0.707107&\;0\\ -0.270598&-0.270598&\;0.923880\\ \;0&\;0&\;0 \end{pmatrix}. $$

検算

$$UH=A\quad(\text{数値的に一致}),\qquad U^{\top}U=I_3\ \ (\text{本例は列フルランクなので }U\text{は等長}).$$

まとめ（この例の極分解）

• 左極分解：$A=U\,H$、 $U=U_rV_r^{\top}$（等長）、$H=V_r\Sigma_rV_r^{\top}=(A^{\top}A)^{1/2}$。
• 本例は列フルランクなので $U^{\top}U=I_3$（$U$ は等長）。正方可逆なら $U$ はユニタリになります。

証明

1) $H$ の存在・性質

• $A^{*}A$ はエルミート半正定値（$\langle x,(A^{*}A)x\rangle=\|Ax\|^{2}\ge0$）。
• $A$ が可逆なら $A^{*}A$ は正定値（$\|Ax\|=0\Rightarrow x=0$）。
• スペクトル定理より，あるユニタリ $U$ と正の固有値 $\sigma_1^2,\dots,\sigma_n^2$ を用いて $$A^{*}A=U\,\mathrm{diag}(\sigma_1^2,\dots,\sigma_n^2)\,U^{*}.$$ 主平方根を $$H:=(A^{*}A)^{1/2}:=U\,\mathrm{diag}(\sigma_1,\dots,\sigma_n)\,U^{*}$$ と定めると，$H$ はエルミート正定値で $H^{2}=A^{*}A$。これは一意である。

2) $Q:=AH^{-1}$ がユニタリ

$H\succ0$ なので $H^{-1}$ が存在する。すると $$Q^{*}Q=(H^{-1})^{*}A^{*}A\,H^{-1} =H^{-1}(A^{*}A)H^{-1} =H^{-1}H^{2}H^{-1}=I.$$ よって $Q$ は等長で，正方ゆえ $QQ^{*}=I$ も成り，$Q$ はユニタリ。

3) 分解式

定義からただちに $$QH=(AH^{-1})H=A.$$

4) 一意性

もし $A=Q_1H_1$ が別の極分解（$Q_1$ ユニタリ，$H_1$ 正定値エルミート）なら $$A^{*}A=H_1Q_1^{*}Q_1H_1=H_1^{2}.$$ 正の平方根は一意なので $H_1=(A^{*}A)^{1/2}=H$，したがって $$Q_1=AH_1^{-1}=AH^{-1}=Q.$$

まとめ

可逆 $A$ に対し， $$H=(A^{*}A)^{1/2}\ \ (\text{正定値}),\qquad Q=AH^{-1}\ \ (\text{ユニタリ})$$ とおけば，$A=QH$ が成り立ち，しかもこの $Q,H$ は一意である。これが極分解（polar decomposition）の標準形である。

定理より、$A_1,\cdots, A_m$が可換ならばそれらの全て対して共通の固有ベクトル$\mathbf{v}_1$とることができ、$A_i\mathbf{v}_1=\lambda_{i_1}\mathbf{v}_1$となる。

そこで、$A_i$の列空間を$\mathbf{v}_1$と適当に延長した$\mathcal B_1=\{v_1,\,w_2,\,\dots,\,w_m\}$による基底で張り直し、線形変換$A_i$を基底$\mathcal B_1$による座標で表し直した表現行列$[A_i]_{\mathcal B_1}$を考える。

$[A_i]_{\mathcal B_1}$は$\mathcal B_1$の基底を並べた行列を$B_1$とおくと$[A_i]_{\mathcal B_1}$ = $B_1^{-1}A_i B_1$である。

これは$[A_i]_{\mathcal B_1}$について、$\mathcal B_1$のある基底を$\mathbf{x}_i$と書き直すと、$A_i\mathbf{x}_i = \sum_{j=1}^{n}c_{ij}\mathbf{x}_j$と表した際の$c_{ij}$を並べた行列であることから、以下のように変形して示せる。

$$ \begin{align} A_i\mathbf{x}_i &= \sum_{j=1}^{n} c_{ij}\mathbf{x}_j = (\mathbf{b}_1, \cdots, \mathbf{b}_n)\begin{pmatrix}c_{i1} \\ \vdots \\ c_{in}\end{pmatrix} \\ \iff A_i(\mathbf{x}_1, \cdots, \mathbf{x}_n) &= B \begin{pmatrix} c_{11} & c_{21} & \cdots & c_{n1} \\ c_{12} & c_{22} & \cdots & c_{n2} \\ \vdots & \vdots & \ddots & \vdots \\ c_{1n} & c_{2n} & \cdots & c_{nn} \end{pmatrix} = B_1 [A_i]_{\mathcal B_1} \\ \iff [A_i]_{\mathcal B_1} = B_1^{-1}A_i B_1 \end{align} $$

$[A_i]_{\mathcal B_1}$の$j$列目は$A_i\mathbf{x}_j$の$\mathcal B_1$上での座標だから、$B_1$の$1$列目が共通の固有ベクトル$\mathbf{v}_1$であったことを考えると、$A_i\mathbf{v}_1 = \lambda_{i_1}\mathbf{v}_1$より$[A_i]_{\mathcal B_1}$の1列目は$(\lambda_{i_1}, 0, \cdots, 0)^T$と第1成分以外は$0$になることが分かる。従って、以下が分かる。

$$ \begin{align} [A_i]_{\mathcal B_1} &= B_1^{-1}A_i B_1 \\ &= \begin{pmatrix} \lambda_{i_1} & *\\ 0 & S_{i_1} \end{pmatrix}, \end{align} \quad (i=1, \cdots, m) $$

ここで$S_{i_1}$と$S_{j_1}$が可換であるか検討する。まず、以下から$[A_i]_{\mathcal B_1}$と$[A_j]_{\mathcal B}$が可換であることを示す。

$$ \begin{align} [A_i]_{\mathcal B_1}[A_j]_{\mathcal B_1} &= (B_1^{-1}A_i B_1)(B_1^{-1}A_j B_1) \\ &= B_1^{-1}A_i A_j B_1 \\ &= B_1^{-1}A_j A_i B_1 \\ &= (B_1^{-1}A_j B_1)(B_1^{-1}A_i B_1) \end{align} $$

続いて、成分同士を比較するためブロックのまま積を計算する。

$$ \begin{align} \begin{pmatrix} \lambda_{i_1} & *\\ 0 & S_{i_1} \end{pmatrix} \begin{pmatrix} \lambda_{j_1} & *\\ 0 & S_{j_1} \end{pmatrix} = \begin{pmatrix} \lambda_{j_1} & *\\ 0 & S_{j_1} \end{pmatrix} \begin{pmatrix} \lambda_{i_1} & *\\ 0 & S_{i_1} \end{pmatrix} \\ \iff \begin{pmatrix} \lambda_{i_1}\lambda_{j_1} & *\\ 0 & S_{i_1}S_{j_1} \end{pmatrix} = \begin{pmatrix} \lambda_{j_1}\lambda_{i_1} & *\\ 0 & S_{j_1}S_{i_1} \end{pmatrix} \end{align} $$

以上より、$S_{i_1}S_{j_1} = S_{j_1}S_{i_1}$となって可換であることが分かる。

次に$S_{i_1}\, (i=2, \cdots, m)$も互いに可換であることから、同様に同時固有ベクトル$\mathbf{v}_2$をとり、それを用いた基底$\mathcal B_2 = \{\mathbf{v}_2, \cdots\}$を並べた行列を$B_2$とすれば、

$$ \begin{align} [S_{i_1}]_{\mathcal B_2} &= B_2^{-1}S_{i_1} B_2 \\ &= \begin{pmatrix} \lambda_{i_2} & * \\ 0 & S_{i_2} \end{pmatrix} \end{align} $$

従って、

$$ B_2′ = \begin{pmatrix}1 & 0 \\ 0 & B_2\end{pmatrix} (B_2^{-1})’ = \begin{pmatrix}1 & 0 \\ 0 & B_2^{-1}\end{pmatrix} $$

とおけば、

$$ \begin{align} (B_2^{-1})’B_1^{-1}A_i B_1 B_2′ &=(B_2^{-1})’\begin{pmatrix}\lambda_{i_1}&*\\0&S_{i_1}\end{pmatrix} B_2′ \\ &= \begin{pmatrix}1&0\\0&B_2^{-1}\end{pmatrix} \begin{pmatrix}\lambda_{i_1}&*\\0&S_{i_1}\end{pmatrix} \begin{pmatrix}1&0\\0&B_2\end{pmatrix} \\ &= \begin{pmatrix}\lambda_{i_1}&*\\0&B_2^{-1}S_{i_1}\end{pmatrix} \begin{pmatrix}1&0\\0&B_2\end{pmatrix} \\ &= \begin{pmatrix}\lambda_{i_1}&*\\0&B_2^{-1}S_{i_1}B_2\end{pmatrix} \\ &= \begin{pmatrix}\lambda_{i_1}&*&*\\0&\lambda_{i_2}&*\\0&0&S_{i_2}\end{pmatrix} \\ \end{align} $$

のようにして適当な$B_*$で$A_i$を繰り返し挟み込むことで上三角化が可能であることが分かる。

「⇐」方向（同時対角化できれば正規かつ可換）は明らかです。すなわち、$U$をユニタリ行列、$D_1, D_2$を対角行列とすれば

$$ U^{*}P_1U =D_1 \, \quad U^{*}P_2 U=D_2 $$ このとき、 $$ \begin{align} &D_1D_2 = D_2D_1 \\ &\iff (U^{*}P_1U)(U^{*}P_2 U) = (U^{*}P_2U)(U^{*}P_1 U) \\ &\iff U^{*}P_1P_2U = U^{*}P_2P_1U \\ &\iff P_1P_2 \end{align} $$ となるから$P_1$と$P_2$は可換。また、対角行列のエルミート共役も対角行列で、かつ、対角行列同士は可換だから、 $$ \begin{align} &D_1D_1^{*} = D_1^{*}D_1 \\ &\iff (U^{*}P_1U)(U^{*}P_1^{*}U) = (U^{*}P_1^{*}U)(U^{*}P_1U) \\ &\iff U^{*}P_1P_1^{*}U = U^{*}P_1^{*}P_1U \\ &\iff P_1P_1^{*} = P_1^{*}P_1 \end{align} $$ となるから$P_1$は正規行列。

次に「⇒」方向を証明します。

1. まず$A_1$ をあるユニタリ $U_1$ で対角化し$D$を得ます。

   $$ D:=U_1^{*}A_1U_1=\operatorname{diag}(\lambda_1,\dots,\lambda_n). $$

   $U_1$と$A_2, \cdots, A_m$について

   $$ B_j:=U_1^{*}A_jU_1\qquad(j=2,\dots,m) $$

   とおくと、$B_j$は正規行列でかつ$D$と可換です。正規行列であることは、

   $$ \begin{align} B_jB_j^{*} &= (U_1^{*}A_jU_1)(U_1^{*}A_jU_1)^{*} \\ &= (U_1^{*}A_jU_1)(U_1^{*}A_j^{*}U_1) \\ &= U_1^{*}A_jA_j^{*}U_1 \\ &= U_1^{*}A_j^{*}A_jU_1 \\ &= (U_1^{*}A_j^{*}U_1)(U_1^{*}A_jU_1) \\ &= (U_1^{*}A_jU_1)^{*}(U_1^{*}A_jU_1) \\ &= B_j^{*}B_j \end{align} $$ から分かります。可換であることは、 $$ \begin{align} B_jD &= (U_1^{*}A_jU_1)(U_1^{*}A_1U_1) \\ &= U_1^{*}A_jA_1U_1 \\ &= U_1^{*}A_1A_jU_1 \\ &= (U_1^{*}A_1U_1)(U_1^{*}A_jU_1) \\ &= DB_j \end{align} $$ から分かります。

2. そこで$DB_j=B_jD$ の $(p,q)$ 成分を両辺で比較すると

   $$ (DB_j)_{pq}=(\lambda_p)b^{(j)}_{pq},\qquad (B_jD)_{pq}=b^{(j)}_{pq}(\lambda_q), $$

   従って

   $$ (\lambda_p-\lambda_q)\,b^{(j)}_{pq}=0\quad(\forall p,q). $$

   よって $\lambda_p\ne\lambda_q$ なら $b^{(j)}_{pq}=0$です。また、逆に$\lambda_p=\lambda_q$ならば$b^{(j)}_{p:q, p:q}$のブロックの要素は0とは限らないことになります。つまり $B_j$ は、$A_1$ の固有値$\mu_1, \cdots, \mu_k$に対応する添字だけで成るブロックに沿ってブロック対角になります。これは例えば、$A_1=\mathrm{diag}(2,2,3,3,5)$ならば$\mu_1=2$、$\mu_2=3$、$\mu_3=5$となり、$B_j$の成分の分布は

   $$ B_j= \begin{pmatrix} \color{gray}{\boxed{\begin{matrix}*&*\\ *&*\end{matrix}}} & 0 & 0\\[4pt] 0 & \color{gray}{\boxed{\begin{matrix}*&*\\ *&*\end{matrix}}} & 0\\[4pt] 0 & 0 & \color{gray}{\boxed{*}} \end{pmatrix} $$

   となることを主張しています。そこで、各ブロックを$B_{j,1}, B_{j,2}, B_{j,3}$として、

   $$ B_j = \underbrace{\begin{pmatrix}*&*\\ *&*\end{pmatrix}}_{\displaystyle B_{j,1}} \ \oplus\ \underbrace{\begin{pmatrix}*&*\\ *&*\end{pmatrix}}_{\displaystyle B_{j,2}} \ \oplus\ \underbrace{(\ *)}_{\displaystyle B_{j,3}}. $$

   と書くように定義します。ここで行列$P, Q$に対する直和$P\oplus Q$は$\begin{pmatrix}P&0\\0&Q\end{pmatrix}$と定義しておきます
   

3. 続いて、固有値 $\mu_k$ に対応するブロック $B_{j,k}$（$j=2,\dots,m$）の対角化を考えます。$B_j$が正規行列であるため、各$B_{j,k}$ も正規となり、$B_{j,k}$を対角化するユニタリ行列$U_{j}$が存在します。すなわち、 $$ U_k^{*}B_{j,k}U_k=\text{対角} \quad(j=2,\dots,m). $$ です。
4. 従って、$U_2=\oplus_{k}U_k$と定義すれば、$(A \oplus B)(C \oplus D)=AC\oplus BD$が成り立つため、 $$ \begin{align} U_2^{*}B_jU_2 &= (\oplus_k U_k)^{*} (\oplus_k B_{j,k}) (\oplus_k U_k) \\ &= (\oplus_k U_k^{*}) (\oplus_k B_{j,k}) (\oplus_k U_k) \\ &= \oplus_k U_k^{*} B_{j,k} U_k \\ &= \text{対角行列} \end{align} $$ となります。一方、$U_2^{*} D\, U_2$はユニタリ行列の性質より$D$となります。以上より、$U=U_1U_2$とおくと$U$は$A_1, \cdots, A_m$を全て対角化することが分かります。