算法导论D Problems 答案
D-1
考虑使用归纳法进行证明。
当$n=2$时，有$V(x_0,x_1)=\begin{pmatrix} 1 & x_0\1 & x_1\end{pmatrix}$，那么有$\det(V(x_0,x_1))=x_1-x_0$，原结论成立。
当$n>2$时，假设对于$\displaystyle{n’=1,2,3,\dots,n-1,\det(V(x0,x_1,\dots,x{n’-1}))=\prod{0\le j< k< n’}(x_k-x_j)}$均成立。考虑$\det(V(x_0,x_1,\dots,x{n-1}))$的值，有
$\begin{aligned}
\det(V(x0,x_1,\dots,x{n-1})) &= \left|\begin{matrix}
1&x0&x_0^2&\dots&x_0^{n-1}\
1&x_1&x_1^2&\dots&x_1^{n-1}\
1&x_2&x_2^2&\dots&x_2^{n-1}\
\vdots & \vdots & \vdots & \ddots & \vdots\
1&x{n-1}&x{n-1}^2&\dots&x{n-1}^{n-1}\
\end{matrix}\right|\
&=\left|\begin{matrix}
1&0&0&\dots&0\
1&x1-x_0&x_1^2-x_1x_0&\dots&x_1^{n-1}-x_1^{n-2}x_0\
1&x_2-x_0&x_2^2-x_2x_0&\dots&x_2^{n-1}-x_2^{n-2}x_0\
\vdots & \vdots & \vdots & \ddots & \vdots\
1&x{n-1}-x0&x{n-1}^2-x{n-1}x_0&\dots&x{n-1}^{n-1}-x{n-1}^{n-2}x_0\
\end{matrix}\right|\
&=\left|\begin{matrix}
1&0&0&\dots&0\
1&x_1-x_0&x_1(x_1-x_0)&\dots&x_1^{n-2}(x_1-x_0)\
1&x_2-x_0&x_2(x_2-x_0)&\dots&x_2^{n-2}(x_2-x_0)\
\vdots & \vdots & \vdots & \ddots & \vdots\
1&x{n-1}-x0&x{n-1}(x{n-1}-x_0)&\dots&x{n-1}^{n-2}(x{n-1}-x_0)\
\end{matrix}\right|\
&=\left|\begin{matrix}
x_1-x_0&x_1(x_1-x_0)&\dots&x_1^{n-2}(x_1-x_0)\
x_2-x_0&x_2(x_2-x_0)&\dots&x_2^{n-2}(x_2-x_0)\
\vdots & \vdots & \ddots & \vdots\
x{n-1}-x0&x{n-1}(x{n-1}-x_0)&\dots&x{n-1}^{n-2}(x{n-1}-x_0)\
\end{matrix}\right|\
&=\prod{i=1}^{n-1}(xi-x_0)\cdot\left|\begin{matrix}
1&x_1&\dots&x_1^{n-2}\
1&x_2&\dots&x_2^{n-2}\
\vdots & \vdots & \ddots & \vdots\
1&x{n-1}&\dots&x{n-1}^{n-2}\
\end{matrix}\right|\
&=\prod{i=1}^{n-1}(xi-x_0)\cdot \det(V(x_1,x_2,\dots,x{n-1}))\
&=\prod_{0\le j< k< n}(x_k-x_j)
\end{aligned}$
故原结论成立。
D-2
a
不失一般性，假设$A$大小为$r$的所有列向量的极大无关组分别为$a_1,a_2,a_3,\dots,a_r$。
那么列向量$a{r+1},a{r+2},\dots,an$都可以由$a_1,a_2,a_3,\dots,a_r$线性表示出。考虑向量$y=Ax$，那么$\displaystyle{y_i=\sum{j=1}^n a{ij}x_j}=\sum{j=1}^ra{ij} \left(x_j+ \sum{k=r+1}^n b{kj}x_k\right)$。其中$b{kj}$表示使用$aj$来表示$a_k$时的系数，即$\displaystyle{a_k=\sum{j=1}^r b_{kj}a_j}$，也就是说，$y$是前$r$个列向量作为线性无关组表示的结果，因此有$|R(A)|\le 2^r$。
另外，由于前$r$个向量是一个极大线性无关组，这个线性无关组的任何子集的组合结果都不相同，因此有$|R(A)|\ge 2^r$。
最终有$|R(A)|=2^r$。另外，当矩阵$A$满秩时，即$r=n$，有$|R(A)|=2^n$，此时$A$定义了一个$S_n$上的排列。
b
与D-2-a一样，不失一般性，假设$A$大小为$r$的所有列向量的极大无关组分别为$a_1,a_2,a_3,\dots,a_r$。
对于任意$y\in R(A)$，$y$可以由$a1,a_2,a_3,\dots,a_r$线性表示出。由于列向量$a{r+1},a{r+2},\dots,a_n$都可以由$a_1,a_2,a_3,\dots,a_r$线性表示出，因此对于任意$T\subseteq {a{r+1},a{r+2},\dots,a_n}$，令$z=\displaystyle{\sum{a\in T}a}$。那么，$z$也可以由$a_1,a_2,a_3,\dots,a_r$线性表示出，因此$y-z\in R(A)$。也就是说，总存在唯一一个$0-1$向量$(x_1,x_2,x_3\dots,x_r)$，使得$a_1x_1+a_2x_2+a_3x_3+\dots+a_rx_r=y-z$。由于子集$T$一共有$2^{n-r}$个，因此对于任意$y\in R(A)$，总有$\vert P(A,y)\vert=2^{n-r}$。
c
矩阵$A$的前$m$行的变化只会影响最终计算结果$y=Ax$的低$m$比特，而不会影响$y$的剩下$n-m$比特。$y$始终在同一个大小为$2^m$的块中，因此不考虑低$m$比特的情况。
由于$x$始终是在同一块中，因此不失一般性，令$x=(x1,x_2,x_3,\dots x{m-1},xm,c{m+1},c_{m+2},\dots,c_n)^T$，其中$c_i$是常数。
那么对于$A$的右下方$(n-m)\times(n-m)$这一块，由于它们仅与$x$的高$n-m,$比特有关系，因此$A$的这部分的第$i$行对最终$yi$的贡献值$\displaystyle{\sum{j=m+1}^n a_{ij}c_j}$为常数，这一部分不会对证明产生影响。
因此我们只考虑左下角这$(n-m)\times m$这一块子矩阵。那么第$i$行对$yi$的贡献值为$\displaystyle{y_m’=\sum{j=1}^m a_{ij}x_j}$。
令$y’=(ym’,y{m+1}’,\dots,yn’)^T$。接下来的证明方法与D-2-b类似。由于这部分矩阵可以看成是$m$个$n-m$维的列向量组合$(a_1’,a_2’,\dots,a_m’)$而成，并且这一个子矩阵的秩为$r$，因此这$m$个列向量中存在一个大小为$r$的极大无关组$a’_1,a_2’,a_3’,\dots,a_r’$。也就是说，$a{r+1}’,a{r+2}’,\dots,a_n’$都可以由$a_1’,a_2’,a_3’,\dots,a_r’$线性表出。对于任意$T\subseteq{a’_1,a_2’,a_3’,\dots,a_r’}$，它们所组合出的$\displaystyle{y’=\sum{x\in T}x}$都是两两不同的，因此一共有$2^r$个不同的$y’$。也就是说，$y$的高$n-m$比特一共有$2^r$种不同的情况，因此按照定义，$|B(S’,m)|=2^r$。对于$B(S’,m)$中的任意一个块$b0$，假设它重新对应得到的$y’=y_0’$，那么对于任意$T\subseteq {a’{r+1},a{r+2}’,\dots,a_m’}$，令$z=\displaystyle{\sum{a’\in T}a’}$，那么$y_0-z$也可以由$a’_1,a_2’,a_3’,\dots,a_r’$线性表出，因此总存在唯一一个$0-1$向量$(x_1’,x_2’,x_3’\dots,x_r’)$，使得$a_1’x_1’+a_2’x_2’+a_3’x_3’+\dots+a_r’x_r’=y-z$成立。由于$T$一共有$2^{m-r}$个，因此$S$中总有$2^{m-r}$个数对应到这个块$b_0$中。
d
此处统计$n$阶满秩矩阵$A$的个数$p(n)$。
将$A$看成是$n$个行向量的组合。为了保证$A$是满秩的，那么就需要保证第$i$个向量不能够由第$1,2,3,\dots,i-1$个向量线性表出。因此，第$1$个行向量有$2^n-1$种选择。选择好$1$后，第$2$个行向量有$2^n-2$种选择。以此类推，第$i$个行向量有$2^n-2^{i-1}$种选择。每个行向量之间选择的数量是独立的，因此有
再加上向量$c$有$2^n$种选择，那么线性排列数目$P(n)$满足$P(n)\le p(n)\cdot 2^n$。
而$S_n$的排列数为$Q(n)=(2^n)!$。可以发现$Q(n)$是由前$2^n$个正整数构造而成的乘积，而$P(n)$的上界仅仅是这$2^n$个正整数中其中的$n+1$个，因此最终可知，$P(n)$远小于$Q(n)$。
e
考虑$n=3$时的情况。这个置换为$\pi=(0, 1, 2, 3, 4, 5, 7, 6)$。由于$\pi(0)=0$，因此向量$c=0$。由于$\pi(7)=6$，因此$A$的后$2$行有奇数个$1$，第$1$行有$2$个$1$（如果没有$1$，那么$A$就不满秩了）。$\pi(1)=1$说明$a{11}=1$。考虑$\pi(3)=3$和$\pi(5)=5$，可以发现无论是取$a{12}=1,a{13}=0$还是取$a{12}=0,a_{13}=1,\pi(3)=3,\pi(5)=5$不能同时成立。也就是说，符合条件的$A$并不存在，因此这个排列为所求。