つぎのような連立一次方程式を考えます。
もちろんみなさんは解けますよね？
上の式の 2 倍を下の式から引いて
下の式を -1 倍して
下の式の 2 倍を上の式から引いて
このように項を消して整理していくことで解を得ます。
実はこの連立一次方程式は行列の形て次のように書きなおすことができます。
実際に成分を計算することでもとの連立一次方程式と同値であることがわかります。
一般に n 元 m 連立の一次方程式は m 行 n 列の行列を用いて書きなおすことができます。各行がひとつの等式に対応します。
このように書きなおした行列の方程式についても、冒頭で項を消して整理するのと同じ操作をすることで解くことができます。これがいわゆる掃き出し法です。蟻本にも載っていますし、ライブラリとして持っている方も多いかと思います。
典型的な実装は、係数行列に定数ベクトルの列を追加した拡大係数行列に対して掃き出していくものです。蟻本の実装もそうなっています。
掃き出し法をもちいて、昨年度のアジア地区予選の問題を解いてみましょう。
問題はこちらです。no title
ある d 次多項式 f が存在し、入力として f(0), f(1), ..., f(d+2) が与えられる。ただし、入力のうちちょうど1つは誤った値である。誤った値がどれであるか指摘せよ。
とおくと、入力の各値を用いてに関する連立一次方程式を立てることができます。これを用いると f を決定することができますが、このとき入力値の選び方により2通りの場合にわかれます。
前者は自明ですね。では後者について証明しましょう。d 次多項式は通る d+1 点を指定すると一意に定まるという定理 *1 を用います。残った値が正しく再現できているとすると、構成した多項式と使った入力値のうち正しいものと再現しようとした点を用いて決まる多項式は同一となるはずですが、前者はもとの f とは異なるものに一意に定まっているはずで後者は f にほかならないので矛盾します。
この事実を用いて、各点を外して連立一次方程式を立てることを繰り返せば解けます。
*1：相異なる d 次式 f, g が条件を満たすとすると f(x) = g(x) は d+1 個の解を持つはずだが、この方程式はたかだか d 次であり、解をたかだか d 個しか持たないので矛盾。