算法导论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$列，行位置不变。根据排列矩阵的定义，这相当于是列变换。

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