初探线性代数

参考资料：

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$ 列。

那么具体怎么做呢？

1. 记已经处理好的方程个数为 $r$，再枚举未知数 $c$ 作为主元。
2. 找到 $j\in[r+1,n]$，使得 $a_{j,c}$ 非 $0$。
3. 若找不到，则处理下一个未知数 $c$，否则将第 $r+1$ 行和第 $j$ 行交换。
4. 对第 $r+1$ 行进行一个倍乘使得 $a_{r+1,c}=1$
5. 对 $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$）。

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

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

简单性质

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

1. $\mathbf{0}$ 唯一。
2. $\forall \mathbf{a}\in V,-\mathbf{a}$ 唯一
3. $\exist 0\in\mathbb{P},\forall \mathbf{a}\in V,0\mathbf{a}=\mathbf{0}$
4. $\forall k\in \mathbb{P},k\mathbf{0}=\mathbf{0}$
5. $\exist -1\in \mathbf{P},\forall \mathbf{a}\in V,(-1)\mathbf{a}=-\mathbf{a}$
6. $\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}$。
7. 加法的消去律，$\forall \mathbf{a},\mathbf{b},\mathbf{c}\in V,\mathbf{a}+\mathbf{c}=\mathbf{b}+\mathbf{c}\Rightarrow \mathbf{a}=\mathbf{b}$（阿贝尔群的性质）。

相关概念

为行文方便，下文 $V$ 中元素（除去 $\mathbf{0}$）不再加粗，请注意分辨。

线性表示，线性相关/无关

对于线性空间 $(V,+,\cdot,\mathbb{P})$

• 称 $a_1,a_2,\dots,a_n\in V$ 是 $V$ 的一个向量组(下文为行文方便，用 $a_n$ 表示向量组 $a_1,a_2,\cdots,a_n$。)。
• 对于 $k_1,k_2,\dots k_n\in\mathbb{P}$，称 $\sum_{i=1}^nk_ia_i$ 为向量组的一个线性组合。
• 对于 $\beta\in V$，若 $\beta$ 可以表示为某向量组的线性组合，则称 $\beta$ 能被该向量组 线性表出，称这个线性组合为 $\beta$ 的线性表示。
• 在某向量组中，若 $\mathbf{0}$ 的唯一线性表示是所有 $k$ 全取 $0$，则称这个向量组线性相关，否则称其线性无关。
• 若向量组 $a_n$ 能线性表出向量组 $b_m$ 中的所有向量，则称向量组 $b_m$ 能被向量组 $a_n$ 线性表出

显然 $\mathbf{0}$ 能被任意向量组线性表出（$k_i$ 全部取 $0$ 即可），所以我们定义 $\mathbf{0}$ 能被任意向量组线性表出。

注意到线性组合的定义是一个线性运算的形式，所以我们可以用矩阵乘法概括，根据习惯，我们通常写成一个由向量构成的行向量和标量构成的列向量相乘的形式：

$$ \beta=\sum_{i=1}^nk_ia_i=\begin{pmatrix}a_1,a_2,\cdots,a_n\end{pmatrix}\begin{pmatrix}k_1\\k_2\\\vdots\\k_n\end{pmatrix} $$

性质

1. 若向量组的一个子集线性相关，那么该向量组线性相关。若一个向量组线性无关，那么它的任意非空子集都是线性无关的。
2. 含 $\mathbf{0}$ 的向量组线性相关

3. 一个向量组线性相关当且仅当存在一个向量能被其它向量线性表出。

   根据定义，我们可以线性表出 $\mathbf{0}$，那么将某个 $k_i\ne 0$ 的 $k_ia_i$ 去掉，剩下的就是 $-k_ia_i$，则 $a_i$ 可以被其他向量线性表出。

4. 若向量 $\beta$ 能被某向量组线性表出，那么表出方式唯一当且仅当该向量组线性无关。

5. 若向量组 $a_n$ 线性无关，且向量 $\beta$ 能被其线性表出，那么向量组 $a_1,a_2,\dots,a_n,\beta$ 线性相关。

线性包/张成空间

注意到对于一个线性空间 $(V,+,\cdot,\mathbb{P})$ 中的一个向量组 $a_n$，$\begin{Bmatrix}x|x=\sum_{i=1}^nk_ia_i\end{Bmatrix}$（其中 $k_i$ 取遍 $\mathbb{P}$）也构成一个线性空间，称为由向量组 $a_n$ 张成的线性空间（或线性包），记作 $\mathrm{span}\begin{Bmatrix}a_n\end{Bmatrix}$。

这 $n$ 个向量 $a$ 不一定线性无关。

线性无关组，秩

容易想到，线性相关可以理解为“多余”，意思是说去掉某个向量这个向量组仍能表出原先能表出的所有向量（等价于这个向量能被其他向量表出），那么我们去掉这些向量剩下的就是这个向量组的极大线性无关组。

形式化地，对于线性空间 $(V,+,\cdot,\mathbf{P})$：

1. 对于向量组 $b_m$，令 $a_n\subseteq b_m$，若有：

   • 向量组 $a_n$ 线性无关。
   • $\forall \beta\in b_m\setminus a_n$，$\beta$ 均能被向量组 $a_n$ 线性表出。

   则称向量组 $a_n$ 是向量组 $b_m$ 的极大线性无关组。类似地，可以定义线性空间的极大线性无关组。

   规定元素全为 $\mathbf{0}$ 的向量组不存在极大线性无关组。

   显然从向量组删向量的方法不唯一，所以极大线性无关组也不唯一，习惯上我们把所有向量写成行向量排列在一起，然后从左到右每一位考虑要删哪些。

   称向量组 $b_m$ 极大线性无关组的大小为向量组的秩，记作 $\mathrm{rank}\begin{Bmatrix}b_m\end{Bmatrix}$，规定全 $\mathbb{0}$ 的向量组秩为 $0$。

   类似地，我们定义了矩阵的秩，即将矩阵看作若干行向量（容易发现其实看作列向量得到的值是一样的），得到的向量组的秩。

2. 若向量组 $a_n$ 能被向量组 $b_m$ 线性表出，且 $b_m$ 也能被 $a_n$ 表出，则称两向量组等价，记作 $a_n\cong b_m$（\cong）。容易发现两向量组等价当且仅当两向量组能表出的向量全集相同（即张成空间 $\mathrm{span}\begin{Bmatrix}a_n\end{Bmatrix}=\mathrm{span}\begin{Bmatrix}b_m\end{Bmatrix}$）。

   显然向量组的等价比矩阵的等价更强，不仅要求秩相同，还要求张成空间完全一样。因此两等价的向量组并在一起秩不能发生改变

性质

• 若向量组 $a_n$ 能被向量组 $b_m$ 表出，则 $\mathrm{rank}\begin{Bmatrix}a_n\end{Bmatrix}\le \mathrm{rank}\begin{Bmatrix}b_m\end{Bmatrix}$

  设 $c_p$ 为 $b_m$ 的极大线性无关组，考虑把 $a_n$ 中的向量全部写成 $\sum_{i=1}^pk_ic_i$ 的形式（因为 $a_n$ 能被 $b_m$ 表出，所以这是必定可行的），那么选出 $a_n$ 中 $p$ 个向量使其能表出其它向量是简单的，高斯消元即可构造。所以向量组 $a_n$ 的秩只能更小。

• 向量组线性无关当且仅当其秩等于其大小。

  首先秩不可能大于其大小。若秩小于大小说明多的能被其它表出。

• 设向量组 $a_n$ 能被向量组 $b_m$ 表出。那么若 $n > m$，则 $a_n$ 线性相关。

  由上两条易得。

• 等价的线性无关向量组大小相等。

  反证法，如果大小不同，根据定义小的可以表出大的，那么大的就线性相关（上一个性质）。

• 一个向量组的所有极大线性无关组大小相等。

  根据上一条易得。

• 等价的向量组秩相等。

  因为极大无关组相等。

线性子空间

对于线性空间 $(V,+,\cdot,\mathbb{P})$，若代数系统 $(V_1,+,\cdot,\mathbb{P})$ 满足：

• $V_1\ne \varnothing$
• $V_1\subseteq V$
• $V_1$ 关于 $+,\cdot$ 构成 $\mathbb{P}$ 上的线性空间。

则称 $V_1$ 是 $V$ 的线性子空间，记作 $V_1\le V$。

任何线性空间都含有两个平凡子空间：它自己 $V$ 和零子空间（只含 $\mathbf{0}$ 向量）。

若 $V_1$ 是 $V$ 的真子集，则称 $V_1$ 是 $V$ 的真子空间，记作 $V_1 < V$。

容易发现线性空间 $V$ 的非空子集 $V_1$ 是线性子空间当且仅当线性运算在 $V_1$ 上封闭。

线性基

线性基是线性空间的一组基，是研究线性空间的重要工具。

线性基的和立体几何中基向量类似，更具体地说，因为三维欧氏空间是特殊的线性空间，三维欧氏空间的基向量在线性空间中就被推广为了线性基。

OI 中有关线性基的应用一般只涉及两类线性空间：$n$ 维实线性空间 $\mathbf{R}^n$ 和 $n$ 维布尔域线性空间 $\mathbf{Z_{\mathrm{2}}}^n$，后者的线性基就是我们熟悉的异或线性基了。

定义

称线性空间 $V$ 的一个极大线性无关组为 $V$ 的一组 Hamel 基或线性基，简称基。

规定线性空间 $\begin{Bmatrix}\mathbf{0}\end{Bmatrix}$ 的基为空集。

显然任意线性空间均存在线性基，根据前文可知任意线性基（极大线性无关组）大小相等，我们定义线性空间 $V$ 的维数为线性基的元素个数，记作 $\dim V$。

在 OI 中，我们一般将 $n$ 维实线性空间 $\mathbf{R}^n$ 下的线性基称为实数线性基（并不常用），$n$ 维布尔域线性空间 $\mathbf{Z_{\mathrm{2}}}^n$ 下的线性基称为异或线性基（这个比较常用，用于处理各种异或信息）。

关于 $n$ 维布尔域线性空间。

对于集合 $\mathbf{Z_{\mathrm{2}}}$（即值域为 $[0,1]$ 的整数集合），我们定义加减法为异或，乘法为与，显然这构成一个域。

可以证明代数系统 $(\mathbf{Z}2^n,+,\cdot,\mathbf{Z{\mathrm{2}}})$ 是线性空间，其中：

$$ \begin{aligned} (a_1,\dots,a_n)+(b_1,\dots,b_n)&:=(a_1\oplus b_1,\dots,a_n\oplus b_n)\\ k\cdot(a_1,\dots,a_n)&:=(k\And a_1,\dots,k\And a_n) \end{aligned} $$

其中 $\oplus$ 是异或，$\And$ 是与。即向量加是逐个异或，数乘是逐个与。

性质

对于有限维线性空间 $V$，设其维数为 $n$，则有：

• $V$ 中任意 $n+1$ 个向量线性相关。
• $V$ 中任意 $n$ 个线性无关的向量均为 $V$ 的线性基。

• 若 $V$ 中任意向量均能被线性组 $a_n$ 线性表出，则 $a_n$ 是 $V$ 的一组线性基。

  证明：考虑任取一组线性基 $b_n$，根据条件，$b_n$ 中的所有元素都能被 $a_n$ 线性表出，则 $\mathrm{rank}(b_n)=n\le \mathrm{rank}(a_n)$，又因为 $a_n$ 是 $V$ 的子集，所以 $\mathrm{rank}(a_n)\le \mathrm{rank}(V)=n$，则 $\mathrm{rank}(a_n)=n$，故 $a_n$ 也是 $V$ 的一组极大线性无关组，即线性基。

• $V$ 中的任意线性无关组都能通过插入若干向量变成 $V$ 的一组线性基。

构造方法

我们的问题是对于给定的向量组 $X=\begin{Bmatrix}x_1,x_2,\dots x_n\end{Bmatrix}$，求出其张成空间的一组线性基。其它问题可以在这个问题的代码上适当修改解决。

以异或线性基为例（实数线性基其实差不多，注意一下哪里加哪里减即可，与异或区分开）。常用方法是增量法和高斯消元法。

高斯消元法比较显然，将其看作一个方程组即可，下面着重介绍增量法。

增量法核心思想是每次将向量 $x_i$ 插入 $\mathrm{span}\begin{Bmatrix}x_1,x_2,\dots x_{i-1}\end{Bmatrix}$ 的线性基内。

类似于高斯消元，我们对向量组的每一位维护一个代表元 $b_j$，每次尝试将 $x_i$ 插入。

具体来说，设我们插入的向量是 $p$，从高到低枚举 $p$ 的每一位 $j$，若 $p$ 的这一位为 $1$，并且这一位没有代表元，那么直接 $b_j\gets p$，否则我们通过一些 $p$ 和 $b_j$ 的线性变换使得 $p$ 的这一位变为 $0$（注意到 $b_j$ 的更高位均为 $0$，这就相当于高斯消元把矩阵消成上三角的过程），然后继续往低枚举，若 $p$ 变为 $\mathbf{0}$ 了仍未成功插入，说明 $p$ 与线性基线性相关。显然单次插入的复杂度是 $\dim \mathrm{span}(X)$。

常见问题

以下是 OI 中用线性基解决的常见问题：

• 求给定向量组的秩。

  显然把线性基求出来就搞定了。

• 对给定的向量组，找到一组极大线性无关组。

  记录一下有哪些向量成功插入线性基即可。

• 判断某向量能否被某向量组线性表出。

  求出该向量组的线性基即可。

• 求某集合异或可得的最大值。

  求出该集合的异或线性基，然后从高到低位确定这一位能否为 $1$ 即可。

  P3812 【模板】线性基

• 求某集合异或可得的最小值。

  就是最小的代表元。

• 求某集合异或可得的第 $k$ 小/大值。

  注意到某异或线性基张成空间的元素个数是有限的，即 $2^{|B|}$（或者 $2^{|B|}-1$，原集合线性无关且题目要求不计空集时无法得到 $\mathbf{0}$ 向量），所以这其实是同一个问题。

  将线性基消成行最简形矩阵（在增量法可以考虑插入某代表元时将对应位上的 $1$ 都去掉），容易发现第 $k$ 小就是将 $k$ 化为二进制后，$1$ 的位对应的代表元异或和，证明考虑从高到低按位贪心。

• 线性基合并

  注意到线性基中只有 $O(k)$ 个元素（其中 $k$ 是维数，在常见的异或问题中是 $\log V$），暴力将一个线性基插入另一个是 $O(k^2)$ 的。

• 最大权线性基

  即每个向量还带一个权值，求出权值和最大的线性无关组。

  我们对每一位记录代表元的权值 $h$，考虑在增量法的过程中贪心，当出现“$p$ 的这一位已经有代表元”的情况时，考虑 $p$ 和原先这一位的代表元 $a$，若 $h_p\le h_a$ 就直接拿 $p \oplus a$ 往下消，否则 $a\gets p$，然后拿 $a \oplus p$ 往下消。

  考虑这为什么对，注意到 $p$ 无法插入线性基当且仅当它和线性基线性相关，即存在集合 $S$ 满足 $\bigoplus_{i\in S} b_i=p$，那么我们将 $S$ 中的任意 $b_i$ 替换为 $p$ 后得到的新向量组和原来的向量组是等价的，因为张成空间不变。显然若 $p$ 能直接插入上述算法显然正确，否则上述算法则会将 $S\cup\begin{Bmatrix}p\end{Bmatrix}$ 中的最小值删掉。显然正确。

• 带删除线性基。

  有简单单次修改 $O(k^2\log n)$ 线性做法，线段树加线性基合并即可。

  还有 $O(k)-O(k^2)$ 离线做法。我们将线性基的删除时间视为权值，维护最大权线性基。查询时把线性基内没被删掉的重新拿出来 $O(k^2)$ 求线性基。（感觉这个在合适的题目能做到更优的复杂度吧）

  还可以 $O(k\log n)$ 线段树分治。

例题

CF1100F Ivan and Burgers

传送门

题意

• 给定长度为 $n$ 的序列 $a_i$，$q$ 次询问，每次询问从一个区间 $a_i$ 选一个子集异或起来能得到的最大值。
• $1\le n\le 5\times 10^5,0\le a_i\le 10^6$

题解

异或最大值，容易想到线性基。

一个想法是离线下来，对每个右端点暴力扫左端点，复杂度 $O(n^2\log a_i)$。

考虑线性基只需要加入每一位最右侧的可行代表元，后面的必定无法加入，即维护下标的最大权线性基，于是就能优化到 $O(n\log^2 a_i)$。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=5e5+5,inf=0x3f3f3f3f;
int n,m,c[N],ans[N];
vector<pii> q[N];
vector<int> vec;
struct linear_basis{
    int b[20],h[20];
    void insert(int p,int v){
        fordown(i,19,0){
            if((p>>i)&1){
                if(!b[i]){
                    b[i]=p;
                    h[i]=v;
                    break;
                }else{
                    if(v>h[i]){
                        swap(p,b[i]);
                        swap(v,h[i]);
                    }
                    p^=b[i];
                    if(!p) break;                    
                }
            }
        }
    }
    void work(){
        vec.clear();
        forup(i,0,19){
            if(b[i]) vec.push_back(h[i]);
        }
        sort(vec.begin(),vec.end(),greater<int>());
    }
}t1;
struct linear_basis_2{
    int b[20];
    void insert(int p){
        fordown(i,19,0){
            if((p>>i)&1){
                if(!b[i]){
                    b[i]=p;
                    break;
                }else{
                    p^=b[i];
                    if(!p) break;
                }
            }
        }
    }
    int Ask(){
        int res=0;
        fordown(i,19,0){
            res=max(res,res^b[i]);
        }
        return res;
    }
}t2;
signed main(){
    n=read();
    forup(i,1,n){
        c[i]=read();
    }
    m=read();
    forup(i,1,m){
        int l=read(),r=read();
        q[r].push_back(mkp(l,i));
    }
    forup(i,1,n){
        t1.insert(c[i],i);
        t1.work();
        mem(t2.b,0);
        sort(q[i].begin(),q[i].end(),greater<pii>());
        int pl=0;
        for(auto j:q[i]){
            while(pl<vec.size()&&vec[pl]>=j.fi){
                t2.insert(c[vec[pl]]);
                ++pl;
            }
            ans[j.se]=t2.Ask();
        }
    }
    forup(i,1,m){
        printf("%d\n",ans[i]);
    }
}

矩阵树定理 留坑待补

Comments