Exercise 1 (1) 利用内积的双线性性质，对于任意 $ u \in V $，有 $ \langle u, 0 \rangle = \langle u, 0 + 0 \rangle = \langle u, 0 \rangle + \langle u, 0 \rangle $，即可得到 $ \langle u, 0 \rangle = 0 $。 (2) 若对于所有 $ u \in V $ 都有 $ \langle u, v \rangle = 0 $，那么我们可以取特例 $ u = v $，此时有 $ \langle v, v \rangle = 0 $。根据内积的正定性公理，$ \langle v, v \rangle = 0 $ 当且仅当 $ v = 0 $。 ...
Problem 1 对于随机图 $ \mathcal{G}(n, p) $，属性“没有孤立点”具有一个锐阈值函数 $ p = \ln n / n $。 证 令 $ p=c\cdot \frac{\ln n}{n} $。设 $ X $ 为图中孤立点的数量。 $$ X = \sum_{i=1}^n I_i $$ 其中 $ I_i $ 是指示变量：若顶点 $ i $ 孤立，则 $ I_i=1 $，否则 $ I_i=0 $。我们需要计算 $ I_i $ 的期望 $$ \mathbf{E}[I_{i}] = (1-p)^{n-1} $$ 我们首先证明当 $ c>1 $ 时 $ \mathbb{P}(X > 0) \to 0 $。根据 Markov 不等式，有 $$ \mathbb{P}(X>0) = \mathbb{P}(X\geq 1) \leq \mathbf{E}[X] = \sum_{i=1}^{n} \mathbf{E}[I_{i}] = n(1-p)^{n-1} $$ 使用不等式 $ 1-x \le e^{-x} $ 近似 $$ \mathbf{E}[X] \le n e^{-p(n-1)} \approx n e^{-pn} = n e^{-c \ln n} = n \cdot n^{-c} = n^{1-c} $$ 因为 $ c > 1 $，所以 $ 1-c < 0 $。当 $ n \to \infty $ 时，$ n^{1-c} \to 0 $。 ...
Exercise 1 不唯一。考虑有奇异值相等的情况，那么最优子空间不唯一。假设 $ \sigma_{k}=\sigma_{k+1} $，那么在由 $ v_{k} $ 和 $ v_{k+1} $ 张成的平面内进行任意旋转后得到的向量组也满足条件。 Exercise 2 根据给定的分解，$ A $ 有唯一的非零奇异值 $ \sigma_1=5 $，对应的 $ u_1 = \begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix} $，$ v_1 = [1] $。 首先计算伪逆 $ A^+ = \frac{1}{\sigma_1} v_1 u_1^T = \frac{1}{5} [1] \begin{bmatrix} 0.6 & 0.8 \end{bmatrix} = \begin{bmatrix} 0.12 & 0.16 \end{bmatrix} $。 接着计算 $ A^+ A = \begin{bmatrix} 0.12 & 0.16 \end{bmatrix} \begin{bmatrix} 3 \\ 4 \end{bmatrix} = 0.36 + 0.64 = 1 $（即 $ I_1 $）。 ...
Exercise 1 注意到 $$ \begin{aligned} \left\| \sum_{i=1}^k c_i w_i \right\|^2 &= \left\langle \sum_{i=1}^k c_i w_i, \sum_{j=1}^k c_j w_j \right\rangle \\ &= \sum_{i=1}^k \sum_{j=1}^k c_i c_j \langle w_i, w_j \rangle \end{aligned} $$ 根据题设，我们知道当 $ i \neq j $ 时 $ \langle w_i, w_j \rangle = 0 $，当 $ i = j $ 时 $ \langle w_i, w_j \rangle = 1 $。因此，上述双重求和中仅保留 $ i=j $ 的项 $$ \sum_{i=1}^k c_i^2 \cdot 1 = \sum_{i=1}^k c_i^2 $$ 得证。 ...
Exercise 1 不唯一。只有奇异值 $ \Sigma $ 是唯一的，而 $ U,V $ 通常不唯一。首先我们改变 $ U,V $ 中对应列的符号不会产生影响；其次相同的奇异值对应的奇异向量可以在保持正交的情况下任意变换，也不会对 SVD 分解产生影响；并且如果存在零奇异值，也可以任意选择。 Exercise 2 我们需要证明对于所有 $ k\in \{ r+1,\dots, m\} $ 满足 $ AA^{T}u_{k}=\mathbf{0} $。 首先根据正交矩阵，因此对于任意 $ j\in [r] $ 和 $ k\in \{ r+1,\dots,m \} $，有 $ u_{j}^{T}u_{k}=0 $。我们考虑 $ A $ 的列空间，显然 $ \{ u_{j} \}_{j=1}^{r} $ 是 $ AA^{T} $ 的非零特征值对应的特征向量，构成了 $ \text{Col}(A) $ 的一组正交基，从而 $ \{ u_{k} \}_{k=r+1}^{m} $ 属于 $ \text{Col}(A) $ 的正交补空间，也就属于 $ A^{T} $ 的零空间，因此 $$ A^{T}u_{k} = \mathbf{0},\quad k=r+1,\dots,m $$ 带入就有 $ AA^{T}u_{k}=\mathbf{0} $，证毕。 ...
Problem 1 图 $ G=(V,E) $ 有 $ n $ 个顶点和 $ m $ 条边，图 $ H $ 是较小的图，且 $ G $ 不包含 $ H $ 作为子图。证明当 $ k > n^2 \ln n / m $ 时，完全图 $ K_n $ 存在一种边 $ k $-染色方案，使得 $ K_n $ 中不存在单色的 $ H $。 证 令 $ V $ 为 $ K_{n} $ 的顶点集。随机选取 $ k $ 个 $ V $ 上的随机排列，将 $ G $ 映射到 $ V $，得到与 $ G $ 同构的 $ k $ 个图 $ G_{1},\dots,G_{k} $。 ...
Exercise 2 根据定义，对于任意 $ \phi \in V' $，有 $$ T_{\text{incl}}'(\phi) = \phi \circ T_{\text{incl}} $$ 由于 $ T_{\text{incl}} $ 是包含映射，因此 $ T_{\text{incl}}' $ 实际上将 $ \phi $ 的定义域限制在了 $ U $ 上，也就是 $ T_{\text{incl}}'(\phi)=\phi|_{U} $，因此 $ \mathrm{Im}(T_{\text{incl}}') $ 由所有形式为 $ \phi|_{U} $ 的线性泛函组成，从而 $ \mathrm{Im}(T_{\text{incl}}')\subseteq U' $。 证明满射。即证对于任意 $ \psi \in U' $，都存在 $ \phi \in V' $ 使得 $ T_{\text{incl}}'(\phi)=\psi $。设 $ \{ u_{1},\dots,u_{m} \} $ 是 $ U $ 的一组基，将它扩充为 $ V $ 的一组基 $ \{ u_{1},\dots,u_{m},v_{m+1},\dots,v_{n} \} $。那么对于给定的 $ \psi \in U' $，在 $ V $ 的基上定义 $ \phi \in V' $ 满足 $$ \begin{cases} \phi(u_{i}) = \psi(u_{i}), \\ \phi(v_{j}) = 0 \end{cases} $$ 根据线性扩展定理，$ \phi $ 在 $ V $ 上唯一确定。从而对于任意 $ u \in U $，$ \phi(u) = \psi(u) $，即 $ \phi|_U = \psi $。因此就有 $ U'\subseteq \mathrm{Im}(T_{\text{incl}}') $。 ...
Problem 1 设 $ H = (V, \mathcal{F}) $ 是一个没有孤立点的超图，满足每条超边至少包含 3 个顶点，且任意两条超边恰好共享一个顶点。假设 $ H $ 不是 2-可着色的（即不能用两种颜色对顶点染色使得每条超边内都有不同颜色的点）。 (1) 证明每个顶点 $ v $ 至少属于 $ \mathcal{F} $ 中的两条超边。 证 假设存在一个顶点 $ v $ 满足 $ d(v)< 2 $。由于没有孤立顶点，因此 $ d(v)=1 $，恰好属于一条超边，记为 $ E $。 我们将顶点 $ v $ 染成红色，将 $ E $ 中的其他点染成蓝色，再将图中除了 $ E $ 之外的所有点染成红色。由于任意两条超边恰好共享一个顶点，并且 $ v $ 只在 $ E $ 中，所以任意一条超边必然和 $ E $ 存在蓝色交点，存在颜色不同的点。因此我们就构造出了一个合法的 2-着色方案，与题设矛盾。 因此每个顶点至少属于两条超边。证毕。 ...
Exercise 1 根据对偶变换的定义 $$ (T'(L))(v) = L(T(v)) $$ 带入 $ T(v)=v $，就有 $$ (T'(L))(v) = L(v) $$ 由于这对所有 $ v \in V $ 均成立，从而 $ T'(L) $ 和 $ L $ 是一个函数，因为输入输出完全相同，因此 $ T'(L)=L $，是恒等变换。 Exercise 2 先证充分性，如果 $ T=\mathbf{0} $，那么对于任意 $ v \in V $，都有 $ T(v)=\vec{0} $。根据定义 $$ (T'(L))(v) = L(T(v)) = 0 $$ 说明 $ T'(L) $ 是零泛函，从而 $ T'=\mathbf{0} $。 如果 $ T'=\mathbf{0} $，那么对于任意 $ L\in W' $，$ T'(L) $ 是 $ V $ 上的零泛函。带入定义就有 $$ L(T(v)) =(T'(L))(v) = 0 $$ 由于对所有的线性泛函均成立，那么可以证明 $ T(v)=\vec{0} $。否则将 $ T(v)=w $ 扩充为 $ W $ 的一组基，定义 $ L $ 只在 $ w $ 上为 $ 1 $，否则为 $ 0 $，这样就构造出了一个不符合的 $ L $，因此矛盾。从而 $ T(v)=\vec{0} $ 对所有 $ v $ 均成立，也就有 $ T=\mathbf{0} $。 ...
Problem 1 (1) 总共有 $ N=\binom{ n }{ 2 } $ 对点。设 $ X_{ij}=\mathbb{I}[(i,j)\in E_{n}] $。那么 $ \mathbf{E}[X_{ij}]=p $。并且 $$ \left| E_{n} \right| = \sum_{1\leq i< j\leq n} X_{i} $$ 由于边与边之间独立，因此 $ X_{i} $ 是独立同分布，并且可积，那么根据强大数定律，就有 $$ \dfrac{\sum X_{i}}{N} = \dfrac{\left| E_{n} \right| }{\binom{ n }{ 2 } } \xrightarrow{a.s.} \mathbf{E}[X_{i}]=p $$ (2) 设 $ \mathcal{C}_n $ 为 $ V_n $ 中所有大小为 $ 3 $ 的子集的集合，也就是所有无序三元组 $ \{i, j, k\} $。集合大小 $ |\mathcal{C}_n| = \binom{n}{3} $。 ...