さて、いろいろな連立一次方程式に掃き出し法を適用していくと、様々なケースに出会います。
まずはこちらのケース。
これに掃き出し法を適用すると、途中でに次のようになります。
最後の式がおかしいですね。このような連立一次方程式は不能であるといい、解が存在しません。
次はこちら。
先ほどの例に似ていますが、最後の定数が違います。こちらに掃き出し法を適用すると次のようになります。
この場合は z を移項し
とすることで、z をパラメータとした解を表示する事ができます。この場合は連立一次方程式が不定であるといい、解が複数存在します。
さて、連立一次方程式の解には3つの場合があることがわかりました。
このような状態を調べるために、線型代数で用いられる行列の階数（ランク）を定義します。今回は、競技プログラミングに適した形で導入します。
これを用いて、次のようにして解の様子を調べることができます。
掃き出し法は連立方程式の解を変えずに変形を繰り返すアルゴリズムです。係数行列と拡大係数行列の階数が異なるとき、掃き出し法の終了後の行列は不能な連立一次方程式の例のように定数ベクトルの部分だけに非ゼロの成分が残ります。これは 0 = 1 を意味し、矛盾します。したがって、この場合には解が存在しないのです。
先に述べたように掃き出し法は解を保存しますので、係数行列のランクは連立方程式を解くときに変数をいくつ消去することができるかを示していると解釈できます。したがって、これによってちょうど変数が全て消去できるならばそれが一意の解となり、余る変数があるならば余った変数を用いて解のパラメータ表示ができるので解は複数個あることになります。ちなみに、このときのパラメータの個数を解の自由度と呼びます。一意解が存在することは解の自由度が 0 であるともいえます。
今年の JAG 春コンテストから例題を1つ解いてみます。
問題はこちらです。J: Tree Reconstruction - Japan Alumni Group Spring Contest 2013 | AtCoder
有向グラフが与えられる。ここに非負流量の循環フローが流れていることがわかっている。すなわち、各辺に非負の流量が設定されていて、各頂点は流量保存則を満たす。あなたは各辺の流量を知らないが、できるだけ少ない辺を調べてすべての辺の流量を決定したい。いくつの辺を調べればよいか求めよ。
頂点 v に関する流量保存則は v に入る辺の流量の和と v から出る辺の流量の和が等しいというもので、これは各辺の流量を変数と見た時に一次式です。したがって、すべての頂点について立式して連立することで連立一次方程式を得ます。この連立一次方程式はすべての流量が 0 という自明解を持ちます（フローが全く流れない場合に対応します）ので、不能ではありません。不能でないとき、連立一次方程式は解の自由度を持ちますが、これは消去しきれずに残った変数の個数のことでした。したがって、この残った変数の値（= ある辺での流量）がわかれば、解が一意に定まることになります。以上の議論から、出力すべき答えはこの連立一次方程式の解の自由度で、これは掃き出し法によって求められます。
出題者による解説もあります。
有効なWikiNameではありません - ACM-ICPC Japanese Alumni Group
SRM 590 の Div.1 Medium 問題に、連立一次方程式の解の数え上げによって解く問題が出題されました。
問題はこちらです。TopCoder Statistics - Problem Statement
いくつかの非負整数が書かれたカードが与えられる。このカードの部分集合のうち、部分集合すべての xor を取った値が、ある整数 limit 以下になるようなとり方は何通りあるか求めよ。
xor sum について考えます。例えば、limit が 22 = 0b10110 であったとき、考えられる xor sum は次のようになります（? は don't care）。
要するに、1 が立っているところを 0 にして以下を don't care にしたものを列挙しています。これらの表す集合は互いに重複しないので、それぞれの場合について考えます。たとえば xor sum = 0b100?? のときについて考えます。
カードの数を 18, 6, 20、各カードを選択するかどうかをとすると、
これを bit wise に考えると、例えば最上位ビットは次のようになります *1。
これを定数が don't care でない各ビットについて連立させた方程式の解の個数を数え上げればよいことになります。これは mod 2 上での連立一次方程式です。mod を取るときの話をしていませんでしたが、mod を取る数が素数の場合は基本的には割り算のところを修正する（逆元を掛けるようにする）だけで問題なく掃き出し法が使えます。実際に掃き出し法を行うことで、解のパラメータ表示を得ます。このとき、各パラメータが 0, 1 のみを取ること、パラメータが異なれば解も当然異なることを考えると、この方程式の解の個数は 2^(解の自由度) であることがわかります。
全体として、xor sum の各ケースについて連立一次方程式の解を数え上げて足せば、求める答えになります。
公式の解説もあります。