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

什么是線性方程組？含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)為實數，括號中為下標。這個方程組有多種表示方法。例如，我們知道m*n矩陣（用大寫字母表示）是一個m行n列的數陣，n維向量（用加粗的小寫字母表示）是n個數的數組，也就是一個n*1矩陣（列向量。我們不考慮行向量）。另外，大家也都知道矩陣乘法。因此一個m*n線性方程組可以表示為
Ax=b，其中A是由系數aij組成的m*n矩陣即系數矩陣，x是n維的未知數向量，b是m維的結果向量。如果把向量b寫到A的右邊得到m*(n+1)的矩陣，得到的新矩陣稱為這個方程組的增廣矩陣。每一個方程組均對應于一個增廣矩陣。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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