Homework

Exercise 1 (1) 对于任意标量 $ c $ 和向量 $ x,y\in U $，都有 $$ \begin{align*} TS(cx+y) & = T(S(cx+y)) \\ & = T(cS(x)+S(y)) \\ & = cT(S(x)) + T(S(y)) \\ & = cTS(x) + TS(y) \end{align*} $$ 从而证明了这是一个线性变换。 (2) 设 $ U,V,W $ 的基为 $$ \bar{u} = \{ u_{1},\dots,u_{p} \},\bar{v}=\{ v_{1},\dots,v_{n} \},\bar{w}=\{ w_{1},\dots,w_{m} \} $$ 根据线性变换矩阵的定义，有 $$ S(u_{i}) = \sum_{k=1}^{n} (A_{S})_{k,i}v_{k},\quad T(v_{i})=\sum_{k=1}^{m} (A_{T})_{k,i}w_{k} $$ 计算 $ TS(u_{i}) $ 并观察系数 $$ \begin{align*} TS(u_{j}) & = T(S(u_{j})) \\ & = T\left( \sum_{k=1}^{n} (A_{S})_{k,j}v_{k} \right) \\ & = \sum_{k=1}^{n} (A_{S})_{k,j}T(v_{k}) \\ & = \sum_{k=1}^{n} (A_{S})_{k,j}\left( \sum_{i=1}^{m} (A_{T})_{i,k}w_{i} \right) \\ & = \sum_{i=1}^{m} \left( \sum_{k=1}^{n} (A_{T})_{i,k}(A_{S})_{k,j} \right)w_{i} \\ & = \sum_{i=1}^{m} (A_{T}A_{S})_{i,j}w_{i} \end{align*} $$ 再结合 $ A_{TS} $ 的定义就证明了 $$ A_{TS}=A_{T}A_{S} $$ ...

Exercise 1 设 $ A $ 的特征多项式为 $ P(\lambda) = \det(A-\lambda I) $。由于特征值 $ \lambda_{1},\lambda_{2},\dots,\lambda_{n} $ 是 $ P(\lambda) $ 的根，因此 $$ P(\lambda) = (-1)^{n}(\lambda-\lambda_{1})(\lambda-\lambda_{2})\dots(\lambda-\lambda_{n}) $$ 我们首先证明 $ \prod_{i=1}^{n}\lambda_{i}=\det(A) $。首先直接带入 $$ P(0)=\det(A-0\cdot I)=\det A $$ 又有 $$ P(0) = (-1)^{n}(0-\lambda_{1})(0-\lambda_{2})\dots(0-\lambda_{n})=\prod_{i=1}^{n} \lambda_{i} $$ 这样就得到了 $ \prod_{i=1}^{n}\lambda_{i}=\det(A) $。 接着证明 $ \sum_{i=1}^{n}\lambda_{i}=\mathrm{trace}(A) $。展开 $ P(\lambda) $ 考察 $ \lambda^{n-1} $ 的系数，为 $$ (-1)^{n}\cdot \sum_{i=1}^{n} (-\lambda_{i}) = (-1)^{n+1}\sum_{i=1}^{n} \lambda_{i} $$ 同时对于矩阵 $ M=A-\lambda I $，利用行列式定义，有 $$ \det(A-\lambda I)=\sum_{\sigma \in S_{n}}\text{sgn}(n)\prod_{i=1}^{n} (A-\lambda I)_{i,\sigma(i)} $$ 其中 $ S_{n} $ 表示 $ [n] $ 中所有置换的集合。 ...

Problem 1 假设有 $ m $ 个俱乐部和 $ n $ 个人，满足以下条件： (i) 每个俱乐部的人数为偶数； (ii) 任意两个俱乐部之间共同拥有的人数为奇数。 证明：$ m \le n $。 证： 我们在有限域 $ \mathbb{F}_{2} $ 上考虑。设 $ v_{1},\dots,v_{m}\in \mathbb{F}_{2}^{n} $ 为每个俱乐部对应向量。根据条件，我们知道 人数为偶数：$ v_{i}\cdot v_{i}=0 $ 交集为奇数：$ v_{i}\cdot v_{j}=1(i\neq j) $ 考察这 $ m $ 个向量的线性相关性。假设存在系数 $ c_{1},\dots c_{m}\in \mathbb{F}_{2} $ 使得 $$ \sum_{i=1}^{m} c_{i}v_{i}=\mathbf{0} $$ 那么对于任意 $ j\in [m] $，我们将上式与 $ v_{j} $ 做内积 $$ \left( \sum_{i=1}^{m} c_{i}v_{i} \right)\cdot v_{j} = c_{j}(v_{j}\cdot v_{j}) + \sum_{i\neq j}c_{i}(v_{i}\cdot v_{j}) = 0 $$ 带入得到 $$ \sum_{i\neq j}c_{i}=0 $$ 由于对于每个 $ j $ 这个条件都要成立，从而 $ c_{j}=\sum_{i\in[m]}c_{i} $，这意味着所有的 $ c_{i} $ 都相等，因此要么全为 $ 0 $，要么全为 $ 1 $。若全为 $ 0 $，则线性无关；若全为 $ 1 $，显然与 $ \sum_{i\neq j}c_{i}=0 $ 矛盾。 ...

Problem 1 (1) 根据泊松分布的定义，我们有 $$ \mathbb{P}[X=\lambda+k] = \dfrac{e^{ -\lambda }\lambda^{\lambda+k}}{(\lambda+k)!},\quad \mathbb{P}[X=\lambda-k-1] = \dfrac{e^{ -\lambda }\lambda^{\lambda-k-1}}{(\lambda-k-1)!} $$ 我们计算两者的比值，有 $$ \dfrac{\mathbb{P}[X=\lambda+k]}{\mathbb{P}[X=\lambda-k-1]} = \dfrac{\lambda^{2k+1}\cdot(\lambda-k-1)!}{(\lambda+k)!} = \dfrac{\lambda^{2k+1}}{(\lambda+k)(\lambda+k-1)\dots(\lambda-k)} $$ 将分母的乘积左右两两配对，得到 $$ (\lambda+k)\dots(\lambda-k) = \lambda \cdot \prod_{i=1}^{k} (\lambda^{2}-k^{2}) > \lambda \cdot \prod_{i=1}^{k} \lambda^{2} = \lambda^{2k+1} $$ 从而就有 $$ \dfrac{\mathbb{P}[X=\lambda+1]}{\mathbb{P}[X=\lambda-k-1]} \geq 1 \implies \mathbb{P}[X=\lambda+1]\geq \mathbb{P}[X=\lambda-k-1] $$ 接着证明 $ \mathbb{P}[X\geq\lambda]\geq \frac{1}{2} $，将事件展开并拆分可以得到 $$ \begin{align*} \mathbb{P}[X\geq \lambda] & =\sum_{k=0}^{\infty} \mathbb{P}[X=\lambda+k] \\ & = \sum_{k=0}^{\lambda-1} \mathbb{P}[X=\lambda+k] + \mathbb{P}[X\geq 2\lambda] \\ & \geq \sum_{k=0}^{\lambda-1} \mathbb{P}[X=\lambda+k] \end{align*} $$ 我们再考虑 $ \mathbb{P}[X< \lambda] $，也就是 $$ \begin{align*} \mathbb{P}[X< \lambda] & = \sum_{k=0}^{\lambda-1} \mathbb{P}[X=\lambda-k-1] \\ & \leq \sum_{k=0}^{\lambda-1} \mathbb{P}[X=\lambda+k] \end{align*} $$ 又因为 $ \mathbb{P}[X\geq\lambda]+\mathbb{P}[X< \lambda]=1 $，这样就得到了 $$ 1-\mathbb{P}[X\geq \lambda] \leq \mathbb{P}[X\geq \lambda] \implies \mathbb{P}[X\geq \lambda] = \dfrac{1}{2} $$ (2) ...

Problem 1 给定平面上 $ 2n $ 个点，任意将 $ n $ 个点染成红色，剩下 $ n $ 个点染成蓝色。证明存在一种红蓝点的 $ 1 $-$ 1 $ 配对，使得连接它们的 $ n $ 条线段相互不相交。 证 定义红点集 $ R=\{ r_{1},r_{2},\dots,r_{n} \} $，蓝点集 $ B=\{ b_{1},b_{2},\dots,b_{n} \} $。$ R\to B $ 的映射，对应一种配对方案，总数为 $ n! $。 对于任意一种配对方案 $ \sigma $，我们定义它的总长度 $ L(\sigma) $ 为该方案中所有线段的长度之和 $$ L(\sigma) = \sum_{(r,b)\in\sigma}\text{dist}(r,b) $$ 由于总方案数有限，因此一定存在一种方案 $ \sigma_{m} $ 使得总长度 $ L(\sigma_{m}) $ 最小。我们下面证明这个最小方案中没有相交的线段。 假设在 $ \sigma_{m} $ 中存在两条线段相交，设为 $ (r_{1},b_{1}) $ 和 $ (r_{2},b_{2}) $，相交于点 $ P $。那么我们考虑交换配对变为 $ (r_{1},b_{2}) $ 和 $ (r_{2},b_{1}) $。根据三角不等式，有 $ \left| r_{1}b_{2} \right|<\left| r_{1}X \right|+\left| Xb_{2} \right|,\left| r_{2}b_{1} \right|<\left| r_{2}X \right|+\left| Xb_{1} \right| $，从而 $$ \left| r_{1}b_{2} \right| +\left| r_{2}b_{1} \right| < \left| r_{1}X \right| +\left| Xb_{1} \right| +\left| r_{2}X \right| +\left| Xb_{2} \right| = \left| r_{1}b_{1} \right| +\left| r_{2}b_{2} \right| $$ 发现交换后得到了一个总长度更小的方案，从而与总长度最小矛盾。这样我们就证明了总长度最小的配对方案所有线段必然不相交，证毕。 ...

Problem 1 (1) 根据题设条件，我们知道最多抽取 $ m $ 个黑球，最少抽取 $ 0 $ 个黑球。设随机变量 $ X $ 表示抽到黑球的个数，根据组合意义，我们得到 $ X $ 的概率质量函数为 $$ \mathbb{P}(X=x) = \dfrac{\binom{ m }{ x } \binom{ n-m }{ k-x } }{\binom{ n }{ k } },\quad x = 0,1,\dots,m $$ (2) 矩生成函数定义为 $ M_{X}(\theta) = \mathbb{E}[e^{ \theta X }] $。我们带入得到 $$ \begin{align*} M_{X}(\theta) & = \sum_{x}e^{ \theta x }\mathbb{P}(X=x) \\ & = \sum_{x=0}^{m} e^{ \theta x } \dfrac{\binom{ m }{ x } \binom{ n-m }{ k-x } }{\binom{ n }{ k } } \\ & = \dfrac{1}{\binom{ n }{ k } }\sum_{x=0}^{m} e^{ \theta x }\binom{ m }{ x } \binom{ n-m }{ k-x } \end{align*} $$ (3) ...

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*} $$ ...