作业4¶

提交截至时间：2022/10/28 周五 12:00（中午）

习题 1. 定义

\[ A = \left( \begin{array}{r r r} 2 & - 2 & 1 \\ - 1 & 1 & - 1 \\ - 3 & - 1 & 1 \end{array} \right) \]

(i) 给出矩阵 $A ^ { \mathrm { T } } A$ 的 Cholesky 分解 $A ^ { \mathrm { T } } A = G G ^ { \mathrm { T } }$

(ii) 试说明 $\| A ^ { \mathrm { T } } A \| _ { 2 } = \| A \| _ { 2 } ^ { 2 } = \| G \| _ { 2 } ^ { 2 }$

解. (i) 记

\[ M = A ^ {\mathrm {T}} A = \left( \begin{array}{c c c} 1 4 & - 2 & 0 \\ - 2 & 6 & - 4 \\ 0 & - 4 & 3 \end{array} \right) \]

消除 $M$ 的第一列中的对角线条目

\[ L _ {1} M = \left( \begin{array}{c c c} \sqrt {1 4} & - \frac {2}{\sqrt {1 4}} & 0 \\ 0 & \frac {4 0}{7} & - 4 \\ 0 & - 4 & 3 \end{array} \right) \qquad L _ {1} = \left( \begin{array}{c c c} \frac {1}{\sqrt {1 4}} & 0 & 0 \\ \frac {1}{7} & 1 & 0 \\ 0 & 0 & 1 \end{array} \right) \]

$L _ { 1 } M$ 右乘 $L _ { 1 } ^ { \mathrm { T } }$

\[ L _ {1} M L _ {1} ^ {\mathrm {T}} = \left( \begin{array}{c c c} 1 & 0 & 0 \\ 0 & \frac {4 0}{7} & - 4 \\ 0 & - 4 & 3 \end{array} \right) \]

消除 $L _ { 1 } M L _ { 1 } ^ { \mathrm { T } }$ 的第二列中的对角线条目

\[ L _ {2} L _ {1} M L _ {1} ^ {\mathrm {T}} = \left( \begin{array}{c c c} 1 & 0 & 0 \\ 0 & \frac {2 \sqrt {7 0}}{7} & - \frac {\sqrt {7 0}}{5} \\ 0 & 0 & \frac {1}{5} \end{array} \right) \quad L _ {2} = \left( \begin{array}{c c c} 1 & 0 & 0 \\ 0 & \frac {\sqrt {7 0}}{2 0} & 0 \\ 0 & \frac {7}{1 0} & 1 \end{array} \right) \]

$L _ { 1 } M$ 右乘 $L _ { 2 } L _ { 1 } M L _ { 1 } ^ { \mathrm { T } } L _ { 2 } ^ { \mathrm { T } }$

\[ L _ {2} L _ {1} M L _ {1} ^ {\mathrm {T}} L _ {2} ^ {\mathrm {T}} = \operatorname {d i a g} _ {3 \times 3} \left(1, 1, \frac {1}{5}\right). \]

令 $L _ { 3 } : = \mathrm { d i a g } _ { 3 \times 3 } ( 1 , 1 , \sqrt { 5 } )$ 使得 $L _ { 3 } L _ { 2 } L _ { 1 } M L _ { 1 } ^ { \mathrm { T } } L _ { 2 } ^ { \mathrm { T } } L _ { 3 } ^ { \mathrm { T } } = I _ { 3 }$ . 我们有 $M = A ^ { \mathrm { T } } A = G G ^ { \mathrm { T } }$ 其中

\[ G = L _ {1} ^ {- 1} L _ {2} ^ {- 1} L _ {3} ^ {- 1} = \left( \begin{array}{c c c} {\sqrt {1 4}} & 0 & 0 \\ {- \frac {\sqrt {1 4}}{7}} & {\frac {2 \sqrt {7 0}}{7}} & 0 \\ {0} & {- \frac {\sqrt {7 0}}{5}} & {\frac {\sqrt {5}}{5}} \end{array} \right) \]

(ii) 令 $G = U \Sigma V ^ { \mathrm { { T } } }$ ，其中 $U , V \in \mathbb { R } ^ { n \times n }$ 正交， $ { \Sigma } = \mathrm { d i a g } _ { n \times n } \left( \sigma _ { 1 } , \dots , \sigma _ { n } \right) \in \mathbb { R } ^ { n \times n }$ 且 $\sigma _ { 1 } \geq \sigma _ { 2 } \geq$ $\cdots \geq \sigma _ { n } \geq 0$ . 故 $A ^ { \mathrm { T } } A = G G ^ { \mathrm { T } } = U \Sigma V ^ { \mathrm { T } } V \Sigma U ^ { \mathrm { T } } = U \Sigma ^ { 2 } U ^ { \mathrm { T } }$ ， $A ^ { \mathrm { T } } A$ 的奇异值为 $\sigma _ { 1 } ^ { 2 } , \ldots , \sigma _ { n } ^ { 2 }$ . 因此$| A ^ { \mathrm { T } } A | _ { 2 } = \sigma _ { 1 } ^ { 2 } = | G | _ { 2 } ^ { 2 } $ . 同样的，我们可以得出 $\| A ^ { \mathrm { T } } A \| _ { 2 } = \| A \| _ { 2 } ^ { 2 }$ .

习题 2. 对 $k \in \mathbb { N } _ { 0 } ,$ , 定义

\[ A = \left( \begin{array}{ccc} - 8 & 5 & 1\\ -4 & 7 & 5\\ -8 & 5 & 1\\ -4 & 7 & 5 \end{array} \right),\quad \gamma_{k} = \inf_{\substack{M\in \mathbb{R}^{3\times 4}\\ \operatorname {rk}(M)\leq k}}\bigl\|A^{\mathrm{T}} - M\bigr\|_{2} \]

(i) 计算矩阵 $A$ 的 SVD 分解 $A = U \Sigma V ^ { \mathrm { { T } } }$ ，并使 $2 U$ 为 Hadamard 矩阵

(ii) 使用 (i) 中的结论, 求 $\operatorname { r a n k } ( A ) , { \mathcal { R } } ( A ) , { \mathcal { N } } ( A ) , \| A \| _ { 2 } , \| A \| _ { F }$

(iii) 对每个 $k \in { \mathbb { N } } _ { 0 } $ , 计算 $\gamma _ { k }$ 并找出矩阵 $A _ { k } \in \mathbb { R } ^ { 3 \times 4 }$ 使得 $\operatorname { r a n k } \left( A _ { k } \right) \leq k$ 且 $ |{ A }^{ \mathrm { T } } - { A }k | _ { 2 } = \gamma $

解. (i)

\[ A ^ {\mathrm {T}} A = 4 \left( \begin{array}{r r r} 4 0 & - 3 4 & - 1 4 \\ - 3 4 & 3 7 & 2 0 \\ - 1 4 & 2 0 & 1 3 \end{array} \right) \]

特征多项式 $p _ { A ^ { \mathrm { T } } A } ( z ) = \operatorname* { d e t } { \bigl ( } z I _ { 3 } - A ^ { \mathrm { T } } A { \bigr ) } = z ( z - 3 6 ) ( z - 3 2 4 )$ . $A ^ { \mathrm { T } } A$ 特征值为

\[ \lambda_ {1} = 3 2 4, \quad \lambda_ {2} = 3 6, \quad \lambda_ {3} = 0 \]

$\lambda _ { i }$ , $i \in \{ 1 , 2 , 3 \}$ 对应 $A ^ { \mathrm { T } } A$ 的特征空间 $E _ { \lambda _ { i } } = { \mathcal { N } } \left( \lambda _ { i } I _ { 3 } - A ^ { \operatorname { T } } A \right)$ 分别为 $E _ { \lambda _ { 1 } } = \mathrm { s p a n } \left( ( - 2 , 2 , 1 ) ^ { \mathrm { T } } \right) , E _ { \lambda _ { 2 } } =$ span $\left( ( 2 , 1 , 2 ) ^ { \mathrm { T } } \right) , E _ { \lambda _ { 3 } } = \operatorname { s p a n } \left( ( 1 , 2 , - 2 ) ^ { \mathrm { T } } \right)$ . 取归一化特征向量

\[ v _ {1} = \frac {1}{3} (- 2, 2, 1) ^ {\mathrm {T}}, \quad v _ {2} = \frac {1}{3} (2, 1, 2) ^ {\mathrm {T}}, \quad v _ {3} = \frac {1}{3} (1, 2, - 2) ^ {\mathrm {T}} \]

令 $V = \left( v _ { 1 } \left| v _ { 2 } \right| v _ { 3 } \right)$

\[ \sigma_ {1} = \sqrt {\lambda_ {1}} = 1 8, \quad \sigma_ {2} = \sqrt {\lambda_ {2}} = 6, \quad \sigma_ {3} = \sqrt {\lambda_ {3}} = 0 \]

并令 $\Sigma = \mathrm { d i a g } _ { 4 \times 3 } \left( \sigma _ { 1 } , \sigma _ { 2 } , \sigma _ { 3 } \right)$ . 然后找到正交矩阵 $U = \left( u _ { 1 } | u _ { 2 } | u _ { 3 } | u _ { 4 } \right) \in \mathbb { R } ^ { 4 \times 4 }$ 使得 $A v _ { i } = \sigma _ { i } u _ { i }$ for all $i \in \{ 1 , 2 , 3 \}$ . 其中

\[ u _ {1} = \frac {A v _ {1}}{\sigma_ {1}} = \frac {1}{2} (1, 1, 1, 1) ^ {\mathrm {T}}, \quad u _ {2} = \frac {A v _ {2}}{\sigma_ {2}} = \frac {1}{2} (- 1, 1, - 1, 1) ^ {\mathrm {T}}. \]

计算 $\mathcal { N } \left( \left( u _ { 1 } \mid u _ { 2 } \right) ^ { \mathrm { T } } \right) = \operatorname { s p a n } \left( ( 1 , 0 , - 1 , 0 ) ^ { \mathrm { T } } , ( 0 , 1 , 0 , - 1 ) ^ { \mathrm { T } } \right)$ 并得到

\[ u _ {3} = \frac {1}{2} (1, 1, - 1, - 1) ^ {\mathrm {T}} \]

(我们希望 $2 U$ 是一个 Hadamard 矩阵, 需要在 ${ \mathcal { N } } \left( \left( u _ { 1 } \mid u _ { 2 } \right) ^ { \mathrm { T } } \right)$ 找个单位向量，其元素只含 $\pm \frac { 1 } { 2 }$ . )

最后，计算 $\mathcal { N } \left( \left( u _ { 1 } \left| u _ { 2 } \right| u _ { 3 } \right) ^ { \mathrm { T } } \right) = \mathrm { s p a n } \left( ( - 1 , 1 , 1 , - 1 ) ^ { \mathrm { T } } \right)$ 并得到 $$ u _ {4} = \frac {1}{2} (- 1, 1, 1, - 1) ^ {\mathrm {T}}. $$

(我们希望 $2 U$ 是一个 Hadamard 矩阵, 需要在 $\mathcal { N } \left( \left( \boldsymbol { u } _ { 1 } \left| \boldsymbol { u } _ { 2 } \right| \boldsymbol { u } _ { 3 } \right) ^ { \mathrm { T } } \right)$ 找个单位向量，其元素只含 $\pm \frac { 1 } { 2 }$ . )因此 $A$ 的 $S V D$ 分解为:

\[ A = \left( \begin{array}{c c c} - 8 & 5 & 1 \\ - 4 & 7 & 5 \\ - 8 & 5 & 1 \\ - 4 & 7 & 5 \end{array} \right) = \left( \begin{array}{c c c c} \frac {1}{2} & - \frac {1}{2} & \frac {1}{2} & - \frac {1}{2} \\ \frac {1}{2} & \frac {1}{2} & \frac {1}{2} & \frac {1}{2} \\ \frac {1}{2} & - \frac {1}{2} & - \frac {1}{2} & \frac {1}{2} \\ \frac {1}{2} & \frac {1}{2} & - \frac {1}{2} & - \frac {1}{2} \end{array} \right) \left( \begin{array}{c c c} 1 8 & 0 & 0 \\ 0 & 6 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array} \right) \left( \begin{array}{c c c} - \frac {2}{3} & \frac {2}{3} & \frac {1}{3} \\ \frac {2}{3} & \frac {1}{3} & \frac {2}{3} \\ \frac {1}{3} & \frac {2}{3} & - \frac {2}{3} \end{array} \right) ^ {\mathrm {T}} = U \Sigma V ^ {\mathrm {T}}. \]

(ii) $A$ 有两个非零奇异值故 $\operatorname { r a n k } ( A ) = 2$ .

\[ \begin{array}{l} \mathcal {R} (A) = \operatorname {s p a n} \left(u _ {1}, \dots , u _ {r}\right) = \operatorname {s p a n} \left(u _ {1}, u _ {2}\right) = \operatorname {s p a n} \left(\frac {1}{2} (1, 1, 1, 1) ^ {\mathrm {T}}, \frac {1}{2} (- 1, 1, - 1, 1) ^ {\mathrm {T}}\right), \\ \mathcal {N} (A) = \operatorname {s p a n} \left(v _ {r + 1}, \dots , v _ {3}\right) = \operatorname {s p a n} \left(v _ {3}\right) = \operatorname {s p a n} \left(\frac {1}{3} (1, 2, - 2) ^ {\mathrm {T}}\right) \\ \left\| A \right\| _ {2} = \sigma_ {1} = 1 8, \left\| A \right\| _ {F} = \sqrt {\sum_ {i = 1} ^ {r} \sigma_ {i} ^ {2}} = \sqrt {\sigma_ {1} ^ {2} + \sigma_ {2} ^ {2}} = 6 \sqrt {1 0}. \\ \end{array} \]

(iii) 例用 (i) 中 $A$ 的 $S V D$ 分解，记 $A ^ { \mathrm { T } } = \tilde { U } \tilde { \Sigma } \tilde { V } ^ { \mathrm { T } }$ ，其中 $\tilde { U } = V$ , $\tilde { \Sigma } = \Sigma ^ { \mathrm { { T } } } , \tilde { V } = U$ :

\[ A ^ {\mathrm {T}} = \left( \begin{array}{c c c} - \frac {2}{3} & \frac {2}{3} & \frac {1}{3} \\ \frac {2}{3} & \frac {1}{3} & \frac {2}{3} \\ \frac {1}{3} & \frac {2}{3} & - \frac {2}{3} \end{array} \right) \left( \begin{array}{c c c c} 1 8 & 0 & 0 & 0 \\ 0 & 6 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right) \left( \begin{array}{c c c c} \frac {1}{2} & - \frac {1}{2} & \frac {1}{2} & - \frac {1}{2} \\ \frac {1}{2} & \frac {1}{2} & \frac {1}{2} & \frac {1}{2} \\ \frac {1}{2} & - \frac {1}{2} & - \frac {1}{2} & \frac {1}{2} \\ \frac {1}{2} & \frac {1}{2} & - \frac {1}{2} & - \frac {1}{2} \end{array} \right) ^ {\mathrm {T}} = \tilde {U} \tilde {\Sigma} \tilde {V} ^ {\mathrm {T}}. \]

记 $\tilde { U } = ( \tilde { u } _ { 1 } | \tilde { u } _ { 2 } | \tilde { u } _ { 3 } ) , \tilde { V } = ( \tilde { v } _ { 1 } | \tilde { v } _ { 2 } | \tilde { v } _ { 3 } | \tilde { v } _ { 4 } ) , \tilde { \Sigma } = \mathrm { d i a g } _ { 3 \times 4 } ( \tilde { \sigma } _ { 1 } , \tilde { \sigma } _ { 2 } , \tilde { \sigma } _ { 3 } ) $ , 其中 $\tilde { u } _ { 1 } , \tilde { u } _ { 2 } , \tilde { u } _ { 3 } \in \mathbb { R } ^ { 3 } , \tilde { v } _ { 1 } , \tilde { v } _ { 2 } , \tilde { v } _ { 3 } , \tilde { v } _ { 4 } \in$ $\mathbb { R } ^ { 4 } , \tilde { \sigma } _ { 1 } \geq \tilde { \sigma } _ { 2 } \geq \tilde { \sigma } _ { 3 } \geq 0$ .

$k = 0$ : 注意到 $\left\{ M \in \mathbb { R } ^ { 3 \times 4 } : { \mathrm { r k } } ( M ) \leq 0 \right\} = \{ 0 _ { 3 \times 4 } \}$ . 记 $A _ { 0 } : = 0 _ { 3 \times 4 }$ 并有 $\gamma _ { 0 } = \left. \| A ^ { \mathrm { T } }\| \right. _ { 2 } = \tilde { \sigma } _ { 1 } = 1 8$

$k = 1$ : 利用 Eckhart-Young-Mirsky 定理, $$ A _ {1} = \tilde {\sigma} _ {1} \tilde {u} _ {1} \tilde {v} _ {1} ^ {\mathrm {T}} = 1 8 \left( \begin{array}{c} - \frac {2}{3} \ \frac {2}{3} \ \frac {1}{3} \end{array} \right) \left( \begin{array}{c c c c} \frac {1}{2} & \frac {1}{2} & \frac {1}{2} & \frac {1}{2} \end{array} \right) = \left( \begin{array}{c c c c} - 6 & - 6 & - 6 & - 6 \ 6 & 6 & 6 & 6 \ 3 & 3 & 3 & 3 \end{array} \right) $$

并有 $\gamma _ { 1 } = \left.\| A ^ { \mathrm { T } } - A _ { 1 }\| \right. _ { 2 } = \tilde { \sigma } _ { 2 } = 6 .$

$k \geq 2$ : 因为 rank $\left( A ^ { \mathrm { T } } \right) = 2$ , 记 $A _ { k } : = A ^ { \mathrm { T } }$ , 对任意 $k \in \mathbb { N } _ { \geq 2 }$ 都有 $\gamma _ { k } = 0$

习题 3.

(i) 假设 $A$ 可逆，根据 $A$ 的 $S V D$ 结果给出 $A ^ { - 1 }$ 的 $S V D$ 分解 (提示: $ A v _ { i } = \sigma _ { i } u _ { i } ,\forall i \in { 1 , \ldots , n } $ )

(ii) 假设 $Q$ 是正交阵. 给出 $Q$ 的 $S V D$ 分解及其奇异值

(iii) 假设 $A = Q B Q ^ { \mathrm { { T } } }$ ，其中 $Q$ 是正交阵, 说明 $A$ 和 $B$ 有相同奇异值

解. (i) 记 $A$ 的SVD分解为

\[ A = U \Sigma V ^ {\mathrm {T}} = \left(u _ {1} \mid \dots \mid u _ {n}\right) \left[ \operatorname {d i a g} _ {n \times n} \left(\sigma_ {1}, \dots , \sigma_ {n}\right) \right] \left(v _ {1} \mid \dots \mid v _ {n}\right) ^ {\mathrm {T}} \]

其中 $U , V \in \mathbb { R } ^ { n \times n }$ 正交, $\sigma _ { 1 } \geq \sigma _ { 2 } \geq \cdot \cdot \cdot \geq \sigma _ { n } \geq 0$ . 因为 $A$ 可逆，有 $\operatorname { r a n k } ( A ) = n$ , $\sigma _ { i } > 0$ ,$\forall i \in \left\{ 1 , \ldots , n \right\}$ . 又由 $A = U \Sigma V ^ { \mathrm { { T } } }$ 有 $A v _ { i } = \sigma _ { i } u _ { i } ,\forall i \in \{ 1 , \ldots , n \}$ ，因此 $\begin{array} { r } { A ^ { - 1 } u _ { i } = A ^ { - 1 } \left( \frac { 1 } { \sigma _ { i } } A v _ { i } \right) = } \end{array}$ $ \frac { 1 } { \sigma _ { i } } v _ { i }$

(其中 $\begin{array} { r } { \frac { 1 } { \sigma _ { n } } \geq \dots \geq \frac { 1 } { \sigma _ { 2 } } \geq \frac { 1 } { \sigma _ { 1 } } > 0 } \end{array}$ ) 故 $$ A ^ {- 1} = \left(v _ {n} | \dots | v _ {2} \mid v _ {1}\right) \left[ \operatorname {d i a g} _ {n \times n} \left(\frac {1}{\sigma_ {n}}, \ldots , \frac {1}{\sigma_ {2}}, \frac {1}{\sigma_ {1}}\right) \right] \left(u _ {n} | \dots | u _ {2} \mid u _ {1}\right) ^ {\mathrm {T}} = (V P) \left(P \Sigma^ {- 1} P\right) (U P) ^ {\mathrm {T}}, $$

记 $P : = ( e _ { n } | \cdot \cdot \cdot | e _ { 2 } \mid e _ { 1 } ) \in \mathbb { R } ^ { n \times n }$ .

(由于 $P P ^ { \mathrm { T } } = P ^ { 2 } = I _ { n }$ ， $P$ 是正交阵，且 $V P , U P$ 是正交阵.)

(ii) 由于 $Q \in \mathbb { R } ^ { n \times n }$ 正交， $Q = Q I _ { n } I _ { n } ^ { T }$ 即 $Q$ 的 $S V D$ 分解. 显然，所有奇异值为 $1$ .

(iii) 记 $B$ 的 $S V D$ 分解为 $B = U \Sigma V ^ { \mathrm { { T } } }$ ，则 $A = Q B Q ^ { \mathrm { { T } } } = Q U \Sigma V ^ { \mathrm { { T } } } Q ^ { \mathrm { { T } } } = ( Q U ) \Sigma ( Q V ) ^ { \mathrm { { T } } }$ . 显然$A$ 和 $B$ 有相同奇异值.