容斥定理、补空间和直和

学习泛函的过程中,深感自己的线性代数拖后腿,回过头补线性代数的知识。偶然看到一位台湾教授的网站,https://ccjou.wordpress.com/, 获益匪浅,非常感谢。

我在这篇博客主要介绍 容斥定理、补空间和直和, 请和我的另一篇博客 线性变换 结合在一起看

1. 容斥定理

向量空间和子空间 一文中,我们提到任何一个向量空间 \(\mathcal {V}\) 都有两个子空间: 一个是仅包含零向量 \(\mathbf 0\) 的子空间,记为 \(\mathcal {O}\) ,一个是空间 \(\mathcal {V}\) 本身

性质1: \(\mathcal {X}\)\(\mathcal {Y}\) 是向量空间 \(\mathcal {V}\) 的两个子空间,则子空间交集 \(\mathcal {X} \cap \mathcal {Y}\) 也是空间 \(\mathcal {V}\) 的子空间

证明: 假设 \(\mathbf {x}, \mathbf {y} \in \mathcal {X} \cap \mathcal {Y}\) ,则 $, $ 因此 \(\alpha \mathbf {x} + \beta \mathbf {y} \in \mathcal {X}\)

同时 $, $ 因此 \(\alpha \mathbf {x} + \beta \mathbf {y} \in \mathcal {Y}\) 。于是 \(\alpha \mathbf {x} + \beta \mathbf {y} \in \mathcal {X} \cap \mathcal {Y}\), 即 \(\mathcal {X} \cap \mathcal {Y}\) 是子空间

自然,\(\mathcal {O}\) 也在 \(\mathcal {X} \cap \mathcal {Y}\) 子空间内

但是, \(\mathcal {X} \cup \mathcal {Y}\) 并不是子空间。举个例子,二维空间过原点两条直线是两个子空间,但显然两条直线的并集并不是子空间。但是如果基于 \(\mathcal {X} \cup \mathcal {Y}\) 进行扩展(span),我们可以得到一个子空间

因此我们定义子空间的加法如下: \[
\mathcal {X} + \mathcal {Y} = \{ \mathbf {x} + \mathbf {y} \vert \mathbf {x} \in \mathcal {X} ,\mathbf {y} \in \mathcal {Y}\} = \mathrm {span} (\mathcal {X} \cup \mathcal {Y})
\]
类似上面的证明,我们可以得出 \(\mathcal {X} + \mathcal {Y}\) 对加法和标量乘法运算封闭的结论

在此基础上,我们可以得到容斥定理\[
\dim \mathcal {X} + \dim \mathcal {Y} = \dim (\mathcal {X} + \mathcal {Y}) + \dim (\mathcal {X} \cap \mathcal {Y})
\]
证明: 假设 \(\dim \mathcal {X} = m, \dim \mathcal {Y} = n\) ,定义 \(\mathcal {X}\) 子空间的一组基底 \(\{\mathbf {x}_1, \ldots, \mathbf {x}_m\}\) ,和 \(\mathcal {Y}\) 空间的一组基底 \(\{\mathbf {y}_1, \ldots, \mathbf {y}_n \}\) ,注: 如果子空间不是在 \(\mathbb C\)\(\mathbb R\) 数系中,我们可以用坐标

定义矩阵 \(A\) 的列向量包含这两组基底: \[
A = \begin {bmatrix} \mathbf {x}_1 &\ldots & \mathbf {x}_m & \mathbf {y}_1 & \ldots & \mathbf {y}_n\end {bmatrix}
\]
显然,子空间 \(\mathcal {X} + \mathcal {Y}\) 就是 \(A\) 的列空间 (column space),因为 \(C(A) = \mathrm {span} (\mathcal {X} \cup \mathcal {Y}) = \mathcal {X} + \mathcal {Y}\) ,因此 \(\dim (\mathcal {X} + \mathcal {Y}) = \dim C(A) = \hbox {rank}A\)

另一方面,考虑 \(A\) 的零空间 (nullspace) \(N(A)\) 中的向量 \(\mathbf c\) ,即 \(A \mathbf {c} = \mathbf {0}\) ,则: \[
c_1 \mathbf {x}_1 + \cdots + c_m \mathbf {x}_m + c_{m+1} \mathbf {y}_1 + \cdots + c_{m+n} \mathbf {y}_n = \mathbf {0}
\]
\(\mathbf {x}_i\)\(\mathbf {y}_i\) 分离,得到: \[
\mathbf {z} = c_1 \mathbf {x}_1 + \cdots + c_m \mathbf {x}_m = – c_{m+1} \mathbf {y}_1 – \cdots – c_{m+n} \mathbf {y}_n
\]
这说明 \(\mathbf {z} \in \mathcal {X}\)\(\mathbf {z} \in \mathcal {Y}\) ,故 \(\mathbf {z} \in \mathcal {X} \cap \mathcal {Y}\) 。反之也成立。(这个技巧经常用到)

因此子空间交集 \(\mathcal {X} \cap \mathcal {Y}\) 就是矩阵 \(A\) 的零空间 \(N(A)\), 即 \(\dim (\mathcal {X} \cap \mathcal {Y}) = \dim N(A)\)

根据秩-零度定理: \[
\dim \mathcal {X} + \dim \mathcal {Y} = m + n = \dim (\mathcal {X} \cap \mathcal {Y}) + \dim (\mathcal {X} + \mathcal {Y})
\]
这个定理非常重要,请记住吧 \[
\dim \mathcal {X} + \dim \mathcal {Y} = \dim (\mathcal {X} \cap \mathcal {Y}) + \dim (\mathcal {X} + \mathcal {Y})
\]

2. 补子空间 (complementary subspace) 和直和

如果 \(\mathcal {X}​\) 是向量空间 \(\mathcal {V}​\) 的子空间,如果 \(\mathcal {X} \cap \mathcal {Y} = \mathcal {O}​\)\(\mathcal {X} + \mathcal {Y} = \mathcal {V}​\) ,我们就称 \(\mathcal {Y}​\)\(\mathcal {X}​\) 的补子空间 (或简称补空间)。此时 \[
\dim \mathcal {X} + \dim \mathcal {Y} = \dim (\mathcal {X} \cap \mathcal {Y}) + \dim (\mathcal {X} + \mathcal {Y}) = 0 + \dim \mathcal {V} = \dim \mathcal {V}
\]
如果 \(\mathcal {Y}\) 是向量空间 \(\mathcal {V}\) 的子空间 \(\mathcal {X}\) 的补子空间,我们称 \(\mathcal {V}\)\(\mathcal {X}\)\(\mathcal {Y}\) 的直和 (direct sum) ,符号记为 \(\mathcal {V} = \mathcal {X} \oplus \mathcal {Y}\) 。设 \(\mathcal {X}\)\(\mathcal {Y}\) 分别有基底 \(\{ \mathbf {x}_i\}\)\(\{ \mathbf {y}_i\}\) ,以下四个陈述是等价的:

  1. \(\mathcal {V} = \mathcal {X} \oplus \mathcal {Y}\)
  2. \(\mathcal {X} \cap \mathcal {Y} = \mathcal {O}\)\(\mathcal {X} + \mathcal {Y} = \mathcal {V}\)
  3. 对于任意 \(\mathbf {z} \in \mathcal {V}\) ,存在唯一向量 \(\mathbf {x} \in \mathcal {X} , \mathbf {y} \in \mathcal {Y}\) ,使得 \(\mathbf {x} + \mathbf {y} = \mathbf {z}\)
  4. \(\{ \mathbf {x}_i\} \cap \{ \mathbf {y}_i\} = \emptyset\)\(\{ \mathbf {x}_i\} \cup \{ \mathbf {y}_i\}\)\(\mathcal {V}\) 的一组基底

因为 (1) 由 (2) 定义的来,我们只需要证明 (2) \(\Rightarrow\) (3) \(\Rightarrow\) (4) \(\Rightarrow\) (2)

陈述 (2) \(\Rightarrow\) (3): 若 (2) 成立,就有 \(\dim \mathcal {V} = \dim \mathcal {X} + \dim \mathcal {Y}\) 。假设存在两种方式表示 \(\mathbf {z} \in \mathcal {V}\) ,即 \(\mathbf {z} = \mathbf {u}_1 + \mathbf {v}_1 = \mathbf {u}_2 + \mathbf {v}_2\), 其中 \(\mathbf {u}_1, \mathbf {u}_2 \in \mathcal {X}\) ,而 \(\mathbf {v}_1, \mathbf {v}_2 \in \mathcal {Y}\) 。则 \(\mathbf {u}_2 – \mathbf {u}_1 = \mathbf {v}_1 – \mathbf {v}_2\) ,也就是说 \(\mathbf {u}_2 – \mathbf {u}_1\) 既可以用 \(\mathbf {u}_1, \mathbf {u}_2\) 的线性组合表示,也可以用 \(\mathbf {v}_1, \mathbf {v}_2\) 的线性组合表示,说明 \(\mathbf {u}_2 – \mathbf {u}_1 \in \mathcal {X} \cap \mathcal {Y}\) ,但是 \(\mathcal {X} \cap \mathcal {Y} = \mathcal {O}\) ,推出 \(\mathbf {u}_2 = \mathbf {u}_1, \mathbf {v}_2 = \mathbf {v}_1\)

陈述 (3) \(\Rightarrow\) (4): 若 (3) 成立,则 \(\mathcal {V} = \mathcal {X} + \mathcal {Y}\) ,同时 \(\mathcal {X} + \mathcal {Y}\) 可由 \(\{ \mathbf {x}_i\} \cup \{ \mathbf {y}_i\}\) 扩张 (span) 而成,因此 \(\{ \mathbf {x}_i\} \cup \{ \mathbf {y}_i\}\) 必定可扩张出 \(\mathcal {V}\) ,即 \(\{ \mathbf {x}_i\} \cup \{ \mathbf {y}_i\}\) 包含向量空间 \(\mathcal {V}\) 的一组基底,下一步我们要证明 \(\{ \mathbf {x}_i\} \cup \{ \mathbf {y}_i\}\) 线性独立。考虑 \[
\mathbf {0} = \sum_{i} c_i \mathbf {x}_i + \sum_{j} d_j \mathbf {y}_j
\]
陈述(3) 指出 \(\mathcal {V}\) 中的每个元素只有一种表示方式,而 \(\mathbf {0} = \mathbf {0} + \mathbf {0}\) 是一个显而易见的解,因此我们只有这个平凡解。推出 \(\mathbf {0} = \sum_{i} c_i \mathbf {x}_i\)\(\mathbf {0} = \sum_{j} d_j \mathbf {y}_j\) 。根据基底的定义,可以得到 \(c_i = 0, d_j =0\), 因此 \(\{ \mathbf {x}_i\} \cup \{ \mathbf {y}_i\}\) 线性独立,自然就推出 \(\{ \mathbf {x}_i\} \cap \{ \mathbf {y}_i\} = \emptyset\) ,而且 \(\{ \mathbf {x}_i\} \cup \{ \mathbf {y}_i\}\)\(\mathcal {V}\) 的基底。

陈述 (4) \(\Rightarrow\) (2): 若 \(\{ \mathbf {x}_i\} \cup \{ \mathbf {y}_i\}\)\(\mathcal {V}\) 的基底,则此向量集线性独立,且 \(\dim \mathcal {V} = \dim \mathcal {X} + \dim \mathcal {Y}\) 。另一方面,根据子空间和的定义可以 \(\{ \mathbf {x}_i\} \cup \{ \mathbf {y}_i\}\) 也足以扩张 \(\mathcal {X} + \mathcal {Y}\) 。于是 \(\mathcal {V} = \mathcal {X} + \mathcal {Y}\) ,于是 \(\dim \mathcal {V} = \dim (\mathcal {X} + \mathcal {Y})\) 。根据子空间容斥定理: \[
\begin {aligned}
\dim (\mathcal {X} \cap \mathcal {Y}) &= \dim \mathcal {X} + \dim \mathcal {Y} – \dim (\mathcal {X} + \mathcal {Y}) \\
&= \dim \mathcal {V} – \dim \mathcal {V} = 0
\end {aligned}
\]
所以 \(\mathcal {X} \cap \mathcal {Y} = \mathcal {O}\)

直和是容斥定理的特殊形式: \[
\dim (\mathcal {X} \oplus \mathcal {Y}) = \dim \mathcal {X} + \dim \mathcal {Y}
\]

发表评论

电子邮件地址不会被公开。 必填项已用*标注