代数余子式和伴随矩阵
之后的一篇文章。
啊啊啊这玩意学了我一整天！这什么菜狗啊！
一、代数余子式
在 \(n\) 阶方阵 \(A=(a_{i,j})\) 中，删去第 \(i\) 行和第 \(j\) 列后所留下的方阵的行列式称为 \(a_{i,j}\) 的余子式 \(M_{i,j}\)，而 \(a_{i,j}\) 的代数余子式为 \(A_{i,j}=(-1)^{i+j}M_{i,j}.\)
代数余子式可以用来算行列式：
\[\det(A)=\sum_{c=1}^n a_{r,c}A_{r,c} \]二、伴随矩阵
(一)、定义
真不是因为我懒，主要是这个矩阵我不太会用 markdown 画出来。懒得搜还不是懒
(二)、性质及求解方法
首先我们用高斯消元计算 \(A\) 的 rank，然后分情况讨论。
1.rank(A)=n
有这样一个公式：\(AA^{*}=|A|I\)，那么可得 \(A^{*}=|A|A^{-1}\)。
我们试着感性证明一波 \(AA^{*}=|A|I\)
首先我们根据左行乘右列，当左边的行序数和右边的列序数相等时，由一、代数余子式中的公式可知算出来就是 \(|A|\)。
那么不相等的时候呢？相当于算的是：\(\sum_{c=1}^n a_{i,c}A_{r,c}(i\not=r)\)，相当于计算将最初的方阵 \(A\) 的第 \(i\) 行换为第 \(r\) 行的方阵后，计算它的行列式，由于有两行相等，\(A\) 不满秩，行列式为 0，所以上面那个式子算出来就是 0。
2.rank(A)
显然此时删掉一行一列之后仍然不满秩，所以 \(A^*=O,\operatorname{rank}(A^{*})=0\)。
3.rank(A)=n-1
麻烦的来了。
首先由 \(\operatorname{rank}(A)=n-1\) 可知 \(\dim\ker(A)=1\)。于是存在非零行向量和列向量 \(p,q\) 使得 \(pA=0,Aq=0\)，\(p,q\) 可以高斯消元求出。(这里有点类似于高中数学求平面的法向量)
由于行列最后得出的结论类似，所以我们这里只以列为例讲解。
\(Aq=0,\dim\ker(A)=1,\operatorname{rank}(A^*)=1\)
可得 \(A*\) 的每一行都是第一行的若干倍数，又因为 \(\operatorname{rank}(A)，所以 \(|A|=0\)。
\(|A|=a_{1,1}A_{1,1}+a_{1,2}A_{1,2}+...+a_{1,n}A_{1,n}=0\)
\(a_{1,1}q_1+a_{1,2}q_2+...+a_{1,n}q_n=0\)
由 \(\dim\ker(A)=1\) 可知 \(\frac{A_{1,1}}{q_1}=\frac{A_{1,2}}{q_2}=...=\frac{A_{1,n}}{q_n}\)。(当然这里如果有0就不能写成分式形式，但是为了美观还是这么写)
那么行的结论同理可得：\(\frac{A_{1,1}}{p_1}=\frac{A_{2,1}}{p_2}=...=\frac{A_{n,1}}{p_n}\)
所以为了求出所有的 \(A_{i,j}\)，我们需要找到 \(r,c\) 使得 \(p_r,q_c\not=0\)，那么可得 \(A_{i,j}=\frac{p_{i}q_{j}}{p_rq_{c}}A_{r,c}\)，至于 \(A_{r,c}\) 直接暴力 \(O(n^3)\) 求即可。
(三)、例题
题目大意：求方阵的余子式。
Vjudge
OpenJudge
差点就拿DDG的代码开拍了
//12252024832524
#include
#define TT template
using namespace std;
typedef long long LL;
const int MAXN = 200;
const int MOD = 998244353;
int n;
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int qpow(int x,int y)
{
int ret = 1;
while(y){if(y & 1) ret = 1ll * ret * x % MOD;x = 1ll * x * x % MOD;y >>= 1;}
return ret;
}
int tmp[MAXN][MAXN];
struct Matrix
{
int n,a[MAXN][MAXN];
Matrix(){memset(a,0,sizeof(a));}
void Get(int x){n = x;for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) a[i][j] = Read();}
void print(){for(int i = 0;i < n;++ i)for(int j = 0;j < n;++ j) Put(a[i][j],j == (n-1) ? '\n' : ' ');}
void Add(int r1,int r2,int k){for(int i = 0;i < n;++ i) a[r2][i] = (a[r2][i] + 1ll * a[r1][i] * k) % MOD;}
void Mul(int r,int k){for(int i = 0;i < n;++ i) a[r][i] = 1ll * a[r][i] * k % MOD;}
void Mul(int k){for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) a[i][j] = 1ll * a[i][j] * k % MOD;}
void Trans(){for(int i = 0;i < n;++ i) for(int j = i;j < n;++ j) swap(a[i][j],a[j][i]);}
Matrix TransNd(){Matrix ret;ret.n = n;for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) ret.a[i][j] = a[j][i];return ret;}
int Det(bool ri = 1)//whether ruin the previous one
{
int ret = 1;
if(!ri) for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) tmp[i][j] = a[i][j];
for(int i = 0;i < n;++ i)
{
if(!a[i][i]) for(int j = i+1;j < n;++ j) if(a[j][i]) {ret = -ret;swap(a[i],a[j]);break;}
if(!a[i][i]) {ret = 0;break;}
for(int j = i+1;j < n;++ j)
if(a[j][i])
{
int mul = 1ll * a[j][i] * qpow(a[i][i],MOD-2) % MOD;
for(int k = i;k < n;++ k) a[j][k] = ((a[j][k] - 1ll * mul * a[i][k]) % MOD + MOD) % MOD;
}
ret = 1ll * ret * a[i][i] % MOD;
}
if(!ri) for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) a[i][j] = tmp[i][j];
return (ret+MOD)%MOD;
}
int Rank(bool ri = 1)
{
int ret = n;
if(!ri) for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) tmp[i][j] = a[i][j];
for(int i = 0;i < n;++ i)
{
if(!a[i][i]) for(int j = i+1;j < n;++ j) if(a[j][i]) {swap(a[i],a[j]);break;}
if(!a[i][i]) {--ret;continue;}
for(int j = i+1;j < n;++ j)
if(a[j][i])
{
int mul = 1ll * a[j][i] * qpow(a[i][i],MOD-2) % MOD;
for(int k = i;k < n;++ k) a[j][k] = ((a[j][k] - 1ll * mul * a[i][k]) % MOD + MOD) % MOD;
}
}
if(!ri) for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) a[i][j] = tmp[i][j];
return ret;
}
Matrix inv(bool ri = 1)
{
if(!ri) for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) tmp[i][j] = a[i][j];
Matrix ret; ret.n = n; for(int i = 0;i < n;++ i) ret.a[i][i] = 1;
for(int i = 0;i < n;++ i)
{
if(!a[i][i]) for(int j = i;j < n;++ j) if(a[j][i]) {swap(a[i],a[j]);swap(ret.a[i],ret.a[j]);break;}
if(!a[i][i]) break;//impossible
for(int j = 0;j < n;++ j)
if((i^j) && a[j][i])
{
int mul = 1ll * a[j][i] * qpow(a[i][i],MOD-2) % MOD;
for(int k = i;k < n;++ k) a[j][k] = ((a[j][k] - 1ll * mul * a[i][k]) % MOD + MOD) % MOD;
ret.Add(i,j,MOD-mul);
}
}
for(int i = 0;i < n;++ i) ret.Mul(i,qpow(a[i][i],MOD-2));//a[i][i] = 1;
if(!ri) for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) a[i][j] = tmp[i][j];
return ret;
}
Matrix Getq(bool ri = 1)//Aq = 0, to get q
{
if(!ri) for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) tmp[i][j] = a[i][j];
Matrix ret; ret.n = n;
for(int i = 0;i < n;++ i)
{
if(!a[i][i]) for(int j = i+1;j < n;++ j) if(a[j][i]) {swap(a[i],a[j]);break;}
if(!a[i][i])
{
ret.a[i][0] = 1;
for(int j = i-1;j >= 0;-- j) ret.a[j][0] = (MOD-a[j][i])%MOD;
for(int j = i-1;j >= 0;-- j)
{
ret.a[j][0] = 1ll * ret.a[j][0] * qpow(a[j][j],MOD-2) % MOD; //a[j][j] = 1;
for(int k = j-1;k >= 0;-- k) ret.a[k][0] = ((ret.a[k][0] - 1ll * ret.a[j][0] * a[k][j]) % MOD + MOD) % MOD;
}
break;
}
for(int j = i+1;j < n;++ j)
if(a[j][i])
{
int mul = 1ll * a[j][i] * qpow(a[i][i],MOD-2) % MOD;
for(int k = i;k < n;++ k) a[j][k] = ((a[j][k] - 1ll * mul * a[i][k]) % MOD + MOD) % MOD;
}
}
if(!ri) for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) a[i][j] = tmp[i][j];
return ret;
}
Matrix Del(int r,int c)//delete row r & column c
{
Matrix ret; ret.n = n-1;
for(int i = 0;i < n;++ i)
for(int j = 0;j < n && (i^r);++ j)
if(j^c)
ret.a[i-(i>r)][j-(j>c)] = a[i][j];
return ret;
}
}A,B,p,q;
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
for(int T = Read(),rk; T ;-- T)
{
A.Get(n = Read()); rk = A.Rank(0);
if(rk == n)
{
B = A.inv(0);
B.Mul(A.Det());
B.Trans();
}
else if(rk < n-1)
{
for(int i = 0;i < n;++ i)
for(int j = 0;j < n;++ j)
putchar('0'),putchar(j == (n-1) ? '\n' : ' ');
putchar('\n'); continue;
}
else
{
q = A.Getq(0);//Aq = 0
p = ((A.TransNd()).Getq()).TransNd();//pA = 0
int r = 0,c = 0;
for(int i = 0;i < n;++ i) if(p.a[0][i]) {r = i;break;}
for(int i = 0;i < n;++ i) if(q.a[i][0]) {c = i;break;}
B.n = n;
B.a[r][c] = ((r+c) & 1 ? MOD-1ll : 1) * A.Del(r,c).Det() % MOD;
int iv = 1ll * qpow(p.a[0][r],MOD-2) * qpow(q.a[c][0],MOD-2) % MOD;
for(int i = 0;i < n;++ i)
for(int j = 0;j < n;++ j)
B.a[i][j] = 1ll * iv * p.a[0][i] % MOD * q.a[j][0] % MOD * B.a[r][c] % MOD;
}
for(int i = 0;i < n;++ i)
for(int j = 0;j < n;++ j)
Put((B.a[i][j] * ((i+j) & 1 ? -1 : 1) + MOD) % MOD,j == (n-1) ? '\n' : ' ');
putchar('\n');
}
return (0-0);
}
显然此时删掉一行一列之后仍然不满秩，所以 \(A^*=O,\operatorname{rank}(A^{*})=0\)。
3.rank(A)=n-1
麻烦的来了。
首先由 \(\operatorname{rank}(A)=n-1\) 可知 \(\dim\ker(A)=1\)。于是存在非零行向量和列向量 \(p,q\) 使得 \(pA=0,Aq=0\)，\(p,q\) 可以高斯消元求出。(这里有点类似于高中数学求平面的法向量)
由于行列最后得出的结论类似，所以我们这里只以列为例讲解。
\(Aq=0,\dim\ker(A)=1,\operatorname{rank}(A^*)=1\)
可得 \(A*\) 的每一行都是第一行的若干倍数，又因为 \(\operatorname{rank}(A)
\(|A|=a_{1,1}A_{1,1}+a_{1,2}A_{1,2}+...+a_{1,n}A_{1,n}=0\)
\(a_{1,1}q_1+a_{1,2}q_2+...+a_{1,n}q_n=0\)
由 \(\dim\ker(A)=1\) 可知 \(\frac{A_{1,1}}{q_1}=\frac{A_{1,2}}{q_2}=...=\frac{A_{1,n}}{q_n}\)。(当然这里如果有0就不能写成分式形式，但是为了美观还是这么写)
那么行的结论同理可得：\(\frac{A_{1,1}}{p_1}=\frac{A_{2,1}}{p_2}=...=\frac{A_{n,1}}{p_n}\)
所以为了求出所有的 \(A_{i,j}\)，我们需要找到 \(r,c\) 使得 \(p_r,q_c\not=0\)，那么可得 \(A_{i,j}=\frac{p_{i}q_{j}}{p_rq_{c}}A_{r,c}\)，至于 \(A_{r,c}\) 直接暴力 \(O(n^3)\) 求即可。
(三)、例题
题目大意：求方阵的余子式。
Vjudge
OpenJudge
差点就拿DDG的代码开拍了
//12252024832524
#include
#define TT template
using namespace std;
typedef long long LL;
const int MAXN = 200;
const int MOD = 998244353;
int n;
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int qpow(int x,int y)
{
int ret = 1;
while(y){if(y & 1) ret = 1ll * ret * x % MOD;x = 1ll * x * x % MOD;y >>= 1;}
return ret;
}
int tmp[MAXN][MAXN];
struct Matrix
{
int n,a[MAXN][MAXN];
Matrix(){memset(a,0,sizeof(a));}
void Get(int x){n = x;for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) a[i][j] = Read();}
void print(){for(int i = 0;i < n;++ i)for(int j = 0;j < n;++ j) Put(a[i][j],j == (n-1) ? '\n' : ' ');}
void Add(int r1,int r2,int k){for(int i = 0;i < n;++ i) a[r2][i] = (a[r2][i] + 1ll * a[r1][i] * k) % MOD;}
void Mul(int r,int k){for(int i = 0;i < n;++ i) a[r][i] = 1ll * a[r][i] * k % MOD;}
void Mul(int k){for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) a[i][j] = 1ll * a[i][j] * k % MOD;}
void Trans(){for(int i = 0;i < n;++ i) for(int j = i;j < n;++ j) swap(a[i][j],a[j][i]);}
Matrix TransNd(){Matrix ret;ret.n = n;for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) ret.a[i][j] = a[j][i];return ret;}
int Det(bool ri = 1)//whether ruin the previous one
{
int ret = 1;
if(!ri) for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) tmp[i][j] = a[i][j];
for(int i = 0;i < n;++ i)
{
if(!a[i][i]) for(int j = i+1;j < n;++ j) if(a[j][i]) {ret = -ret;swap(a[i],a[j]);break;}
if(!a[i][i]) {ret = 0;break;}
for(int j = i+1;j < n;++ j)
if(a[j][i])
{
int mul = 1ll * a[j][i] * qpow(a[i][i],MOD-2) % MOD;
for(int k = i;k < n;++ k) a[j][k] = ((a[j][k] - 1ll * mul * a[i][k]) % MOD + MOD) % MOD;
}
ret = 1ll * ret * a[i][i] % MOD;
}
if(!ri) for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) a[i][j] = tmp[i][j];
return (ret+MOD)%MOD;
}
int Rank(bool ri = 1)
{
int ret = n;
if(!ri) for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) tmp[i][j] = a[i][j];
for(int i = 0;i < n;++ i)
{
if(!a[i][i]) for(int j = i+1;j < n;++ j) if(a[j][i]) {swap(a[i],a[j]);break;}
if(!a[i][i]) {--ret;continue;}
for(int j = i+1;j < n;++ j)
if(a[j][i])
{
int mul = 1ll * a[j][i] * qpow(a[i][i],MOD-2) % MOD;
for(int k = i;k < n;++ k) a[j][k] = ((a[j][k] - 1ll * mul * a[i][k]) % MOD + MOD) % MOD;
}
}
if(!ri) for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) a[i][j] = tmp[i][j];
return ret;
}
Matrix inv(bool ri = 1)
{
if(!ri) for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) tmp[i][j] = a[i][j];
Matrix ret; ret.n = n; for(int i = 0;i < n;++ i) ret.a[i][i] = 1;
for(int i = 0;i < n;++ i)
{
if(!a[i][i]) for(int j = i;j < n;++ j) if(a[j][i]) {swap(a[i],a[j]);swap(ret.a[i],ret.a[j]);break;}
if(!a[i][i]) break;//impossible
for(int j = 0;j < n;++ j)
if((i^j) && a[j][i])
{
int mul = 1ll * a[j][i] * qpow(a[i][i],MOD-2) % MOD;
for(int k = i;k < n;++ k) a[j][k] = ((a[j][k] - 1ll * mul * a[i][k]) % MOD + MOD) % MOD;
ret.Add(i,j,MOD-mul);
}
}
for(int i = 0;i < n;++ i) ret.Mul(i,qpow(a[i][i],MOD-2));//a[i][i] = 1;
if(!ri) for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) a[i][j] = tmp[i][j];
return ret;
}
Matrix Getq(bool ri = 1)//Aq = 0, to get q
{
if(!ri) for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) tmp[i][j] = a[i][j];
Matrix ret; ret.n = n;
for(int i = 0;i < n;++ i)
{
if(!a[i][i]) for(int j = i+1;j < n;++ j) if(a[j][i]) {swap(a[i],a[j]);break;}
if(!a[i][i])
{
ret.a[i][0] = 1;
for(int j = i-1;j >= 0;-- j) ret.a[j][0] = (MOD-a[j][i])%MOD;
for(int j = i-1;j >= 0;-- j)
{
ret.a[j][0] = 1ll * ret.a[j][0] * qpow(a[j][j],MOD-2) % MOD; //a[j][j] = 1;
for(int k = j-1;k >= 0;-- k) ret.a[k][0] = ((ret.a[k][0] - 1ll * ret.a[j][0] * a[k][j]) % MOD + MOD) % MOD;
}
break;
}
for(int j = i+1;j < n;++ j)
if(a[j][i])
{
int mul = 1ll * a[j][i] * qpow(a[i][i],MOD-2) % MOD;
for(int k = i;k < n;++ k) a[j][k] = ((a[j][k] - 1ll * mul * a[i][k]) % MOD + MOD) % MOD;
}
}
if(!ri) for(int i = 0;i < n;++ i) for(int j = 0;j < n;++ j) a[i][j] = tmp[i][j];
return ret;
}
Matrix Del(int r,int c)//delete row r & column c
{
Matrix ret; ret.n = n-1;
for(int i = 0;i < n;++ i)
for(int j = 0;j < n && (i^r);++ j)
if(j^c)
ret.a[i-(i>r)][j-(j>c)] = a[i][j];
return ret;
}
}A,B,p,q;
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
for(int T = Read(),rk; T ;-- T)
{
A.Get(n = Read()); rk = A.Rank(0);
if(rk == n)
{
B = A.inv(0);
B.Mul(A.Det());
B.Trans();
}
else if(rk < n-1)
{
for(int i = 0;i < n;++ i)
for(int j = 0;j < n;++ j)
putchar('0'),putchar(j == (n-1) ? '\n' : ' ');
putchar('\n'); continue;
}
else
{
q = A.Getq(0);//Aq = 0
p = ((A.TransNd()).Getq()).TransNd();//pA = 0
int r = 0,c = 0;
for(int i = 0;i < n;++ i) if(p.a[0][i]) {r = i;break;}
for(int i = 0;i < n;++ i) if(q.a[i][0]) {c = i;break;}
B.n = n;
B.a[r][c] = ((r+c) & 1 ? MOD-1ll : 1) * A.Del(r,c).Det() % MOD;
int iv = 1ll * qpow(p.a[0][r],MOD-2) * qpow(q.a[c][0],MOD-2) % MOD;
for(int i = 0;i < n;++ i)
for(int j = 0;j < n;++ j)
B.a[i][j] = 1ll * iv * p.a[0][i] % MOD * q.a[j][0] % MOD * B.a[r][c] % MOD;
}
for(int i = 0;i < n;++ i)
for(int j = 0;j < n;++ j)
Put((B.a[i][j] * ((i+j) & 1 ? -1 : 1) + MOD) % MOD,j == (n-1) ? '\n' : ' ');
putchar('\n');
}
return (0-0);
}