我们讨论如何解线性方程组
这里
%5E%5Ctop#card=math&code=%5Cmathbf%7Bx%7D%3D%28x_1%2C%20%5Cldots%2C%20x_n%29%5E%5Ctop&id=sFA5L)是未知数，其它字母是已知常数（可以看成复数，虽然一般我们用实数为例子）。
令
%7Bk%5Ctimes%20n%7D%2C%20%5C%3B%20%5Cmathbf%7Bb%7D%3D(b_1%2C%20%5Cldots%2C%20b_k)%5E%5Ctop#card=math&code=A%3D%28a%7Bij%7D%29_%7Bk%5Ctimes%20n%7D%2C%20%5C%3B%20%5Cmathbf%7Bb%7D%3D%28b_1%2C%20%5Cldots%2C%20b_k%29%5E%5Ctop&id=HH2i1), 原方程组用矩阵记号可以简洁地表示为
. 这是”矩阵乘法为什么要像课本那样定义”的一个原因。矩阵
#card=math&code=A%2C%20%5C%3B%20%28A%2C%20%5Cmathbf%7Bb%7D%29&id=j5DxO)分别称为原方程组的系数矩阵(coefficient matrix)与增广矩阵(augmented matrix)
最简单的情况当然是
, 且方程组像下面的形式：
这几乎是直接写出了解。此时系数矩阵是对角矩阵。
稍微复杂一些，则是系数矩阵是上三角矩阵的形式：
求解时从下向上，先解出
, 然后代入倒数第二个方程
求出
. 如此类推 (back substitution).
这时要注意几个问题：
(i) 当且仅当
时，方可解出
, 否则无解（是整个方程组无解）！
(ii) 进一步，Cramer’s rule告诉我们，方程组有唯一解的充要条件是所有的
, 即系数矩阵的行列式
不等于0.
(iii) 如果
，那么方程组有解当且仅当
. 这时要注意，当方程组有解时，一定有多个解（因为一定有一些自变量可以取任意值）.
下面讨论一般情况（为简便，经常考虑3个未知数，
个方程）.
例1：”百鸡百钱问题”：一只公鸡5文钱，一只母鸡3文钱，三只小鸡1文钱。用100文钱买100只鸡，有几种可能？
解：设公鸡，母鸡，小鸡分别买
只，则
此外，对这个问题，还要假设
都是非负整数。
暂且不管
是否整数，只看方程组(*). 它与下面的方程组同解：
第一个方程乘以-15，加到第二个方程，得到新方程组
这个方程组的第二个方程，两边乘以-1/6, 得 
x_3%20%3D%20200#card=math&code=x_2%20%2B%20%287%2F3%29x_3%20%3D%20200&id=Hoac9). 这样，方程组(*)与下面的方程组
x_3%20%26%3D%20200%2C%0A%5Cend%7Barray%7D%0A%20%5Cend%7Bcases%7D%0A#card=math&code=%5Cbegin%7Bcases%7D%5Ctag%7B%23%7D%0A%5Cbegin%7Barray%7D%7Bcccc%7D%0A%20x_1%20%2B%20%26%20x_2%20%2B%20%26x_3%20%26%3D%20100%2C%5C%5C%0A%20%26%20x_2%20%2B%20%26%287%2F3%29x_3%20%26%3D%20200%2C%0A%5Cend%7Barray%7D%0A%20%5Cend%7Bcases%7D%0A&id=uFntP)
是同解方程组。
方程组(
)有3个未知数，但只有2个方程。此时可以选择任何一个未知数作为”常数”（自由变量），允许它取任意值，这样就化为2个未知数2个方程的情况，而且系数矩阵是上三角矩阵。即(3)的情形(不过
)。我们选
作为自由变量，则(
)可以进一步化简为
x_3%20%26%3D%20-100%2C%5C%5C%0A%20%26%20x_2%20%2B%20%26(7%2F3)x_3%20%26%3D%20200%2C%0A%5Cend%7Barray%7D%0A%20%5Cend%7Bcases%7D%0A#card=math&code=%5Cbegin%7Bcases%7D%5Ctag%7B%23%23%7D%0A%5Cbegin%7Barray%7D%7Bcccc%7D%0A%20x_1%20%2B%20%26%20%20%26%20%28-4%2F3%29x_3%20%26%3D%20-100%2C%5C%5C%0A%20%26%20x_2%20%2B%20%26%287%2F3%29x_3%20%26%3D%20200%2C%0A%5Cend%7Barray%7D%0A%20%5Cend%7Bcases%7D%0A&id=LiSQU)
马上可以写出解：
.
我们把解写成列向量的形式：
其中
为任意常数。当然也可以写为
是任意常数. 各位也可以选择
或
作为自由变量，写出相应的解。
注：百鸡百钱问题要求
都是非负整数。这样
必定要是3的倍数。最后求出百鸡百钱问题的解为
%3D(0%2C%2025%2C%2075)%2C%5C%3B%20(4%2C%2018%2C%2078)%2C%5C%3B%20(8%2C%2011%2C%2081)%2C%5C%3B%20(12%2C%204%2C%2084).#card=math&code=%28x_1%2C%20x_2%2C%20x_3%29%3D%280%2C%2025%2C%2075%29%2C%5C%3B%20%284%2C%2018%2C%2078%29%2C%5C%3B%20%288%2C%2011%2C%2081%29%2C%5C%3B%20%2812%2C%204%2C%2084%29.&id=sVz26)
例2：
这个方程组无解，因为第2,3两个方程矛盾。具体而言，第二个方程乘以-3，加到第3个方程，得到
这样的矛盾方程。用增广矩阵表示如下：
我们看到，解线性方程组，是用消元法 (elimination)，把方程组化简为系数矩阵是上三角的形状。为陈述解线性方程组的算法，我们引入下面的
定义：所谓阶梯形(row echelon form)的矩阵，是指矩阵的形状满足下面两个条件：
(i) 元素全部是零的行（如果有），要在非零行的下面；
(ii) 矩阵的每一个非零行，从左向右数的第一个非零元素的下方，全部是零。
例3：百鸡百钱问题中，我们最后得到的方程组
#card=math&code=%28%5C%23%5C%23%29&id=H1mTI)的增广矩阵是
这是阶梯形。
例4：下面两个矩阵也是阶梯形：
例5：下面这个矩阵不是阶梯形：
现在指出解线性方程组(1)的算法——初等行变换！这个算法据说在Newton的笔记中就已经出现。现代通用的陈述一般认为是Gauss提出的。
Step 0. 如果
, 找一个非零的
(最好
)，把原方程组第
行与第1行对调。以对调后的方程组为目标来求解。以下假设
.
Step 1. 第一行乘以
, 这样第一个方程的
的系数变成了
；
Step 2. 第一行依次乘以
, 加到其它各行（各个方程），把其它方程中的
这一项消掉。这时系数矩阵变成了
Step 3. 现在对
这部分重复上面的步骤，我们的最后目标是把系数矩阵化为阶梯形.
Step 4. 把增广矩阵化为阶梯形后，看系数矩阵的非零行数目，是否等于增广矩阵的非零行数目。如果相等，那么原方程组有解，如果不相等，那么无解。
注：这个判断准则看起来挺复杂，但只用一个最简单的例子就能解释：考虑
的情形，即方程
. 增广矩阵是
#card=math&code=%28a~%5Cvdots~b%29&id=zRfHe), 系数矩阵是
#card=math&code=%28a%29&id=NG3aR). 熟知
有解只能是如下两种情况：
（唯一解
, 或
(无数个解, 
可以取任何数). 第一种情形即系数矩阵与增广矩阵的非零行数目都是1，第二种情形即系数矩阵与增广矩阵的非零行数目都是0.
那么，有解时，如何能快速求出（写出）所有的解？这时要引入下面的：
定义：简化行阶梯形（reduced row echelon form, RREF, 也称”行最简形”）是这样的矩阵：
(i) 首先是阶梯形；
(ii) 其次，阶梯形中每个非零行，从左往右数，第一个非零元要等于1；我们把这些1称为“主元”(pivot)。
(iii) 在(ii)中出现的那些主元”1”，它所在的列，其它元素都要是0.
例6：百鸡百钱问题的矩阵(4’’)是简化阶梯形。
例7：矩阵
的简化行阶梯形是
它的主元在第1，2，4列。
继续解线性方程组的算法：
Step 5. 观察主元在哪几列，用对应的未知数作为主要未知数，其它未知数作为自由变量，用自由变量表示出主要未知数，从而得到方程组的解。（求解的步骤是从最后一个非零行开始，往上逐个求解—back substituion)
以上就是解线性方程组的算法。我们把上面的结论总结如下：
定义：矩阵
的秩(rank)
#card=math&code=r%28M%29&id=PYcfW)是指把这个矩阵化为阶梯形后，非零行的数目。
定理：线性方程组(1) 
有解当且仅当
%3Dr(A%2C%20%5Cmathbf%7Bb%7D)#card=math&code=r%28A%29%3Dr%28A%2C%20%5Cmathbf%7Bb%7D%29&id=RV2Of). 当它有解时，如果%3C#card=math&code=r%28A%29%3C&id=f9KfU)未知数的数目（即
的列数），则有无穷个解，否则只有唯一的解。
推论：当
时，方程组
称为齐次(homogeneous)线性的。它有唯一解当且仅当%3DA#card=math&code=r%28A%29%3DA&id=CGBjp)的列数。它的唯一解一定是
.
