Ax=bの解の存在判定をO(N×M×min(N,M))で行う

拡大係数行列 (A|b) を考える

この時、\mathrm{rank}(A)=\mathrm{rank}(A|b) の時のみ解が存在する事が知られている。

転置行列についても rank は同じであるため、\mathcal{O}(N\times M\times \min(N,M)) で計算が出来る。

\mathrm{rank}(A^{t}) から \mathcal{O}(N^{2}) で \mathrm{rank}((A|b)^{t}) が求められる事から転置行列においては 2 倍の定数倍高速化も可能である。