对一个线性方程组，比如：
现在我们想要解这个线性方程组，我们能做的是其中一个式子乘以一个数，与另一个式子相减，消去一个变量，重复上述步骤再消去另一个变量。这种解方程组的方式初中就已经学过，它被称为“消元”。
比如对于上边的方程组，（1）+（2），消去变量,得到新的方程
。再用新方程乘以5，再减去（3）式得到只含有x_3的式子
。解得
。再回代
解得
。
这个过程很简单，但想一想我们在消元的过程中做了哪些工作：
- 行倍加变换（把某一行乘以一个数加到另一行上)
- 倍乘变换（某一行乘以一个非0的数）
- 行交换（两行对调位置）：在我们看来，这条变换我们并没有使用，但你确实可以在消元的过程中对任意俩个式子调换位置，这在矩阵运算中及其重要。
我们把以上三种变换称为初等行变换,可以看出初等行变换不影响方程组的解集。
接下来，我们将方程组的系数提取出来，并按照原来的位置放进第一个方框中，并在第二个方框中放入方程组右侧的常量。
我们把这种一堆数加一个方框的列表称为矩阵。对于求解线性方程组而言我们更喜欢增广矩阵的形式。考虑如果我们把矩阵的每一行看作一个方程，我们对这些行做初等行变换，根据我们所作的初等行变换的次数和方式，我们会得到许多新的矩阵，而这些矩阵和原矩阵必然有着相同的解集。
因此我们说如果一个矩阵经过了若干次初等行变换变为了另一个矩阵，我们就称这两个矩阵是行等价的。行等价的矩阵具有完全相同的解集。
这样一来，对方程组进行消元就转换为了对矩阵进行消元。在处理及其大的方程组和解存与唯一性问题上，矩阵消元法远比传统的解方程组方便的多。
方程组的系统解法—高斯消元法
通过初等行变换将增广矩阵化为阶梯型矩阵的形式：
是阶梯型矩阵每一行的先导元素，我们称之为主元，主元所在的列称为主列,主元不在的列称为自由列。主列对应的变量称为基本变量，自由列对应的变量称为自由变量。
接下来我们通过初等行变换把主元位置的元素化为1，把主列中除主元外其他元素化为0。得到的矩阵称为简化行阶梯型矩阵。
有简化行阶梯型矩阵我们得知：
解得：
这个解称为解的显式表达，只要两个自由变量得值确定，方程组的解就确定。因为存在了自由变量，所以这方程有无数个解。
矩阵方程与向量方程
对于方程组：
我们有另外两种表达：
矩阵方程：
向量方程：
可以看出，矩阵与向量的乘积，是以X中元素为权的A中列向量的线性组合。
向量的运算
- 加法：
- 数乘：
矩阵的线性性质
解的隐式表达：参数向量形式
对于方程的显式解：
我们可以写为以自由变为权的线性组合
例题
poj1222
//高斯消元
#include<iostream>
#include<cstring>
using namespace std;
int a[31][31];//表示30个方程组
int d[5][2] = {{0, 0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int res[5][6];//结果
void back () {
for (int i = 29; i >= 0; i--) {
res[i / 6][i % 6] = a[i][30];
}
}
void gauss () {
for (int i = 0; i < 30; i++) {
//行交换
int k = i;
for (; k < 30; k++) {
if (a[k][i]) break;
}
for (int j = 0; j <= 30; j++) {//att1:根据题意存在唯一解，所以这里k不会>=30 不用再判断了
swap(a[i][j], a[k][j]);
}
//消元--化成单位矩阵
for (int j = 0; j < 30; j++) {//att1：从0开始
if (i == j) continue;//att2:别漏了
if (a[j][i]) {
for (int k = i; k <= 30; k++) {
a[j][k] ^= a[i][k];
}
}
}
}
back();
}
int main()
{
int t, cnt = 0;
cin >> t;
while (t--) {
memset(a, 0, sizeof(a));
for (int i = 0; i < 30; i++) {
cin >> a[i][30];
}
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 6; j++) {
int ti = i * 6 + j;
for (int k = 0; k < 5; k++) {
int tx = i + d[k][0];
int ty = j + d[k][1];
if (tx < 0 || tx > 4 || ty < 0 || ty > 5) continue;
a[ti][tx * 6 + ty] = 1;
}
}
}
gauss();
cout << "PUZZLE #" << ++cnt << endl;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
cout << res[i][j] << ' ';
}
cout << res[i][5] << endl;
}
}
return 0;
}