算法导论D.1 Exercises 答案

D.1-1

如果\(A,B\)是\(n\times n\)对称矩阵，那么\(\forall 1\le i,j\le n,a_{ij}=a_{ji},b_{ij}=b_{ji}\)都成立。

令\(C=A+B,D=A-B\)，将两个式子相加或者相减，得到：

\(\begin{aligned} c_{ij}=a_{ij}+b_{ij}=a_{ji}+b_{ji}=c_{ji}\\ d_{ij}=a_{ij}-b_{ij}=a_{ji}-b_{ji}=d_{ji}\\ \end{aligned}\)

因此，矩阵\(C,D\)仍然是对称的。

D.1-2

令\(a_{ij}^T\)表示转置矩阵\(A^T\)的元素，也就是有\(a_{ij}=a_{ji}^T\)。同理，\(b_{ij}^T\)表示转置矩阵\(B^T\)的元素。

对于\((AB)^T\)中的元素，有：

\(\begin{aligned} (ab)^T_{ji}&=(ab)_{ij}\\ &=\sum_{k=1}^n a_{ik}\cdot b_{kj}\\ &=\sum_{k=1}^n a_{ki}^T\cdot b_{jk}^T\\ &=\sum_{k=1}^n b_{jk}^T\cdot a_{ki}^T\\ \end{aligned}\)

可见，对于最后一行，\(\displaystyle{\sum_{k=1}^n b_{jk}^T\cdot a_{ki}^T}\)是计算\(B^TA^T\)矩阵乘法的单个元素的定义式。因此有\((AB)^T=B^TA^T\)。

由\((A^TA)^T=A^T(A^T)^T=A^TA\)可知，\(A^TA\)是对称矩阵。

D.1-3

假设\(A,B\)是两个下三角矩阵。也就是说，对于\(1\le i< j< n\)，都有\(a_{ij}=b_{ij}=0\)。

令\(C=AB\)，那么有：

\(\begin{aligned} c_{ij}&=\sum_{k=1}^n a_{ik}\cdot b_{kj}\\ &=\sum_{k=1}^{i-1} a_{ik}\cdot b_{kj}+\sum_{k=i}^{j} a_{ik}\cdot b_{kj} + \sum_{k=j+1}^n a_{ik}\cdot b_{kj} \\ &=\sum_{k=1}^{i-1} a_{ik}\cdot 0+\sum_{k=i}^{j} a_{ik}\cdot b_{kj} + \sum_{k=j+1}^n 0\cdot b_{kj} \\ &=\sum_{k=i}^{j} a_{ik}\cdot b_{kj} \end{aligned}\)

当\(i>j\)时，剩下的求和项并不存在。因此此时\(c_{ij}=0\)，最终\(C\)为下三角矩阵。

D.1-4

令\(C=PA\)。那么有：

\[c_{ij}=\sum_{k=1}^n p_{ik}\cdot a_{kj} \]

如果对于某个特定的\(1\le k'\le n\)，有\(p_{ik'}=1\)，对于其他\(k\neq k',p_{ik}=0\)，那么有\(c_{ij}=a_{k'j}\)。这相当于将矩阵\(A\)的第\(k'\)行的内容转移到第\(i\)行，列位置不变。根据排列矩阵的定义，这相当于是行变换。

类似的，令\(D=AP\)。那么有

\[d_{ij}=\sum_{k=1}^n a_{ik}\cdot p_{kj} \]

如果对于某个特定的\(1\le k'\le n\)，有\(p_{k'j}=1\)，对于其他\(k\neq k',p_{kj}=0\)，那么有\(c_{ij}=a_{ik'}\)。这相当于将矩阵\(A\)的第\(k'\)列的内容转移到第\(j\)列，行位置不变。根据排列矩阵的定义，这相当于是列变换。

由于两个排列矩阵相乘，本质上是通过一个矩阵对另外一个排列进行重置，因此相乘结果仍然是排列矩阵。