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

拡大係数行列を考える。

この時、の時のみ解が存在する事が知られている。

転置行列についてもrankは同じであるため、で計算が出来る。

からでが求められる事から転置行列においては2倍の定数倍高速化も可能である。