前言

这篇东西大部分都是在瞎bb，大佬们可以选择不看。大部分内容来自 \(\rm 3Blue1Brown\) 大佬的视频。

需要先学高斯消元。

基础向量

定义一个 \(n\) 维的向量 \(\vec v\) ，其长度用 \(|\vec v|\) 表示，一般来说，我们可以用一个 \(n\) 元组（可以理解为一个长度为 \(n\) 的序列）表示一个向量，表示方式如下：

\[\vec v = (x_{v,1}, x_{v,2}, \dots, x_{v, n}) \]

这时候，\(v\) 可以看成 \(n\) 维空间上从原点到点 \((x_{v,1}, x_{v,2}, \dots, x_{v, n})\) 的一条有向线段，也可以直接看成 \((x_{v,1}, x_{v,2}, \dots, x_{v, n})\) 这个点。特别的，原点对应了一个特殊的向量：零向量，写作 \(\vec 0\)。

同时，对于空间上的两个点 \(A,B\) , 从 \(A\) 到 \(B\) 的有向线段也可以表示向量，记为 \(\overrightarrow{AB}\) 。

一个向量的长度可以用下面式子表示：

\[|\vec v| = \sqrt{\sum_{i=1}^n x_{v,i} ^2} \]

两个向量 \(\vec a\), \(\vec b\) 共线，可以表示为 \(\vec a//\vec b\)

容易得到判定：

\[\forall i, j \in [1,n] \cap \mathbb{N}^+, \frac{x_{a,i}}{x_{b,i}}=\frac{x_{a,j}}{x_{b,j}} \Rightarrow \vec a//\vec b \]

因为忽略了 \(0\) 的情况，因此只是右箭头。

$<\vec a, \vec b> $ 可用于表示 \(\vec a, \vec b\) 的夹角。

向量基本运算和推论

PS：以下是高中课本内容

加法：\(\vec c = \vec a + \vec b \Longleftrightarrow \forall i \in [1, n] \cap \mathbb{N}^+, x_{c,i} = x_{a,i}+x_{b,i}\)

减法：\(\vec c = \vec a + \vec b \Longleftrightarrow \forall i \in [1, n] \cap \mathbb{N}^+, x_{c,i} = x_{a,i}-x_{b,i}\)

乘法：\(\vec c = k\vec a \Longleftrightarrow \forall i \in [1, n] \cap \mathbb{N}^+, x_{c,i} = kx_{a,i}\)，这个也被叫做向量的缩放。

有了上述两个运算，可以得到一些基本的推论：

\[\begin{aligned} \overrightarrow{AC} = \overrightarrow{AB} + \overrightarrow{BC}\\ \overrightarrow{AB} = \overrightarrow{OB} - \overrightarrow{OA} \end{aligned} \]

其中 \(O\) 为坐标原点。

点积：\(\vec a \cdot \vec b = \sum_{i=1}^n x_{a,i} x_{b,i}\)

当 \(n = 2\) 或 \(n = 3\) 的时候，有 \(\vec a \cdot \vec b = |\vec a||\vec b| \cos <\vec a, \vec b>\) ，这个因此这个东西可以用于判定两条直线是否垂直。

这个东西有些基本的运算律：

交换律：\(\vec a \cdot \vec b = \vec b \cdot \vec a\)

结合律：\((m\vec a) \cdot \vec b = m(\vec a \cdot \vec b) = \vec a \cdot (m\vec b)\)

交换律：\(\vec a \cdot (\vec b + \vec c) = \vec a \cdot \vec b + \vec a\cdot \vec c\)

一些定义

线性组合：给定 \(m\) 个向量：\(\overrightarrow{v_1}, \overrightarrow{v_2}, \dots, \overrightarrow{v_m}\) ，再给定一个向量 \(\vec a\) 。如果存在一个长度为 \(m\) 的有理数序列 \(A\) ，满足 下列式子：

\[\vec a = \sum_{i=1}^m A_i \overrightarrow{v_i} \]

则称 \(\vec a\) 是 \(\overrightarrow{v_1}, \overrightarrow{v_2}, \dots, \overrightarrow{v_m}\) 的一个线性组合。

容易想到，求解一组 \(A_{1\dots m}\) 可以使用高斯消元。

PS:本人不太清楚向量是否也能使用 \(\Sigma\) 符号，但是上述式子应该是可以理解的。

线性空间：一个线性空间可以看成一个向量集合 \(V\) ，集合中任意一个向量缩放后仍在 \(V\) 中，并且任意两个在 \(V\) 中的向量相加仍在 \(V\) 中，则称 \(V\) 是一个线性空间。形式化的，有：

\[\forall \vec a, \vec b \in V, x, y \in \mathbb{R}, x\vec a+y\vec b\in V \Longleftrightarrow V \text{ 是一个线性空间} \]

这个东西可以理解为我们熟知的：一个点，一条直线，一个平面，一个三位空间。

线性相关：给定 \(m\) 个向量 \(\overrightarrow{v_1}, \overrightarrow{v_2}, \dots, \overrightarrow{v_m}\)，如果存在一个不全为 \(0\) 的序列 \(k_{1 \dots m}\)，满足：

\[\sum_{i=1}^m k_i \overrightarrow{v_i} = 0 \]

则称这 \(m\) 个向量线性相关，可以发现，将上述式子变化一下，可以得到另一种看待方式：如果存在一个向量是其他向量的线性组合，则称这些向量线性相关。

线性无关：
如果 \(\sum_{i=1}^m k_i \overrightarrow{v_i} = 0\) 当且仅当 \(k\) 全为 \(0\) ，则称 \(\overrightarrow{v_1}, \overrightarrow{v_2}, \dots, \overrightarrow{v_m}\) 线性无关。也就是说，没有办法将其中一个向量表示为其余向量的线性组合。

向量组的秩：一个向量组（可以认为是一个有限大小的集合）中极大的线性无关的子集的大小被称为向量的秩。这里定义极大的线性无关的集合是指往其中添加任何一个其他向量都会让它变得线性有关。

线性基：一个线性空间 \(V\) ，如果存在一组线性无关的向量 \(\overrightarrow{v_1}, \overrightarrow{v_2}, \dots, \overrightarrow{v_m}\) ，满足 \(V\) 中所有的向量可以表示为这组向量的线性组合，那么称 \(\overrightarrow{v_1}, \overrightarrow{v_2}, \dots, \overrightarrow{v_m}\) 是 \(V\) 的一组(线性基/基)。容易发现线性基的大小和线性空间的维度有关，即线性基的大小等于线性空间的维度。比如在二位直角坐标系中，我们最常用的就是 \((0,1),(1,0)\) 这组最基本的基向量。

有了基向量，我们可以认为所有向量（假设为 \(v\)）都是由基向量缩放对应的系数得到的，而 \(x_{v,i}\) 就是第 \(i\) 个基向量的缩放系数。

线性变换：通俗点来讲，就是将空间绕原点旋转，然后均匀拉伸的操作，这个均匀拉伸类似于我们编辑图片时候的拉伸。一条直线在经过线性变化之后仍然为直线。可以理解为基向量发生了改变，引起其他向量改变。

线性基的求解可以看我的另一篇博客 \(\Rightarrow\)高斯消元入门

基础矩阵

一个大小为 \(N\times M\) 的矩阵可以用 \(A_{1\dots N, 1\dots M}\) 表示。其中第 \(i\) 行，第 \(j\) 列的元素用 \(A_{i,j}\) 表示。同时，还有一种表示矩阵的方法，就是将矩阵内容全部写出来：

\[\begin{bmatrix} A_{1,1} & A_{1,2} & \cdots & A_{1,M}\\ A_{2,1} & A_{2,2} & \cdots & A_{2,M}\\ \vdots & \vdots & \ddots & \vdots \\ A_{N,1} & A_{N,2} & \cdots & A_{N,M} \end{bmatrix} \]

和向量的联系

一般来说，我们可以将一个 \(N\) 维向量写成一列：

\[\vec v = (x_{v,1},x_{v,2}, \dots, x_{v,N}) = \begin{bmatrix} x_{v,1}\\ x_{v,2}\\ \vdots\\ x_{v,N} \end{bmatrix} \]

而矩阵，实际上就是将 \(M\) 个向量依次写下来。

还有另一种理解：线性变换。（这里只讨论 \(N\times N\) 矩阵）

将一个 \(N\) 维的线性基变化，描述其线性变化的信息就是一个 \(N\times N\) 的矩阵。其中第 \(i\) 列描述的是第 \(i\) 个基向量变化后的向量，这个向量基于变换前的线性基（回想一下之前提到的向量的描述方式，这里描述的是基于变化前线性基的缩放系数）。

基本运算

加法：只适用于两个大小完全相同的矩阵。

\[\begin{aligned} &C_{1...N, 1...M} = A_{1...N, 1...M}+B_{1...N, 1...M} \\ &\Longleftrightarrow \\ &\forall i\in [1,N]\cap \mathbb{N}^+ , j \in [1, M] \cap \mathbb{N}^+, C_{i,j} = A_{i,j} + B_{i,j} \end{aligned} \]

乘法：只有结合律。

\[\begin{aligned} & C_{1...N, 1...P} = A_{1...N, 1...M}B_{1...M,1...P}\\ & \Longleftrightarrow\\ & \forall i\in [1,N]\cap \mathbb{N}^+, j \in [1, M] \cap \mathbb{R}, C_{i,j} = \sum_{r = 1}^M A_{i,r}B_{r,j} \end{aligned} \]

这里bb一下大小为 \(N\times N\) 的矩阵的矩阵乘法的理解：一次矩阵乘法实际上可以看成一个先按 \(B\) 线性变化，然后按 \(A\) 线性变化。（从右往左）

幂运算：可以搞快速幂。

\[A^m = A^k A^{m - k} \]

一些特殊的矩阵

三角矩阵：\(A_{1\dots N, 1\dots N} \text{是三角矩阵} \Longleftrightarrow \forall i, j \in [1, N] \cap \mathbb{N}^+ \text{且} i<j, A_{i,j}=0\)

对角矩阵：\(A_{1\dots N, 1\dots N} \text{是三角矩阵} \Longleftrightarrow \forall i, j \in [1, N] \cap \mathbb{N}^+ \text{且} i \ne j, A_{i,j}=0\)

单位矩阵：\(A_{1\dots N, 1\dots N} \text{是元矩阵} \Longleftrightarrow \forall i, j \in [1, N] \cap \mathbb{N}^+, A_{i,j}=[i=j]\)，这样的矩阵可以用 \(I\) 表示。这个矩阵显然是 \(N\) 维空间最基本的基向量写在一起。

这里给一些关于 \(I\) 的显而易见的性质：

\[II = I, AI=A \]

这些定义都非常好理解，就不解释了。

逆矩阵

类似逆元，如果两个矩阵的乘积是一个元矩阵，那么我们称这两个矩阵互逆。形式化的，就是 \(AB=BA=I \Longleftrightarrow A,B \text{ 互为逆矩阵}\)，一个矩阵 \(A\) 的逆矩阵用 \(A^{-1}\) 表示。

\(\mathrm{PS}\)：注意到定义，因为乘积必须是一个元矩阵，因此 \(A\) 的行数和 \(B\) 的列数必须相同。为了少打点字，这里指讨论 \(A\) 的大小是 \(N\times N\) 的情况。

\(\Rightarrow\) 模版题

考虑将 \(A, I\) 左右拼接起来，\(A\) 在前，\(I\) 在后，得到一个大小为 \(N\times 2N\) 的新矩阵，然后将其高斯消元，将前半部分消成对角矩阵，接着每行做除法，将前半部分变成 \(I\)，那么后半部分就是 \(A^{-1}\) 了。

当消元的时候，存在一个 \(A_{i,i} = 0\) ，那么这时候就无解了。

这里直接给出代码：

LL t[maxn][maxn << 1];
int CalcInvMtrx(LL a[maxn][maxn], int N, LL res[maxn][maxn]) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) t[i][j] = a[i][j];
        t[i][i + N] = 1;
    }
    for (int i = 1; i <= N; i++) {
        int tp = i;
        for (int j = i + 1; j <= N; j++) if (a[j][i] > a[i][i]) {
            tp = j; break;
        }
        if (tp != i) swap(t[tp], t[i]);
        if (!t[i][i]) return -1; //无解
        LL inv_tii = qpow(t[i][i], MOD - 2);
        for (int j = 1; j <= N; j++) if (j != i) {
            LL tmp = t[j][i] * inv_tii % MOD;
            for (int k = 1; k <= (N << 1); k++) 
                t[j][k] = (t[j][k] - tmp * t[i][k] % MOD + MOD) % MOD;
        }
        for (int j = 1; j <= (N << 1); j++)     
            t[i][j] = t[i][j] * inv_tii % MOD;
    }
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++) res[i][j] = t[i][j + N];
    return 0;
}

行列式

这里直接给出行列式的计算式：

\[\det (A) = |A| = \sum\limits_{P} (-1) ^ {\tau(P)} \prod\limits_{i=1}^n A_{i,p_i} \]

其中 \(P\) 是 \(1\) 到 \(n\) 的排列， \(\tau(A)\) 表示序列 \(A\) 的逆序对个数。

叉积实际上就是 \(n = 2\) 的行列式。

详细的性质表和计算过程可以看我另一篇博客。\(\Rightarrow\)高斯消元入门

如果将 \(A\) 看成 \(N\) 个向量竖着写，那么 \(\det(A)\) 可以理解为这 \(N\) 个向量围成的面积/体积/超几何体的体积之类的东西。

这里再补充一个性质：\(\det(AB) = \det(A)\det(B)\) 。一种理解：行列式可以视为线性变换的后面积的缩放倍数。那么将原图形按 \(B\) 线性变化，然后按 \(A\) 线性变化得到的图形，也是按 \(AB\) 线性变化后的图形。

当 \(\det(A) = 0\) 的时候，可以理解为 \(A\) 中的向量线性相关，也可以理解为 \(A\) 对应的线性变换使得线性空间降维了，但是不清楚具体变成了多少维。

特征值和特征向量

在一次线性变换中，存在一些非零向量不会发生旋转，变换后仍然在变换前该向量所在的直线上，这些向量被称为特征向量，而这些向量的缩放系数被称为特征值。不同特征向量的特征值可能不同，但是在同一直线上的特征向量的特征值相同。

现在讲讲怎么求出特征值和特征向量。

具体而言，假设线性变化对应的矩阵为 \(A\)，特征值为 \(k\)。 设所求特征向量为 \(\vec v\)，那么可以得到下面的式子：

\[A\vec v = k\vec v \]

这看起来非常好理解，但是不容易算，我们用 \(I\) 将系数转化成矩阵:

\[\begin{aligned} \Rightarrow AI\vec v &= kI\vec v\\ \Rightarrow A\vec v &= kI\vec v \end{aligned} \]

接着进行个简单的变形：

\[\Rightarrow (A - kI)\vec v = \vec 0 \]

这里得到了一个新的线性变换，而这个线性变换让线性空间降维了，也就是 \(\det(A-kI)=0\)。这里将式子展开，显然是一个关于 \(k\) 的多项式，可以求解（有点困难）。然后对于每一个特征值，可以分别求出一个特征向量（有点困难）。

对角矩阵的特征值

对于对角矩阵对应的线性变换，其特征值实际上就是矩阵左上\(-\)右下对角线上的元素。同时，特征向量一定是基向量所在的直线上的任何一个非零向量。