Problem 1 (1) 证明： $$ \chi(G) + \chi(\overline{G}) \leq v(G) + 1 $$ 证 归纳证明。对于大小为 $ 1 $ 的图，结论显然成立，此时 $ \chi(G)=\chi(\overline{G})=1 $。 假设对于大小为 $ n-1 $ 的图这个结论都成立，那么对于一个大小为 $ n $ 的图 $ G $，我们考虑加入一个点 $ v $。此时我们有 $$ \chi(G-v)+\chi(\overline{G}-v) \leq n $$ 我们现在证明 $ \chi(G) $ 和 $ \chi(\overline{G}) $ 中至多只有一个可能会增加 $ 1 $。设 $ G $ 中 $ v $ 的度数为 $ d(v) $，在 $ \overline{G} $ 中为 $ \overline{d}(v)=n-1-d(v) $。 ...
Exercise 1 先证明行阶梯矩阵中主元列的唯一性。由于初等行变换保持了列向量之间的线性关系，因此如果矩阵 $ A $ 的第 $ j $ 列是前 $ j-1 $ 列的线性组合，初等行变换之后也仍然成立。并且一个列为主元列，当且仅当它不能被前面的列线性表示，所以 $ A_{1} $ 和 $ A_{2} $ 中的主元列位置完全相同。 接着证明简化行阶梯矩阵的唯一性。对于每个主元列 $ j_{k} $，必须化简成单位向量 $ e_{k} $，满足主元为 $ 1 $，其余元素为 $ 0 $，具有唯一性；对于非主元列，可以表示为前面的列的线性组合，所以为 $ 0 $，也具有唯一性。因此简化行阶梯矩阵具有唯一性。 Exercise 2 (1) 我们通过选择 $ W=\text{span}\{ v_{1},v_{2},\dots,v_{n} \} $ 中的一个子集，可以构造出 $ W $ 的一个基。我们依次考虑 $ i=1,2,\dots,n $，如果 $ i=1 $ 或者 $ v_{i} $ 不是前 $ i-1 $ 个向量的线性组合，就选择 $ v_{i} $，这样最终就得到了 $ B=\{ v_{i_{1}},v_{i_{2}},\dots,v_{i_{r}} \} $。 ...
Exercise 1 首先初等行变换保持了行向量之间的线性关系，因此保证了矩阵的行空间不会改变，从而它的行秩自然也不便。同时对于列秩，这等价于左乘一个一个初等矩阵，此时显然 $ Ax=0 $ 与 $ EAx=0 $ 等价，说明两者有相同的零空间，因此列秩也不边。 对于列变换，和行变换完全同理，也可以证明行秩和列秩都不变。 下面证明矩阵 $ A $ 可以通过初等操作化为 $ \begin{pmatrix}I & 0 \\ 0 & 0\end{pmatrix} $。设 $ \mathrm{rank}(A)=r $，那么我们先通过初等行变换将 $ A $ 化成阶梯矩阵的形式，得到 $ \begin{pmatrix}I_{r} & R \\ 0 & 0\end{pmatrix} $。再对这个结果进行初等列变换，可以直接消除掉 $ R $ 部分中的所有非零元素，并且不影响其他部分。最终就可以化简为 $ \begin{pmatrix}I & 0 \\ 0 & 0\end{pmatrix} $。 Exercise 2 我们需要证明通过任意执行步骤的高斯消元得到的行阶梯矩阵，其主元数量是相同的，从而说明矩阵的秩是一个唯一的值，和消元过程无关。 由于高斯消元本质上就是一系列初等矩阵变换操作，根据第一问我们已经证明了这些操作不会改变矩阵的秩，因此最后得到的阶梯矩阵的秩也不变，最终主元数量就是秩的数量必然相同，等于原来的秩。 Exercise 3 若 $ c=0 $，那么显然有 $$ A\cdot \begin{pmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{pmatrix} = \mathbf{0} $$ 说明 $ \text{rank}(A)\neq n $，因此 $ A $ 不可逆，矛盾，所以 $ c\neq 0 $。 ...
题目 Problem 1 (1) 设每次合成仙丹为一次尝试。 在每次尝试中： 合成成功：概率为 $ p $。 产生 $ 1 $ 份仙丹。 消耗 $ 2 $ 份仙果。 合成失败：概率为 $ 1-p $。 产生 $ 0 $ 份仙丹。 消耗 $ 1 $ 份仙果。 我们关注的是平均每份仙果可以得到多少仙丹。这可以理解为仙丹产出的期望值与仙果消耗的期望值之比。 每次尝试中，获得的仙丹数量的期望值 $ \mathbb{E}[\text{仙丹}] $ 为： $$ \mathbb{E}[\text{仙丹}] = 1 \cdot p + 0 \cdot (1-p) = p $$ 每次尝试中，消耗的仙果数量的期望值 $ \mathbb{E}[\text{仙果}] $ 为： $$ \mathbb{E}[\text{仙果}] = 2 \cdot p + 1 \cdot (1-p) = 2p + 1 - p = p + 1 $$ ...
Exercise 1 Let $ A $ be an $ n \times n $ matrix. Prove the equivalence between: (i) There is a $ B $ with $ AB = I $. (ii) There is a $ C $ with $ CA = I $. Proof: We show both conditions are equivalent to $ \operatorname{rank}(A) = n $. If there exists $ B $ with $ AB = I $, then $ A $ is surjective, so $ \operatorname{rank}(A) = n $. ...
Problem 1 证明存在常数 $ c > 1 $ 和 $ N > 0 $，使得当 $ n > N $ 时， $ [n] $ 上树的同构类数量至少为 $ c^n $ 。 证 我们需要的同构类的数量则可以看成 $ n $ 个点无标号的树的数量。需要证明这个数量增长的足够快。 首先根据 Cayley 公式，$ n $ 个点的有标号的树的数量为 $ n^{n-2} $。显然所有无标号的树的数量大于 $ \dfrac{n^{n-2}}{n!} $，因为这里直接假设所有点都是对称的，但是实际上一棵有标号的树并不会对应 $ n! $ 颗无标号的树。我们直接取 $ c=2 $，于是就只需要证明存在 $ N>0 $ 满足在 $ n>N $ 时有 $$ \dfrac{n^{n-2}}{n!} > 2^{n} $$ 我们使用斯特林公式，在 $ n $ 足够大时有 $$ n! \approx \sqrt{ 2\pi n }\left( \dfrac{n}{e} \right)^{n} $$ 带入下界，得到 $$ \dfrac{n^{n-2}}{n!} \approx \dfrac{e^{n}}{\sqrt{ 2\pi}\cdot n^{5 / 2}} $$ 所以只需要证明在 $ n>N $ 时有 $$ (\sqrt{ 2\pi })^{1 / n} \cdot n^{5 / 2n} < \dfrac{e}{2} $$ 对于左式，显然有 $$ \lim_{ n \to \infty } [(\sqrt{ 2\pi })^{1 / n} \cdot n^{5 / 2n}] = 1 < \dfrac{e}{2} $$ 根据极限的定义，我们总能找到一个 $ N $ 满足条件。因此得证！ ...
Exercise 1 Let $ S \subseteq V $ be a subset of vectors in a vector space $ V $. A finite subset $ S' \subseteq S $ is maximally linearly independent in $ S $ if $ S' $ is linearly independent, and for any $ v \in S \setminus S' $ the set $ S' \cup \{v\} $ is not linearly independent. Prove that: (i) $ S' $ is maximally linearly independent in $ S $ if and only if $ S' $ (viewed as a sequence of vectors) is a basis for $ \operatorname{span}(S) $. ...
Exercise 1 Give a basis for the vector space $ M_{m\times n}(\mathbb{R}) $ consisting of all $ m \times n $ matrices. A basis consists of the matrices $ E_{ij} $ for $ 1 \leq i \leq m $ and $ 1 \leq j \leq n $, where $ E_{ij} $ has a 1 in the $ (i,j) $-th position and 0 elsewhere. Exercise 2 Give a basis for $ V = \mathbb{R}^+ = \{x \mid x \in \mathbb{R} \text{ with } x > 0\} $ with $ x \oplus x' = x \times x' $ and $ c \otimes x = x^c $. ...
Problem 1 证明 $$ \begin{align*} \sum_{i=0}^{n} (-1)^{i}\binom{ n }{ i } \binom{ n+m-i }{ k-i } = \binom{ m }{ k } \\ \sum_{i=0}^{n} \binom{ k }{ i } D_{n-i} = \sum_{j=0}^{n-k} (-1)^{j}\binom{ n-k }{ j } (n-j)! \end{align*} $$ 证 1 对于第一个式子，我们考虑组合意义。设有 $ A,B $ 两个集合，分别包含 $ n $ 和 $ m $ 个元素，总共 $ n+m $ 个元素。我们希望从集合 $ B $ 中恰好选择 $ k $ 个元素。我们可以通过容斥原理的补集形式求解，定义事件 $ A_{i} $ 为所选的 $ k $ 个元素中至少包含 $ i $ 个来自 $ A $ 的元素，那么我们需要求解的事件集合为 $ U\setminus\bigcup_{i\leq n}A_{i} $，并且 $$ \left| A_{i} \right| = \binom{ n }{ i } \binom{ n+m-i }{ k-i } $$ 因此根据容斥原理，就可以得到 $$ \left| U\setminus \bigcup_{i\leq n}A_{i} \right| = \sum_{i=0}^{n} (-1)^{i}\binom{ n }{ i } \binom{ n+m-i }{ k-i } = \binom{ m }{ k } $$ ...
题目 Problem 1.1 设 $ \mathcal{F} $ 是一个有限的 $ \sigma $-代数。定义其中“最小"的元素为其包含于 $ \mathcal{F} $ 中的子集仅为自身和空集，形式化地描述，若 $ A\in \mathcal{F} $ 为“最小”的元素，那么如果 $ B\in \mathcal{F} $ 并且 $ B\subseteq A $，那么一定有 $ B\in \{ \emptyset,A \} $。 可以证明这样的元素存在并且有限：如果不存在，那么我们每次任取一个 $ \mathcal{F} $ 中的元素，都能找到属于它的一个更小的元素，但 $ \mathcal{F} $ 是有限集，所以这样的过程不可能一直重复下去，因此“最小”元素必然存在并且有限。 我们设所有这些不同的“最小”元素为 $ S=\{ A_{1},A_{2},\dots,A_{n} \} $。我们先证明这构成了全空间的一个分划： 首先这些元素肯定两两不相交，否则不满足“最小”的定义。假设 $ A_{i}\cap A_{j}= C\neq\emptyset $，根据“最小”，非空的 $ C $ 是 $ A_{i} $ 的子集，一定有 $ C=A_{i} $，同样也有 $ C=A_{j} $，这就推出了 $ A_{i}=A_{j} $，从而矛盾。 ...