高斯消元

即通过初等行变换，将矩阵变换为 行最简形矩阵。通过这种方法，可以求解矩阵的逆，矩阵的秩，以及求解线性方程组。
注：行最简形矩阵，它是一种阶梯形的矩阵，指的是矩阵中非零行的第一个非零元素全是1，且非零行的第一个元素1所在的列的其余元素全是0的矩阵。
初等行变换：
  • 某两行位置交换
  • 某一行乘上非零系数a
  • 某一行的若干倍加到另一行上。
初等行变换后：
  • 完美阶梯型——唯一解
  • 0=非0值——无解
  • 0=0——无穷个解
化解为 行最简形矩阵 之后，最后一列即为未知数的答案，如下图所示
notion imagenotion image
化解为 行最简形之后，矩阵中1 的个数即为 矩阵的秩
伪代码
枚举第 j 列：
		从第 j 行开始，往下找一个非 0 数
				如果没找到：
						输出跳过该列
				如果找到了，设它在第 k 行：
						交换第 k 行和第 j 行
						第 j 行除以 Ajj ，使 Ajj = 1
						消掉第 j 列的其他元素
剩下的第 n+1 列即为答案。
def gauss(arr):
    m, n = len(arr), len(arr[0])
    for j in range(0, m):
        # 当前需要修改的行
        cur_i = j

        # 找到当前列的非 0 元素 所在行
        idx = cur_i
        while idx < m:
            if arr[idx][j] != 0:
                break
        # 如果当前列没有非0 元素，判断下一列
        if arr[idx][j] == 0:
            continue
        
        # 交换非 0 元素所在行idx 与 cur_i 行
        if idx != cur_i:
            for k in range(0, n):
                arr[idx][k], arr[cur_i][k] = arr[cur_i][k], arr[idx][k]
        
        # 把当前行 cur_i 除 arr[cur_i][j],使得 当前行首个非0元素为1
        temp = arr[cur_i][j]
        for k in range(0, n):
            arr[cur_i][k] /= temp
        
        # 对当前列的其他行进行消元，使得当前列其他元素为 0 
        for i in range(0, m):
            if i == cur_i:
                continue
            temp = arr[i][j]
            for k in range(j, n):
                arr[i][k] += - arr[cur_i][k] * temp
       

arr = [[2, -1, 1, 1], [4, 1, -1, 5], [1, 1, 1, 0]]

>>>gauss(arr)
>>>print(arr)
[[1.0, 0.0, 0.0, 1.0], [0.0, 1.0, 0.0, 0.0], [0.0, 0.0, 1.0, -1.0]]

# 最后一列 即为 未知数的答案 即 x_1 = 1.0, x_2 = 0.0, a_3 = -1.0