Homework

Problem 1 设 $ n>rst $。证明 $ n $ 个数的实数列一定至少含有长度为 $ r $ 的严格上升子序列、长度为 $ s $ 的严格下降子序列、长度为 $ t $ 的常数列中的一个。 证 反证法，假设结论不成立。 我们为第 $ i $ 个元素 $ x_{i} $ 记下标签 $ (a_{i},b_{i}) $，其中 $ a_{i} $ 表示以 $ x_{i} $ 结尾的最长上升子序列长度，$ b_{i} $ 表示以 $ x_{i} $ 结尾的最长下降子序列长度。那么我们有 $ a_{i}\in[r-1],b_{i}\in[s-1] $。因此总共只有 $ (r-1)(s-1) $ 种标签，此时又有 $ n>t\cdot(r-1)(s-1) $，所以至少有 $ t $ 个元素的标签完全相同。 我们假设 $ a_{i}=a_{j},b_{i}=b_{j} $，可以证明 $ x_{i}=x_{j} $。如果不相等，不妨设 $ i< j $。若 $ x_{i}< x_{j} $，那么我们将 $ x_{j} $ 加到以 $ x_{i} $ 结尾的最长上升子序列之后，就得到了一个长度为 $ a_{i}+1 $ 的上升子序列，所以 $ a_{j}\geq a_{i}+1 $，与 $ a_{i}=a_{j} $ 矛盾；若 $ x_{i}>x_{j} $，同理可以得到 $ b_{j}\geq b_{i}+1 $，与 $ b_{i}=b_{j} $ 矛盾。所以一定有 $ x_{i}=x_{j} $。 ...

Exercise 1 解 根据题设，平面法向量为 $ \mathbf{n}=(1,1,2) $。我们观察出一组解 $ v_{1}=(1,-1,0) $，再取 $$ v_{2} = \mathbf{n}\times v_{1} = (2,2,-2) $$ 单位化得到 $$ e_{1} = \dfrac{1}{\sqrt{ 2 }}(1,-1,0),\quad e_{2} = \dfrac{1}{\sqrt{ 3 }}(1,1,-1) $$ Exercise 2 (1) 我们取 $ q_{1}=(1,3,4,5,7) $，利用 G-S 正交化，得到 $$ q_{2} = \mathbf{b} - \dfrac{q_{1}\cdot \mathbf{b}}{\| q_{1} \| ^{2}}q_{1} = (-7,3,4,-5,1) $$ 再单位化得到 $$ \mathbf{e}_{1} = \dfrac{1}{10}(1,3,4,5,7),\quad \mathbf{e}_{2} = \dfrac{1}{10}(-7,3,4,-5,1) $$ (2) 实际上只需要求 $ y $ 到平面的投影。根据 $ (1) $ 我们得到的一组标准正交基，我们就有投影为 $$ p = (y\cdot e_{1})e_{1} + (y\cdot e_{2})e_{2} = \dfrac{1}{10}e_{1} - \dfrac{7}{10}e_{2} = \left( \dfrac{1}{2},-\dfrac{9}{50},-\dfrac{6}{25},\dfrac{2}{5},0 \right) $$ ...

Exercise 1 (1) 如果 $ A=B $，那么 $ Ax=Bx $ 对于所有 $ x \in \mathbb{R}^{n\times 1} $ 是显然的。 如果 $ \forall x \in \mathbb{R}^{n\times 1} $，都有 $ Ax=Bx $，那么我们有 $ (A-B)x=0 $。由于 $ x $ 是 $ \mathbb{R}^{n} $ 中的任意一个向量，说明 $ A-B $ 的零空间是 $ \mathbb{R}^{n} $，因此 $ \text{rank}(A-B)=0 $，也就有 $ A-B=0 $，从而 $ A=B $。 (2) $ A(A^{T}A)^{-1}A^{T} $ 和 $ B(B^{T}B)^{-1}B^{T} $ 分别是 $ A $ 和 $ B $ 的投影矩阵，记为 $ P_{A},P_{B} $。 ...

题目 Problem 1 (1) 不正确。 反例 设离散概率空间 $ (\Omega,\mathcal{F},\mathbb{P}) $，其中 $ \Omega=\mathbb{N}^{+} $，$ \mathcal{F} $ 是 $ \Omega $ 的幂集，概率测度定义为 $ \mathbb{P}(\{ k \})=\dfrac{1}{2^{k}} $。我们定义随机变量 $ X_{n}:\Omega\to \mathbb{R} $ 为 $$ X_{n}(k) = \begin{cases} 2^{n} & k = n \\ -2^{n+1} & k = n+1\\ 0 & \text{o.w.} \end{cases} $$ 此时显然每个 $ X_{n} $ 都可积，并且 $$ \mathbb{E}[X_{n}] = X_{n}(n)\mathbb{P}(\{ n \}) + X_{n}(n+1)\mathbb{P}(\{ n+1 \}) = 0 \implies \sum_{n=1}^{\infty} \mathbb{E}[X_{n}] = 0 $$ 但是 $$ \sum_{n=1}^{\infty} X_{n}(k) = \begin{cases} 2 & k=1 \\ 0 & \text{o.w.} \end{cases} $$ 从而 $$ \mathbb{E}\left[ \sum_{n=1}^{\infty} X_{n} \right] = 2 \times \mathbb{P}(\{ 1 \}) + 0 \times (1 - \mathbb{P}(\{ 1 \})) = 1 $$ 所以此时 $$ \sum_{n=1}^{\infty} \mathbb{E}[X_{n}] \neq \mathbb{E}\left[ \sum_{n=1}^{\infty} X_{n} \right] $$ 不成立的原因在于我们需要级数绝对可积才能交换求和和期望。 ...

Problem 1 在一个 $ m $ 条边的二分图中，存在一个匹配，其大小至少为 $ m / \Delta $，其中 $ \Delta $ 表示图中最大顶点的度数。 证 我们需要证明这个二分图最大匹配的大小大于等于 $ m / \Delta $。根据柯尼希定理，只需要证明最小边覆盖的大小大于等于 $ m / \Delta $。 设最小边覆盖大小为 $ t $。若 $ t< m / \Delta $，对于一个被选中的顶点 $ v $，其至多覆盖 $ \text{deg}(v)\leq\Delta $ 条边，因此最多只能覆盖 $$ t\cdot\Delta < m $$ 显然不能覆盖所有的边，不可能是一个边覆盖，矛盾。 因此至少存在一个匹配的大小至少为 $ m / \Delta $。 Problem 2 证明一名学生有 $ 20 $ 周的时间来准备 ICPC，他决定每周至少完成一次训练比赛，但他只有 $ 30 $ 套训练题。请证明，无论他如何安排训练，都会存在连续的几周，他完成的训练题集数正好是 $ 9 $ 套。 ...

Exercise 1 (1) $$ u\cdot v = v\cdot u = \sum_{i=1}^{m} v_{i}w_{i} $$ (2) $$ (u+v)\cdot w = u\cdot w + v\cdot w = \sum_{i=1}^{m} (v_{i}+u_{i})w_{i} $$ (3) $$ cu\cdot v = c(u\cdot v) = \sum_{i=1}^{m} (c\cdot u_{i}v_{i}) $$ (4) $$ u\cdot u = \sum_{i=1}^{m} u_{i}^{2} \geq 0 $$ 若 $ u\cdot u = 0 $，可以得到 $ u_{i}=0 $，从而 $ u=\mathbf{0} $。 Exercise 2 $$ u\perp v \implies u\cdot v = \sum_{i=1}^{m} u_{i}v_{i} = 0 $$ 从而 $$ \begin{align*} \| u+v \| ^{2} & = \sum_{i=1}^{m} (u_{i}+v_{i})^{2} \\ & = \sum_{i=1}^{m} u_{i}^{2} + \sum_{i=1}^{m} v_{i}^{2} + 2\sum_{i=1}^{m} u_{i}v_{i} \\ & = \sum_{i=1}^{m} u_{i}^{2} + \sum_{i=1}^{m} v_{i}^{2} \\ & = \| u \| ^{2} + \| v \| ^{2} \end{align*} $$ ...

Exercise 1 (1) 若 $ x \in \mathcal{N}(A) $，说明 $ Ax=0 $，从而一定有 $ BAx=0 $，这就得到了 $ x \in \mathcal{N}(BA) $，因此 $$ \mathcal{N}(A) \subseteq \mathcal{N}(BA) $$ (2) 当 $ \text{rank}(B)=n $，设 $ x \in \mathcal{N}(BA) $，此时有 $ BAx=0 $。由于 $ \text{rank}(B)=n $，因此我们可以得到 $ Ax=0 $，从而 $$ x \in \mathcal{N}(A) $$ 于是必然有 $ \mathcal{N}(A)=\mathcal{N}(BA) $。 如果 $ \mathcal{N}(A)=\mathcal{N}(BA) $，并不能推出 $ \text{rank}(B)=n $。我们可以构造出反例 $$ A = \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix},\quad B = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} $$ 显然这时 $ A=BA $，结论成立，但是 $ B $ 不满秩。 ...

题目 Problem 1.1 (1) 证：若 $ \sigma $-代数包含所有 $ (a,b) $，则包含 $ [a,b] $。 $$ [a,b] = \bigcap_{n=1}^{\infty} \left(a-\frac{1}{n}, b+\frac{1}{n}\right) $$ 由 $ \sigma $-代数对可数交封闭，故 $ [a,b] $ 在其中。 证：若 $ \sigma $-代数包含所有 $ [a,b] $，则包含 $ (a,b) $。 $$ （a,b) = \bigcup_{n=1}^{\infty} \left[a+\frac{1}{n}, b-\frac{1}{n}\right] $$ 由 $ \sigma $-代数对可数并封闭，故 $ (a,b) $ 在其中。 (2) 证：若 σ-代数包含所有 $ (a,b) $，则包含 $ [x,\infty) $。 $$ [x,\infty) = \bigcap_{n=1}^{\infty} \left(x-\frac{1}{n}, \infty\right) = \bigcap_{n=1}^{\infty} \bigcup_{m=1}^{\infty} \left(x-\frac{1}{n}, m\right) $$ 由 $ \sigma $-代数对可数并、可数交封闭，故 $ [x,\infty) $ 在其中。 ...

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}} \} $。 ...