线性代数学习笔记
FLY_lai
·
·
个人记录
元素：一个个体，一般是一个数。
【向量】
向量：一组元素，向量 a 记作 \vec{a}。
我们只在乎向量的方向和大小，并不在乎向量的起点和终点。
定义： n 维向量，即 \vec{a} 中包含 n 个元素。
向量的运算：
-
向量的大小：|\vec{a}|。
-
向量加减：只有两个规模相等的向量的进行加减运算。
-
向量乘以一个数：\vec{a}\times x。若 \vec{a}=(a_1,a_2,\cdots,a_n)，则 \vec{a} \times x = (a_1\times x, a_2\times x, \cdots, a_n\times x)。
-
向量乘以向量，一共两种：点乘和叉乘，这里只提点乘。
点乘只有两个向量规模相等才能进行运算。
【更具象化的意义】
向量：一个有方向的量。
如果没有方向，称为 “标量”；有方向，就是 “向量”。
平面向量：就是 2 维向量。
维度：如果一个向量是 n 维的，说明它可以用 n 个数确定方向。
例如 2 维向量。
此时，终点落在平面上的一个点 $(a_1,a_2)$ 上，**这就是向量的坐标。**
同理，在 $3$ 维向量中，我们可以用 $(a_1,a_2,a_3)$ 来表示终点所在的坐标。
所以，维度就是表示**我们用多少个数就可以确定平面上的点**。
# 【矩阵】
矩阵就是一些元素排成一个矩形的形式。用行和列来描述矩阵的规模。
可见，向量其实就是一种特殊的矩阵，它们的行（列）等于 $1$。
下面用 $n$ 表示行数，$m$ 表示列数。
一些关于矩阵的定义：
1. 同型矩阵：两个矩阵，如果 $n$ 和 $m$ 对应相等，称它们为同型矩阵。
2. 方阵：$n=m$ 的矩阵。
$a$ 阶方阵：$n=m=a$ 的方阵。
3. 对角矩阵：除了主对角线，其余所有元素都为 $0$ 的矩阵。
**主对角线上的元素都为 $1$ 的对角矩阵，称为单位矩阵**。
矩阵的运算：
1. 加减，类似向量加减，规模必须相等，对应元素加减即可。
2. 数乘，每个元素都乘以这个数。
3. **矩阵乘法（包括向量乘以矩阵）**。
如果两个矩阵 $a,b$ 进行矩阵乘法，**必须保证 $a$ 的列数等于 $b$ 的行数**。
$$ a =
\begin{pmatrix}
a_{1,1}&a_{1,2}&\cdots&a_{1,m}\\
a_{2,1}&a_{2,2}&\cdots&a_{2,m}\\
\cdots&\cdots&\cdots&\cdots\\
a_{n,1}&a_{n,2}&\cdots&a_{n,m}\\
\end{pmatrix}
$$
$$ b =
\begin{pmatrix}
b_{1,1}&b_{1,2}&\cdots&b_{1,k}\\
b_{2,1}&b_{2,2}&\cdots&b_{2,k}\\
\cdots&\cdots&\cdots&\cdots\\
b_{m,1}&b_{m,2}&\cdots&b_{m,k}\\
\end{pmatrix}
$$
运算结果矩阵 $c$ 是一个 $n\times k$ 的矩阵。其中 $c_{i,j}=\displaystyle \sum^k_{x=1}a_{i,x}\times b_{x,j}$。
看得出来，矩阵乘法满足**结合律、对矩阵加法的分配律**，但是不满足**交换律**。
## 【具象化】
矩阵乘法，就是一个**线性变换**。
什么叫**线性变换**？
我们看一个函数：$f(x)=kx$，这是一个一次函数，也就是**线性的**。
类推：$f(x_1,x_2,\cdots,x_n)=\displaystyle \sum_{i=1}^n k_ix_i$，也是**线性的**。
这样我们通过 $(k_1,k_2,\cdots,k_n)$ 这个线性变换，把 $(x_1,x_2,\cdots,x_n)$ 变成了一个数。
观察矩阵乘法的运算法则：
$c_{i,j}=\displaystyle \sum^k_{x=1}a_{i,x}\times b_{x,j}$，这不就是可以视为线性变换吗？
把 $a_{i,x}$ 视作上面的 $k_i$，$b_{x,j}$ 视作上面的 $x_i$，$c_{i,j}$ 视作线性变换的结果。
再回过头看我们的矩阵乘法：
向量乘以矩阵，得出的向量就是**经过线性变换后得出的向量**。
两个矩阵相乘，既可以视作很多个向量存在矩阵里，依次进行线性变换；也可以视为得出一个**先做第一个变换，再做第二个变换的等价变换**。
[oi-wiki](https://oi-wiki.org/math/linear-algebra/linear-mapping/#%E7%BA%BF%E6%80%A7%E5%8F%98%E6%8D%A2%E7%9A%84%E7%9F%A9%E9%98%B5%E8%A1%A8%E7%A4%BA)
# 【到代码】
建议把矩阵写成一个结构体，因为在 OI 中一般只研究方阵，所以我们就只写方阵。
首先解决基本的运算，（只写矩阵乘法，因为加减法简单，向量等于矩阵）。
```
struct Mtr {
int n;
vector<vector<long long> > m;
Mtr (int x) {
n = x;
m = vector<vector<long long> >(n, vector<long long>(n, 0));
}
Mtr () {
n = 0;
}
void read() {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> m[i][j];
}
void write() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
cout << m[i][j] << ' ';
cout << endl;
}
}
} a, b;
Mtr operator*(Mtr a, Mtr b){
Mtr c = Mtr(a.n);
for (int i = 0; i < a.n; i++)
for (int j = 0; j < a.n; j++)
for (int k = 0; k < a.n; k++)
c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;
return c;
}
```
$O(n^3)$。
因为矩阵乘法满足结合律，所以可以考虑使用**快速幂**来加速运算。
（**看到结合律，就要想想快速幂和线段树可不可以用。**）
把矩阵包装成结构体的好处此时也显现出来了，快速幂的代码基本不用动。
[【模板】矩阵快速幂](https://www.luogu.com.cn/problem/P3390#submit)
看，当我们需要连续乘以一个东西的时候，我们就只能用**方阵**了，这也是为什么 OI 中主要研究方阵的原因。
# 【应用到问题】
上面的所有其实都没有真正跨入解决问题的大门。
我们说到，**矩阵可以视作一个线性变换**。
那么，如果我们的答案是一个**经过若干次线性变换得出**的，就可以考虑编成一个矩阵，然后利用**快速幂**在 $\log$ 级别的时间内求出来。
例题：[斐波那契数列](https://www.luogu.com.cn/problem/P1962)，这题可谓相当经典。
我们看这个递推式：$F_i=F_{i-2}+F_{i-1}$，满足 $y=k_1x_1+k_2x_2$ 的形式，$F_{i-2}\rightarrow x_1,F_{i-1}\rightarrow x_2$，这是线性变换！
所以我们可以考虑用矩阵乘法。
研究矩阵乘法的递推，我们从起点开始。
上面提到过，系数 $(k_1,\cdots,k_n)$ 是线性变换，那么 $x_1,\cdots,x_n$ 就是起点。
所以把 $x_1,x_2$ 存进矩阵当起点：
$$ mar =
\begin{pmatrix}
F_{i-2}&F_{i-1}
\end{pmatrix}
$$
我们往后推一步：
$$ mar^{*} =
\begin{pmatrix}
F_{i-1}&F_{i}
\end{pmatrix}
$$
$mar\cdot$ 变换矩阵$\,change$ $=mar^{*}$。
$mar^{*}_{\;\;1,1}=F_{i-1}$ 正好就是 $mar_{2,1}$，根据矩阵乘法的定义，$mar^*_{\;\;1,1}=mar_{1,1}change_{1,1}+mar_{1,2}change_{2,1}$。
我们只要恰好一个 $mar_{2,1}$：所以$change_{1,1}=0,change_{2,1}=1$。
同理得：$change_{1,2}=change_{2,2}=1$。
所以：
$$
\begin{pmatrix}
F_{i-2}&F_{i-1}
\end{pmatrix}
\begin{pmatrix}
0&1\\
1&1\\
\end{pmatrix}
=\begin{pmatrix}
F_{i-1}&F_i\\
\end{pmatrix}
$$
$$
\begin{pmatrix}
F_{1}&F_{2}
\end{pmatrix}
\begin{pmatrix}
0&1\\
1&1\\
\end{pmatrix}^{i-2}
=\begin{pmatrix}
F_{i-1}&F_i\\
\end{pmatrix}
$$
同时，为了好写，我们可以把初始的一行矩阵也写成 $2\times2$ 的方阵，第二行全是 $0$ 即可。
# 【高斯消元】
高斯消元用来解决线性方程组的问题。
例如：
$$
\begin{cases}
2x_1+3x_2+4x_3=20\\
x_1+2x_2+3x_3=14\\
3x_1+x_2+2x_3=11
\end{cases}
$$
得出 $x_1=1,x_2=2,x_3=3$。
这就是线性方程组。
高斯消元法给出了一个普遍性的解决这种问题的方法。
假设我们要解决一个 $n$ 元的线性方程组，第 $i$ 个方程是 $k_{i,1}x_1+k_{i,2}x_2+k_{i,3}x_3+\cdots+k_{i,n}x_n=a_i$。
我们建立一个 $n\times (n+1)$ 的矩阵，其中矩阵的第 $i$ 行为 $(k_{i,1},k_{i,2},\cdots,k_{i,n},a_i)$。
例如：
$$
\begin{pmatrix}
2&3&4&20\\
1&2&3&14\\
3&1&2&11
\end{pmatrix}
$$
我们的目标是得出一个矩阵，这个矩阵左边的 $n\times n$ 应该是一个单位矩阵。
例如：
$$
\begin{pmatrix}
1&0&0&1\\
0&1&0&2\\
0&0&1&3\\
\end{pmatrix}
$$
这样，第 $n+1$ 列的所有数就是 $\{x_i\}$ 的解了。
回到一开始的矩阵，我们考虑考虑怎么做。
我们希望最后第一行第一列的是 $1$，其他行第一列的都是 $0$。
所以我们先让第一行第一列变成 $1$，也就是除一下：
$$
\begin{pmatrix}
1&1.5&2&10\\
1&2&3&14\\
3&1&2&11
\end{pmatrix}
$$
然后我们用第一行 “消” 掉其他行的 $x_1$，这就是平时解方程的加减消元法。
$$
\begin{pmatrix}
1&1.5&2&10\\
0&0.5&1&4\\
0&-3.5&-4&-19
\end{pmatrix}
$$
然后到 $x_2$，注意到当我们消完 $x_1$ 的时候，对之后每一行的乘除都不会影响到第一列的系数了。
因此我们让第二行的第二列变成 $1$。
$$
\begin{pmatrix}
1&1.5&2&10\\
0&1&2&8\\
0&-3.5&-4&-19
\end{pmatrix}
$$
这个时候再用第二行消去其他行的 $x_2$。因为第一列已经是 $0$，所以第二行加减第一行也不会影响 $x_1$ 的系数 $1$。
$$
\begin{pmatrix}
1&0&-1&-2\\
0&1&2&8\\
0&0&3&9
\end{pmatrix}
$$
最后到 $x_3$，一样的操作。
$$
\begin{pmatrix}
1&0&0&1\\
0&1&0&2\\
0&0&1&3\\
\end{pmatrix}
$$
这样我们就得出了解。
但是！还有情况！无解或者无穷多解怎么办？
考虑一个无解的情况：
$x_1+x_2=1,2x_1+2x_2=3
\begin{pmatrix}
1&1&1\\
2&2&3
\end{pmatrix}
消去 x_1：
\begin{pmatrix}
1&1&1\\
0&0&1
\end{pmatrix}
发现，这个时候的最后一行，前面都是 0 但是最后一列不是。
这表示 0\ne 0，矛盾，所以无解。
因此，只要我们做完高斯消元，发现有一行前面都是 0 但最后不是 0，说明无解。
再看看无穷多解。
$$
\begin{pmatrix}
1&1&1\\
2&2&2
\end{pmatrix}
$$
消去。
$$
\begin{pmatrix}
1&1&1\\
0&0&0
\end{pmatrix}
$$
这个时候最后一行**全都是 $0$**，说明无穷多组解。
------------
总结：
1. 构建矩阵。
2. 第 $i$ 次操作，从 $i\sim n$ 行中找出一个第 $i$ 列非 $0$ 的行，把这个行换到第 $i$ 行的位置，用这个行消去其他行。
**注意：如果找不到非 $0$ 的行，说明无穷多组解。**
3. 结束后判断有没有全 $0$ 的行或者前面全 $0$ 但最后不是 $0$ 的行。