线性代数

线性空间

指向量空间，在线性空间里，定义了向量加法与标量乘法

其中标量乘法对向量加法有分配律

我们称标量乘与向量加为线性组合

线性无关

如果一组向量中不存在一个子集使得其能线性组合出该组向量中的另一向量

线性基

也称线性空间的基底，即最小的一组能线性表示出整个线性空间的向量组

向量

点积

对于两个 \(k\) 维向量 \(\vec a,\vec b\)，其点积 \(\vec a\cdot \vec b=\sum_{i=0}^{k-1}a_ib_i\)

显然，点积对加法有分配律 \((\vec a+\vec b)\cdot \vec c=\vec a\cdot \vec c+\vec b\cdot \vec c\)

向量正交化

对于一组线性无关的向量组，构造一组向量使得其组成的线性空间与原向量组等价，且两两垂直，模长为单位长度

考虑一个个向量处理，对于第 \(i\) 个向量 \(\vec{v_i}\)，我们只需让取系数 \(a_{i,j}\) 得到 \(\vec{v_i'}=\vec{v_i}+\sum_{j=0}^{i-1} \vec{v_j’}a_{i,j}\)

我们考虑由于 \(v_j'\) 两两垂直，我们把 \(v_i\) 拆成向量 \(\vec a+\vec b\) 使得 \(\vec a\bot \vec{v_j'},\vec b//\vec{v_j'}\)

考虑 \(\vec b\) 实际上是 \(\vec{v_j'}\) 到 \(\vec{v_i}\) 的投影，写个点积求模长，把 \(\vec b\) 减掉即可

矩阵

矩阵，为一个按矩形排列的复数集合，将 \(n\)​ 行 \(m\)​ 列的矩阵简称为 \(n\times m\)​ 矩阵

矩阵的转置

对于 \(n\times m\) 的矩阵 \(A\)，称一个满足 \(A^{T}_{i,j}=A_{j,i}\) 的 \(m\times n\) 矩阵 \(A^{T}\) 为 \(A\) 的转置

矩阵运算

对于 \(n\times m\) 矩阵 \(A,B\)

定义数乘 \(vA=C\)

满足 \(C\) 是 \(n\times m\) 矩阵且 \(c_{i,j}=v*a_{i,j}(i\in[1,n],j\in[1,m])\)

定义矩阵加法 \(A+B=C\)

满足 \(C\) 是 \(n\times m\) 矩阵且 \(c_{i,j}=a_{i,j}+b_{i,j}(i\in[1,n],j\in[1,m])\)

减法类似

矩阵加减法均有交换结合律，对数乘有结合律

对于 \(n\times m\) 矩阵 \(A\) 与 \(m\times p\) 矩阵 \(B\)

定义矩阵乘法 \(A\times B=C\)

满足 \(C\) 是 \(n\times p\) 矩阵且 \(c_{i,j}=\sum_{k=1}^ma_{i,k}b_{k,j}(i\in[1,n],j\in[1,p])\)

矩乘没有交换律，但有结合律

时间复杂度 \(O(nmp)\)

for(int i=1;i<=n;i++)
	for(int k=1;k<=m;k++)
        for(int j=1;j<=p;j++)
            c[i][j]=add(c[i][j]+1ll*a[i][k]*b[k][j]%mod);

这样一段矩乘代码内存访问更为连续，常数较小

特别的，对于 \(n\times n\) 矩阵 \(A\)

定义 \(A^k\) 为 \(A^{k-1}\times A\) ，且 \(A^1=A\)

一般采取矩阵快速幂在 \(O(n^3logk)\) 的复杂度内得到 \(A^k\)

在OI中，可以重新定义矩阵乘法，例如 \(\min+\) 矩乘

需注意应满足结合律才可采用矩阵快速幂算法

矩阵变换

矩阵的初等行变换

1. 交换两行
2. 以非零实数乘以某行
3. 将某行替换为它与其它行倍数的和

我们试图通过初等行变换消元，得到原多个向量组成的线性空间的一组基

这个过程用高斯消元实现，高斯校园后下三角矩阵变为0，称为行阶梯形

矩阵的秩

对于一个 \(n\times m\) 的矩阵 \(A\)

行秩：矩阵 \(n\)​ 个行向量中线性无关的极大数目

列秩：矩阵 \(m\)​ 个列向量中线性无关的极大数目

行秩=列秩，称为 \(\rank(A)\)​

满秩：称行秩为行数的矩阵行满秩，同理可得列满秩定义

对于一个方阵，若其秩为阶数则称其为满秩矩阵

矩阵的逆

若方阵 \(A\)​ 满秩，\(A\)​ 存在逆矩阵 \(A^{-1}\)​

满足 \(A\times A^{-1}=A^{-1}\times A=I\)​

矩阵求逆可以考虑将矩阵 \(A\) 高消成 \(I\) 的过程

由于矩阵初等变换本质是给矩阵乘一个矩阵

那么，\(A\times B=I\)，则 \(B\) 为 \(A^{-1}\)，实现考虑 \(I\times B=B\)​，即可

结论

\((AB)^{-1}=B^{-1}\times A^{-1}\)

\((AB)^{T}=B^{T}\times A^{T}\)

\((A^T)^{-1}=(A^{-1})^T\)

行列式

对于一个 \(n\times n\) 的矩阵 \(A\)

定义其行列式 \(\det(A)\) 为一个与矩阵 \(A\) 对应的标量

\(\det(A)=\sum_{p}(-1)^{\tau(p)}\prod_{i=1}^na_{i,p_i}\)

其中，\(p\) 为一个1到n的排列，\(\tau(p)\) 表示该排列的逆序对数

行列式的性质

1. 对换行列式两行（列）的位置，行列式的值反号
2. 把行列式的某一行（列）乘上实数 \(k\) ，行列式的值乘以 \(k\)
3. 将某行（列）的倍数加到其它行（列）上，行列式的值不变
4. 行阶梯形矩阵的行列式为主对角线的乘积

综上，我们可以利用高斯消元求解行列式

从行列式的定义出发

考虑 \(\sum_p\prod a_{i,p_i}\) 实际上是一个满二分图匹配的方案数

套上 \((-1)^{\tau(p)}\)​​ 实际上跟二分图匹配时交点个数的奇偶性，答案为偶方案-奇方案

[NOI2021] 路径交点

循环矩阵的行列式

计算 \(\begin{vmatrix}c_0&c_1&...&c_{n-1}\\c_1&c_2&...&c_0\\\vdots&\vdots&\ddots&\vdots\\c_{n-1}&c_0&\dots&c_{n-2}\end{vmatrix}\)

相关多项式 \(F(x)=\sum_{i=0}^{n-1}c_ix^i\)

\(\det(A)=\prod_{j=0}^{n-1}F(\omega_n^j)\)

范德蒙德行列式

其形如 \(A=\begin{vmatrix}1&1&...&1\\x_0&x_1&...&x_n\\\vdots&\vdots&\ddots&\vdots\\x_0^n&x_1^n&\dots&x_n^n\end{vmatrix}\)​

\(\det(A)=\prod_{0\leq i<j\leq n}(x_j-x_i)\)​

值得一提的是范德蒙德矩阵与多项式很有关联

左乘一个表示多项式系数的行向量得到的行向量本质是对于 \(x_0\dots x_n\) 多点求值的结果

克莱姆法则

对于线性方程组，记其系数矩阵为 \(A\)，增广矩阵最后一列为 \(B\)

若 \(\det(A)\neq 0\)，则方程组有唯一解 \(x_i=\dfrac{\det(A_i)}{\det(A)}\)

其中，\(A_i\) 指将 \(A\) 的第 \(i\) 列换成 \(B\) 得到的矩阵

大概能和行列式有特殊性质的系数矩阵联合使用