盘活一下线性代数。我也不知道为什么看着格路计数然后看到LGV引理然后就来补线性代数了。
高斯消元可以拿来干什么？解方程组。线性方程组。
怎么解？我们现在有一个线性方程组长这样：
\[\left\{ \begin{aligned} a_{1,1}x_1+a_{1,2}x_2+a_{1,3}x_3+&\cdots+a_{1,n}x_n=b_1\\ a_{2,1}x_1+a_{2,2}x_2+a_{2,3}x_3+&\cdots+a_{2,n}x_n=b_2\\ a_{3,1}x_1+a_{3,2}x_2+a_{3,3}x_3+&\cdots+a_{3,n}x_n=b_3\\ &\vdots\\ a_{n,1}x_1+a_{n,2}x_2+a_{n,3}x_3+&\cdots+a_{n,n}x_n=b_n\\ \end{aligned} \right. \]这显然是个 \(n\) 阶线性方程组。然后我们有这么一个增广矩阵：
\[\begin{pmatrix} a_{1,1} & a_{1,2} & a_{1,3} & \cdots & a_{1,n} & b_1\\ a_{2,1} & a_{2,2} & a_{2,3} & \cdots & a_{2,n} & b_2\\ a_{3,1} & a_{3,2} & a_{3,3} & \cdots & a_{3,n} & b_3\\ &&\vdots&&&\\ a_{n,1} & a_{n,2} & a_{n,3} & \cdots & a_{n,n} & b_n\\ \end{pmatrix} \]也就是说我们把未知数的每个系数和常数组成了一个矩阵。所以说我们只需要对这个矩阵进行初等行变换，消成行最简形，然后就可以求解一个变量，进而求出所有的变量。具体说一下过程：
首先，我们把这么一个矩阵消成下三角矩阵（就是主对角线以下都是 \(0\) 的矩阵），然后最后一行就只有一个系数和一个常数，可以直接得出变量。然后从下往上一层层回带，就能得到所有的解。
还有一个叫高斯·约旦消元，这个是直接把矩阵消成对角矩阵，更常用。
然后是关于判无解的情况。如果一个位置消元之后 \(a_{i,i}=0\) ，那么如果 \(b_i\neq 0\) ，无解。如果 \(b_i=0\) ，则有无数组解。
bool gauss(){
for(int i=1;i<=n;i++){
int maxx=i;
for(int j=i+1;j<=n;j++){
if(fabs(a[j][i])>fabs(a[maxx][i]))maxx=j;//找到最大的一个
}
for(int j=1;j<=n+1;j++)swap(a[i][j],a[maxx][j]);//把最大的一行交换过来
if(fabs(a[i][i])<=eps)return false;//无解
for(int j=1;j<=n;j++){
if(i==j)continue;
double rate=a[j][i]/a[i][i];
for(int k=i+1;k<=n+1;k++)a[j][k]-=a[i][k]*rate;//消元
}
}
for(int i=1;i<=n;i++)ans[i]=a[i][n+1]/a[i][i];//求解答案
return true;
}
然后是两个常见应用。
- 矩阵求逆。
我们现在要求一个 \(n\) 阶矩阵的逆。我们构造一个 \(n\times 2n\) 的矩阵，左边是这个 \(n\) 阶矩阵，右边是一个 \(n\) 阶单位矩阵。然后我们使用高斯消元，把左边消成单位矩阵，此时右边就是这个矩阵的逆。如果左边不是单位矩阵，则不可逆。
bool gauss(){
for(int i=1;i<=n;i++){
int maxx=i;
for(int j=i+1;j<=n;j++){
if(a[j][i]>a[maxx][i])maxx=j;
}
for(int j=1;j<=(n<<1);j++)swap(a[i][j],a[maxx][j]);
if(a[i][i]==0)return false;//不可逆
int inv=qpow(a[i][i],mod-2);
for(int j=1;j<=n;j++){
if(i==j)continue;
int rate=1ll*a[j][i]*inv%mod;
for(int k=i+1;k<=(n<<1);k++)a[j][k]=(a[j][k]-1ll*a[i][k]*rate%mod+mod)%mod;//板子
}
for(int j=1;j<=(n<<1);j++)a[i][j]=1ll*a[i][j]*inv%mod;//直接在这里乘上逆元 就不用最后再乘了
}
return true;
}
- 行列式求值。
不再普及行列式是什么东西。一个行列式的理解是所有列向量夹的几何体的有向体积。它有几个性质：
- 矩阵转置，行列式不变。
- 矩阵行/列交换，行列式取反。
- 矩阵行/列相加减，行列式不变。
- 矩阵一行/列所有元素同乘 \(k\) ，行列式乘 \(k\) 。
然后我们可以把行列式消成对角的，此时行列式的值就是对角线所有元素乘积。然后我们在消元过程中记录消元对行列式的值的影响，最后乘上即可。
int gauss(int n){
int ans=1,w=1;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
while(a[i][i]){
int rate=a[j][i]/a[i][i];
for(int k=i;k<=n;k++){
a[j][k]=(a[j][k]-1ll*rate*a[i][k]%mod+mod)%mod;
}
for(int k=1;k<=n;k++)swap(a[i][k],a[j][k]);
w=-w;
}
for(int k=1;k<=n;k++)swap(a[i][k],a[j][k]);
w=-w;
}
}
for(int i=1;i<=n;i++)ans=1ll*ans*a[i][i]%mod;
ans=(1ll*ans*w%mod+mod)%mod;
return ans;
}
- 异或方程组
异或方程组就是把上面的线性方程组的所有加改成异或。然后所有的常数和变量都只有 \(0\) 和 \(1\) 。事实上直接把高斯消元的加减乘改成异或就可以了。可以一行上一个bitset优化。代码不放了，没写。
标签：int,矩阵,然后,cdots,行列式,高斯消 From： https://www.cnblogs.com/gtm1514/p/16771568.html