昨日の
「行列マジック」
パズルの解答。
数学には「よくよく考えてみると当たり前なんだけれども、やっぱり不思議」
ということがあるもので、これはその典型例。つまり明らかだけれど、トリヴィアルではない。
2 行 2 列から試すのが筋で、しばらくすると（多分、4 x 4 あたりで）悟りが開けるのだが、
一般的な証明にチャレンジしてみよう。しかも、
数学記号を使わないと却って分かり難いところを、あえて、普通の言葉で説明してみる。
よーく考えると、「アーハー！」体験できること間違いなし。
すでに各行の中では大きい順に並び換え終わったとしよう。 どれでもいいのだが、一つの行について考える。 3 番目の行としておこうか。 さらにその行のどこでもいいから、二つの場所に注目する。 5 番目と 8 番目としておこう(5 番目の数の方が大きい)。 ここで、第 5 列、8 列それぞれの中で、大きい順に並び換えたあとでも、 この二箇所にある数の大小関係が変わらないことを示せばよい。 列の中で並び換えると、この二つの場所には各列で 3 番目に大きい数が入る。 列で並び変える前は、5 列目の数それぞれは同じ行の 8 列目の数より大きかった。 すると、第 8 列の数の中で、3 行目 5 番目の数 X より大きい可能性があるのは、高々 3 - 1 = 2 つしかない。 なぜなら、他の数は全て、X より小さいか(列で並び換える前に X と同じ行にあった）、 X より小さい数より小さい（X より小さい数と同じ行にあった）。 一方、現在 8 列目 3 行目にある数は 8 列目の中で大きさで 3 番目なのだから、 X より小さい。証明終わり。
説明するとややこしいが、分かってしまうと、どうにも明らかである。でも不思議。 もちろん、この性質は正方行列に限らず、 全く一般のどんなサイズの行列でも、どんな成分でも(順序づけ可能なら)、成り立つ。 衝撃的な性質の割にあまり知られていないが、古典的な定理である。 D.Knuth の "The Art of Programming" によれば、「Boerner の定理」らしい。
