算法导论D.2 Exercises 答案

发表于 2023-02-19 更新于 2025-12-23 分类于算法导论阅读次数：本文字数： 3.3k 阅读时长 ≈ 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}}$。最终原结论成立。

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

令$P1$表示将矩阵$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 P1A=I$。由于所有行$a{i0}$都是由小于$i$的行线性表示出，因此所有$Pi$的矩阵都是下三角矩阵，因此它们的乘积$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)$。