初探线性代数

参考资料：

Oi Wiki
command_block：线性基小记
 Alex_Wei：线性代数相关

向量相关

其实是高中数学来着。

向量

既有大小又有方向的量称为向量。数学上研究的向量为自由向量，即只要不改变它的大小和方向，起点和终点可以任意平行移动的向量，换句话说，我们研究中不关心向量的起点和终点。向量 $\vec{a}$ 记作 $\vec{a}$（\vec{a}）或 $\boldsymbol{a}$（\boldsymbol{a}）。为了更方便辨认，本文会尽量使用 $\vec{a}$ 代表向量。
向量的坐标表示

对于一个 $k$ 维向量，若将其起点移到坐标原点，那么终点显然是唯一确定的，故我们可以用终点坐标 $(x,y)$ 表示向量 $\vec{a}$，显然 $k$ 维向量和 $k$ 元有序实数组能建立双射。
向量的模长

即向量的长度，记作 $|\vec{a}|$，对于 $k$ 维向量 $a$，若坐标表示为 $(p_1,p_2,\cdots,p_k)$，有 $|\vec{a}|=\sqrt{\sum_{i=1}^kp_i^2}$。
单位向量和 $\vec{0}$ 向量

单位向量，即模为 $1$ 的向量，通常记为 $\vec{e}$。同理零向量即模为 $0$ 的向量，记为 $\vec{0}$。
相反向量

对于 $\vec{a}$，我们称和它模相同，方向相反的向量为相反向量，显然相反向量 $\vec{a}'=(-p_1,-p_2,\cdots,-p_k)$
平行向量/贡献向量

若两向量方向相同或相反，则称两向量平行。并且由于我们不关注向量的位置，所以我们也称两向量共线。
向量的加减法

几何意义是将两个向量同时作用于一点可以得到一个新的向量，即两向量首尾相连，然后从前者的起点连向后者的终点。

减法即加上对应向量的相反向量。

对于坐标表示，向量相加即每一位分别相加，即 $(a_1,a_2,\cdots,a_k)+(b_1,b_2,\cdots,b_k)=(a_1+b_1,a_2+b_2,\cdots,a_k+b_k)$。
向量的数乘

和普通的乘法定义相同，$x\vec{a}$ 相当于 $x$ 个 $a$ 加在一起，有 $x(a_1,a_2,\cdots,a_k)=(xa_1,xa_2,\cdots,xa_k)$。
平面向量基本定理

定理内容：如果两个向量 $\vec{e_1},\vec{e_2}$ 不共线，那么存在唯一实数对 $(x,y)$，使得与 $\vec{e_1},\vec{e_2}$ 共面的任意向量 $\vec{p}$ 满足 $\vec{p}=x\vec{e_1}+y\vec{e_2}$。

这也是向量的坐标表示的理论依据。事实上，向量的坐标表示 $(x,y)$ 本质上就是取一对互相垂直的单位向量 $\vec{e_1},\vec{e_2}$ 得到 $x\vec{e_1}+y\vec{e_2}$。

我们称这样不共线的一对向量叫基，事实上，任意一对不共线的向量都能叫基。
向量内积

对于任何维度的向量，均有定义向量内积，因为符号是点 $\cdot$（\cdot），所以通常俗称为点积/点乘。

具体来说若 $\vec{a}=(a_1,a_2,\cdots,a_k),\vec{b}=(b_1,b_2,\cdots,b_k)$，则记 $\vec{a}\cdot \vec{b}=a_1b_1+a_2b_2+\cdots+a_kb_k$，显然我们得到的应该是一个实数。

注意这个 $\cdot$ 符号不能省去。

矩阵相关

我认为矩阵是线性代数的灵魂，因为任何线性变换都能概括为矩阵，并且有一大车证明都得用上矩阵。

定义与符号

矩阵

大小为 $n\times m$ 的矩阵即 $n$ 行 $m$ 列元素排列在一起，或许可以视作 $m$ 个 $n$ 维列向量（或者 $n$ 个 $m$ 维列向量）排列在一起。
同型矩阵

若两矩阵行列数相同，则称两个矩阵为同型矩阵。
方阵

行数等于列数的矩阵称为方阵，方阵是一种特殊的矩阵，大部分人（其实包括我）常说的“$n$ 阶矩阵”指的就是 $n$ 阶方阵，显然，阶数相同的方阵是同型矩阵。

研究方程组、向量组、矩阵的秩的时候，使用一般的矩阵。研究特征值和特征向量、二次型的时候，使用方阵。根据我的体感，OI 范围内方阵使用的较多，平时谈到矩阵通常会默认是方阵。
主对角线

方阵中行编号等于列编号的元素构成主对角线，即从左上到右下的对角线。
对称矩阵

如果方阵的元素关于主对角线对称，即对于任意的 $i$ 和 $j$，$i$ 行 $j$ 列的元素与 $j$ 行 $i$ 列的元素相等，则将方阵称为对称矩阵。
对角矩阵

主对角线之外所有元素均为 $0$ 的矩阵为对角矩阵，可记作 $\mathrm{diag}\begin{Bmatrix}\lambda_1,\lambda_2,\dots,\lambda_m\end{Bmatrix}$，表示主对角线上的元素。
单位矩阵

对角矩阵 $\mathrm{diag}\begin{Bmatrix}1,1,\dots,1\end{Bmatrix}$ 为单位矩阵，记作 $I$，关于为什么它叫单位矩阵暂且按下不表。
三角矩阵

如果方阵主对角线左下方的元素均为 $0$，称为上三角矩阵。如果方阵主对角线右上方的元素均为 $0$，称为下三角矩阵。

两个上（下）三角矩阵的乘积仍然是上（下）三角矩阵。如果对角线元素均非 $0$，则上（下）三角矩阵可逆，逆也是上（下）三角矩阵。对于矩阵的逆我们稍后再谈。
单位三角矩阵

如果上三角矩阵 $A$ 的对角线全为 $1$，则称 $A$ 是单位上三角矩阵。如果下三角矩阵 $A$ 的对角线全为 $1$，则称 $A$ 是单位下三角矩阵。

两个单位上（下）三角矩阵的乘积仍然是单位上（下）三角矩阵，单位上（下）三角矩阵的逆也是单位上（下）三角矩阵。

运算

矩阵的线性运算

矩阵的线性运算分为加减法与数乘，它们均为逐个元素分别进行。只有同型矩阵之间可以对应相加减。
矩阵的转置

记 $A^{T}$ 表示 $A$ 的转置矩阵，形式化地，$A^{T}{i,j}=A{j,i}$。
矩阵乘法

据 OIWiki 所说，矩阵乘法的概念源自于线性方程组。

对于一个线性方程组：

$$ \begin{cases} a_{1,1}x_1+a_{1,2}x_2+a_{1,3}x_3=b_1\\ a_{2,1}x_1+a_{2,2}x_2+a_{2,3}x_3=b_2\\ a_{3,1}x_1+a_{3,2}x_2+a_{3,3}x_3=b_3 \end{cases} $$

容易发现它看起来非常像一个向量分别与三个向量点积得到三个实数。具体来说，设 $\vec{x}=(x_1,x_2,x_3)$，上面的方程组等价于：

$$ \begin{cases} (a_{1,1},a_{1,2},a_{1,3})\cdot \vec{x}=b_1\\ (a_{2,1},a_{2,2},a_{2,3})\cdot \vec{x}=b_2\\ (a_{3,1},a_{3,2},a_{3,3})\cdot \vec{x}=b_3 \end{cases} $$

因为我们认为矩阵是对向量的打包，所以先人设计了这么一个表示方式：

$$ \begin{pmatrix} a_{1,1},&a_{1,2},&a_{1,3}\\ a_{2,1},&a_{2,2},&a_{2,3}\\ a_{3,1},&a_{3,2},&a_{3,3} \end{pmatrix} \begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix}= \begin{pmatrix} b_1\\ b_2\\ b_3 \end{pmatrix} $$

简记为 $A\vec{x}=\vec{b}$。

形式化的，对于一个 $n$ 行 $x$ 列的矩阵 $A$ 和一个 $x$ 行 $m$ 列的矩阵 $B$，我们定义 $A\times B$（此处乘号可以省去）得到一个 $n$ 行 $m$ 列的矩阵 $C$，则有 $C_{i,j}=\sum_{k=1}^xA_{i,k}\times B_{k,j}$，相当于把 $A$ 的第 $i$ 行拉出来和 $B$ 的第 $j$ 列进行点乘，将结果填到 $C_{i,j}$ 中。

容易发现这个 $B$ 可以是一个列向量（我们称只有一列的矩阵为列向量），$A$ 可以是一个行向量，这样我们也定义了向量与矩阵的乘法。
矩阵的逆

容易发现，对于任何方阵 $A$，均有 $A\times I=A$。所以 $I$ 是矩阵乘法的单位元，于是我们定义方阵 $A$ 的逆矩阵 $A^{-1}$ 表示 $AA^{-1}=I$，方阵不一定存在逆，但若存在就可以高斯消元求出。
矩阵嵌套

注意到矩阵的元素也能是矩阵，但是这里我要提的不是这种。这里提这个算是一种约定符号吧。

为了方便表述，我在矩阵 $A$ 中使用其它矩阵 $B$ 意味着“这个矩阵 $A$ 的某一部分和 $B$ 一样”。

比如 $\begin{pmatrix}I_2&\\ & 0\end{pmatrix}$ 代表 $\begin{pmatrix}1&0&0\\ 0 &1 &0\\ 0&0&0\end{pmatrix}$，其中空置部分默认为全 $0$ 矩阵。
矩阵等价

这个其实不应该放在这里，但是我找不到地方塞了。请阅读完“线性无关组，秩”这一节再回过来看。

若矩阵 $A$ 能通过矩阵 $B$ 进行若干次初等变换得到，则称 $A,B$ 等价。

一个等价的定义是若存在两可逆矩阵 $P,Q$，满足 $A=PBQ$，则称矩阵 $A,B$ 等价。

容易发现两矩阵等价当且仅当秩相同。

矩阵乘法的性质

矩阵乘法满足不少数乘的性质，这使得矩阵乘法能有助于解决一些实际问题。

结合律

矩阵乘法具有结合律。即 $A(BC)=(AB)C$。此处我们不妨设三个矩阵分别为 $x\times n,n\times y,y\times m$。暴力拆开可得：

$$ \begin{aligned} &((AB)C)_{i,j}\\ =&\sum_{k=1}^{y}(AB)_{i,k}C_{k,j}\\ =&\sum_{k=1}^{y}\left(\sum_{p=1}^nA_{i,p}\times B_{p,k}\right)C_{k,j}\\ =&\sum_{k=1}^{y}\sum_{p=1}^nA_{i,p}\times B_{p,k}\times C_{k,j} \end{aligned} $$

容易发现另一种拆法也能得到相同的结果。

注意到第二步到第三步用了乘法结合律和乘法对加法的分派率。并且整个过程均依赖于乘法和加法的交换律。事实上，任何满足以上性质的两种运算组成的广义矩阵乘法都具有结合律，但这是后话了。
交换律

显然，矩阵乘法没有交换律。
分配律

由于矩阵乘法没有交换律，所以分配律要分左分配律和右分配律考虑。即分别考虑 $C(A+B)=CA+CB$ 和 $(A+B)C=AC+BC$。

证明还是暴力拆，此处就略过了。
对数乘的结合律

$k(AB)=(kA)B=A(kB)$，证明还是暴力拆。
转置

$(AB)^T=B^TA^T$，暴力拆开即可。

矩阵乘法的应用

通常应用的比较多的还是结合律，因为很多主流数据结构（比如说最经典的线段树和平衡树，甚至是快速幂）都要求维护的元素具有结合律。

矩阵快速幂加速递推

以矩阵乘法典中典之斐波那契数列加速递推为例。

注意到斐波那契数的每一项只和前两项有关，所以我们可以把斐波那契数列的相邻两项用一个向量表示成一个状态。

设一个待定矩阵（此处指方阵，后文应该会频繁出现矩阵方阵混用的情况）$B$，那么我们需要构造矩阵 $B$，使得 $(f_{i-1},f_{i})\times B=(f_{i},f_{i+1})=(f_{i},f_{i-1}+f_{i})$。

容易构造出 $B=\begin{pmatrix}0,&1\\1,&1\end{pmatrix}$。

那么我们可以发现 $f_n(n\ge 1)$ 就是 $(1,1)\times B^{n-1}$ 的前一项。因为矩阵乘法具有结合律，所以 $B^{n-1}$ 可以使用矩阵快速幂求得。

模板题需要将答案对 $10^9+7$ 取模，这里给出参考代码。

参考代码

const i64 mod=1e9+7;
struct Matrix{
    i64 c[2][2];
    Matrix(bool p=0){
        mem(c,0);
        c[0][0]=c[1][1]=p;
    }
    Matrix operator *(const Matrix &r){
        Matrix res;
        forup(i,0,1){
            forup(j,0,1){
                forup(k,0,1){
                    (res.c[i][j]+=1ll*c[i][k]*r.c[k][j]%mod)%=mod;
                }
            }
        }
        return res;
    }
};
Matrix ksm(Matrix a,i64 b){
    Matrix c(1);
    while(b){
        if(b&1) c=c*a;
        a=a*a;
        b>>=1;
    }
    return c;
}
i64 n;
signed main(){
    n=read();
    Matrix tr(0),bs(0);
    tr.c[0][1]=tr.c[1][0]=tr.c[1][1]=1;
    bs.c[0][0]=bs.c[0][1]=1;
    bs=bs*ksm(tr,n-1);
    printf("%lld\n",bs.c[0][0]);
}

矩阵表达修改

考虑 OIWiki 引用的 P7453 [THUSCH2017] 大魔法师

容易发现不太好直接用线段树维护 $A_i\gets A_i+B_i$ 之类的操作，因为很难维护懒标记。这种时候就可以考虑用矩阵维护。

具体来说，用一个向量 $(A_i,B_i,C_i,1)$ 代表点 $i$ 的信息（套路地，因为修改中有加一个常数，所以还需要再维护一个常数），

然后容易构造六种操作的矩阵，就在单位矩阵的基础上修改一下即可，分别为：

$$ \begin{aligned} B_1=\begin{pmatrix}1,&0,&0,&0\\ 1,&1,&0,&0\\ 0,&0,&1,&0\\ 0,&0,&0,&1\end{pmatrix}\\ B_2=\begin{pmatrix}1,&0,&0,&0\\ 0,&1,&0,&0\\ 0,&1,&1,&0\\ 0,&0,&0,&1\end{pmatrix}\\ B_3=\begin{pmatrix}1,&0,&1,&0\\ 0,&1,&0,&0\\ 0,&0,&1,&0\\ 0,&0,&0,&1\end{pmatrix}\\ B_4=\begin{pmatrix}1,&0,&0,&0\\ 0,&1,&0,&0\\ 0,&0,&1,&0\\ v,&0,&0,&1\end{pmatrix}\\ B_5=\begin{pmatrix}1,&0,&0,&0\\ 0,&v,&0,&0\\ 0,&0,&1,&0\\ 0,&0,&0,&1\end{pmatrix}\\ B_6=\begin{pmatrix}1,&0,&0,&0\\ 0,&1,&0,&0\\ 0,&0,&0,&0\\ 0,&0,&v,&1\end{pmatrix}\\ \end{aligned} $$

每次修改区间乘一个矩阵即可，注意到矩阵乘法对向量（矩阵）加有分配律，所以区间乘矩阵是正确的。

参考代码

const int N=2.5e5+5,mod=998244353;
int n,m,a[N],b[N],c[N];
struct Matrix{
    int c[4][4];
    Matrix(int p=0){
        mem(c,0);
        forup(i,0,3) c[i][i]=p;
    }
    bool isI(){
        forup(i,0,3){
            forup(j,0,3){
                if(i==j){
                    if(c[i][j]!=1) return false;
                }else{
                    if(c[i][j]) return false;
                }
            }
        }
        return true;
    }
    Matrix operator*(const Matrix &r){
        Matrix res;
        forup(i,0,3){
            forup(k,0,3){
                int v=c[i][k];
                forup(j,0,3){
                    (res.c[i][j]+=1ll*v*r.c[k][j]%mod)%=mod;
                }
            }
        }
        return res;
    }
};
struct Vector{
    int c[4];
    Vector(){mem(c,0);}
    Vector operator+(const Vector &r){
        Vector res;
        forup(i,0,3){
            res.c[i]=(c[i]+r.c[i])%mod;
        }
        return res;
    }
    Vector operator*(const Matrix &r){
        Vector res;
        forup(k,0,3){
            int v=c[k];
            forup(j,0,3){
                (res.c[j]+=1ll*v*r.c[k][j]%mod)%=mod;
            }
        }
        return res;
    }
};
struct SegTree{
    #define mid ((l+r)>>1)
    #define lson l,mid,id<<1
    #define rson mid+1,r,id<<1|1
    Vector sum[N<<2];
    Matrix mark[N<<2];
    void PushUp(int id){
        sum[id]=sum[id<<1]+sum[id<<1|1];
    }
    void PushDown(int id){
        if(mark[id].isI()) return;
        sum[id<<1]=sum[id<<1]*mark[id];
        mark[id<<1]=mark[id<<1]*mark[id];
        sum[id<<1|1]=sum[id<<1|1]*mark[id];
        mark[id<<1|1]=mark[id<<1|1]*mark[id];
        mark[id]=Matrix(1);
    }
    void Build(int l=1,int r=n,int id=1){
        mark[id]=Matrix(1);
        if(l==r){
            sum[id].c[0]=a[l];
            sum[id].c[1]=b[l];
            sum[id].c[2]=c[l];
            sum[id].c[3]=1;
            return;
        }
        Build(lson);Build(rson);
        PushUp(id);
    }
    void Update(int L,int R,const Matrix &X,int l=1,int r=n,int id=1){
        if(L<=l&&r<=R){
            sum[id]=sum[id]*X;
            mark[id]=mark[id]*X;
            return;
        }
        PushDown(id);
        if(L<=mid) Update(L,R,X,lson);
        if(mid< R) Update(L,R,X,rson);
        PushUp(id);
    }
    Vector Query(int L,int R,int l=1,int r=n,int id=1){
        if(L<=l&&r<=R){
            return sum[id];
        }
        PushDown(id);
        Vector res;
        if(L<=mid) res=res+Query(L,R,lson);
        if(mid< R) res=res+Query(L,R,rson);
        return res;
    }
}mt;
signed main(){
    n=read();
    forup(i,1,n){
        a[i]=read();b[i]=read();c[i]=read();
    }
    mt.Build();
    m=read();
    forup(i,1,m){
        int op=read(),l=read(),r=read();
        if(op<7){
            Matrix tr(1);
            if(op==1){
                tr.c[1][0]=1;
            }else if(op==2){
                tr.c[2][1]=1;
            }else if(op==3){
                tr.c[0][2]=1;
            }else{
                int v=read();
                if(op==4){
                    tr.c[3][0]=v;
                }else if(op==5){
                    tr.c[1][1]=v;
                }else{
                    tr.c[3][2]=v;
                    tr.c[2][2]=0;
                }
            }
            mt.Update(l,r,tr);
        }else{
            Vector rr=mt.Query(l,r);
            printf("%d %d %d\n",rr.c[0],rr.c[1],rr.c[2]);
        }
    }
}

定长路径统计

考虑这样一个问题。

给一个 $n$ 阶有向图，每条边的边权均为 $1$，然后给一个整数 $k$，你的任务是对于所有点对 $(u,v)$ 求出从 $u$ 到 $v$ 长度为 $k$ 的路径的数量（不一定是简单路径，即路径上的点或者边可能走多次）。

不妨用邻接矩阵存图，显然邻接矩阵 $G$ 就是 $k=1$ 的答案。

容易想到 DP，设 $f_{k,u,v}$ 表示是否存在一条长度为 $k$，从 $u$ 到 $v$ 的路径，那么转移即为：

$$ f_{k+1,u,v}=\sum_{p=1}^nf_{k,u,p}\times G_{p,v} $$

容易发现这个就是矩阵乘法的形式，可以写成：

$$ f_{k+1}=f_k\times G $$

于是矩阵快速幂优化即可，可以做到 $O(n^3\log k)$。

结合前文提到的广义矩阵还能求出包含恰好 $k$ 条边的最短路，这个可以参考 OiWiki，此处不过多展开。

行列式

行列式是对方阵的一种运算，对于方阵 $A$，记 $\det A$ 表示 $A$ 的行列式。

同时，我们记

$$ \det A=\begin{vmatrix} A_{1,1} &A_{1,2} &\cdots &A_{1,n}\\ A_{2,1} &A_{2,2} &\cdots &A_{2,n}\\ \vdots &\vdots &\ddots &\vdots\\ A_{n,1} &A_{n,2} &\cdots &A_{n,n} \end{vmatrix} $$

定义

记 $\pi(p_1,p_2,\dots,p_n)$ 表示排列 $p_1,p_2,\dots p_n$ 的逆序对数。

$n$ 阶矩阵的行列式是从每一行每一列各选一个元素得到的 $n!$ 种乘积（乘上一个 $\pm 1$ 系数）的代数和。

具体来说，对于 $\prod_{i=1}^n a_{i,p_i}$（此处 $p_i$ 是一个排列）这一项，它的系数是 $(-1)^{\pi(p_i)}$。也就是说，若 $p_i$ 是一个偶排列，那么系数为 $+1$，否则系数为 $-1$。

形式化地，$\det A=\sum_{p}(-1)^{\pi(p)}\prod_{j=1}^nA_{j,p_j}$。

初等变换

对于任何矩阵（不限于方阵），我们定义了初等行变换和初等列变换，统称为初等变换。此处我们先说初等行变换（因为初等列变换是类似的）。

初等行变换有三种，分别是倍乘，对换，倍加。

倍乘：第 $i$ 行全部乘非 $0$ 整数 $k$。
对换：将第 $i$ 行和第 $j$ 行互换。
倍加：将第 $j$ 行全部乘 $k$，依次加到第 $i$ 行。

将上述操作的行改为列即为初等列变换。

初等矩阵

容易发现初等行变换均为线性变换，故可以用矩阵乘法概括，我们称这样的矩阵为初等矩阵。

倍乘矩阵

即乘这个矩阵等于进行一次倍乘。

倍乘矩阵是一种特殊的对角矩阵，记：

$$ D_i(k)=\mathrm{diag}\begin{Bmatrix}1,1\dots 1,k,1\dots 1\end{Bmatrix} $$

即单位矩阵的第 $i$ 行 $i$ 列改为 $k$。

容易发现，矩阵左乘倍乘矩阵相当于进行一次初等行变换，右乘相当于初等列变换。

显然，单位矩阵是一种特殊的倍乘矩阵。
对换矩阵

对换矩阵是一种特殊的对称矩阵。

$$ P_{ij}=\begin{pmatrix} I_{i-1} & & & & \\ & 0 & & 1 & \\ & & I_{j-i-1} & & \\ & 1 & & 0 & \\ & & & & I_{n-j}\\ \end{pmatrix} $$

即主对角线上只有 $i,j$ 为 $0$，但是 $(i,j),(j,i)$ 为 $1$。

同样地，矩阵左对换乘矩阵相当于进行一次初等行变换，右乘相当于初等列变换。
倍加矩阵

倍加矩阵 $T_{i,j}(k)$ 是在单位矩阵的基础下，将 $i$ 行 $j$ 列设为 $k$。

$$ T_{ij}(k)=\begin{pmatrix} 1 & & & & & & \\ & \ddots & & & & & \\ & & 1 & \cdots & k & & \\ & & & \ddots & \vdots & & \\ & & & & 1 & & \\ & & & & & \ddots & \\ & & & & & & 1\\ \end{pmatrix} $$

倍加矩阵要求 $i$ 与 $j$ 不能相等。如果 $k$ 为 $0$，则 $T_{ij}(0)$ 退化为单位矩阵 $I$。

显然地，倍加矩阵是一种上三角矩阵或者下三角矩阵。

行列式的性质

猜猜为什么要隔着个初等矩阵。

定理 $1$：三角矩阵的行列式是主对角线的乘积

根据行列式的定义，考虑一个排列 $p$。

注意到对于上三角矩阵，若 $p_i < i$ 则 $A_{i,p_i}=0$，对于下三角也是同理。

那么只要存在 $p_i\ne i$，行列式种对应项均为 $0$。换句话说，只有 $p_i=i$ 这一个排列能对行列式产生贡献。又由于 $\pi(p)=0$，所以系数为 $+1$。
定理 $2$：单位矩阵 $I$ 的行列式为 $1$。

由定理 $1$ 易得。
定理 $3$：两矩阵乘积的行列式等于两矩阵行列式的乘积

考虑拆式子。

$$ \begin{aligned} &\det(A)\det(B)\\ =&\left(\sum_{p}(-1)^{\pi(p)}\prod_{i=1}^nA_{i,p_i}\right)\times \left(\sum_{q}(-1)^{\pi(q)}\prod_{i=1}^nB_{i,q_i}\right)\\ =&\sum_{p}\sum_{q}(-1)^{\pi(p)+\pi(q)}\prod_{i=1}^nA_{i,p_i}\prod_{i=1}^nB_{i,q_i}\\ \end{aligned} $$

考虑一个排列 $h_i$，使得 $h_i=q_{p_i}$，则上式可化为：

$$ \begin{aligned} &\sum_{q}\sum_{p}(-1)^{\pi(p)+\pi(q)}\prod_{i=1}^nA_{i,p_i}B_{p_i,h_i}\\ \end{aligned} $$

容易发现 $\prod$ 中连乘的东西来自 $AB$ 矩阵的不同元素 $(AB)_{i,h_i}$，并且显然固定 $i,h_i$ 时中间的 $p_i$ 是可以取遍全排列的，即从 $AB$ 每一行每一列的 $n$ 个 $A_{i,k}\times B_{k,j}$ 中各选一个相乘。

考虑从另一边化一下：

$$ \begin{aligned} &\det(AB)\ =&\sum_{h}(-1)^{\pi(h)}\prod_{i=1}^n(AB)_{i,h_i}\\ =&\sum_{h}(-1)^{\pi(h)}\prod_{i=1}^n\sum_{k=1}^nA_{i,k}B_{k,h_i}\\ =&\sum_{h}\sum_{s}(-1)^{\pi(h)}\prod_{i=1}^nA_{i,s_i}B_{s_i,h_i}\\ \end{aligned} $$

这里的序列 $s$ 是可以取遍所有长度为 $n$ 值域为 $n$ 的所有序列。但是注意到一个“长度为 $n$ 值域为 $n$ 的序列”不是“排列”当且仅当有两个数相同，考虑若有两个数相同会发生什么事。

假设 $s_a=s_b$，那么它就会影响两项 $A_{a,s_a}B_{s_a,h_a}$ 和 $A_{b,s_b}B_{s_b,h_b}$。但是假如我们交换 $h_a,h_b$（显然这个排列也是会被枚举到的），容易发现后面 $\prod$ 的值并未改变，注意到对任何一个排列进行任何一次交换都会改变 $\pi$ 的奇偶性，所以 $(-1)^{\pi(h)}$ 的正负性改变，那么这个 $s$ 的贡献就抵消了。

以上，我们证明了这一项会产生贡献当且仅当 $s$ 是一个排列。也就是说，我们只要证明 $\pi(q)+\pi(q)\equiv \pi(h)\pmod{2}$ 即可证明上面两式相等。

考虑 $h_i=q_{p_i}$ 是怎么得到的，相当于先把排列 $q$ 摆出来，然后在 $q_i$ 的右下角打一个标记 $i$，接下来进行若干次交换让下标的顺序变成 $p_i$。

由于对任何一个排列进行任何一次交换都会改变 $\pi$ 的奇偶性，既然下标的从偶数变成了 $p$ 的奇偶性，那么 $q$ 的奇偶性必定也产生了同样的变化，于是有 $\pi(q)+\pi(q)\equiv \pi(h)\pmod{2}$。

这个证明感谢 @grass8cow 的帮助。
定理 $4,5,6$：

考虑初等矩阵的行列式。

根据定理 $1$，容易得到倍乘矩阵和倍加矩阵的行列式分别是 $\det D_i(k)=k,\det T_{i,j}(k)=1$。

根据行列式的定义，又容易得到对换矩阵 $\det P_{i,j}=-1$。

故我们能得到：
- 定理 $4$：一个矩阵交换两行/两列行列式乘 $-1$。
- 定理 $5$：一个矩阵某一行乘以 $k$ 行列式乘 $k$。
- 定理 $6$：一个矩阵第 $i$ 行加上第 $j$ 行的 $k$ 倍行列式不变。
定理 $7$：一个矩阵若两行/列相同行列式为 $0$

交换这两行，矩阵没有变化，但是行列式变为 $-1$，于是 $-\det A=\det A$，得到 $\det A=0$。
定理 $8$：若矩阵两行/列有倍数关系行列式为 $0$

考虑进行一个倍乘，然后就变成定理 $7$ 了。
定理 $9$：若矩阵有某一行/列全为 $0$ 行列式为 $0$。

我能想到一堆做法，留给读者自行思考（你会发现有了定理 $4,5,6$ 后定理 $7,8,9$ 都有一堆证法）。

高斯消元

我觉得我需要在这里提一下高斯消元，因为后面的证明我实在想不到更简单的方法了。

我们之前提过线性方程组，高斯消元就是用来求解线性方程组的。

具体来讲，高斯消元是用来求解形如：

$$ \begin{cases} a_{1,1}x_0+a_{1,1}x_1+\cdots+a_{1,m}x_{m}=b_1\\ a_{2,1}x_0+a_{2,1}x_1+\cdots+a_{2,m}x_{m}=b_2\\ \vdots\\ a_{n,1}x_0+a_{n,2}x_1+\cdots+a_{n,m}x_{m}=b_{n} \end{cases} $$

的线性方程组的算法。

算法流程

注意到解方程时未知数并不参与运算，所以我们可以将系数写成矩阵的形式。

不妨设 $a_{i,m+1}=b_i$，得到一个新的矩阵，我们称这个矩阵是该线性方程组的增广矩阵。

高斯消元的过程就是使用矩阵的初等行变换将增广矩阵化为行最简形。（事实上还需要考虑无解和无数解的情形，但我感觉 OI 一般不考这个，最多让你判断一下）

那么什么是行最简形呢？在三角矩阵中（通常我们会化为上三角矩阵），若非零行的第一个非零元素全是 $1$，且非零行的第一个元素 $1$ 所在列的其余元素全为零，就称该矩阵为行最简形矩阵。

那么为什么用初等行变换将矩阵化为最简形就能求出线性方程组的解呢？我们回到线性方程组来看，容易发现任何一个初等变换都不会改变方程组的解（因为右方的 $b_i$ 作为增广矩阵的一部分也参与了运算），而行最简形就是方程组的最简形式了。容易发现若方程组有唯一解，那么行最简形的前 $m$ 行（除去 $b_i$ 外）其实就是单位矩阵，显然解就是第 $m+1$ 列。

那么具体怎么做呢？

记已经处理好的方程个数为 $r$，再枚举未知数 $c$ 作为主元。
找到 $j\in[r+1,n]$，使得 $a_{j,c}$ 非 $0$。
若找不到，则处理下一个未知数 $c$，否则将第 $r+1$ 行和第 $j$ 行交换。
对第 $r+1$ 行进行一个倍乘使得 $a_{r+1,c}=1$
对 $r+1\sim n$ 行加上第 $r+1$ 行的 $k$ 倍，使得所有大于 $r+1$ 的行第 $c$ 列均为 $0$。

这样我们就能得到一个上三角矩阵，但这并不是行最简形，因为每次 $1\sim r$ 行的第 $c$ 列仍有可能非 $0$。

容易发现，若 $r=m$，且所有大于 $m$ 的行均全 $0$，则方程有唯一解（此时），否则方程无解或无数解，无解当且仅当某一行 $a_{i,1}\sim a_{i,m}$ 均为 $0$ 但 $a_{i,m+1}$ 非 $0$。其余情况就是无数解了。

若方程有解，那么我们只需要保留矩阵的前 $m$ 行，因为后面必定全 $0$。

然后从 $m$ 到 $1$ 枚举 $i$，每次用第 $i$ 行（注意到因为从 $m$ 开始枚举，所以这一行除去自由元以外只有第 $i$ 个非 $0$）将其余行的第 $i$ 列全部消为 $0$ 即可得到行最简形矩阵。

应用

感觉高消的应用其实挺广泛的。

线性方程组求解。

显然。
行列式求值。

注意到三角矩阵的行列式是好算的，初等矩阵的行列式是已知的。那么我们通过初等变换将矩阵 $A$ 转化为上三角矩阵 $A'$，算出 $A'$ 的行列式即可简单算出 $A$ 的行列式
矩阵求逆

详见后文。

可逆矩阵

我们之前提到了矩阵的逆。还提到了一部分矩阵可逆一部分矩阵不可逆。

具体来说，对于一个矩阵 $A$，若存在矩阵 $B$ 满足 $AB=BA=I$，则称矩阵 $A$ 可逆，并且记 $B$ 为 $A^{-1}$。

首先我们需要证明一个看起来好像很显然的东西，若 $AB=I$，则 $BA=I$（即矩阵 $A$ 的左逆和右逆是相同的）。

证明

假设 $A$ 的左逆和右逆不同，即存在两个不同的矩阵 $B,B'$，满足 $B'A=AB=I$。

那么显然，$B=IB=B'AB=B'I=B'$，与“$B$ 和 $B'$ 不同”矛盾。

然后是一些显然的性质：

可逆矩阵的逆矩阵也可逆。
可逆矩阵的转置也可逆，并且转置的逆就是逆的转置。
$A,B$ 均可逆 $\Rightarrow$ $AB$ 可逆（并且 $AB$ 的逆是 $B^{-1}A^{-1}$）。
初等矩阵均可逆，并且逆矩阵和自己是同类型的初等矩阵，比如倍乘矩阵的逆也是倍乘矩阵，构造是简单的。

那么如何判断矩阵可逆呢？

定理：矩阵可逆当且仅当行列式非 $0$。
- 矩阵可逆 $\to$ 行列式非 $0$：
  
  因为矩阵 $A$ 可逆，所以存在 $AA'=I$。
  
  故 $\det(A)\det(A')=\det(I)=1$，则 $\det A$ 非 $0$。
- 行列式非 $0$ $\to$ 矩阵可逆
  
  若 $\det A\ne 0$，则 $A$ 必然能由若干个初等矩阵相乘得到。
  
  因为进行一次初等变换等价于乘一个初等矩阵，所以假如我们能构造出从 $I$ 初等变换到 $A$ 的方案即可证明上述引理。
  
  一个平凡构造是，考虑高斯消元的过程。因为矩阵行列式非 $0$，并且初等矩阵行列式非 $0$，所以进行若干次初等变换（乘初等矩阵）后得到的行最简矩阵行列式也非 $0$，那么这个行最简矩阵必定是单位矩阵。即存在若干个初等矩阵，使得该矩阵和这些矩阵的乘积是单位矩阵，这是什么意思？即存在 $P$ 使得 $A\times P=I$，换言之，矩阵可逆。

然后矩阵求逆就简单了，对原矩阵进行高斯消元（因为矩阵可逆所以必定能消成单位矩阵 $I$），把中途的所有初等矩阵乘起来即可。

线性空间

坏了，抽象代数打过来了。

前置知识：阿贝尔群，域。

通俗地讲，一个集合关于某运算封闭，满足结合律、单位元与逆元则构成群。如果还满足交换律，则构成阿贝尔群。

如果一个集合关于四则运算封闭，则构成域。相关定义详见OiWiki 群论简介。

定义

线性空间是 $d$ 维欧氏空间 $(0\le d\le 3)$ 等的推广，为方便理解或许我们可以先带着二维或三维空间的概念来看问题。

线性空间（向量空间）是线性代数的基本概念与重要研究对象。线性空间是由向量集合 $V$、域 $\mathbb{P}$、向量加法运算 $+$ 和数乘组成的模类代数结构。

具体来说，设 $(V,+)$ 是一个阿贝尔群，$\mathbb{P}$ 是一个域。（为了方便理解，我们可以暂时认为 $V$ 是某 $k$ 维向量集合，只定义了向量加，$\mathbb{P}$ 是实数域）。

定义 $\mathbb{P}$ 中的数与 $V$ 中元素的代数运算，称为数乘，即 $\mathbb{P} \times V\to V$，记为 $p\cdot \mathbf{v}$ 或 $p\mathbf{v}$，其中 $p\in \mathbb{P},\mathbf{v}\in V$。我们称这个运算为数乘，要求该数乘运算是封闭的，运算结果始终有意义，也在群 $V$ 中。且满足以下条件：

为方便叙述，我们称阿贝尔群 $(V,+)$ 中的加法为向量加法，域 $\mathbb{P}$ 中的四则运算为标量加减乘除。

数乘对向量加法有分配律，即对于 $\mathbf{u},\mathbf{v}\in V,p\in \mathbb{P},p\mathbf{u}+p\mathbf{v}=p(\mathbf{u}+\mathbf{v})$。
数乘对标量加法有分配律，即对于 $p,q\in \mathbb{P},\mathbf{v}\in V,q\mathbf{v}+p\mathbf{v}=(q+p)\mathbf{v}$。
数乘有结合律，即对于 $\mathbf{v}\in V,p,q\in\mathbb{P},p(q\mathbf{v})=(pq)\mathbf{v}$。
标量乘法具有单位元，即存在 $e\in \mathbb{P}$，使得 $\forall p\in\mathbb{P},pe=p$。

则称代数系统 $(V,+,\cdot,\mathbb{P})$ 是 $V$ 关于 $+,\cdot$ 构成 $\mathbb{P}$ 上的一个线性空间（注意这句话的主语是 $V$，即线性空间只针对那个阿贝尔群），$\mathbb{P}$ 为线性空间的基域，$V$ 中元素称为向量，$\mathbb{P}$ 中元素称为标量。当域 $\mathbb{P}$ 为实数域时，称为实线性空间。当域 $\mathbb{P}$ 为复数域时，称为复线性空间。

值得一提的是这里的向量和之前定义的既有方向又有大小的量并不等价，任何满足上述公理的阿贝尔群 $V$ 中的元素都能称作向量（比如多项式或者矩阵），也都能用线性代数的理论进行研究。

称阿贝尔群中的零元为零向量，记作 $\mathbf{0}$（\mathbf{0}，加粗的数字 $0$）。

原阿贝尔群中向量的加减法，与线性空间新定义的数乘，统称为线性运算。

容易发现，所有线性运算都能用矩阵乘法概括。另外，我们通常将某元素进行线性运算得到另一元素称作线性变换，但这个貌似不是学术用词。

简单性质

大概属于群论的前置知识？各种证明可以在群论中找到

$\mathbf{0}$ 唯一。
$\forall \mathbf{a}\in V,-\mathbf{a}$ 唯一
$\exist 0\in\mathbb{P},\forall \mathbf{a}\in V,0\mathbf{a}=\mathbf{0}$
$\forall k\in \mathbb{P},k\mathbf{0}=\mathbf{0}$
$\exist -1\in \mathbf{P},\forall \mathbf{a}\in V,(-1)\mathbf{a}=-\mathbf{a}$
$\forall \mathbf{a}\in V,p\in \mathbb{P},p\mathbf{a}=\mathbf{0}\Rightarrow p=0\lor \mathbf{a}=\mathbf{0}$，即两个非 $0$ 元的代数对象数乘不可能得到 $\mathbf{0}$。
加法的消去律，$\forall \mathbf{a},\mathbf{b},\mathbf{c}\in V,\mathbf{a}+\mathbf{c}=\mathbf{b}+\mathbf{c}\Rightarrow \mathbf{a}=\mathbf{b}$（阿贝尔群的性质）。