算法导论28.2 Exercises 答案

发表于 2023-08-01 更新于 2025-12-23 分类于算法导论阅读次数：本文字数： 5.7k 阅读时长 ≈ 5 分钟

28.2-1

首先证明矩阵平方并不比矩阵乘法更难。令任意一个矩阵$A$，那么有$A^2=A\cdot A$。也就是说，一个$M(n)$时间复杂度的矩阵乘法算法意味着一个$O(M(n))$的矩阵平方算法。

接下来证明矩阵乘法并不比矩阵平方更难，证明过程和定理28.1的过程类似：假设$S(n)$时间内可以求出两个$n\times n$矩阵的乘积，并且$S(n)=\Omega(n^2)$且满足正则性条件：$S(2n)=O(S(n))$，那么可以在$O(S(n))$求出任意两个矩阵的乘积。

证明：构造矩阵$C=\begin{pmatrix}
A&B\I&O\end{pmatrix}$，其中$A,B$分别是两个$n\times n$大小的矩阵，那么有：

$C^2=\begin{pmatrix}A^2+B&AB\\A&B\end{pmatrix}$

可以发现，计算$C^2$完后，相当于完成了一次$AB$的矩阵乘法。计算上其它开销，可以知道

$M(n)\le S(2n)=O(S(n))$

其中等号是通过正则性条件得出，最终有$M(n)=O(S(n))$。

因此，对矩阵进行平方和乘法的困难性是一样的。

28.2-2

本解答参考了此页面的信息。

我们令$L(n)$表示对大小为$n$的方阵进行LUP分解的时间。证明过程和定理28.2的过程类似：假设$S(n)$时间内可以求出两个$n\times n$矩阵的乘积，并且$M(n)=\Omega(n^2)$且满足两个正则性条件：$\forall k\in[0,n],M(n+k)=O(M(n))$均成立；$\exists c<1/2,M(n/2)\le cM(n)$成立。那么可以在$O(M(n))$内对矩阵进行LUP分解。

证明：假设矩阵$A$的大小$n$是二次幂，那么对$A$进行分块$A=\begin{pmatrix}
B&C\D&E\end{pmatrix}$，可以发现每个矩阵大小都是一样的。

对$B$递归进行分解，假设是$P_1B=L_1U_1$，那么有

$\begin{aligned}
A&=\begin{pmatrix}P1^{-1}&O\O&I{n/2}\end{pmatrix}\begin{pmatrix}L1U_1&(P_1^{-1})^T C\D&E\end{pmatrix}\
&=\begin{pmatrix}P_1^{-1}&O\O&I{n/2}\end{pmatrix}\begin{pmatrix}L1&O\DU_1^{-1}&E-DU_1^{-1}L_1^{-1}(P{1}^{-1})^TC\end{pmatrix}\begin{pmatrix}U1&L_1^{-1}(P_1^{-1})^T C\O&I{n/2}\end{pmatrix}\
\end{aligned}$

接下来再对$E-DU1^{-1}L_1^{-1}(P{1}^{-1})^TC=P_2^{-1}L_2U_2$进行LUP分解，那么得到

$\begin{aligned}
A&=\begin{pmatrix}P1^{-1}&O\O&I{n/2}\end{pmatrix}\begin{pmatrix}L1&O\DU_1^{-1}&P_2^{-1}L_2U_2\end{pmatrix}\begin{pmatrix}U_1&L_1^{-1}(P_1^{-1})^T C\O&I{n/2}\end{pmatrix}\
&=\begin{pmatrix}P1^{-1}&O\O&I{n/2}\end{pmatrix}\begin{pmatrix}I_{n/2}&O\O&P_2^{-1}\end{pmatrix}\begin{pmatrix}L_1&O\DU_1^{-1}&L_2\end{pmatrix}\begin{pmatrix}U_1&L_1^{-1}(P_1^{-1})^T C\O&U_2\end{pmatrix}\
&=\begin{pmatrix}P_1^{-1}&O\O&P_2^{-1}\end{pmatrix}\begin{pmatrix}L_1&O\DU_1^{-1}&L_2\end{pmatrix}\begin{pmatrix}U_1&L_1^{-1}(P_1^{-1})^T C\O&U_2\end{pmatrix}\
\end{aligned}$

那么令$P=\begin{pmatrix}P_1&O\O&P_2\end{pmatrix},L=\begin{pmatrix}L_1&O\DU_1^{-1}&L_2\end{pmatrix},U=\begin{pmatrix}U_1&L_1^{-1}(P_1^{-1})^T C\O&U_2\end{pmatrix}$，我们得到了$A$的一个LUP分解。

在这个过程中，我们进行了$2$次小矩阵的递归LUP分解。其余操作都是对小矩阵进行矩阵乘法，矩阵求匿，根据定理28.1和28.2，这两个操作的时间都为$O(M(n))$；此外还涉及了一些矩阵转置，矩阵移位等操作，这些操作的时间为$O(n^2)$。那么有

$\begin{aligned}
L(n)&\le2L(n/2)+O(M(n))+O(n^2)\
&=2L(n/2)+O(M(n))\
&=O(M(n))
\end{aligned}$

与定理28.2的证明过程类似，最终有$L(n)=O(M(n))$，原结论成立。

对于$n$不是$2$的幂的情况，证明方式和定理28.2的证明过程相同，此处不赘述。

28.2-3

首先证明：如果存在一个时间为$M(n)$的布尔矩阵乘法算法，那么存在一个时间复杂度为$O(M(n)\lg n)$的求解传递闭包算法。

布尔矩阵$A,B$上的乘法定义成是：$\displaystyle{(AB){ij}=\bigvee{k=1}^n a{ik}\land b{kj}}$。此外由于$A$的传递闭包$A^{\ast}$相当于是$A^n$，因此按照第23.1章的思想，可以使用单次矩阵乘法依次计算出$A^2,A^4,A^8,\dots$也就是说，总共需要进行$\lceil \lg(n-1)\rceil$次矩阵乘法即可。因此存在一个时间复杂度为$O(M(n)\lg n)$的求解传递闭包算法。

接下来证明：如果存在一个时间为$T(n)$的求解转递闭包算法，那么存在一个时间复杂度为$O(T(n))$的布尔矩阵乘法。此处需要假设$T(n)$满足正则性条件$T(3n)=O(T(n))$。

将矩阵$A,B$视为是某些矩阵的邻接矩阵。需要注意的是，传递闭包所求出的是从当前节点$u$能够到达的所有节点。因此我们考虑构造出一个图$G=(V,E)$（其邻接矩阵为$D$），最长路径只有$2$，从而保证对这个图求出其传递闭包后，这个传递闭包的一部分就是矩阵$A,B$的乘积。

假设对于$A$的每一行（列），在$G$中都有$3$个节点。其中第$i$行表示有节点$ui,v_i,w_i$。此外，矩阵$D$的行和列顺序都是$u_1,u_2,\dots,u_n,v_1,v_2,\dots,v_n,w_1,w_2,\dots,w_n$。如果$a{ik}=1$，那么$(ui,v_k)\in E$；如果$b{kj}=1$，那么$(v_k,w_j)\in E$。并且令$D$中的主对角线上的值都为$1$，那么构造好的$D$如下：

$D=\begin{bmatrix} I_n&A&O\\ O&I_n&B\\ O&O&I_n \end{bmatrix}$

可见，右上角的那一块属于至少长度为$2$的路径的区域。因此可以得到$D$的传递闭包$D^{\ast}$为：

$D^{\ast}=\begin{bmatrix} I_n&A&AB\\ O&I_n&B\\ O&O&I_n \end{bmatrix}$

只需要取出右上角的一块即可得到$AB$的乘积。因此，求出矩阵$AB$需要$T(3n)$的运行时间。如果$T(3n)=O(T(n))$，那么矩阵乘法只需要花费$O(T(n))$的时间。

28.2-4

此时定理28.2所提出的矩阵所发求逆无效。定理28.2指出，如果$A$不是正定矩阵，那么可以构造出对称正定矩阵$A^TA$，通过间接求出对称正定矩阵$A^TA$的逆矩阵$(A^TA)^{-1}$，从而通过$A^{-1}=(A^TA)^{-1}A^T$间接求出$A^{-1}$。然而，$A_TA$是正定矩阵在$\mathbb{Z}_2$中不一定是成立的。

定理D.6指出在$\mathbb{R}$中，$A^TA$是正定矩阵，是因为对于某个$n$维向量向量$\mathbf{x}\in\mathbb{R}^n,\mathbf{x}^T(A^TA)\mathbf{x}=\lVert A\mathbf{x}\rVert=0$当且仅当$\mathbf{x}$中的全部值为$\mathbf{x}$。但是在$\mathbb{Z}_2^n$中，$\lVert A\mathbf{x}\rVert=0$并不意味着向量$A\mathbf{x}$中全部值为$0$（可以是偶数个$1$）。

最终，由于$A^TA$不一定是正定的，定理28.2无法有效地求出非正定对称（但满秩）矩阵$A$的一个逆。

$\star$ 28.2-5

和证明定理28.2的过程类似。首先假设Hermitian矩阵$A$是正定的，其大小为$2$的整数次幂。因此矩阵$A$可以分块成

$A=\begin{bmatrix} B&C^{\ast}\\ C&D \end{bmatrix}$

其中$C^{\ast}$是$C$的共轭对称矩阵。

其余过程的步骤完全相同。

当$A$不是Hermitian矩阵，或者不是正定矩阵时，使用类似的方式，先计算出Hermitian且正定的矩阵$A^{\ast}A$的逆$(A^{\ast}A)^{-1}$，然后再计算$A^{-1}=(A^{\ast}A)^{-1}A^{\ast}$即可。容易验证$((A^{\ast}A)^{-1} A^{\ast})A=(A^{\ast}A)^{-1}(A^{\ast}A)=I_n$。

接下来证明$A^{\ast}A$是既是Hermitian矩阵，又是正定的矩阵。整个过程分三步进行。

证明对于任意复数矩阵$A,B$，都有$(AB)^{\ast}=B^{\ast}A^{\ast}$。证明过程和题目D.1-2类似。为了方便表示，$A$中的元素用$a{rc}+b{rc}i$表示，$B$中的元素用$x{rc}+y{rc}i$表示。

令$a{rc}^{\ast}+b{rc}^{\ast}i$表示转置矩阵$A^T$的元素，也就是有$a{rc}^{\ast}+b{rc}^{\ast}i=a{cr}-b{cr}i$。同理，$x{rc}^{\ast}+y{rc}^{\ast}i$表示转置矩阵$B^T$的元素。

对于$(AB)^{\ast}$中的元素$p{rc}+q{rc}i$，有：

$\begin{aligned}
p{cr}^{\ast}-q{cr}^{\ast}i&=p{rc}+q{rc}i\
&=\sum{k=1}^n (a{rk}+b{rk}i)(x{kc}+y{kc}i)\
&=\sum{k=1}^n (a{kr}^{\ast}-b{kr}^{\ast}i)(x{ck}^{\ast}-y{ck}^{\ast}i)\
&=\sum{k=1}^n (x{ck}^{\ast}-y{ck}^{\ast}i)(a{kr}^{\ast}-b_{kr}^{\ast}i)\
\end{aligned}$

可见，对于最后一行，$\displaystyle{\sum{k=1}^n (x{ck}^{\ast}-y{ck}^{\ast}i)(a{kr}^{\ast}-b_{kr}^{\ast}i)}$是计算$B^{\ast}A^{\ast}$矩阵乘法的单个元素的定义式。因此有$(AB)^{\ast}=B^{\ast}A^{\ast}$。

证明对于列满秩矩阵$A,A^{\ast}A$是一个正定矩阵。对于任意$n$维向量$\mathbf{x}$，都有$\mathbf{x}^{\ast}A^{\ast}A\mathbf{x}=(A\mathbf{x})^{\ast} (A\mathbf{x})=\langle ((A\mathbf{x})^{\ast})^T,A\mathbf{x}\rangle$。如果$Ax$中存在一个项目不为$0$，那么$\langle ((A\mathbf{x})^{\ast})^T,A\mathbf{x}\rangle$的值就大于$0$，因此$A^{\ast}A$是一个正定矩阵。
证明对于列满秩矩阵$A,A^{\ast}A$是一个Hermitian矩阵。这里是直接计算$A^{\ast}A$中的每个元素$u{rc}+v{rc}i$。可见，有

$\begin{aligned}
u{rc}+v{rc}i&=\sum{k=1}^n (a{rk}^{\ast}+b{rk}^{\ast}i)(a{kc}+b{kc}i)\
&=\sum{k=1}^n (a{kr}-b{kr}i)(a^{\ast}{ck}-b^{\ast}{ck}i)\
&=u{cr}^{\ast}-v{cr}^{\ast}i
\end{aligned}$

因此$A^{\ast}A$是一个Hermitian矩阵。

当$n$不是$2$的幂时，对矩阵$A$的操作相同。因此原结论成立。