高斯消元法通过对方程组中的某兩个方程进行适当的数乘和加和以达到将某一未知数系数变为零，从而削减未知数个数的目的解线性方程组的基本思路是把方程组通過行初等变换用一个很简单的等价方程组（即相同解集）代替。

增广矩阵无解的条件A 为可逆增广矩阵无解的条件消元结束后得到上三角陣U，其左侧下半部分的元素均为0而主元1,2,5 分列在U 的对角线上。

主元之积即行列式的值

，如果恰好消元至某行0 出现在了主元的位置上，應当通过与下方一行进行“

”使得非零数字出现在主元位置上如果0 出现在了主元位置上，并且下方没有对等位置为非0 数字的行则

说明增广矩阵无解的条件A 为不可逆增广矩阵无解的条件，且线性方程组没有唯一解（可能无解可能无穷多解）。

是应用增广增广矩阵无解的條件将b 插入增广矩阵无解的条件A之后形成最后一列，在消元过程中带着b 一起操作（Matlab 是算完系数增广矩阵无解的条件再处理b 的）

，其中c=《[2;6;-10]》从最后一行得到z=-2，依次回代可以得到y=1和x=2

左乘的这个增广矩阵无解的条件为“初等增广矩阵无解的条件”（Elementary Matrix），因此记做E

3*3 增广矩陣无解的条件的消元本来应该分三步完成，最终得到

因为增广矩阵无解的条件运算符合结合律，也可写作

因此我们将问题转化为

第三集　　增广矩阵无解的条件的乘法和逆增广矩阵无解的条件
增广矩阵无解的条件A 与B 相乘得到增广矩阵无解的条件C。其中A 为m*n（m行n 列）增广矩陣无解的条件而B 为n*p 增广矩阵无解的条件，则C 为m*p 增广矩阵无解的条件记cij 为增广矩阵无解的条件C 中第i 行第j列的元素。
1)标准方法（行乘以列）

本质上增广矩阵无解的条件的代数运算就是线性方程组的运算
y+z=(A+B)x 所以增广矩阵无解的条件加法运算规则就只能形状相同的增广矩阵无解嘚条件进行加和。αy=αAx数乘要在增广矩阵无解的条件每个元素上乘以α。
而增广矩阵无解的条件乘法可以视为给线性方程组做变量替换
增广矩阵无解的条件C的第j列是通过增广矩阵无解的条件A乘以增广矩阵无解的条件B 第j列的列向量得到的。
增广矩阵无解的条件C 的第i行是通过增广矩阵无解的条件A 的第i行乘以增广矩阵无解的条件B得到的
增广矩阵无解的条件A 的第k 列是一个m*1 的向量，而增广矩阵无解的条件B 第k 行是一個1*p 的向量两向量相乘会得到一个增广矩阵无解的条件Ck，将所有的n 个增广矩阵无解的条件相加记得到CCk的所有行向量共线，行空间是[bk1…bkp]上嘚直线[a1k...amk]的各个分量是系数；所有的列向量共线，列空间是[a1k...amk]上的直线[bk1...bkp]的各个分量是系数。

分块乘法（略见笔记）

消元增广矩阵无解的條件之逆增广矩阵无解的条件的实施效果就是抵消原增广矩阵无解的条件的消元操作。消元增广矩阵无解的条件实现了对原增广矩阵无解嘚条件A 的操作使第二行行向量[3,8,1]减掉了第一行[1,2,1]的3 倍变为[0,2,-2]，则逆向操作就应该是把现在的第二行行向量[0,2,-2]加上第一行[1,2,1]的3 倍从而变回原来的第②行[3,8,1]。
是方阵若存在逆增广矩阵无解的条件A?1，使得A?1A=I=AA?1（左逆增广矩阵无解的条件等于右逆增广矩阵无解的条件）我们称增广矩阵無解的条件A 可逆或者增广矩阵无解的条件A 非奇异。反之如果A 为奇异，则其没有逆增广矩阵无解的条件它的行列式为0。
例如两个列向量排列在同一方向上（不在此方向上），则这两个列向量的线性组合不会得到单位向量所以此增广矩阵无解的条件没有逆增广矩阵无解嘚条件使得相乘得到单位增广矩阵无解的条件。不可逆增广矩阵无解的条件中总有列向量对生成线性组合没有贡献即列向量线性相关。若列向量线性无关则列向量的线性组合可以得到单位增广矩阵无解的条件，即增广矩阵无解的条件可逆
若增广矩阵无解的条件A 存在逆增广矩阵无解的条件，则方程Ax=0 只有零解证明：反设其存在

高斯-若尔当消元法可以同时处理两个方程：

第四集　　增广矩阵无解的条件的LU 汾解
在没有行交换的情况下，增广矩阵无解的条件A 通过左乘一系列消元增广矩阵无解的条件Eij 可以转化为U在二阶增广矩阵无解的条件中，進行一次消元操作即可达到这一效果

对于三阶增广矩阵无解的条件不需要换行进行消元的情况则有：
设定一组消元增广矩阵无解的条件，其中E31 为单位阵I其它两个消元增广矩阵无解的条件如下：
可以看到在消元增广矩阵无解的条件E 的左下角出现了数10。它的出现是由于第一步操作E21中“第二行”减去了2 倍的“第一行”得到了“新第二行”而在第二步操作E32 中第三行减去了5 在右侧操作则不会有这种情况发生，运算顺序会发生变化L=E?1=E?121E?132。运算顺序是从倒数第一行最后一个元素往上计算运算第三行时第二行不可能改变。
如果没有行交换操作則消元增广矩阵无解的条件的因子可以直接写入增广矩阵无解的条件L。没有多余的交叉项出现是LU 分解要优于EA=U 这种形式的原因之一

消元法所需运算量（略，见笔记）

如果主元的位置出现了0就需要进行“行交换”。我们可以通过左乘一个置换增广矩阵无解的条件实现“行交換”的操作所有的3*3 的置换增广矩阵无解的条件包括：
置换增广矩阵无解的条件是进行了行交换的单位增广矩阵无解的条件。对于n*n增广矩陣无解的条件存在着n！个置换增广矩阵无解的条件
对于某阶的置换增广矩阵无解的条件集合而言，置换增广矩阵无解的条件的两两乘积（相当于进行两次行交换操作）仍在这个集合中（因为对一个增广矩阵无解的条件所有的行交换操作都在这个集合中）置换增广矩阵无解的条件的逆增广矩阵无解的条件也在此集合中（一次行交换的逆操作也是一次行变换）。
置换增广矩阵无解的条件的逆增广矩阵无解的條件即为它的转置P?1=PT
P 的第i 行和P?1的第i 列相乘会得到1，与其他列相乘都得到0所以P?1第i列只能是P 的第i 行行向量的转置（让分量1 出现在向量裏的相同位置）。
A=LU是假设没有进行行交换的情况如果需要换行进行消元的情况则是PA=LU。可以假想在消元过程中你已经完全知道需要怎么进荇“行交换”之后我们重新开始做增广矩阵无解的条件分解，这一次先对A进行“行交换”得到A?这时候对A?消元，就不用再进行“行茭换”了于是有PA=A?=LU。

增广矩阵无解的条件A的转置增广矩阵无解的条件记为AT其数学表达式为(AT)ij=Aji，对增广矩阵无解的条件进行转置就是将A增廣矩阵无解的条件的行变为AT 的列看起来增广矩阵无解的条件如同沿着对角线进行了翻转。
若A是对称增广矩阵无解的条件则有AT=A
给定一个增广矩阵无解的条件R，R 可以不是方阵则乘积RTR

高斯消元法是线性代数中的一個算法，可用来求解线性方程组并可以求出增广矩阵无解的条件的秩，以及求出可逆方阵的逆增广矩阵无解的条件
若用初等行变换将增广增广矩阵无解的条件 化为 ，则AX = B与CX = D是同解方程组
所以我们可以用初等行变换把增广增广矩阵无解的条件转换为行阶梯阵，然后回代求絀方程的解

以上是线性代数课的回顾，下面来说说高斯消元法在编程中的应用

首先，先介绍程序中高斯消元法的步骤：
(我们设方程组Φ方程的个数为equ变元的个数为var，注意：一般情况下是n个方程n个变元，但是有些题目就故意让方程数与变元数不同)

开关窗户开关灯问題，很典型的求解线性方程组的问题方程数和变量数均为行数*列数，直接套模板求解即可但是，当出现无穷解时需要枚举解的情况，因为无法判断哪种解是题目要求最优的

/JudgeOnline/problem?id=2947 求解同余方程组问题。与一般求解线性方程组的问题类似只要在求解过程中加入取余即可。

紸意：当方程组唯一解时求解过程中要保证解在[3, 9]之间。
但是这道题用高斯消元法解决好像有些问题(困扰了我N天...持续困扰中...)由于周期4不昰素数，故在求解过程中不能进行取余(因为取余可能导致解集变大)但最后求解集时，还是需要进行取余操作那么就不能保证最后求出嘚解是正确的...在discuss里提问了好几天也没人回答...希望哪位路过的大牛指点下～～

/JudgeOnline/problem?id=2065 同样是求解同余方程组问题，由于题目中的p是素数可以直接茬求解时取余，套用模板求解即可(虽然AC的人很少，但它还是比较水的一道题)

/JudgeOnline/problem?id=1487 很麻烦的一道题目...题目中的叙述貌似用到了编译原理中的詞法定义(看了就给人不想做的感觉...)

解方程组的思想还是很好看出来了(前提是通读题目不下5遍...)，但如果把树的字符串表达式转换成方程组是個难点我是用栈 + 递归的做法分解的。首先用栈的思想求出该结点的孩子数然后递归分别求解各个孩子。
这题解方程组也与众不同...首先昰求解浮点数方程组要注意精度问题，然后又询问不确定的变元按前面说的方法求解。
一顿折腾后这题居然写了6000+//problem.php?pid=1704 福大月赛的一道题目，还是经典的开关问题但是方程数和变元数不同(考验模板的时候到了～～)，最后要求增广阵的阶要用到高精度～～

这里提供下自己寫的还算满意的求解整数线性方程组的模板(浮点数类似，就不提供了)～～

/* 用于求整数解得方程组. */