~~（不全，会一种就更一种...）~~

$1、Cayley-Hamilton$ 定理

**$Cayley-Hamilton$ 定理： **

设 $A$ 是环 $R$ 上的 $n \times n$ 矩阵，记 $f(\lambda) = \det(\lambda I - A)$ 为其特征多项式，则 $f(A) = O$ .

证 $1.$

考虑一个 $\lambda$ 矩阵 $M(\lambda)$ ，即其每个元素都为一个系数在 $R$ 中的多项式，以 $\lambda$ 为变元. 将 $\lambda$ 的各次项分开，可以写作

$M(\lambda) = M_k \lambda^k + M_{n-1} \lambda^{n-1} + \dots + M_1 \lambda + M_0$

注意到 $\lambda$ 矩阵虽然像多项式，但是其乘法也是不交换的.

对于 $\lambda$ 矩阵 $M$ 与数量矩阵 $A$ （都是 $n \times n$ 的），可以考虑左代入

$M_L(A) = A^k M_k + A^{k-1} M_{k-1} + \dots + A M_1 + M_0$

此时我们有定理：

定理 $1.1.$

对任意 $\lambda$ 矩阵 $M(\lambda)$ 与任意数量矩阵 $A$（即元素在 $R$ 中的矩阵，区别于 $\lambda$ 矩阵），存在唯一的 $\lambda$ 矩阵 $Q(\lambda)$ 与数量矩阵 $R$ 使得

$M(\lambda) = (\lambda I - A)Q(\lambda) + R$

并且 $R = M_L(A)$ .

证明：存在性：直接对 $M(\lambda)$ 中 $\lambda$ 的次数归纳即可.

唯一性即相当于说若 $(\lambda I - A)U(\lambda)$ 是数量矩阵，则 $U(\lambda) = 0$ .

若 $U(\lambda) \neq 0$ ，则其最高次项也会变成 $(\lambda I - A)U(\lambda)$ 的最高次项，矛盾.

我们知道对于一个矩阵 $Q$ ，其伴随矩阵 $Q^* $ 满足 $QQ^* =Q^* Q = \det(Q)I$.

这个证明中所有过程都可以将 $R$ 更换成 $R[\lambda]$ ，于是其对 $\lambda$ 矩阵也成立.

于是若记 $P(\lambda) = \lambda I - A$ ，则我们有 $f(\lambda)I = P(\lambda)P(\lambda)^*$

也就是说

$f(\lambda)I = (\lambda I-A)P(\lambda)^*$

根据定理 $1.1.$ （注意唯一性），即知 $O = f(A)I = f(A)$ .

证 $2$

这个部分只对 $\mathbb C$ 上的矩阵证明.

对每个 $A$ ，我们要证明 $f(A) = O$ . 记 $Q_A = f(A)$ .

分三步：

第一步，若 $A$ 是对角矩阵，则 $f(A) = O$ . 这是显然的，因为若 $A$ 的对角元是 $\lambda_1, \dots, \lambda_n$ ，则 $f(\lambda) = (\lambda - \lambda_1) \dots (\lambda - \lambda_n)$ .

第二步，若 $A$ 可对角化，即存在 $P$ 使得 $PAP^{-1}$ 是对角阵，则 $f(A) = O$ . 若 $PAP^{-1} = \Lambda$ ，则 $A$ 和 $\Lambda$ 特征多项式相同；从而 $f(A) = Pf(\Lambda)P^{-1} = O$ .

第三步， $A$ 是任意矩阵. 此时我们取一族 $\{ A_k \}_{k \geq 1}$ ，使得它们都可对角化，且 $\lim_{k \to \infty} A_k = A$ . 若这样一族矩阵存在，则由于 $Q_A$ 可以看作依赖于 $A$ 的 $n \times n$ 个 $n \times n$ 元多项式，从而其关于 $A$ 是连续的. 于是由于每个 $Q_{A_k}$ 都为 $O$ ，所以 $Q_A$ 也为 $O$ .

那么为什么这样一族矩阵存在？这也就是要证明，可对角化矩阵在所有 $n \times n$ 的 $\mathbb C$ 矩阵中稠密.

我们有如下定理

定理 $2.1.$

若矩阵 $A$ 有 $n$ 个互不相同的特征值，则 $A$ 可对角化.

证明：每个特征值分别取一组特征向量组成基，则 $A$ 在这组基下的矩阵就是对角矩阵. $\square$

定理 $2.2.$

若 $P(x_1, \dots, x_k)$ 是 $\mathbb C$ 上的 $k$ 元非零多项式，则集合 $S = \{ \mathbb{v} \in \mathbb C^k \colon P(\mathbb{v}) \neq 0\}$ 稠密.

证明: 逆否命题就是说，若这东西不稠密，那么 $P$ 肯定是零多项式. 如果这个集合不稠密，也就是说有一个小球和它不相交（你如果不太理解这句话，那就是说，有一个点 $\mathbb{v}$ ，使得这个点周围一个小球里面都没有 $S$ 里的点）；换句话说就是 $P$ 在这个小球里面恒为 $0$ . 那么它在这里面每一阶偏导数都是 $0$ ，从而它就是 $0$ . 如果你不喜欢偏导数的话也可以选一堆点不断差分.

定理 $2.3.$

可对角化的 $n \times n$ 矩阵在 $\mathbb{C}^{n \times n}$ 中稠密.

证明：根据定理 $2.1.$ ，若特征值互不相同的矩阵稠密，那么可对角化的矩阵更多，肯定也稠密.

对于一个矩阵 $A$ ，先求出特征多项式 $f_A(\lambda)$ ，然后再求出 $f_A(\lambda)$ 的判别式 $\Delta_A$ （如果你不知道什么是判别式，那么它大约性质就是 $f_A$ 和 $f_A'$ 的多项式 $\gcd$ 一样的东西）.

根据特征多项式和判别式的定义，它们都是用 $A$ 里面的元素加减乘（没有除）搞出来的；

于是 $\Delta_A$ 肯定是一个巨长的式子，它是关于 $A$ 的 $n \times n$ 个元素的多项式.

比如如果 $A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}$ ，那么 $f_A(\lambda) = (\lambda - a)(\lambda - d) - bc$

计算可知判别式是 $(a-d)^2+4bc$ ，是一个关于 $a,b,c,d$ 的四元多项式.

若 $\Delta_A \neq 0$ ，那么 $f_A(\lambda)$ 没有重根，从而 $A$ 特征值互不相同，从而 $A$ 可对角化. 根据定理 $2.2.$ ，满足 $\Delta_A \neq 0$ 的矩阵 $A \in \mathbb{C}^{n \times n}$ 是稠密的，于是可对角化矩阵也是稠密的.

综上，我们就说明了 $\mathbb{C}$ 上所有矩阵都可以对角化.

日期：$2023.9.15$
时间：$9:33$

$2、Konig$ 定理

$Konig$ 定理:在二分图中，最大匹配数等于最小点覆盖的点数。

说明

最小点覆盖，即选出一部分点使得每条边的两端点都至少被选出一个。求至少选出多少点。

构造证明

显然最大匹配数不超过最小点覆盖的点数（因为每一对匹配点都至少要选择一个）。

记 $L, R$ 分别为左边的点集和右边的点集。

如果已知一个最大匹配，令 $U$ 表示左边所有未匹配点， $Z$ 表示从 $U$ 出发走增广路（就是非匹配边和匹配边交替的路径）能到达的所有点。

令 $S = (L \setminus Z) \cup (R \cap Z)$ ，即左边不能到达的点和右边能到达的点。

注意到从左边出发的增广路，相当于把非匹配边从左往右定向而匹配边从右往左定向形成的路径。于是对每条边 $(u,v)$

如果它是非匹配边，那么 $u \in Z \implies v \in Z$ （因为 $u$ 可以到达 $v$ ）；

如果它是匹配边，那么 $u \in Z \iff v \in Z$ （因为 $v$ 可以到达 $u$ ；并且只有 $v$ 可以到 $u$ ，因为 $u$ 只能连一个匹配边）。

可以发现无论 $(u,v)$ 是不是匹配边，都不存在 $u \in Z, v \notin Z$ 的情况。所以这样选出来的 $S$ 是一个点覆盖。

接下来还需要说明 $|S| = M$ 。

由于我们从所有左边的未匹配点开始走，所以左边不能到达的点一定是匹配点。由于从左往右走不可能走到非匹配点（否则说明有一条两端都是非匹配点的增广路，这样就可以增广否则就有一条两端都是非匹配点的从左到右的增广路，与最大匹配矛盾)。所以右边能到达的点一定是匹配点。

综上， $S$ 中所有点都是匹配点。但是由上面的 $2.$ 可知，每条匹配边都恰好有一个点在 $S$ 中。从而 $|S| = M$ 。

利用最小割最大流定理的证明

首先我们知道，二分图最大匹配可以转换成最大流问题。

转化为：建立源点 $U$ 和汇点 $V$ ，从 $U$ 到左边的点分别连一条流量为 $1$ 的边；从右边的点到 $V$ 分别连一条流量为 $1$ 的边。中间的边我们设其流量为 $+\infty$ 。

然后我们知道，最大流问题和最小割问题对偶，它们的答案相同。

令最小割中 $U$ 所处的连通分量点集为 $Z$ ， $V$ 所处的连通分量点集为 $Y$ 。

由于我们割不掉 $+\infty$ 的边，于是没有长成 $(L \cap Z) \to (R \cap Y)$ 的边。这个最小割的容量即为 $|L \cap Y| + |R \cap Z|$ 。

我们直接令 $S = (L \cap Y) \cup (R \cap Z)$ 。由于没有 $(L \cap Z) \to (R \cap Y)$ 的边，所以所有边都至少有一个端点在 $S$ 中。由于最小割最大流定理， $|S| = |L \cap Y| + |R \cap Z| =$ 最小割 $=$ 最大流 $=M$ 。所以 $S$ 是最小点覆盖。

最大独立集，最小边覆盖

最大独立集即为最小点覆盖的补集（显然，对于任意图都成立）。

二分图中最小边覆盖（如果存在，即没有度为 $0$ 的点） = 总点数减去匹配数。

事实上这对任意图都成立：每条边都最多覆盖掉两个点；而那些覆盖掉两个点的边（一个点被重复覆盖不算）构成一个匹配。所以要最小化边覆盖，就等价于最大匹配。

构造办法即为选取所有匹配边，然后每个未匹配点随便选一条边。

日期：$2023.9.15$
时间：$11:09$

$3、Hall$ 定理，正则二分图的完美匹配

$Hall$ 定理

给定一个二分图，我们记 $L, R$ 分别为其两边的点。对于 $S \subseteq L$ ，我们令 $N(S)$ 表示直接连到 $S$ 的所有右边的点。

如果对任意 $S \subseteq L$ ，都有 $|N(S)| \geq S$ ，那么最大匹配数为 $|L|$ （即左边的每个点都能被匹配上）。特别的，如果 $|L| = |R|$ ，则此时存在完美匹配。

注意到这个条件显然是充要条件，因为存在完美匹配时对每个 $S \subseteq L$ ，只是与 $S$ 匹配的点就也有 $|S|$ 个；与 $S$ 直接相连的点肯定更多。

证明概要：对点数归纳。如果存在一个子集 $T \subseteq L$ 使得 $|N(T)| = |T|$ ，那么不难证明整张图去掉 $T$ 和 $N(T)$ 中的点之后仍然满足 $Hall$ 条件。（并且显然 $T$ 和 $N(T)$ 中的点单独拿出来满足 $Hall$ 条件）。所以这样就拆成了两个点数更小的问题。

如果不存在这样的 $T$ ，那么我们随便从二分图里面删边，直到它存在为止。可以证明在此之前不会破坏 $Hall$ 条件。

正则二分图

如果一个二分图中每个点的度数都是 $k$ ，那么称作一个 $k-$ 正则二分图。

显然一个正则二分图左右两边点数相同（因为边数 $= k|L| = k|R|$ ）。下面以 $N$ 指代 $|L|$ （或 $|R|$ ）。

如果 $S \subseteq L$ ，那么连到 $S$ 的边有 $k|S|$ 条，连到 $N(S)$ 的边有 $k|N(S)|$ 条。由于前者是后者的子集，我们就有 $|S| \leq |N(S)|$ 。

所以正则二分图满足 $Hall$ 定理的条件，其必定存在完美匹配。

$k=2^d$时的完美匹配

如果给定一个 $2^d-$ 正则二分图，如何找出其一个完美匹配？

这个算法很容易：直接找出一条欧拉回路，这样就给所有边定了向；且每个点出度入度相同。删掉某一个方向的所有边，然后忽略掉定向，就变成了 $2^{d-1}-$ 正则二分图。递归直到 $d=0$ 即可。

复杂度为 $2^dN+2^{d-1}N+\dots+N = O(2^dN)$ ，也就是 $O($ 边数 $)$ ，不能再快了。

$k$ 任意时的完美匹配

这是一个随机算法，随机在运行时间上。

算法如下：

$\bullet$ 重复 $N$ 次：

$\bullet$ 随机选一个左边的未匹配点，然后沿增广路随机游走（即从左往右随机走未匹配边，从右往左走匹配边），直到走到一个右边的未匹配点。

$\bullet$ 把走出来的环去掉（找到最后一个出现过多次的点，然后把第一次走到它到最后一次走到它中间的这段路砍掉）。这样就找到了一条增广路。对它进行增广以把匹配数增加 $1$ 。

它确实非常蠢。但是可以证明：当还剩下 $2T$ 个未匹配点（即重复过 $N-T$ 次）时，随机游走的步数期望是

\[2\frac{(N-T)(k-1)}{kT}+1 \]

这个东西直接放缩成 $\frac{2N}{T}$ ，所以期望复杂度是

\[O\left(\sum_{T=1}^N \frac{2N}{T}\right) = O(N\log N) \]

非常神奇。

上述算法的证明

我们要证明的是：如果有一个 $k-$ 正则二分图，两边分别有 $N$ 个点，任意给定一个大小为 $M-T$ 的匹配，在其基础上随机增广，则期望步数为

\[2\frac{(N-T)(k-1)}{kT}+1 \]

或者说，期望需要从右往左走 $\frac{(N-T)(k-1)}{kT}$ 次。

令 $b(v)$ 表示从 $v$ 开始随机增广，期望需要从右往左走多少次。

记：$L_m,R_m$ 表示左右两边的已匹配点；$L_u,R_u$ 表示左右两边的未匹配点。如果 $v \in L_m$ 或 $v \in R_m$ ，记 $M(v)$ 为当前其匹配的点。

那么直接计算期望。对于 $y \in R$ ，有（从右往左只能走匹配边）

\[b(y) = \begin{cases} 0 & y \in R_u \\ 1 + b(M(y)) & y \in R_m \end{cases} \]

对于 $x \in L_u$ ，有

\[\begin{aligned} b(x) &= \frac{1}{k} \sum_{y \in N(x)} b(y) \\ \implies kb(x) &= \sum_{y \in N(x)} b(y) \end{aligned} \]

对于 $x \in L_m$ ，有 $（$ 注意到 $b(M(x)) = 1 + b(x)$ $）$

\[\begin{aligned} b(x) &= \frac{1}{k-1} \left(\sum_{y \in N(x)} b(y) -b(M(x))\right)\\ \implies (k-1)b(x) + b(M(x)) &= \sum_{y \in N(x)} b(y) \\ \implies kb(x) &= \sum_{y \in N(x)} b(y) - 1 \end{aligned} \]

把上面两个合起来，注意到这是一张 $k$ 正则二分图，所以上面两个式子对 $x$ 求和之后每个 $y$ 也恰好出现了 $k$ 次。于是

\[\begin{aligned} k\sum_{x \in L} b(x) &= k\sum_{y \in R} b(y) - M \\ k\sum_{x \in L} b(x) &= k\sum_{y \in R_m} (b(M(y))+1) - M \\ k\sum_{x \in L_m} b(x) + k\sum_{x \in L_u} b(x) &= k\sum_{x \in L_m} b(x) + kM - M \\ k\sum_{x \in L_u} b(x) &= (k-1)M \end{aligned} \]

由于我们最开始的时候是从 $L_u$ 中随机选一个点 $X$ 开始增广，所以期望往左走的次数即为

\[\frac{1}{T}\sum_{x \in L_u} b(x) = \frac{(k-1)M}{kT} = \frac{(k-1)(N-T)}{kT} \]

证毕。

日期：$2023.9.15$
时间：$16:03$

$4、$ 二次剩余

下文中， $p$ 将代指任意奇素数。

$\mathbb{F}_ p$ 指模 $p$ 意义下的域（即 $0,1,\dots,p-1$ 在模 $p$ 意义下以加法、乘法构成的代数结构）。

若不特殊说明，则 $a = b$ 表示 $a$ 和 $b$ 在 $\mathbb{F}_ p$ 中相等。即 $a \equiv b \pmod{p}$ 。

定义：二次剩余

称 $a$ 是 $\bmod $ 意义下的二次剩余，如果存在 $b \in \mathbb{F}_ p$ 使得 $b^2 = a$。

一些性质

$\bullet$ 在 $1, \dots, p-1$ 中恰有一半，即 $\frac{p - 1}{2}$ 个二次剩余。

设 $g$ 是 $\mathbb{F}_ p$ 的原根，则二次剩余恰为

\[1,g^2,g^4,\dots,g^{p-3} \]

另一个证明：如果 $x^2 \equiv y^2$ ，那么 $p|(x+y)(x-y)$ ，所以 $x \equiv \pm y$ . 于是二次剩余恰为 $1^2,2^2,\dots,\left(\frac{p-1}{2}\right)^2$ ，并且这些两两不同。

$\bullet$ $xy$ 是二次剩余当且仅当 $x$ 和 $y$ 都是或者都不是二次剩余。

考虑 $x=g^u,y=g^v$ ，那么相当于说 $u+v$ 是偶数当且仅当 $u,v$ 都是偶数或者都是奇数。

$\bullet$ 令 $\left(\frac{a}{p}\right)$ （ $Legendre symbol$ ）为：

\[\left(\frac{a}{p}\right)=\begin{cases} 0 & a \equiv 0 \\ 1 & a \text{ 是二次剩余 } \\ -1 & a \text{ 不是二次剩余 } \end{cases} \]

则 $\left(\frac{a}{p}\right) \equiv a^{(p-1) / 2}$ 。

如果 $a = g^u$ ，那么 $a^{(p-1) / 2} = g^{u(p-1) / 2}$ ，而这个数等于 $\pm1$ ； $u$ 为奇数，即 $a$ 不是二次剩余的时候， $a^{(p-1)/2} = -1$ ；否则 $a^{(p-1)/2} = 1$ 。

这样我们还可以得出：

\[\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)=\left(\frac{ab}{p}\right) \]

$\bullet$ 二次互反律：若 $q$ 是另一个奇素数，那么

\[\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{(p-1)(q-1)/4} \]

另外，

\[\left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}\quad \left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8} \]

在 $OI$ 中很少用到，证明比较麻烦，此处略去。

$Cipolla$ 算法

给定 $n$ ，我们已经知道如何判断它是否是二次剩余（利用上面的性质 $3$ ，只需要做一次快速幂）。现在问题是：如果已知 $n$ 是二次剩余，如何快速求出一个 $x$ 使得 $x^2 \equiv n \pmod{p}$ ？

首先我们找到一个 $a \in \mathbb{Z}_ p$ 使得 $a^2 - n$ 不是二次剩余。

这一步没有什么高效的办法，可以随机 $a$ 。可以证明满足条件的 $a$ 也有 $\frac{p-1}{2}$ 个（见下），所以期望随机 $\frac{2p}{p-1} \approx 2$ 次就可以找到一个满足条件的 $a$ 。

不妨设 $n \equiv b^2$ 。那么 $a^2-b^2=(a+b)(a-b)$ 不是二次剩余当且仅当 $\frac{a+b}{a-b}$ 不是二次剩余。

可以发现 $a$ 在除 $b$ 以外的数（ $[0,p)$ 以内）之间遍历一遍的时候 $\frac{a+b}{a-b}$ 在 $1$ 以外的数遍历了一遍。从而恰有 $\frac{p-1}{2}$ 个 $a$ 使得 $a^2-b^2$ 不是二次剩余。

接下来考虑扩域 $\mathbb{F}_ p[\sqrt{a^2-n}]$ 。（如果 $a^2-n$ 是二次剩余，那这个域就不存在，或者说就等于 $\mathbb{F}_ p$ 本身；强行搞出形式的和也会导致得到的结构不是域，从而一些条件不成立）。

也就是所有形如 $u + v\sqrt{a^2-n}$ 的数，其中 $u,v\in\mathbb{F}_ p$ 。我们记 $\alpha = \sqrt{a^2-n}$ ，那么域中的数即为 $u+v\alpha$ 。

在这个扩域中，我们有一些性质：

$\bullet$ $(x+y)^p = x^p + y^p$ 。（这个性质在任何特征 $p$ 域，即每个元素的 $p$ 倍都是 $0$ 的域中都存在）。这是因为 $(x+y)^p = \sum_{k = 0}^p \binom{p}{k} x^k y^{p-k}$ ，而当 $0 < k < p$ 的时候 $\binom{p}{k}$ 被 $p$ 整除。

$\bullet$ $\alpha^p = -\alpha$ 。因为 $\alpha^p = (a^2-n)^{(p - 1)/2} \alpha = -\alpha$ 。

$\bullet$ 如果 $x \in \mathbb{F}_ p$ ，那么仍然有 $x^p = x$ 。因为 $\mathbb{F}_ p$ 里有 $x^p = x$ ，并且嵌入到新的域里面之后乘法法则没有变。

现在令

\[x = (a + \alpha)^{(p + 1) / 2} \]

那么

\[\begin{aligned} x^2 &= (a + \alpha)^{p + 1} \\ &= (a + \alpha)^p (a + \alpha) \\ &= (a - \alpha) (a + \alpha) \\ &= a^2 - \alpha^2 = n \end{aligned} \]

于是我们在 $\mathbb{F}_ p[\sqrt{a^2 - n}]$ 中求得了 $x^2 = n$ 的一个解。还需要说明 $x$ 一定属于 $\mathbb{F}_ p$ 。

然而域里面的 $k$ 次方程至多有 $k$ 个解，所以 $x^2 = n$ 至多有两个解。由于 $n$ 是 $\mathbb{F}_ p$ 里的二次剩余，所以这两个解都在 $\mathbb{F}_ p$ 里。因此这样求得的 $x$ 必定在 $\mathbb{F}_ p$ 里。

（类比一下，如果 $a > 0 \in \mathbb{R}$ ， $x \in \mathbb{C}$ 使得 $x^2 = a$ ，那么一定有 $x \in \mathbb{R}$ ）。

在代码实现中，选好 $a$ 之后即可用一个数对 $(u,v)$ 表示 $u+v\alpha$ ，乘法规则即为 $(u_1,v_1)(u_2,v_2) = (u_1u_2 + (a^2-n)v_1v_2, u_1v_2 + u_2v_1)$。

代码实现

typedef long long LL;

int p, l;

struct F2 {
  int u, v;
  F2(int u = 0, int v = 0) : u(u), v(v) {}
  friend F2 operator*(const F2 &a, const F2 &b) {
    LL u = (LL)a.u * b.u + (LL)a.v * b.v % p * l;
    LL v = (LL)a.u * b.v + (LL)a.v * b.u;
   return F2(u % p, v % p);
  }
};

LL pow_mod(LL a, int b) {
    LL ans = 1;
  for (a %= p; b; b >>= 1, a = a * a % p)
    if (b & 1) ans = ans * a % p;
  return (ans + p) % p;
}

F2 pow_mod2(F2 a, int b) {
    F2 ans(1, 0);
  for (; b; b >>= 1, a = a * a)
    if (b & 1) ans = ans * a;
  return ans;
}

LL Cipolla(LL n) {
  LL a = 0;
  while (pow_mod(a * a - n, (p - 1) / 2) != p - 1)
    a = rand() % p;
  l = (a * a - n) % p;
  if (!l) return a;
  return (pow_mod2(F2(a, 1), (p + 1) / 2).u + p) % p;
}

日期： $2023.9.15$
时间： $23:11$