受不了感性理解的线性代数。这个笔记说是线性代数，实际上只是矩阵的入门知识&线性基。
矩阵相关定义
矩阵加法、减法、乘法、数乘不会可以上网搜一下。
单位矩阵：\(I_n=\begin{bmatrix} 1 & 0 & 0 & \cdots & 0\\ 0 & 1 & 0 & \cdots & 0\\ 0 & 0 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & 0 & \cdots & 1\\ \end{bmatrix}\)
假设\(A\)是一个\(n\times m\)的矩阵，那么\(I_n A=A I_m=A\)
转置矩阵：\(A\)的转置矩阵通过交换\(A\)的行和列得到，记为\(A^T\)
例子：
\(A=\begin{bmatrix} 1 & 2 \\ 2 & 5 \\ 7 & 0 \\ \end{bmatrix},A^T=\begin{bmatrix} 1 & 2 & 7 \\ 2 & 5 & 0 \\ \end{bmatrix}\)
若\(A=A^T\)，称\(A\)为对称矩阵。例如无向图的邻接矩阵为对称矩阵。
根据定义能推出来：\(A^TB^T=(BA)^T\)
如果把向量当成一个\(1\times n\)或\(n\times 1\)的矩阵，那向量也可以使用矩阵乘法的定则
若\(x,y\)都是\(n\)向量（\(n\)行\(1\)列），那么\(x^Ty=\sum_{i=1}^n x_i y_i\)称为向量内积（实际上是个\(1\times 1\)的矩阵）
\(xy^T=\sum_{i=1}^n x_i y_i\)称为向量外积（\(n\times n\)的矩阵）
定义范式\(||x||=(x_1^2+x_2^2+...+x_n^2)^{\frac{1}{2}}=(x^Tx)^{\frac{1}{2}}\)，实际上就是\(n\)维空间的欧几里得长度。
排列矩阵：\(n\times n\)的矩阵，每行每列有且仅有一个元素是1，其他是0
排列矩阵的性质：若A是排列矩阵，则：
-
向量\(x\)乘以一个对应大小的排列矩阵会得到\(x\)的一个排列
-
\(A^T\)也是排列矩阵。
-
两个排列矩阵的积也是排列矩阵
对于性质\(3\)，可以考虑若\(C=A\times B\)，\(C_{i,j}=\sum_{k=1}^n A_{i,k}B_{k,j}\)
若A第\(i\)行的\(1\)为\(A_{i,a(i)}=1\)，\(B\)第\(i\)行的\(1\)为\(B_{i,b(i)}=1\)，那么
\(C_{i, j}=A_{i,a(i)}B_{a(i),j}=A_{i,a(i)}[j=b(a(i))]=[j=b(a(i))]\)
可以得证。
初等矩阵：单位矩阵通过一次初等变换（对于行变换来说，是交换两行、数乘一行、行乘\(k\)加到另一行）得到的矩阵称为初等矩阵。
初等变换等价于乘一个初等矩阵（行变换是左乘，列变换是右乘）。
这三种这里都试着证明，其实熟悉矩乘定义这是显然的。
设交换A的\(i,j\)两行得到的矩阵为\(A_1\)，设\(P_{i,j}\)表示单位矩阵交换\(i,j\)行得到的矩阵，则\(A_1=P_{i,j}A\)
证明：\(A_1[i][q]=\sum_{k}P[i][k]A[k][q]=\sum_{k}[k=j]A[k][q]=A[j][q]\)，第\(j\)行同理
设A的第\(i\)乘\(d\)得到的矩阵为\(A_1\)，设\(P_{i,j}\)表示单位矩阵交换\(i\)行乘\(d\)得到的矩阵，则\(A_1=P_{i,j}A\)
证明：\(A_1[i][q]=\sum_{k}P[i][k]A[k][q]=\sum_{k}[k=i]dA[k][q]=dA[i][q]\)
设A第\(i\)行加上第\(j\)行\(d\)倍得到的矩阵为\(A_1\)，设\(P_{i,j}\)表示单位矩阵第\(i\)行加上第\(j\)行\(d\)倍得到的矩阵，则\(A_1=P_{i,j}A\)
证明：\(A_1[i][q]=\sum_{k}P[i][k]A[k][q]=\sum_{k}([k=i]A[k][q]+[k=j]d A[k][j])=A[i][q]+dA[j][q]\)
有了这个结论，下面就可以用了。
矩阵逆、秩、行列式
矩阵的逆：\(A\)的逆矩阵（若存在）为\(A^{-1}\)，满足\(AA^{-1}=I\)。
没有逆矩阵的矩阵称为不可逆或是奇异的，反之是可逆或非奇异的
性质：若\(A\)和\(B\)都是可逆的\(n\times n\)矩阵，那么
-
\((AB)^{-1}=B^{-1}A^{-1}\)，证明两边同乘\(AB\)即可
-
\((A^T)^{-1}=(A^{-1})^T\)，证明两边同乘\(A^T\)即可
求逆：
首先，对于方阵来说\(AB=I\)等价于\(BA=I\)。
证明：\(AB=I\Rightarrow B(AB)=B\Rightarrow(BA)B=B\Rightarrow BA=I\)
上面介绍了初等矩阵的知识。假设矩阵\(A\)经过若干次初等行变换得到单位矩阵\(I\)，即：
\(P_1P_2...P_t A=I\)，等价与\(AP_1P_2...P_t =I\)
因为\(AA^{-1}=I\)，所以\(A^{-1}=P_1P_2...P_t\)
高斯消元，一边把\(A\)消成上三角一边对单位矩阵进行同样的操作即可。
参考代码：
const int N = 405;
const int mo = 1e9 + 7;
int n;
struct mat {
int a[N][N];
int *operator [] (int x) { return a[x]; }
void swp(int x, int y) {
for(int i = 1; i <= n; i ++)
swap(a[x][i], a[y][i]);
}
void mul(int x, int y) {
for(int i = 1; i <= n; i ++)
a[x][i] = 1ll * a[x][i] * y % mo;
}
void addk(int x, int y, int k) {
for(int i = 1; i <= n; i ++)
a[x][i] = (a[x][i] + 1ll * k * a[y][i]) % mo;
}
};
int qpow(int a, int b) {
int ans = 1;
for(; b >= 1; b >>= 1, a = 1ll * a * a % mo)
if(b & 1) ans = 1ll * ans * a % mo;
return ans;
}
bool mat_inv(mat &A, mat &ans, int n) {
static int inv[N];
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
ans[i][j] = i == j;
for(int i = 1; i <= n; i ++) {
int j = i;
for(int k = i; k <= n; k ++) {
if(A[k][i]) { j = k; break ; }
}
if(j != i) { A.swp(i, j); ans.swp(i, j); }
if(!A[i][i]) return 0;
inv[i] = qpow(A[i][i], mo - 2);
for(j = i + 1; j <= n; j ++) {
int x = 1ll * A[j][i] * inv[i] % mo;
A.addk(j, i, mo - x); ans.addk(j, i, mo - x);
}
}
for(int i = n; i >= 1; i --) {
for(int j = i + 1; j <= n; j ++) {
ans.addk(i, j, mo - A[i][j]);
A.addk(i, j, mo - A[i][j]);
}
A.mul(i, inv[i]); ans.mul(i, inv[i]);
}
return 1;
}
矩阵的行列式：\(A\)的行列式记为\(\det(A)\)，设\(A_{[i,j]}\)表示\(A\)删除第i行、第j列得到的子矩阵，则：
\(\det(A)=\begin{cases} A_{1,1} ,n=1 \\ \sum_{j=1}^n (-1)^{j+1}A_{1,j}\det(A_{[1,j]}) ,n>1 \\ \end{cases}\)
这个\((-1)^{i+j}a_{i,j}\det(A_{[i,j]})\)称为元素\(a_{i,j}\)的代数余子式
重要性质：这里性质太多，仅提几个
- A可逆当且仅当\(\det(A)\not = 0\)
- 某一行（列）元素的\(k\)倍加到某一行（列）上，\(\det\)不变
- 交换两行（列），\(\det\)变成相反数
- 某行（列）乘\(k\)，\(\det\)乘\(k\)
- 对角矩阵的\(\det\)为主对角线元素的乘积
有了以上性质就可以高斯消元消成对角矩阵求行列式了。
矩阵的秩：一个矩阵\(A\)的秩是\(A\)的线性独立的纵列（或行）的极大数，记为\(r(A),rk(A)\)或\(rank(A)\)
有个结论：是说矩阵\(A\)线性独立的纵列的极大数等于线性独立的行的极大数（行秩=列秩）
原因：每个矩阵都能通过初等变换得到唯一的标准型，行初等变换与列初等变换得到的是相同的标准型，非零行个数就是秩。
矩阵求秩直接消元（注意行、列用两个变量分开记录）
增广矩阵：系数矩阵右边加一列（方程组等号右边的值）
\(n\)元一次方程组的增广矩阵的秩\(rk\)就是主元个数，\(n - rk\)就是自由元个数
高斯消元
高斯消元：消成上三角矩阵；高斯-约旦消元：消成对角矩阵
范围较广，异或方程组、模一个数意义下方程组都能做。
这个大家都会不讲了，丢个代码：（高斯消元）
bool gauss() {
const db eps = 1e-17;
for(int i = 1; i <= n; i ++) {
int j = i;
for(int k = i + 1; k <= n; k ++)
if(fabs(a[k][i]) > fabs(a[j][i])) j = k;
if(j != i) {
for(int k = i; k <= n + 1; k ++) swap(a[j][k], a[i][k]);
}
if(fabs(a[i][i]) < eps) return 0;
for(j = i + 1; j <= n; j ++) {
db z = a[j][i] / a[i][i];
for(int k = i; k <= n + 1; k ++) {
a[j][k] -= z * a[i][k];
}
}
}
for(int i = n; i >= 1; i --) {
for(int j = i + 1; j <= n; j ++)
a[i][n + 1] -= a[j][n + 1] * a[i][j];
a[i][n + 1] /= a[i][i];
}
return 1;
}
下面这部分根据sengxian：线性基学习笔记学习，十分感谢博主。
线性基相关概念
定义向量空间\((F,V,+,\cdot)\)。分别为域、集合、加法、标量乘法。
\(n\)个元素向量组\((v_1,v_2,...,v_n)\)，若存在不全为\(0\)的\(a_i\)满足：
\(a_1 v_1 + a_2 v_2 + ... + a_n v_n = 0\)
称这\(n\)个向量线性相关，否则线性无关
\(a_1 v_1 + a_2 v_2 + ... + a_n v_n\)称为线性组合。
\(n\)个元素的向量组线性无关等价于没有向量能用其他向量的线性组合表示出来。
\(n\)个向量的张成\(\text{span}(v_1,v_2,...,v_n)\)：线性组合构成的集合。
若一个向量组是线性无关的而且能张成向量空间，称这个向量组为向量空间的基。
线性基
OI里的线性基基本上都是二进制异或运算下的，就是把一个数的二进制看成一个向量。
有上三角矩阵和最简行阶梯矩阵两种形式。
（最简行阶梯矩阵：每个非零行第一个非零元素均为1，且所在列其他元素为0。对应这里就是线性基里每个数二进制中最大的1只有自己含有）
一般来说上三角矩阵便于建立，但是其他操作要复杂一点，要讨论当前位的情况。
线性基的建立：（上三角矩阵）
for(int i = 1; i <= n; i ++) {
scanf("%d", a + i);
for(int j = 30; j >= 0; j --) {
if(a[i] & (1 << j)) {
if(!r[j]) {
r[j] = a[i];
break ;
} else {
a[i] ^= r[j];
}
}
}
}
最简行阶梯矩阵：
for(int i = 1; i <= n; i ++) {
scanf("%d", a + i);
for(int j = 30; j >= 0; j --) {
if(a[i] & (1 << j)) {
if(!b[j]) {
b[j] = a[i];
c ++;
for(int k = j - 1; k >= 0; k --) if(b[j] >> k & 1) b[j] ^= b[k];
for(int k = j + 1; k <= 30; k ++) if(b[k] >> j & 1) b[k] ^= b[j];
break ;
}
a[i] ^= b[j];
}
}
}
线性基的trick1：求\(n\)个数选若干个异起来最大
把线性基建出来，然后把所有向量异或起来。证明正确性归纳即可。
线性基trick2：求\(n\)个数选若干个异起来第k大（kth）。（HDU 3949 ）
假设一共n个数，线性基大小为\(m\)（以下都这样记）
若\(m<n\)，则异或和有\(2^m\)（有\(0\)），否则是\(2^m-1\)
二进制表示：\(k=(b_k b_{k-1} ... b_0)_2\)，则答案为\(\text{xor}_{i=0}^k v_i b_i\)
（上三角也可以，但有一些不同）
//rk是除了0以外的排名
ll ans = 0;
for(int i = 0; i < base.size(); i ++)
if(rk >> i & 1) ans ^= base[i];
线性基trick3：求\(n\)个数选若干个异起来值是第几大（rank）。（BZOJ 2844）
和康拓展开之类的差不多，每次假设前i位相等算多少比他小。
//r是线性基（最简行阶梯矩阵）, m是线性基的大小
//q是异或值，ans是除了0以外的排名
for(int i = 30; i >= 0; i --) if(r[i]) {
x ++;
if(q & (1 << i)) {
(ans += 1 << (m - x)) %= mo;
}
}
线性基trick4：线性基的合并。
往往题目的线性基都是二进制异或线性基，大小log级别，暴力插入即可。