「OI之路」03数学-6线性代数

线性代数

先讲一些,在OI中必须掌握的内容

矩阵乘法

业界一般是采用列向量,左乘矩阵,如果习惯行向量可能后面学习会带来不便

其实广义来说,满足结合律就好;例如矩乘做倍增floyd,一些ddp

高斯消元

带状矩阵:$a_{i,j} \ne 0的必要条件是,|i-j| \le d$,这种矩阵的高斯消元可以做到$O(nd^2)$,例题是CF963E Circles of Waiting,$n=\pi R^2,d=R$

不过有一点要注意,消第i个元的时候不是去找$a_{t,i} \ne 0$,否则换到第i行会导致这行特别长,然后向下消元的时候会破坏带状的性质;解决方案是找$a_{i,t}$,将那一列换过来,到时候多出来的部分会被消掉

主元法:经典的例子就是开关灯,将第一行看做未知,其他所有位置都可以被表示为线性组合,本质上是减少未知数个数

简单的例题是「Topcoder 12984」TorusSailing,只需要设最后一行和最后一列的就好了

上面那个例题也可以用这个做,将每行最左边的设为主元,每次这一列已知,然后根据这一列的方程得到下一列的线性组合方程,当推出每行最右边点的时候方程和线性组合列起来得到真正的方程,2R+1个未知数,2R+1个方程,$O(R^3)$

非质数模意义下可以通过辗转相除法$O(n^3loga)$搞出倒三角(搞不出对角矩阵),之前曾看到过$O(n^3)$的黑科技法,现在找不到了

线性基

如果真看不懂可以看menci的,下文省略概念性常识

判断是否存在子集能异或出这个数,若到最后依然没break意味着已有这个数:

1
fd(i,60,0) if(num&bin(i)) {if(!bs[i]) {bs[i]=num,cnt++;break;} else num^=bs[i];}

求最大子集异或和:

1
fd(i,60,0) chmax(num,num^bs[i]);

上述这些情况不需要消成三角矩形所以很好写(用高斯消元理解,即$bs_i=2^i$),接下来就要理解这个线性基的一些性质了

首先线性基里面的子集不应能异或出0,否则意味着基能更小;

因此也不存在两个不同的子集异或和相同,因为这两个子集做「集合异或」就能得到「能异或出0的子集」;

线性基不仅是最小的基底,同时也是最大的线性无关集

因此n个数的大小为cnt的线性基,其线性空间(要求选非空子集的话)为$2^{cnt}-[cnt=n]$,后面那个是特判0;

于是我们就会做求线性空间第k大(findkth)了,例题:hdu3949 XOR;另外线性空间问排名(findrk)也差不多

也很容易推知,异或和为wt的集合数=在线性基外n-cnt个数中选一个集合,得出now,然后在线性基里面异或出$now \oplus wt$的方案数,后者唯一,故方案数为$2^{n-cnt}$,也就是说异或空间里每个数对应的子集方案数都是一样的

albus就是要第一个出场就是求子集异或和中某个数的排名,直接$2^{n-cnt}*findrk+1$即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
namespace BS
{
ll bs[100];int cnt,zero;void clear(){mem(bs,0);cnt=zero=0;}
void insert(ll num)
{
fd(i,60,0) if(num&bin(i))
{
if(!bs[i]) {
fo(t,0,i-1) if(num&bin(t)) num^=bs[t];
fo(t,i+1,60) if(bs[t]&bin(i)) bs[t]^=num;
bs[i]=num,cnt++;return;
}
else num^=bs[i];
} zero++;
}
ll findkth(ll k){ll ret=0,right=cnt;k-=(zero>0);fd(i,60,0)if(bs[i]){right--;if(k&bin(right))ret^=bs[i],k-=bin(right);}return k?-1:ret;}
ll findrk(ll num){ll rk=0,right=cnt;fd(i,60,0)if(bs[i]){right--;if(num&bin(i))rk|=bin(right);}return rk;}
};

另外线性基套贪心也很常见:「SDWC2018」Set「bzoj4644」经典傻逼题「集训队互测2015」最大异或和「BJWC2011」元素


真·线性代数

选择性证明一些比较好证明的吧……不好证的我就跑路了QAQ

普适的代价是抽象

如果想先对线性代数有些简单但直观的理解,推荐看一看3B1B的视频

如果不想细看视频,找到两篇笔记: 笔记1自为风雨马前卒的笔记,没那么长

基向量:在向量空间中,找到一组线性无关的基,作为基向量

则线性空间内,任意向量可以表示为基向量的线性组合

线性变换的直观定义:1. 直线依然是直线 2. 原点固定

这个变换可以表示为,对基向量的变换。将第i个基向量作为一个矩阵的列向量,则这个矩阵可以表示这个线性变换:

列空间:所有列向量张成的空间

行列式$det(A)、|A|$:线性变换前后,基变量搞出来的多面体有向体积比(二、三维挺好理解?)

若$det=0$代表线性相关(如下图)

img

秩$r(A)$:变换后(列空间)的维数,满秩表示与列数相同;也可以理解为极大线性无关组大小,所以秩相当于是对det=0的压缩程度的表示,上图就是1

向量点积(维数相同,也叫数量级、内积)

​ 代数理解:相应坐标配对乘后求和,显然满足交换律

​ 几何理解:A在B上的带符号投影乘B的长度,即$A \cdot B=|A||B|cos \theta$,不显然满足交换律,如何用直观的方式理解?先考虑两个向量的模一样时显然成立,然后你把某个伸缩依然成立

​ 然后也可以理解为从n维变换到1维,即把某个向量横过来做矩阵乘法($A \cdot B=A^TB$)

叉积(向量积、外积、叉乘)

首先结果是一个向量,与「两个向量所在平面」垂直,$模长=|a||b|*|sin \theta|,二维下=x1y2-x2y1$
方向:右手法则,四指从a到b,大拇指的朝向,向上为正

对于二维叉积比较好理解,就是两个基向量变换过去,用基变换的行列式表示面积

三维叉积(v*w)的计算方式(带基向量的行列式)的本质:

考虑存在一个函数,在固定的v和w下返回自变量p与它们张成的平行六边形的体积;然后这是一个线性变换,而根据对偶性这个线性变换的矩阵可以竖起来变成一个向量h与p做点积

然后你发现,其实这个h就是一个「与v、w所在平面垂直且长度为其平行四边形」的一个向量,即v和w的叉积

因此,在右边填上三个单位向量算是某种技巧,每个单位向量的系数就是线性变换的系数,这个线性变换对应着的向量就是v和w的叉积

据说除此之外,只有七维向量有叉积,告辞

最后总结一下向量的本质

对于线性代数,向量这个东西的本质应当是具有线性性质(formally,具备向量加法和数乘的八条公理)的任何事物,常见的如坐标、一组数、函数……但他们的系统都含有线性的运算,所以上述内容对这些事物都具有普适性


接下来从代数角度考虑(主要抄自雅礼201903的课件)

n阶方阵:就是大小为$n \times n$ 的矩阵

矩阵的转置$A^{T}$ :$a_{i,j}^T=a_{j,i}$

单位矩阵:主对角线上为1,其他为0,符号为$I或E$

行列式的计算公式(并不会从几何意义推):$\sum_P (-1)^{p的逆序对个数} \prod_{i}a_{i,p_i}$。虽然不会推,但起码要知道的是,相当于我们关心p的逆序对的奇偶性,而逆序对只是一种交换方式,本质上是一种排序方式的奇偶性。众所周知交换任意两个元素一定使排列逆序对奇偶性发生变化,因此$(-1)^{逆序对数}=(-1)^{偶环个数}$,因为环内排序是做长度-1次相邻交换

奇异方阵:行列式=0的方阵

行列式的性质(非常重要!!)

  1. 根据通项公式,行列地位平等,转置不影响行列式
  2. 三角矩阵和某些特殊的矩阵的行列式是主对角线元素乘积,因为合法p只有对角线
  3. 交换任意两行、列后行列式取反(所以用高斯消元求行列式的话要注意),证明:其实就是证排列交换两个元素后逆序对数的奇偶性必定变化,考虑到交换相邻一定改变,而现在要做奇数次相邻交换,证毕(upd:好像也没必要这么证)。
  4. 性质2的推论,两行完全相同下行列式=0;进一步发现,两行成比例的话也=0,因为可以把比例系数放到行列式的外面;于是你发现我们对行列式的几何理解与我们现在的数学推导是吻合的(当然我并不知道怎么相互推导)
  5. 可以把某一行拆分成序列A和序列B的和,然后行列式就是两个其他行不变的矩阵的行列式之和。这个比较显然,和性质3放在一起可知,做初等行列变换(带系数叠加去某行)不影响行列式
  6. $|A*B|=|A||B|$,证明考虑行与列做点积

余子式$M_{i,j}$:删除第i行和第j列后矩阵的行列式,代数余子式$A_{i,j}=(-1)^{i+j}M_{i,j}$

拉普拉斯展开:$\forall i,det(A)=\sum_{j=1}^n a_{i,j}A_{i,j}$ ,写成$(-1)^{(n-i)+(n-j)}$ 就会变得很显然

推论:$det(A)[i=j]=\sum_{k=1}^n a_{i,k}A_{j,k}$ ,证明:本质上就是第i行代替第j行后求行列式=0

范德蒙行列式:对一个序列Q,$F_{i,j}=Q_i^{j-1}$ ,当然你可以旋转,主要是 $det(F)=\prod_{i<j} (Q_j-Q_i)$

克莱姆法则:众所周知线性方程组可以表示为 $Ax=c,其中x和c都是列向量$

$当det(A) \ne 0,x_i=\frac{det(A_i)}{det(A)},其中A_i表示用c取代A的第i列得到的矩阵$

证明:将 $A_{i,k}$乘到第i个方程然后对n个方程求和可知,$\sum_{j=1}^n( \sum_{i=1}^n a_{i,j}A_{i,k} )x_j=\sum_{i=1}^n c_iA_{i,k}$

然后右边就是$det(A_i)$ ,左边考虑拉普拉斯展开的推论可得 $det(A)x_k$

k阶子式:选k行k列组成的k阶方阵的行列式

逆矩阵:联系几何意义可知要求行列式不为0,也可以数学推导:$A^{-1}A=E,|A^{-1}||A|=1,|A| \ne 0$

先明确:$(AB)^{-1}=B^{-1}(A^{-1}A)B(AB)^{-1}=B^{-1}A^{-1}$ ,其实几何意义下显然

考虑利用初等变换矩阵,而一个可逆矩阵经过有限次初等变换后显然是$I$

$(一堆初等变换矩阵)*A=E,A^{-1}A=E$ ,如果你认可A的逆矩阵唯一(几何意义不难理解),那么求矩阵的逆就是将A高斯消元成E,然后按原顺序将过程中所做的初等变换在E上做一次,洛谷板子

余子矩阵:将原矩阵的$a_{i,j}$ 替换为代数余子式$A_{i,j}$得到的矩阵

伴随矩阵:$A*=余子矩阵^T$,$A*=|A|A^{-1}$ ,这个也不难理解,两边同时乘上A,这样左边就是个拉普拉斯展开的推论;于是我们可以快速求出余子矩阵

分块矩阵:做矩乘的时候,行分块、列分块然后看做元素是矩阵的矩阵做乘法,这样和直接乘是等价的

向量组的等价:A和B可线性表示对方;故向量组和其极大线性无关组是等价的

n元齐次方程组: $Ax=0$ 有非0解的充要条件是$r(A)<n$;且不难发现他的解集是一个向量空间

通过初等变换搞成左上角E右上角有东西下面n-r行都是0的形式

然后具体怎么求解好像没啥好说的,推一推就会发现向量空间的维护=自由元个数

正交:$a^Tb(即a \cdot b)=0$;

正交向量组:非零向量两两正交,一定线性无关,证明: $a1\cdot (a1)展开发现=0$

正交矩阵A: $AA^{T}=E$ ;模拟矩乘发现列/行向量组是正交向量组且所有列/行向量模长=1

相似矩阵:n阶方阵A和B,要求存在可逆矩阵P满足 $B=P^{-1}AP$,可以理解为不同基向量下的线性变换,故不难理解一个性质:$B^k=P^{-1}A^kP$;定理:相似矩阵的特征多项式和特征值相同

可对角化矩阵A:能找到一个B是对角矩阵且与A相似,即$B=diag(\lambda_1,\lambda_2,..\lambda_n)$

$P^{-1}AP=diag(\lambda_1,\lambda_2,..\lambda_n),AP=Pdiag(\lambda_1,\lambda_2,..\lambda_n),AP_i=\lambda P_i$ ,即P的每个列向量都是A的特征向量,又因P可逆,故A可对角化的充要条件是有n个线性无关的特征向量(而任意n阶方阵最多n个)。

特征向量(没有离开其张成的直线):$A\vec x=\lambda \vec x,其中\lambda为特征值表示缩放程度,\vec x为特征向量,求\vec x则变形成(A-\lambda E)\vec x=0$

这是一个齐次线性递推,前面说过条件为$det(A-\lambda E)=0$ ,行列式展开后是一个关于$\lambda$的n次多项式,称为A的特征多项式,记作 $f(\lambda)$,然后就是求零点。特殊的,三角矩阵的特征值为主对角线上的n个元素,因为$A-\lambda E$仍是三角矩阵,其行列式为主对角线上乘积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Matrix//求矩阵行列式板子
{
ll a[N][N];int n;
int Det()//去掉最后一行一列,只需消成倒三角
{
ll ret=1;
fo(i,1,n-1)
{
if(!a[i][i]) return 0;
fo(j,i+1,n-1) while(a[j][i])//有的时候给出的模数不是质数,需要辗转相除
{
ll pp=a[i][i]/a[j][i];ret=mm(MOD-ret);
fo(t,i,n-1) add(a[i][t],MOD-a[j][t]*pp%MOD);swap(a[i],a[j]);
}
ret=ret*a[i][i]%MOD;
}return ret;
}
}A;

常系数线性齐次递推

常系数:递推系数和下标n无关;线性:递推式中每一项的次数都是1;齐次:递推式常数项等于0

Hamilton-Cayley theorem:$f(A)=0$ (A的特征多项式),并不是什么前沿科技其实,dzy的证明

模板:bzoj4161 Shlw loves matrixl;例题:loj547「LibreOJ β Round #7」匹配字符串

考虑本题的转移矩阵,考虑计算其行列式,不妨在第一行拉普拉斯展开,然后你发现去掉第一行及任意一列后得到的矩阵非常特别,其行列式用排列p的式子计算只有一种合法排列:主对角线,所以其行列式很好表达
$$
A-\lambda I=
\left[
\begin{matrix}
a_1-\lambda & a_2 &…& a_n \\
1 & -\lambda &…& 0 \\
0 & 1 & -\lambda & 0 \\
0 & 0 & 1 & -\lambda
\end{matrix}
\right],
g=
\left[
\begin{matrix}
a_{n-1} \
a_{n-2} \
… \
a_0 \
\end{matrix}
\right]
\\
f(\lambda)=det(A-\lambda I)=(-\lambda)^n+\sum_{j=1}^n a_j (-1)^{j+1} (-\lambda)^{n-j}=(-\lambda)^n+(-1)^{n+1}\sum_{j=1}^n a_j \lambda^{n-j} \\
f(A)=0,A^n=\sum_{j=1}^n a_jA^{n-j} ,可见任何 A^k都可以被表示为 A^{0 \sim n-1}的线性组合 \\
ans=(A^eG)[n,1],考虑表示为 A^{0 \sim n-1}的线性组合即 \sum_{i=0}^{n-1}q_i(A^iG)[n,1]=\sum_{i=0}^{n-1}q_ih_i,h为所求序列 \\
考虑这个q以及f(A)=0,你发现我们其实就是在做矩阵多项式模,A^e=f(A)p(A)+q(A) \\
考虑怎么用n相关的复杂度计算多项式模,你发现我们左边是个幂,所以我们不妨用快速幂来搞 \\
A^{2k}=A^k \times A^k(\% f(A)),暴力做(用解线性组合做取模)就是O(m^2logn),写全家桶就是O(mlogmlogn)
$$
没有加任何优化然后 时限80s我跑了79s可还行;另有luogu的板子要求写全家桶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ll a[N],h[N],C[N];int n;
void mul(ll A[],ll B[])
{
for(int i=0;i<n+n;i++) C[i]=0;
for(int i=0;i<n;i++) for(int j=0;j<n;j++) C[i+j]=(C[i+j]+A[i]*B[j])%MOD;
for(int i=n+n-1;i>=n;i--) for(int t=1;t<=n;t++) C[i-t]=(C[i-t]+C[i]*a[t])%MOD;
for(int i=0;i<n;i++) A[i]=C[i];
}
ll q[N],tmp[N];
void main()
{
int e=qread();n=qread();
for(int i=1;i<=n;i++) a[i]=qread();for(int i=0;i<n;i++) h[i]=qread();
q[0]=tmp[1]=1;while(e){if(e&1)mul(q,tmp);mul(tmp,tmp);e>>=1;}
ll ans=0;for(int i=0;i<n;i++) ans=(ans+q[i]*h[i])%MOD;write((ans+MOD)%MOD);
}

bzoj4162 Shlw loves matrix II

如果并不是上面那样特殊的矩阵(常系数齐次线性递推),我们可以 $O(n^4+n^2loge)$ 做矩阵快速幂(显然要卡只能把e搞大),思路就是求出特征多项式,然后后面就上上题一样了

求特征多项式的话,考虑拉格朗日插值,那么现在考虑怎么求对$\lambda_i$求点值,弄出 $A-\lambda_iI$ 然后高斯消元成三角矩阵,然后行列式就是对角积了(口胡ing……


Matrix-Tree定理

作用:计算给定图的生成树个数;对于自环,显然对答案没有影响,去掉

先考虑简单无向图:

拉普拉斯矩阵C=度数矩阵D(是个对角矩阵)-邻接矩阵AA,根据任意行、列的和为0及考虑初等变换可知行列式为0(辅助记忆、好像证明也要用)

Matrix-Tree定理:无向简单图的生成树个数=C的任意一个代数余子式值;证明1证明-lca

对于重边,就是边有权值,生成树的权值为各边权值之积,然后对所有生成树权值求和

那么对于边带权,称之为变元矩阵树定理,D改为相连各边权值和,AA改为边权;

对于有向图,$AA_{i,j}=(i \to j)$,求外向树的话D为入度(列的和=0),内向树就出度(行的和=0);点x为根就是$代数余子式A_{x,x}$

例题:「SHOI2016」黑暗前的幻想乡

best定理

存在欧拉回路的图,deg=入度=出度,任一点出发外向树个数相同(记为cnt)

$从st出发的个数\ = \ cnt*deg_{st} \ \prod (deg_x-1)!$(如果边的环同构算一种方案,就不要乘$deg_{st}$)

并不知道有啥用。有人闲着没事出了数据:bzoj3659

循环矩阵

$$
\left{
\begin{matrix}
x_0&x_1&x_2&…&x_{n-1} \\
x_{n-1}&x_0&x_1&…&x_{n-2} \\
x_{n-2}&x_{n-1}&x_0&…&x_{n-3}\\
\vdots &\vdots &\vdots &\ddots & \vdots \\
x_1&x_2&x_3&…&x_0
\end{matrix}
\right}
,发现两个循环矩阵的乘积依然是循环矩阵
\\
C_{0,i}=\sum_{j=0}^{n-1} A_{0,j}*A_{j,i},
根据循环可知
C_{(i+j) \bmod n}=\sum_{i=0}^{n-1} A_i*A_j,FFT优化卷积O(nlognlogk),exp的话假装O(nlogn)
$$

例题:bzoj2510弱题

上面是最基本的,高端东西见这里

yww的矩阵快速幂姿势

由于暂时没怎么碰到,所以没细看

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/c6a2.html
转载请注明出处,谢谢!