算法导论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(x_0,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(x_0,x_1,\dots,x_{n-1})) &= \left|\begin{matrix} 1&x_0&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&x_1-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}-x_0&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}-x_0&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}-x_0&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}(x_i-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}(x_i-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,a_n\)都可以由\(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}\)表示使用\(a_j\)来表示\(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\)可以由\(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_{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=(x_1,x_2,x_3,\dots x_{m-1},x_m,c_{m+1},c_{m+2},\dots,c_n)^T\)，其中\(c_i\)是常数。

那么对于\(A\)的右下方\((n-m)\times(n-m)\)这一块，由于它们仅与\(x\)的高\(n-m,\)比特有关系，因此\(A\)的这部分的第\(i\)行对最终\(y_i\)的贡献值\(\displaystyle{\sum_{j=m+1}^n a_{ij}c_j}\)为常数，这一部分不会对证明产生影响。

因此我们只考虑左下角这\((n-m)\times m\)这一块子矩阵。那么第\(i\)行对\(y_i\)的贡献值为\(\displaystyle{y_m'=\sum_{j=1}^m a_{ij}x_j}\)。

令\(y'=(y_m',y_{m+1}',\dots,y_n')^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)\)中的任意一个块\(b_0\)，假设它重新对应得到的\(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}\)种选择。每个行向量之间选择的数量是独立的，因此有

\[p(n)=\prod_{i=0}^{n-1} (2^n-2^i)\]

再加上向量\(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\)并不存在，因此这个排列为所求。