浅析线性代数
目录更好的阅读体验戳此进入
还没写完，春测之后有机会继续写。
写在前面
大概就是整理一下线性代数相关的内容，也算是复习一下，可能很多地方比较简略。
矩阵定义与运算
定义没什么可说的，矩阵运算的复杂度一般是 $ O(n^3) $ 的，一般的矩阵乘法大概是这样的：
如果有：
\[A \times B = C \]那么：
\[C_{i, j} = \sum_{k = 1}^nA_{i, k} \times B_{k, j} \]单位矩阵
如果你了解过群论对这个应该不陌生，这个就是群论里面的单位元，也就是满足 $ a \circ e = a $ 中的 $ e $。
不难想到单位矩阵为所有 $ A_{i, i} $ 为 $ 1 $，其余为 $ 0 $ 的矩阵，即：
\[\begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \\ \end{bmatrix} \]证明显然。
矩阵快速幂
没什么区别，重载一下乘法然后写个一般的快速幂即可。
矩阵快速幂优化 DP
在 DDP 里面说过相关内容，且这类内容较为宽泛，这里就不再赘述了。
高斯-约旦消元
给定线性方程组，求解。
考虑将线性方程组表示为增广矩阵的形式，然后枚举每一列，用该列最大值作为主元进行加减消元，消去 $ [1, n] $ 中非当前枚举列的所有行的对应值，这样对于每一行就会变为 $ kx = y $ 的形式，直接求解即可。注意当找到的最大值为 $ 0 $ 时，线性方程组一定无解或无数解，需要特判。
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define EPS (1e-5)
template < typename T = int >
inline T read(void);
int N;
double G[110][110];
void Gauss(void){
for(int i = 1; i <= N; ++i){//i-row
int mxp(i);
for(int j = i + 1; j <= N; ++j)
if(fabs(G[j][i]) > fabs(G[mxp][i]))mxp = j;
for(int j = 1; j <= N + 1; ++j)
swap(G[i][j], G[mxp][j]);
if(fabs(G[i][i]) < EPS)printf("No Solution\n"), exit(0);
for(int j = 1; j <= N; ++j){
if(i == j)continue;
double tmp = G[j][i] / G[i][i];
for(int k = i + 1; k <= N + 1; ++k)
G[j][k] -= G[i][k] * tmp;
}
}
for(int i = 1; i <= N; ++i)G[i][N + 1] /= G[i][i];
}
int main(){
N = read();
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= N + 1; ++j)
G[i][j] = read();
Gauss();
for(int i = 1; i <= N; ++i)printf("%.2lf\n", G[i][N + 1]);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
矩阵求逆
记 $ [AB] $ 表示将两个矩阵连结，则对于矩阵 $ A $，单位矩阵 $ I $，显然存在 $ A^{-1} \times [AI] = [IA^{-1}] $。
则我们通过高斯约旦消元法将 $ [AI] $ 消元成左半部分为单位矩阵的形式，此时显然矩阵将会变为 $ [IA^{-1}] $，那么后者的右半部分即为逆矩阵。
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define MOD (ll)(1e9 + 7)
template < typename T = int >
inline T read(void);
int N;
ll G[410][810];
ll qpow(ll a, ll b){
ll ret(1), mul(a);
while(b){
if(b & 1)ret = ret * mul % MOD;
b >>= 1;
mul = mul * mul % MOD;
}return ret;
}
void Gauss(void){
for(int i = 1; i <= N; ++i){
int mxp(i);
for(int j = i + 1; j <= N; ++j)
if(G[j][i] > G[mxp][i])mxp = j;
swap(G[i], G[mxp]);
if(!G[i][i])printf("No Solution\n"), exit(0);
ll inv = qpow(G[i][i], MOD - 2);
for(int j = 1; j <= N; ++j){
if(i == j)continue;
ll tmp = G[j][i] * inv % MOD;
for(int k = i + 1; k <= N * 2; ++k)
G[j][k] = (G[j][k] - G[i][k] * tmp % MOD + MOD) % MOD;
}
}
for(int i = 1; i <= N; ++i)
for(int j = N + 1; j <= N * 2; ++j)
(G[i][j] *= qpow(G[i][i], MOD - 2)) %= MOD;
}
int main(){
N = read();
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= N; ++j)
G[i][j] = read();
for(int i = 1; i <= N; ++i)
G[i][N + i] = 1;
Gauss();
for(int i = 1; i <= N; ++i)
for(int j = N + 1; j <= N * 2; ++j)
printf("%lld%c", G[i][j], j == N * 2 ? '\n' : ' ');
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
线性基
基础操作与证明就不说了，主要说一下删除操作：
在线的删除是可以支持的，但是实现起来
矩阵的转置
定义
记矩阵 $ $
UPD
update-2022__ 初稿
标签：return,int,void,矩阵,ret,线性代数,浅析,define From： https://www.cnblogs.com/tsawke/p/17180261.html