高斯消元是求解線性方程組的重要方法，在OI中有廣泛的應(yīng)用。本文就來討論這個方法。

什么是線性方程組？含m個方程和n個未知量的方程組定義為
a(11)x(1)+a(12)x(2)+…+a(1n)x(n)=b(1)
a(21)x(1)+a(22)x(2)+…+a(2n)x(n)=b(2)
…
a(m1)x(1)+a(m2)x(2)+…+a(mn)x(n)=b(m)
這個方程組稱為m*n線性方程組，其中a(ij)和b(i)為實數(shù)，括號中為下標(biāo)。這個方程組有多種表示方法。例如，我們知道m(xù)*n矩陣（用大寫字母表示）是一個m行n列的數(shù)陣，n維向量（用加粗的小寫字母表示）是n個數(shù)的數(shù)組，也就是一個n*1矩陣（列向量。我們不考慮行向量）。另外，大家也都知道矩陣乘法。因此一個m*n線性方程組可以表示為
Ax=b，其中A是由系數(shù)aij組成的m*n矩陣即系數(shù)矩陣，x是n維的未知數(shù)向量，b是m維的結(jié)果向量。如果把向量b寫到A的右邊得到m*(n+1)的矩陣，得到的新矩陣稱為這個方程組的增廣矩陣。每一個方程組均對應(yīng)于一個增廣矩陣。

下面介紹一下矩陣的初等行變換:
1 交換兩行
2 用非零實數(shù)乘以任一行
3 把某一行的倍數(shù)加到另一行上
同理可以定義初等列變換。初等行變換和初等列變換統(tǒng)稱初等變換。
定理：對于一個方程組對應(yīng)的增廣矩陣進行有限次初等行變換，所得矩陣對應(yīng)的方程組與原方程組等價。即它們是等價方程組。

高斯消元的過程，就是利用初等行變換將原來不容易求解的方程組轉(zhuǎn)化為容易求解的方程組。

下面我們以求解n*n線性方程組為例。因為如果m<>n,這個m*n方程組一般不會有唯一的解。

定義：上三角矩陣是一個n*n的矩陣，其中對于任意i>j的項a(ij)=0。若i=j時a(ij)<>0則稱為嚴(yán)格上三角矩陣。下面就是一個嚴(yán)格上三角矩陣。
1 2 1
0 1 1
0 0 1
我們發(fā)現(xiàn)，如果將系數(shù)矩陣化為上三角矩陣，就可以輕而易舉地求解。

可以證明，n*n方程組有唯一解等價于它的增廣矩陣可以化為嚴(yán)格上三角矩陣。

消元過程如下：
對于增廣矩陣A
1 for i:=1 to n-1 do
2 選擇第i至第n行中第i個元素絕對值最大的行，與第3行交換//選擇主元，由于涉及實數(shù)除法運算，選取大絕對值可以減小誤差
3 for j:=i+1 to n do
4 使用第3種行變換使a(j,i)=0
根據(jù)得到的矩陣，可以回代求出每個未知數(shù)x(i)

這只是對于有唯一解的情況。那么，其他情況呢？

我們定義在消元過程中保留的那行稱為主行，主行第一個非零元素稱為主元。消元的任務(wù)就是使主元非0，使主元下方元素變?yōu)?。當(dāng)消元過程中無法選擇非0主元，則此方程組無解或無窮解。此時，我們選擇右邊一列操作。即，若第i行為主行，在第j列無法選擇主元，就對第i+1列操作。這樣，最后的結(jié)果不再是上三角形，而是行階梯形：每一次在豎直方向下降1，在水平方向擴展可能大于1。在增廣矩陣中能夠選擇主元的列對應(yīng)的變量稱為首變量，跳過的列對應(yīng)的變量稱為自由變量。

定義：行階梯形矩陣是一個滿足（1）每一個非零行的第一個非零元為1;(2)若第i行為非零行，則第i+1行行首的0多于第i行;(3)非零行在全零行之前
如這就是一個行階梯形矩陣：
1 2 3 4
0 0 1 3
0 0 0 1
當(dāng)然，對于競賽解方程沒必要把首元素化為1。

定理：m*n線性方程組有解當(dāng)且僅當(dāng)其行階梯形矩陣不含這樣一行：[0 0 ... 0 1]
亦即，對于n*n線性方程組，若沒有唯一解，我們就將其化為行階梯形，若最后某行形如[0 0 ... 0 a] (a<>0) 則無解，否則有無窮多的解。

上面我們主要討論了n*n方程組。下面討論m<>n的方程組：

1 若m>n 則這個方程組稱為超定方程組。超定方程組對應(yīng)的矩陣行數(shù)增加，因此通常無解（但若其行階梯形矩陣上方為嚴(yán)格上三角，下方全為[0 0 ... 0]，則有唯一解；若下方全為[0 0 ... 0]而上方是階梯形，則有無窮解)

2 若m<n 則這個方程組稱為亞定方程組。這個方程組一定沒有唯一解，如果最后有[0 0 ... 0 a](a<>0)則無解，否則有無窮解。

由此可見，對于任意m*n線性方程組，求解均將其轉(zhuǎn)化為行階梯形矩陣。這就是我們所討論的：

定義 利用矩陣行初等變換，將線性方程組的增廣矩陣化為行階梯形的過程稱為高斯消元法（Gaussian elimination)。

而求解線性方程組的步驟：
1 將其增廣矩陣化為行階梯形
2 若最后有形如[0 0 ... 0 a] （a<>0)的行則無解 否則
3 若含有自由變量則有無窮組解 否則
4 原方程有唯一解。采用回代求解。

至于有無窮組解的方程組的求解，需將其化為行最簡形矩陣，其方法稱為高斯-若爾當(dāng)消元法。這里就不討論了。如果只需求出任意一組可行解，則只要給自由變量任意賦值即可。