526互联

zkq 数学听课笔记

发布时间 2023-12-29 21:41:08作者: jeefy

线性代数

  • 域 \(F\)，OI 中常用的域是 \(\Z_{p^c}\)。
  • \(n\) 维向量 \(\vec x \in F^n\)，其中 \(x_i \in F\)，注意向量是列向量。
    • \(F^n\) 向量/线性空间，满足线性性
      • 八个性质，\(u, v, w \in V\)，\(c, d \in F\)
        1. \(u + v = v + u\)
        2. \((u + v) + w = u + (v + w)\)
        3. 存在 \(0\) 元
        4. \(\exists (-u) \in F \quad u + (-u) = 0\)
        5. \(1u = u\)
        6. \(c(u + v) = cu + cv\)
        7. \((c + d)u = cu + du\)
        8. \(c(du) = (cd)u\)
  • 矩阵：\(M \in F^{n \times m}\)。
    • 线性变换：\(f: V \to V, f(u + v) = f(u) + f(v), f(cx) = cf(x)\)
    • 乘向量：\(F^m \to F^n\)。
    • 乘矩阵，线性变换的复合（可以这么理解，结果仍然是线性变换。
  • 有限集合下
    • 向量线性独立：\(\not \exists i ~ v_i = \sum_{j \ne i} \alpha_i v_j\)
    • 张成 \(\mathrm{span}(\{v_1, \ldots, v_n\}) = \{v | \alpha_1 v_1 + \ldots + \alpha_n v_n, \alpha_i \in F\}\)。
    • 线性空间的基 \(B\) 是一组线性独立，张成 \(V\) 的向量集
      • \(\dim (V) = \mathrm{card} (B)\)。
  • 无限集合下
    • 线性独立：所有有限子集线性独立
    • 张成：所有有限子集张成的并
  • 子空间 \(W \subseteq V\) 注意 \(W\) 也是线性空间
    • \(0 \in W\)，\(W \bigcap V = W\)。
  • 矩阵 —— 列空间
    • 秩 \(\mathrm{rank}\)：列空间的维度
    • 满秩矩阵：方阵，秩 = 行数
    • \(A\) 满秩 \(\iff （A x = 0 \iff x = 0)\)
    • \(\mathrm{rank}(A + B) \le \mathrm{rank}(A) + \mathrm{rank}(B)\)
    • 逆矩阵：\(A A^{-1} = A^{-1} A = I\)，不存在当且仅当不满秩。
      • CF1070L, CF963E
  • \(\det A = \sum_P (-1)^{inv(P)} \prod_{i = 1}^n a_{i, P_i}\).
    • \(\det I = 1\)
    • 基本变换：
      • 交换行：\(\det \leftarrow -\det\)
      • 行数乘：\(\det \leftarrow c \det\)
      • 行加上另一行：\(\det\) 不变。
    • 满秩 \(\iff \det \ne 0\)。
    • 矩阵树定理：
      • \(L = D - A, \det(L_{[0]}) = \sum_T \prod_{e \in T} w(e)\)。
      • P6624, CF578F
    • LGV 引理
      • 对于 DAG 和若干起点，终点，令 \(M_{i,j} = A_i\) 到 \(B_j\) 的方案数。
      • 那么 \(\det M\) 是不交路径的方案数。
      • P7736, gym102978A
  • 特征值/多项式
    • \(Ax = \lambda x \to \det (A - \lambda I) = 0\)，求特征值即求解上述方程。
    • 特征多项式：\(P_A = \det(A - \lambda I)\) 是关于 \(\lambda\) 的 \(n\) 次多项式
      • 矩阵的迹：对角线的和
      • \([\lambda^n]P_A = (-1)^n\)
      • \([\lambda^{n - 1}] P_A = (-1)^{n - 1} tr(A)\)
      • \([\lambda^0] P_A = \det A\)
    • 代数闭域：\(\forall f ~ \exists x (f(x) = 0)\)。
    • \(P_A = \prod \lambda_i - \lambda\)
      • \(\sum \lambda_i = tr(A)\)
      • \(\prod \lambda_i = \det (A)\)
    • 谱范数 \(A^T A\) 的最大特征值的平方根（\(A\) 的最大奇异值）
    • 谱分解（对角化）
      • \(AQ = Q\Lambda \to A = Q \Lambda Q^{-1} \to A^k = Q \Lambda^k Q^{-1}\)。
      • ……
  • 马尔克夫矩阵：
    • \(A 1 = 1, A\)，考虑随机游走的过程
    • \(A\) 有特征值 \(\lambda = 1\)。
    • ……
  • 计算几何
    • 平面凸包，闵和
    • 旋转卡壳
    • 半平面交
    • ……
  • 多项式技巧
    • NTT：有限域下的 FFT
    • 另一种卷积的方式