掃き出し法

要点：第 $j$ 列まで処理した時点で「最初の $j$ 列が簡約階段形で、第 $r+1$ 行以下の最初の $j$ 列は $0$」が保たれる。

上の補題により、$E_1A$ は 1 回目の変形を施した行列で、以下同様に $E_s\cdots E_1A=B$ である。基本行列は正則で、正則行列の積は正則である（正則行列 の記事の命題「逆行列と演算」の 2）ので $P$ は正則である。区分けした行列の積により $P(A\mid I_m)=(PA\mid P)=(B\mid P)$ である。$\square$

1 は (b) と (d) による。2：第 $i$ 行が $0$ の行（$i>r$）なら $r_{ik}=0$ である。$i\le r$ で $j_i>k$ なら、第 $i$ 行の先頭成分は第 $k$ 列より右にあるので $r_{ik}=0$ である。よって $\rho_k$ の $0$ でない成分は $j_i\le k$ となる行 $i$ にしかない。
3：2 により $\rho_1,\dots,\rho_{k-1}$ はすべて $\operatorname{span}\{e_i\mid j_i< k\}$ に入り、逆にこの $e_i$ は 1 により $\rho_{j_i}$（$j_i< k$）そのものなので、$\operatorname{span}\{\rho_1,\dots,\rho_{k-1}\}=\operatorname{span}\{e_i\mid j_i< k\}$ である。第 $k$ 列が主列 $j_t$ なら $\rho_k=e_t$ で、$j_t=k$ なので $e_t$ はこの部分空間に入らない（標準基底は線形独立）。主列でなければ $\{i\mid j_i\le k\}=\{i\mid j_i< k\}$ なので、2 により $\rho_k$ はこの部分空間に入る。
4：主列でない $k$ について、2 の式の $e_i$ を 1 により $\rho_{j_i}$ に置き換えればよい。$\square$

$R'$ の列を $\rho'_1,\dots,\rho'_n$ とする。$x\in K^n$ について $Rx=\sum_lx_l\rho_l$ なので、「$\rho_k\in\operatorname{span}\{\rho_1,\dots,\rho_{k-1}\}$」は「$x_k=1$ かつ $l>k$ で $x_l=0$ を満たす $x$ で $Rx=0$ となるものがある」と同値である。$R'$ についても同じであり、仮定により $Rx=0$ と $R'x=0$ の解は同じなので、各 $k$ について $\rho_k\in\operatorname{span}\{\rho_1,\dots,\rho_{k-1}\}$ と $\rho'_k\in\operatorname{span}\{\rho'_1,\dots,\rho'_{k-1}\}$ は同値である。lem-ge-columns の 3 により、$R$ と $R'$ の主列の番号の集合は一致する。したがって $0$ でない行の個数 $r$ も、先頭成分の列 $j_1<\cdots< j_r$ も一致し、1 により主列は $\rho_{j_i}=e_i=\rho'_{j_i}$ である。
主列でない $k$ をとる。lem-ge-columns の 4 により、$x_k=1$、$x_{j_i}=-r_{ik}$（$j_i< k$）、ほかの成分を $0$ とした $x$ は $Rx=0$ を満たすので、$R'x=0$ でもある。これは $\rho'_k=\sum_{i:\,j_i< k}r_{ik}\rho'_{j_i}=\sum_{i:\,j_i< k}r_{ik}e_i$ ということであり、右辺は同じ 4 と 1 により $\rho_k$ に等しい。よってすべての列が一致し、$R=R'$ である。$\square$

存在は prop-ge-output による。$R,R'$ がともに $A$ と行同値な簡約階段形なら、行基本変形は $Ax=0$ の解の集合を変えない（連立1次方程式 の記事の命題「行基本変形は解集合を変えない」で $b=0$ とする）ので、$R$ と $R'$ の核はどちらも $A$ の核に等しい。thm-ge-kernel-determines により $R=R'$ である。$\square$

(i)⇒(ii) は prop-ge-elementary である。
(ii)⇒(iii)：$PA$ の第 $i$ 行は $\sum_kp_{ik}\cdot(A\text{ の第 }k\text{ 行})$ なので $\operatorname{Row}B\subset\operatorname{Row}A$ である。$A=P^{-1}B$ なので逆の包含も成り立つ。
(iii)⇒(iv)：$Ax=0$ は、$A$ の各行 $a$ について $ax=0$（横ベクトルと縦ベクトルの積）ということであり、$y\mapsto yx$ は線形なので、これは $\operatorname{Row}A$ のすべての $y$ について $yx=0$ と同値である。よって核は行空間だけで決まる。
(iv)⇒(v)：$A,B$ の簡約階段形を $R_A,R_B$ とすると、cor-ge-rref-unique の証明と同じく $R_A$ の核は $A$ の核、$R_B$ の核は $B$ の核に等しい。仮定によりこれらは等しいので、thm-ge-kernel-determines により $R_A=R_B$ である。
(v)⇒(i)：$A$ と $R_A$、$B$ と $R_B=R_A$ は行同値で、行同値は同値関係なので $A$ と $B$ は行同値である。$\square$

1：thm-ge-row-equivalence の (i)⇒(iii) により $\operatorname{Row}A=\operatorname{Row}R$ で、$R$ の $0$ の行は行空間に寄与しないので、$0$ でない行は $\operatorname{Row}A$ を張る。$0$ でない行の線形結合 $\sum_{i\le r}c_i(R\text{ の第 }i\text{ 行})$ の第 $j_t$ 成分は、主列 $\rho_{j_t}=e_t$（lem-ge-columns の 1）により $c_t$ である。よってこれが $0$ なら $c_1=\cdots=c_r=0$ であり、線形独立である。
2：$A$ と $R$ は行同値なので核が等しく、$\sum_kx_ka_k=0$ と $\sum_kx_k\rho_k=0$ は同値である。$\sum_ic_ia_{j_i}=0$ なら $\sum_ic_i\rho_{j_i}=\sum_ic_ie_i=0$ なので $c=0$ であり、$a_{j_1},\dots,a_{j_r}$ は線形独立である。主列でない $k$ について、lem-ge-columns の 4 の関係 $\rho_k-\sum_{j_i< k}r_{ik}\rho_{j_i}=0$ の係数を並べた $x$ は $Rx=0$、したがって $Ax=0$ を満たし、これは $a_k=\sum_{j_i< k}r_{ik}a_{j_i}$ ということである。よって $a_{j_1},\dots,a_{j_r}$ は列空間を張り、その基底で、列空間の次元は $r$ である。
3：$y^{\top}A=0$ は $y^{\top}P^{-1}R=0$ と同値である。$z^{\top}:=y^{\top}P^{-1}$ とおくと $z^{\top}R=\sum_{i\le r}z_i(R\text{ の第 }i\text{ 行})$ であり、1 によりこれが $0$ であることは $z_1=\cdots=z_r=0$ と同値である。よって $y^{\top}A=0$ は $y^{\top}=z^{\top}P=\sum_{i>r}z_i(P\text{ の第 }i\text{ 行})$ と書けることと同値である。$P$ は正則なのでその行は線形独立であり、第 $r+1,\dots,m$ 行は左零空間の基底である。$\square$

要点：前進消去の第 $k$ 段は $(n-k)(n-k+2)$ 回、後退代入で $x_k$ を求めるのは $n-k+1$ 回である。