算法导论28.2 Exercises 答案
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}P_1^{-1}&O\\O&I_{n/2}\end{pmatrix}\begin{pmatrix}L_1U_1&(P_1^{-1})^T C\\D&E\end{pmatrix}\\ &=\begin{pmatrix}P_1^{-1}&O\\O&I_{n/2}\end{pmatrix}\begin{pmatrix}L_1&O\\DU_1^{-1}&E-DU_1^{-1}L_1^{-1}(P_{1}^{-1})^TC\end{pmatrix}\begin{pmatrix}U_1&L_1^{-1}(P_1^{-1})^T C\\O&I_{n/2}\end{pmatrix}\\ \end{aligned}\)
接下来再对\(E-DU_1^{-1}L_1^{-1}(P_{1}^{-1})^TC=P_2^{-1}L_2U_2\)进行LUP分解，那么得到
\(\begin{aligned} A&=\begin{pmatrix}P_1^{-1}&O\\O&I_{n/2}\end{pmatrix}\begin{pmatrix}L_1&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}P_1^{-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\)行表示有节点\(u_i,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\)，那么\((u_i,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\)的操作相同。因此原结论成立。