Exercise 1 设 $ A $ 是一个 $ n\times n $ 的矩阵，记 $ A $ 的不同特征值为 $ \lambda_{1},\lambda_{2},\dots,\lambda_{k} $，代数重数分别为 $ a_{i} $，几何重数为 $ g_{i}=\text{dim ker}(A-\lambda_{i}I) $。 (⇒) 若 $ A $ 可对角化，则存在可逆矩阵 $ P $ 使得 $ P^{-1}AP=D $ 为对角阵。由于 $$ \begin{align*} \det(A - \lambda I) & = \det(P^{-1}DP-\lambda I) \\ & = \det(P^{-1}(D-\lambda I)P) \\ & = \det(D-\lambda I) \end{align*} $$ 说 $ A $ 和 $ D $ 的特征多项式相同，从而有一样的特征值和代数重数。 ...
Exercise 2 先证充分性。如果 $ G $ 是一个二分图，设两部分的点集分别为 $ L,R $，所有边均满足两端点分别在 $ L,R $ 中。反证法，加入存在奇环，设环中第一和最后一个点分别为 $ v_{1},v_{k} $，那么 $ k $ 为奇数。不妨设 $ v_{1}\in L $，由于一条边必然在 $ L,R $ 两部分之间 ，所以环中的点在 $ L,R $ 交替出现，即 $ v_{2}\in R,v_{3}\in L,\dots $，由于 $ k $ 是奇数，因此 $ v_{k}\in L $。这说明 $ v_{1},v_{k} $ 两个 $ L $ 中的点存在连边，与二分图矛盾。因此二分图中没有奇环。 再证必要性。如果 $ G $ 没有奇环，我们可以将 $ G $ 分成若干个连通块，每个连通块中任取一个点 $ u_{i} $，我们按照一下顺序将所有点分成 $ L,R $ 两组：首先令 $ u_{i}\in L $，将所有与 $ u_{i} $ 最短距离为偶数的点加入 $ L $，其余的点，也就是到 $ u_{i} $ 最短距离为奇数的点加入 $ R $。 ...
Exercise 1 首先计算 $ A $ 的特征值和特征向量。 $$ \det(A-\lambda I) = (-1-\lambda)(-\lambda)-6 = 0 \implies \lambda^{2}+\lambda-6 = 0 $$ 解得 $ \lambda_{1}=2,\lambda_{2}=-3 $。 对于 $ \lambda_{1}=2 $，我们求解 $ (A-2I)x=0 $，特征向量为 $$ x_{1} = k\begin{pmatrix} 1 \\ 1 \end{pmatrix} $$ 对于 $ \lambda_{2}=-3 $，我们求解 $ (A+3I)x=0 $，可以取特征向量为 $$ x_{2} = k\begin{pmatrix} 3 \\ -2 \end{pmatrix} $$ 对于 $ A^{2} $，我们计算得到 $ \mu_{1}=4,\mu_{2}=9 $。对于每个特征值，带入解出 $$ x_{1} = k\begin{pmatrix} 1 \\ 1 \end{pmatrix},x_{2} = k\begin{pmatrix} 3 \\ -2 \end{pmatrix} $$ ...
Exercise 1 证 我们有 $ \det(A^{T})=\det(-A) $，同时又有 $ \det(A^{T})=\det A $ 以及 $ \det(-A)=(-1)^{n}\det A $。 如果 $ n $ 是奇数，那么 $ (-1)^{n}=-1 $，从而得到 $ \det A=-\det A\implies \det A=0 $。如果 $ n $ 是偶数，则无法说明，这个结论必然成立。 Exercise 2 解 我们直接展开计算，就可以得到 $$ \begin{align*} \det & = \begin{vmatrix} b & b^{2} \\ c & c^{2} \end{vmatrix} - a\begin{vmatrix} 1 & b^{2} \\ 1 & c^{2} \end{vmatrix} + a^{2}\begin{vmatrix} 1 & b \\ 1 & c \end{vmatrix} \\ & = (bc^{2}-b^{2}c) - a(c^{2}-b^{2}) + a^{2}(c-b) \\ & = (b-a)(c-a)(c-b) \end{align*} $$ ...
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*} $$ ...