線性代數：奇異值分解與極分解

這份筆記是關於奇異值分解與極分解的存在性。

廣義伴隨映射

註記 1

給定有限維內積空間\((V,\langle\cdot,\cdot\rangle_V),(W,\langle\cdot,\cdot\rangle_W)\)及線性映射\(T:V\to W\)。則存在唯一的線性映射\(T^\ast:W\to V\)使得 \[ \langle T(x),y\rangle_W=\langle x,T^\ast(y)\rangle_V \] (此命題的證明和這裡的定理1是類似的，我們某種程度上也稱這裡的\(T^\ast\)是\(T\)的伴隨映射。)

註記 2

考慮註記1中的\(T:V\to W\)和\(T^\ast:W\to V\)，則\(T^\ast T:V\to V\)和\(TT^\ast:W\to W\)都是正定的。

證明：對於所有\(0\neq x\in V\)，有 \[ \langle T^\ast T(x),x\rangle_V=\langle T(x),T(x)\rangle_W=\|T(x)\|^2>0 \] 且\(\langle T(x),T(x)\rangle_W=\langle x,T^\ast T(x)\rangle_V\)，故\(T^\ast T\)是自伴隨的。故\(T^\ast T\)是正定的。同理\(TT^\ast\)是正定的。QED

註記 3

考慮註記1中的\(T:V\to W\)和\(T^\ast:W\to V\)，則 \[ \mbox{rank}(T^\ast T)=\mbox{rank}(T)=\mbox{rank}(T^\ast)=\mbox{rank}(TT^\ast) \]

證明：給定\(V\)和\(W\)的正交規範基底\(\beta\)和\(\gamma\)，類似這裡的定理2，有 \[ [T^\ast]_\gamma^\beta=([T]_\beta^\gamma)^\ast \] 故有\(\mbox{rank}(T)=\mbox{rank}(T^\ast)\)。於是我們只須證明\(\mbox{rank}(T^\ast T)=\mbox{rank}(T)\)即可。
由維度定理，有 \[ \mbox{rank}(T^\ast T)=\dim V-\dim N(T^\ast T), \mbox{rank}(T)=\dim V-\dim N(T) \] 我們希望說明\(\dim N(T^\ast T)=\dim N(T)\)。易知\(N(T)\subseteq N(T^\ast T)\)。給定\(x\in N(T^\ast T)\)，則\(T^\ast T(x)=0\)。故有 \[ 0=\langle T^\ast T(x),x\rangle_V=\langle T(x),T(x)\rangle_W=\|T(x)\|^2 \] 故\(T(x)=0\)，即\(x\in N(T)\)，於是有\(N(T^\ast T)\subseteq N(T)\)。故有 \[ N(T)=N(T^\ast T)\mbox{ i.e. }\dim N(T)=\dim N(T^\ast T) \] 於是有\(\mbox{rank}(T^\ast T)=\mbox{rank}(T)\)。QED

奇異值分解

定理 4：奇異值分解 (Single Value Decomposition)

給定有限維內積空間\((V,\langle\cdot,\cdot\rangle_V),(W,\langle\cdot,\cdot\rangle_W)\)及線性映射\(T:V\to W\)，令\(\mbox{rank}(T)=r\)。則存在\(V\)和\(W\)的正交規範基底\(\{v_1,v_2,\cdots,v_n\}\)和\(\{u_1,u_2,\cdots,u_m\}\)及實數\(\sigma_1\geq\sigma_2\geq\cdots\geq\sigma_r>0\)使得 \[ T(v_i)=\left\{ \begin{aligned} \sigma_iu_i&,1\leq i\leq r\\ 0&,i>r \end{aligned} \right. \] 並且\(\sigma_i\)是被\(T\)唯一決定的：\(v_i\)是\(T^\ast T\)的特徵向量，並且相應的特徵值\(\lambda_i\)為 \[ \lambda_i=\left\{ \begin{aligned} \sigma_i^2&,\mbox{ for }1\leq i\leq r\\ 0&,\mbox{ for }i>r \end{aligned} \right. \]

證明：由註記2，我們知道\(T^\ast T\)是正定的(故由定義也是自伴隨的)，且由註記3有\(\mbox{rank}(T^\ast T)=\mbox{rank}(T)=r\)。則由這裡的定理10可知存在由\(T^\ast T\)的特徵向量構成的\(V\)的正交規範基底\(\{v_1,v_2,\cdots,v_n\}\)。令相應的特徵值為\(\lambda_i\)，即\(T^\ast T(v_i)=\lambda_iv_i\)。由於\(T^\ast T\)是正定的，故\(\lambda_i\geq 0\)(見這裡的註記13)。不失一般性可以令\(\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_r>0\)，且\(\forall i>r\), \(\lambda_i=0\)。而對於\(1\leq i\leq r\)，令\(\sigma_i=\sqrt{\lambda_i}\)，並令 \[ u_i=\frac{1}{\sigma_i}T(v_i) \] 即\(T(v_i)=\sigma_iu_i,\forall 1\leq i\leq r\)。考慮\(\{u_1,u_2,\cdots,u_r\}\)，則\(\forall 1\leq i\leq r\)，有 \[ \begin{aligned} \langle u_i,u_j\rangle_W&=\left\langle\frac{1}{\sigma_i}T(v_i),\frac{1}{\sigma_j}T(v_j)\right\rangle_W\\ &=\frac{1}{\sigma_i\sigma_j}\langle T(v_i),T(v_j)\rangle_W\\ &=\frac{1}{\sigma_i\sigma_j}\langle T^\ast T(v_i),v_j\rangle_V\\ &=\frac{\lambda_i}{\sigma_i\sigma_j}\langle v_i,v_j\rangle_V\\ &=\frac{\lambda_i}{\sigma_i\sigma_j}\delta_{ij}=\delta_{ij} \end{aligned} \] 關於最後一個等號，若\(i\neq j\)，則 \[ 0=\delta_{ij}=\frac{\lambda_i}{\sigma_i\sigma_j}\delta_{ij} \] 而若\(i=j\)，則 \[ 1=\frac{\lambda_i}{\sqrt{\lambda_i}\sqrt{\lambda_i}}=\frac{\lambda_i}{\sigma_i\sigma_j}\delta_{ij} \] 故有 \[ \frac{\lambda_i}{\sigma_i\sigma_j}\delta_{ij}=\delta_{ij} \] 故知\(\{u_1,u_2,\cdots,u_r\}\)是正交規範的，由這裡的註記9-2知\(\{u_1,u_2,\cdots,u_r\}\)是線性獨立的。我們可以把\(\{u_1,u_2,\cdots,u_r\}\)擴張成\(W\)的正交規範基底\(\{u_1,u_2,\cdots,u_m\}\)(可以用格蘭-施密特正交化過程做到這件事，見這裡的定理10)。最後，由於對於所有\(i>r\)有\(T^\ast T(v_i)=0\)且由註記3的證明過程知\(N(T)=N(T^\ast T)\)，我們有\(T(v_i)=0,\forall i>r\)。於是可知這裡建構的\(\{v_1,\cdots,v_n\}\), \(\{u_1,\cdots,u_m\}\)和\(\sigma_1\geq\sigma_2\geq\cdots\geq\sigma_r>0\)是滿足要求的。
接著，我們希望說明這樣的\(\sigma_i\)是唯一的。假設存在\(V\)的正交規範基底\(\{v_1,v_2,\cdots,v_n\}\)及\(W\)的正交規範基底\(\{u_1,u_2,\cdots,u_m\}\)使得 \[ T(v_i)=\left\{ \begin{aligned} \sigma_iu_i&,1\leq i\leq r\\ 0&,i>r \end{aligned} \right. \] 則 \[ \langle T^\ast(u_i),v_j\rangle_V=\langle u_i,T(v_j)\rangle_W=\left\{ \begin{aligned} \sigma_i&,\mbox{ if }i=j\leq r\\ 0&,\mbox{ otherwise} \end{aligned} \right. \] 故由這裡的定理9有 \[ T^\ast(u_i)=\sum_{j=1}^n\langle T^\ast(u_i),v_j\rangle_V v_j=\left\{ \begin{aligned} \sigma_iv_i&,\mbox{ if }i\leq r\\ 0&,\mbox{ otherwise} \end{aligned} \right. \] 故對於\(1\leq i\leq r\)，有 \[ T^\ast T(v_i)=T^\ast(\sigma_iu_i)=\sigma_iT^\ast(u_i)=\sigma_i^2v_i \] 且\(i>r\)時\(T^\ast T(v_i)=0\)，故\(\sigma_i^2\)一定要是\(T^\ast T\)的特徵值，即\(\sigma_1\geq\sigma_2\geq\cdots\geq\sigma_r>0\)是唯一的。QED

定義 4-1：奇異值 (Singular Value)

我們稱定理3中的\(\lambda_i\)為\(T\)的奇異值。

定理 4-2：矩陣的奇異值分解

給定矩陣\(A\in M_{n\times n}(F)\)，其中\(\mbox{rank}(A)=r\)，並令\(\sigma_1\geq\sigma_2\geq\cdots\geq\sigma_r>0\)為\(L_A\)的奇異值。並定義矩陣\(\Sigma\in M_{m\times n}(F)\)為 \[ \Sigma=\left( \begin{array}{ccc|c} \sigma_1 & & 0 & 0\\ & \ddots & & 0\\ 0 & & \sigma_r & 0\\ \hline 0 & \cdots & 0 & 0 \end{array} \right) \] 則存在么正矩陣\(U\in M_{m\times M}(F)\)和\(V\in M_{n\times n}(F)\)使得\(A=U\Sigma V^\ast\)。

證明：考慮\(T=L_A:F^n\to F^m\)。則由定理4知存在\(F^n\)的正交規範基底\(\beta=\{v_1,v_2,\cdots,v_n\}\)與\(F^m\)的正交規範基底\(\gamma=\{u_1,u_2,\cdots,u_m\}\)使得 \[ T(v_i)=\left\{ \begin{aligned} \sigma_iu_i&,\mbox{ for }1\leq i\leq r\\ 0&,\mbox{ otherwise} \end{aligned} \right. \] 故由定義\(\Sigma=[L_A]_\beta^\gamma\)。令\(\delta\)為\(F^n\)或\(F^m\)的標準基底(這裡稍微濫用一點符號)，則由這裡的定理6的證明過程知\([I]_\gamma^\delta\)和\([I]_\beta^\delta\)都是么正的。令\(U=[I]_\gamma^\delta\), \(V=[I]_\beta^\delta\)，則 \[ \begin{aligned} {[L_A]}_\delta&=[I]_\gamma^\delta[L_A]_\beta^\gamma[I]^\beta_\delta\\ &=U\Sigma V^{-1}=U\Sigma V^\ast \end{aligned} \] 又\([L_A]_\delta=A\)，故有\(A=U\Sigma V^\ast\)。QED

極分解

定理 5：極分解 (Polar Decomposition)

給定矩陣\(A\in M_{n\times n}(F)\)，則存在么正矩陣\(W\in M_{n\times n}(F)\)與半正定矩陣\(P\in M_{n\times n}(F)\)使得\(A=WP\)。且若\(A\)可逆，則這樣的分解是唯一的。

證明：由定理4-2知存在么正的\(U,V\)使得 \[ A=U\Sigma V^\ast=U(V^\ast V)\Sigma V^\ast=UV^\ast(V\Sigma V^\ast) \] 其中\(\Sigma\)的定義可見定理4-2。令\(W=UV^\ast\), \(P=V\Sigma V^\ast\)。因為\(\Sigma\)顯然是半正定的，故對於所有\(x\in F^n\)，有 \[ \langle V\Sigma V^\ast(x),x\rangle=\langle \Sigma(V^\ast(x)),V^\ast(x)\rangle\geq 0 \] 即\(P\)也是半正定的。另一方面，我們有 \[ WW^\ast=(UV^\ast)(VU^\ast)=UIU^\ast=I=W^\ast W \] 故\(W\)是么正的。
若\(A\)可逆，則假設存在么正的\(W,Z\)與半正定的\(P,Q\)使得\(A=WP=ZQ\)。由於\(A,W,Z\)都可逆，故\(P\)和\(Q\)也可逆。並且 \[ QP^{-1}=Z^{-1}W=Z^\ast W \] 由於\(W,Z\)是么正的，故\(QP^{-1}\)也是么正的，即 \[ \begin{aligned} I&=(Z^\ast W)^\ast(Z^\ast W)\\ &=(QP^{-1})^\ast(QP^{-1})\\ &=(P^{-1})^\ast Q^\ast QP^{-1} \end{aligned} \] 又由於\(Q\)是半正定的，故由定義知\(Q\)是自伴隨的，即\(I=(P^{-1})^\ast QQP^{-1}\)。而又\(I=I^\ast\)，故 \[ I=PP^{-1}=(P^{-1})^\ast P^\ast=(P^{-1})^\ast P \] 即\((P^{-1})^\ast=P^{-1}\) i.e. \(I=P^{-1}QQP^{-1}\) i.e. \(P^2=Q^2\)。而這在已知\(P\)和\(Q\)都是半正定矩陣的前提下會導致\(P=Q\)(詳略)，故也有\(Z=W\)，即\(A\)的極分解是唯一的。QED