主要參考了 oi-wiki。

線性方程組

首先搞清楚線性方程組的本質(zhì)。或者說(shuō)是搞清楚矩陣的本質(zhì)。

將其看作矩陣乘法：

換句話說(shuō)，我們將一個(gè)向量通過(guò)線性變換到了另一個(gè)向量，這就是線性方程組的本質(zhì)。

解方程的本質(zhì)就是根據(jù)變換矩陣和終向量，推算出原向量。

其實(shí)不難想到：

所以其實(shí)相當(dāng)于做一個(gè)矩陣求逆了。

雖然說(shuō)我覺(jué)得你在求解線性方程組的時(shí)候要把這個(gè)矩陣當(dāng)作一類特殊矩陣，不然你會(huì)很難受 /kk

通常我們?cè)谇蠼饩€性方程組時(shí)會(huì)使用這樣一個(gè)增廣矩陣：

其實(shí)就是把有值的地方提取出來(lái)。

我們要處理這個(gè)矩陣，其實(shí)就相當(dāng)于通過(guò)一些滿足線性方程組的變換來(lái)修改這個(gè)矩陣。詳情見(jiàn)下。

初等行變換

這里只用到了小學(xué)二年級(jí)的知識(shí)。

先記錄一些初等矩陣。

對(duì)角矩陣

即有且只有主對(duì)角線上所有元素非 \(0\) 的矩陣。

這個(gè)矩陣的作用是倍乘，你想象把它乘到一個(gè)矩陣上（左乘），恰好就是每一行的所有數(shù)乘上那一行的 \(k\) 值。所以又稱之為倍乘矩陣。

體現(xiàn)到線性方程組上就是把一個(gè)線性方程的系數(shù)同時(shí)擴(kuò)大，正確性顯然。

對(duì)換矩陣

畫(huà)的不好看，盡量理解一下。

其實(shí)就是單位矩陣后，對(duì)某兩 \(i,j\)，使第 \((i,i)\) 項(xiàng)和第 \((j,j)\) 項(xiàng)變成 \(0\)，使 \((i,j)\) 和 \((j,i)\) 變成 \(1\).

這個(gè)矩陣左乘后的作用是交換 \(i,j\) 兩行。

體現(xiàn)在線性方程組上就是交換兩個(gè)線性方程的順序，正確性顯然。

倍加矩陣

這里沒(méi)有畫(huà)省略號(hào)，感性理解一下。

這個(gè)矩陣是單位矩陣的基礎(chǔ)上第 \((i,j)\) 項(xiàng)變成 \(k\)。

左乘后的作用是將第 \(j\) 行的系數(shù)每一項(xiàng)都擴(kuò)大 \(k\) 倍加入第 \(i\) 行。

體現(xiàn)在線性方程組上就是加減消元法，正確性顯然。

有了上述三種矩陣，就可以對(duì)原增廣矩陣求解了。

高斯消元法

上三角矩陣：\((i,j)\) 項(xiàng)有值當(dāng)且僅當(dāng) \(i\le j\)。

高斯消元的目標(biāo)是將原增廣矩陣通過(guò)上述初等變換變成上三角矩陣。

對(duì)于每一行，我們找到它的主元。當(dāng)然第 \(i\) 行的主元就是第 \(i\) 個(gè)未知數(shù)。

如果這一行里這個(gè)未知數(shù)系數(shù)為 \(0\) 的話就用將有系數(shù)的對(duì)換上來(lái)。這里我們直接找系數(shù)絕對(duì)值最大的，因?yàn)檫@樣做誤差最小。

然后通過(guò)倍加操作，把后面所有行的第 \(i\) 列的系數(shù)全部變?yōu)?\(0\)，這一步就是在消元了。

不難發(fā)現(xiàn)，遞歸此操作后，我們就會(huì)得到原增廣矩陣變換后的上三角矩陣。

只需要求出最后一個(gè)方程未知數(shù)的值，再回代即可。

高斯約旦消元法

在這個(gè)方法中，我們將增廣矩陣變換成對(duì)角矩陣。

這一步只需要在消元那一步的同時(shí)向上消元即可。

比較推薦實(shí)現(xiàn)這種方法，感覺(jué)更符合人類直覺(jué)。

判斷是否無(wú)解或無(wú)數(shù)解

無(wú)解和無(wú)數(shù)解本質(zhì)上都是兩個(gè)方程描述了同一個(gè)未知數(shù)，描述相反就是無(wú)解，描述相同就是無(wú)數(shù)解。

以高斯約旦消元法為例，當(dāng)我們遇到一列不存在非 \(0\) 系數(shù)時(shí)跳過(guò)當(dāng)前列的消元，執(zhí)行完整個(gè)消元過(guò)程。

如果某個(gè)方程左邊為 \(0\) 右邊確不為 \(0\) 那就是無(wú)解。如果兩個(gè)方程描述了同一個(gè)未知數(shù)，那就是無(wú)數(shù)解。

這里給出 P2455 [SDOI2006] 線性方程組 的代碼：

/*
The Order...
Active...
Punishment!
*/
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
//#define int long long
/*
furina /se /se
yanami /se /se
yamada /se /se
sayaka /se /se
konata /se /se
藍(lán)仙未未 /se /se 
*/
namespace TYX_YNXK{
	#define il inline
	#define bl bool
	#define vd void
	#define ll long long
	#define ull unsigned ll
	#define db double
	#define ldb long db
	#define pii pair<int,int>
	#define fi first
	#define se second
	#define MP make_pair
	#define pb push_back
	#define N 55
	#define INF 0x3f3f3f3f3f3f3f3fll
	#define DEBUG cerr<<"\tfurina begin:\n"
	#define END cerr<<"\tyanami end.\n"
	const db eps=1e-8;
	il int sgn(db x){if(fabs(x)<eps)return 0;return x<0?-1:1;}
	int n;db s[N][N];
	signed main(){
		cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n+1;j++)cin>>s[i][j];
		for(int i=1,j=1,r;i<=n&&j<=n;i++,j++){//第 i 行第 j 列的消元 
			r=i;for(int k=i+1;k<=n;k++)if(sgn(fabs(s[k][j])-fabs(s[r][j]))==1)r=k;//找到絕對(duì)值最大的行 
			if(sgn(fabs(s[r][j]))==0){--i;continue;}//為 0，跳過(guò) 
			if(i^r)for(int k=1;k<=n+1;k++)swap(s[r][k],s[i][k]);//對(duì)換目標(biāo)行 
			for(int k=1;k<=n;k++)if(k^i)for(int p=n+1;p>=i;p--)s[k][p]-=s[k][j]/s[i][j]*s[i][p];//消元 
		}
		bl flag1=0,flag2=0;
		for(int i=1,d;i<=n;i++){ 
			d=0;for(int j=1;j<=n;j++)d+=sgn(s[i][j])!=0;
			if(!d){
				if(sgn(s[i][n+1])!=0)flag1=1;
				else flag2=1;
			}
		}
		if(flag1)return cout<<"-1\n",0;
		if(flag2)return cout<<"0\n",0;
		for(int i=1;i<=n;i++){
			cout<<"x"<<i<<"=";
			db val=s[i][n+1]/s[i][i];
			if(sgn(val)==0)cout<<"0.000\n";
			else cout<<fixed<<setprecision(3)<<val<<'\n';
		}
		return 0;
	}
} 
signed main(){
//	freopen("Hazuki.in","r",stdin);
//	freopen("Hazuki.out","w",stdout);
	TYX_YNXK::main();
	return 0;
}/*
SATT is the world's best Dynamic Trees algorithm!
*/

矩陣求逆

只需要增廣一個(gè)單位矩陣做高斯約旦消元即可。

線性空間

就是由向量運(yùn)算組成的域。性質(zhì)都可以參照域的性質(zhì)。

線性基

極大線性無(wú)關(guān)向量組。

異或線性基

維度為 \(base\)，每一維只有 \(01\) 表示。

實(shí)現(xiàn)時(shí)從高到低遍歷，如果某一位沒(méi)有就加入，有就異或。