算法导论D.2 Exercises 答案

发表于 2023-02-19 更新于 2023-07-03 分类于算法导论阅读次数：本文字数： 3.7k 阅读时长 ≈ 3 分钟

D.2-1

由于\(B,C\)都是\(A\)的逆，因此有\(AB=BA=I,AC=CA=I\)。

因此有\(B=BI=B(AC)=(BA)C=C\)。

D.2-2

不失一般性，假设\(A\)是一个下三角矩阵（对于一个上三角矩阵，将其进行转置即可），那么使用归纳法来证明行列式的值等于其主对角线上元素的乘积。

当\(A\)是\(1\)下三角阶矩阵时，\(\det(A)=a_{11}\)，此时\(A\)是下三角矩阵，原结论成立。
当\(A\)是\(n\)下三角阶矩阵时，假设对于\(1,2,3,\dots,n-1\)阶矩阵，原结论都成立。那么按照行列式的递归定义，有\(\displaystyle{\det (A)=\sum_{j=1}^n (-1)^{i+j} a_{1j}\det(A_{[1j]})=a_{11}\det(A_{[11]})}\)。\(A[11]\)显而易见是一个\(n\)阶下三角矩阵，因此有\(\displaystyle{\det(A_{[11]})=\prod_{i=2}^n a_{ii}}\)，那么有\(\displaystyle{\det(A)=\prod_{i=1}^n a_{ii}}\)。最终原结论成立。

接下来证明下三角矩阵的逆仍然是下三角矩阵：

令\(P_1\)表示将矩阵\(A\)的第\(1\)行进行变换的操作，它将\(A\)的第\(1\)行以某个倍数加到第\(1,2,3,4,\dots,n\)行，最终使得\(a_{11}=1,a_{i1}=0(i>1)\)，那么新矩阵为\(P_1A\)。类似的，\(P_2\)是将\(P_1A\)的第\(2\)行以某个倍数加到第\(2,3,4,\dots,n\)行……最终，进行\(n\)次操作后，有\(P_nP_{n-1}\dots P_1A=I\)。由于所有行\(a_{i0}\)都是由小于\(i\)的行线性表示出，因此所有\(P_i\)的矩阵都是下三角矩阵，因此它们的乘积\(A^{-1}=P_nP_{n-1}\dots P_1\)也是下三角矩阵。

D.2-3

考虑使用归纳法证明\(P\)是可逆的，即证明\(\det(P)\neq 0\)。

当\(P\)为\(1\)阶矩阵，原结论明显成立，因为\(P=[1]\)。

当\(P\)为\(n\)阶矩阵时，假设对于\(1,2,3,\dots,n-1\)阶矩阵都成立，那么根据排列矩阵的定义，令\(p(i)\)表示第\(i\)行为\(1\)的那个列。那么有\(\displaystyle{\det (P)=\sum_{j=1}^n (-1)^{i+j} p_{1j}\det(P_{[1j]})=(-1)^{1+p(1)}\det(P_{[1,p(1)]})}\)。

考虑\(n-1\)阶矩阵\(P_{[1,p(1)]}\)。由于\(P\)的第\(1\)行只有第\(p(1)\)列元素为\(1\)，第\(p(1)\)列也只有第\(1\)行对的元素为\(1\)，因此去掉这一行和这一列后，其它元素的相对位置都不变。因此\(P_{[1,p(1)]}\)仍然是一个排列矩阵。那么有\(\det(P)=(-1)^{1+p(1)}\det(P_{[1,p(1)]})\neq 0\)，故\(P\)是可逆的。

将矩阵\(P\)的行映射到\(P^T\)的列上，将\(P\)的列映射到\(P^T\)的行上，可以发现\(P^T\)和\(P\)一样，满足每一行每一列都只有一个元素\(1\)。因此\(P^T\)仍然是排列矩阵。

考虑矩阵乘积\(PP^T\)，那么可以计算出\(\displaystyle{(PP^T)_{ij}=\sum_{k=1}^k p_{ik}\cdot p^T_{k,j}=\sum_{k=1}^k p_{ik}\cdot p_{jk}}\)。根据排列矩阵对定义，当且仅当\(i=j\)时，才有\((PP^T)_{ij}=1\)。因此\(PP^T=I\)，即\(P^T\)是\(P\)的逆。

D.2-4

构造矩阵\(C,D\)。其中矩阵\(C,D\)满足

\[ \begin{aligned} &c_{i,j}= \left \{\begin{aligned} &1 & & \text{if}\quad i=j\lor (i=i_0\land j=j_0) \\ &0 & & \text{otherwise} \end{aligned}\right. \\ &d_{i,j}= \left \{\begin{aligned} &1 & & \text{if}\quad i=j \\ &-1 & & \text{if}\quad i=i_0\land j=j_0 \\ &0 & & \text{otherwise} \end{aligned}\right. \end{aligned} \]

那么有\(A'=CA,B'=BD\)。为证明\(B'\)是\(A'\)的逆矩阵，只需证明\(A'B'=I\)，即\(CABD=C(AB)D=CD=I\)即可。

令\(W_{i,j}\)表示除了\(w_{i,j}=1\)以外，其它所有元素都为\(0\)的矩阵。那么有\(CD=(I+W_{i,j})(I-W_{i,j})=I+W_{i,j}-W_{i,j}+O=I\)，从而原题得证。

D.2-5

本题的主要证明之处在于，对于任何可逆非实数矩阵\(A\)，无法构造出可逆实数矩阵\(B\)，使得\(AB=I\)。这是显而易见的。假设\(AB=I\)，那么右乘一个\(B^{-1}\)，有\(A=B^{-1}\)。由于\(I,B^{-1}\)都是实数矩阵，而\(A\)是非实数矩阵，因此这个假设必定不成立。故原结论正确。

D.2-6

由\((A^{-1})^{T}=(A^T)^{-1}=A^{-1}\)可知，如果\(A\)是对称的，那么\(A^{-1}\)也是对称的。由\((BAB^T)^T=(B^T)^TA^TB^T=BAB^T\)可知，\(BAB^T\)是对称的。

D.2-7

通过证明这个命题的逆否命题，从而使得原命题得证。将矩阵\(A\)看作是一系列列向量的组合\(A=(a_1,a_2,a_3,\dots,a_n)\)，如果存在一组非零向量\(x=(x_1,x_2,x_3,\dots,x_n)^T\)使得\(Ax=0\)，那么说明\(a_1x_1+a_2x_2+a_3x_3+\dots+a_nx_n=0\)。这说明这\(n\)个向量是线性相关的，因此\(A\)并不是列满秩矩阵。

D.2-8

将\(n\times m\)大小的矩阵\(A\)看作是一个个列向量构成的矩阵\(A=(a_1,a_2,a_3,\dots,a_m)\)，将\(n\times s\)大小的矩阵\(B\)看成是一个系数矩阵，那么有

\[AB= (a_1,a_2,a_3,\dots,a_m) \begin{pmatrix} b_{11}& b_{12} & b_{13}&\dots&b_{1s}\\ b_{21}& b_{22} & b_{23}&\dots&b_{2s}\\ b_{31}& b_{32} & b_{33}&\dots&b_{3s}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ b_{m1}& b_{m2} & b_{m3}&\dots&b_{ms}\\ \end{pmatrix} = \begin{pmatrix} a_1b_{11}+a_2b_{21}+a_3b_{31}+\dots+a_mb_{m1}\\ a_1b_{12}+a_2b_{22}+a_3b_{32}+\dots+a_mb_{m2}\\ a_1b_{13}+a_2b_{23}+a_3b_{33}+\dots+a_mb_{m3}\\ a_1b_{14}+a_2b_{24}+a_3b_{34}+\dots+a_mb_{m4}\\ a_1b_{15}+a_2b_{25}+a_3b_{35}+\dots+a_mb_{m5} \end{pmatrix}^T \]

那么矩阵\(AB\)的每一个列向量都可以由\(A\)中的列向量线性表出，因此\(\text{rank}(AB)\le\text{rank}(A)\)。

类似的证明方式，矩阵\(AB\)的每一个行向量都可以由\(B\)中的行向量线性表出，因此\(\text{rank}(AB)\le\text{rank}(B)\)。

因此最终有\(\text{rank}(AB)\le\min\{\text{rank}(A),\text{rank}(B)\}\)。如果\(A,B\)是方阵，其中一个是非奇异的（不失一般性，假设\(B\)是非奇异的），那么\(AB\)中的极大线性无关组大小和\(A\)相同，此时有\(\text{rank}(AB)=\text{rank}(A)\)。