《Algebra》习题选做 Chapter 1
Elegia
2020-03-15 14:16:05
# Chapter 1 Matrices
> 2.6. 计算帕斯卡三角矩阵的逆：
$$
\begin{bmatrix}
1\\
1&1\\
1&2&1\\
1&3&3&1\\
1&4&6&4&1\\
\end{bmatrix}
$$
注意到下三角矩阵，可以比较方便消元。
$$
\begin{aligned}
&\left[
\begin{matrix}
1\\
1&1\\
1&2&1\\
1&3&3&1\\
1&4&6&4&1\\
\end{matrix}
\middle|
\begin{matrix}
1\\
&1\\
&&1\\
&&&1\\
&&&&1\\
\end{matrix}
\right]\\
\Rightarrow& \left[
\begin{matrix}
1\\
&1\\
&1&1\\
&1&2&1\\
&1&3&3&1\\
\end{matrix}
\middle|
\begin{matrix}
1\\
-1&1\\
&-1&1\\
&&-1&1\\
&&&-1&1\\
\end{matrix}
\right] \\
\Rightarrow& \left[
\begin{matrix}
1\\
&1\\
&&1\\
&&1&1\\
&&1&2&1\\
\end{matrix}
\middle|
\begin{matrix}
1\\
-1&1\\
1&-2&1\\
&1&-2&1\\
&&1&-2&1\\
\end{matrix}
\right] \\
\Rightarrow& \left[
\begin{matrix}
1\\
&1\\
&&1\\
&&&1\\
&&&1&1\\
\end{matrix}
\middle|
\begin{matrix}
1\\
-1&1\\
1&-2&1\\
-1&3&-3&1\\
&-1&3&-3&1\\
\end{matrix}
\right] \\
\Rightarrow& \left[
\begin{matrix}
1\\
&1\\
&&1\\
&&&1\\
&&&&1\\
\end{matrix}
\middle|
\begin{matrix}
1\\
-1&1\\
1&-2&1\\
-1&3&-3&1\\
1&-4&6&-4&1\\
\end{matrix}
\right]
\end{aligned}
$$
容易得到，$[\binom i j]^{-1} = [(-1)^{i-j}\binom i j]$，其实这就是变换 $f(x+1)$ 和 $f(x-1)$（或者转置上说就是对 EGF 乘以 $\exp x$ 和 $\exp -x$）
点评：其实结论的形式我们并不陌生，但是求解的过程其实是很多途径的。
> M.1. 记分块矩阵 $\mathbf M=\begin{bmatrix} \mathbf A&\mathbf B\\\mathbf C&\mathbf D \end{bmatrix}$，其中都是 $n\times n$ 的矩阵。求证若 $\mathbf A$ 可逆且 $\mathbf A\mathbf C=\mathbf C\mathbf A$，则 $\det \mathbf M = \det (\mathbf A \mathbf D - \mathbf C \mathbf B)$。
考虑 $\begin{bmatrix} \mathbf I&\\-\mathbf C&\mathbf A \end{bmatrix}\begin{bmatrix} \mathbf A&\mathbf B\\\mathbf C&\mathbf D \end{bmatrix}=\begin{bmatrix} \mathbf A&\mathbf B\\\mathbf A\mathbf C - \mathbf C\mathbf A&\mathbf A\mathbf D - \mathbf C\mathbf B \end{bmatrix}$，两边同取行列式得
$$
\det \mathbf I \det \mathbf A \det \mathbf M = \det \begin{bmatrix} \mathbf A&\mathbf B\\&\mathbf A\mathbf D - \mathbf C\mathbf B \end{bmatrix} = \det \mathbf A \det(\mathbf A \mathbf D - \mathbf C \mathbf B)
$$
因为 $\mathbf A$ 可逆，所以两边可以除掉 $\det \mathbf A$，等式得证。
点评：分块矩阵的行列变换在进行的时候要分析更加小心，一是要注意不存在交换律，二是对行列式值的影响。
> M.4. 求证 $\mathbf A \mathbf B - \mathbf B \mathbf A = \mathbf I$ 对于方阵 $\mathbf A, \mathbf B$ 无解。
考虑计算矩阵的迹，$\operatorname{tr} \mathbf A \mathbf B = \operatorname{tr} \mathbf B \mathbf A$，而 $\operatorname{tr} \mathbf I = n$，左右必然不相等。
点评：矩阵的迹 $\operatorname{tr} \mathbf M = \sum_{i=1}^n \mathbf M_{ii}$ 有很不错的性质，因为 $\mathbf M_1 \mathbf M_2 \cdots \mathbf M_k$ 的任何一个 cyclic shift 都不改变迹的值。
> M.10. 矩阵 $\mathbf A,\mathbf B$ 分别是一个 $m\times n$ 和 $n\times m$ 的矩阵，求证 $\mathbf I_m - \mathbf A\mathbf B$ 可逆当且仅当 $\mathbf I_n - \mathbf B\mathbf A$ 可逆。
我们先做一个启发式的推导：由 $(1-x)^{-1} = \sum_{n\ge 0} x^n$，我们先尝试展开：
$$
\begin{aligned}
(\mathbf I_m - \mathbf {AB})^{-1} & = \mathbf I_m + \mathbf{AB} + (\mathbf{AB})^2 + \cdots\\
&= \mathbf I_m + \mathbf A ( \mathbf I_n + \mathbf {BA} + (\mathbf{BA})^2 + \cdots )\mathbf B \\
&= \mathbf I_m + \mathbf A (\mathbf I_n - \mathbf{BA})^{-1} \mathbf B
\end{aligned}
$$
这个推导并不严谨，但是让我们猜到了答案。设 $\mathbf X = (\mathbf I_n - \mathbf{BA})^{-1}$，根据 $\mathbf {X - BAX} = \mathbf I_n$ 我们可以得到
$$
\begin{aligned}
& \quad (\mathbf I_m - \mathbf{AB}) (\mathbf I_m + \mathbf {AXB}) \\
&=\mathbf I_m - \mathbf{AB} + \mathbf{AXB} - \mathbf{ABAXB}\\
&=\mathbf I_m - \mathbf{AB} + \mathbf{AXB} - \mathbf A (\mathbf X - \mathbf I_n) \mathbf B\\
&=\mathbf I_m
\end{aligned}
$$
因此 $(\mathbf I_m - \mathbf {AB})^{-1} = \mathbf I_m + \mathbf {AXB}$，同理可知反着也正确。
点评：级数展开的意想不到的用途。
> M.11. （离散 _Dirichlet_ 问题）对于函数 $f(u, v)$ 的 Laplace 方程 $\frac{\partial ^2f}{\partial u^2} + \frac{\partial ^2f}{\partial v^2} = 0$ 的离散情况：
>
> 在离散情况下，一个点满足的 Laplace 方程是
> $$
> f(u+1,v)+f(u-1,v)+f(u,v+1)+f(u,v-1)-4f(u,v)=0
> $$
> 也就是每个点的值是相邻四个点的平均数。令平面的有限整点区域 $R$ 是满足该方程的全体 $(u, v)$，边界 $\partial R$ 是不在 $R$ 中，但与 $R$ 的距离为 $1$ 的全体整点。$\overline R = \partial R \cup R$ 是 $f$ 的定义域。我们想要求解这个线性方程组 $\mathbf {LX} = \mathbf B$，其中已知值是 $\partial R$ 上的点有 $f(u, v) = \beta_{uv}$。
>
> (b) _maximum principle_ 指出 $f$ 的最大值必然在边界上，请证明。
>
> (c) 请证明对于任意一组 $R, \beta$，方程的解唯一。
(b) 反证，假设 $R$ 中有最大数 $M$ 大于 $\max \beta$，那么它相邻的数必然都 $=M$ ，我们将这个数加进来，得到的是一个：$3 x_1 + 3x_2 = \cdots$，其中右边有 $6$ 项，两边除以 $6$，又是一个平均值，这个平均值还是 $= M$，我们将这个过程看做一个区域 $R'$ 的扩张，那么每时每刻满足一个等式：
$$
\sum_{(u,v) \in R'} \operatorname \alpha_{uv} f(u,v) = \sum_{(u,v) \in \partial R'} \operatorname \alpha_{uv} f(u,v)
$$
其中 $\alpha_{uv}$ 在 $R'$ 内是与 $\partial R$ 的邻接数量，在 $\partial R$ 是与 $R$ 的邻接数量。可知两个 $\alpha$ 求和相等，因此邻接的数总是 $=M$。一直扩张到 $\partial R' \cap \partial R \neq \varnothing$，导出矛盾。
(c) 假设有两个解 $\mathbf X, \mathbf Y$，考察 $\mathbf X - \mathbf Y$，对它而言 $\beta = 0$ 也就是最小值和最大值都是 $0$，由 (b) 可知解只能是 $\mathbf X - \mathbf Y=\mathbf 0$，因此 $\mathbf X = \mathbf Y$，即解唯一。