離散数学と線形代数と計算量理論の絶妙なコラボ本
今回は、マトウシェク『33の素敵な数学小景』(徳重典英・訳、日本評論社)の紹介をしようと思う。
この本は刊行直後に入手していたにもかかわらず、読んだのはつい最近だ。なぜ、つい最近読んだかといえば、前回のエントリー、
二つの雑誌に寄稿しています！ - hiroyukikojima’s blog
に書いたように、『現代思想』の特集号「巨大数の世界」で徳重さんの記事を読んだからだった。その記事には、本書の内容の紹介もあり、「ああ、そういうことが書かれた本だったのか」と判明して、興味がわいて、早く読んでみたいと思ってひもといたのだ。
そうしたら、予想外にとても面白い本だとわかった。
この本は、簡単にまとめれば、「離散数学と線形代数と計算量数学の絶妙なコラボ」というひじょーに面白いテーマを持っている本だ。そういうテーマの本はぼくは他に知らない。
３３個の話題のうちの６個程度を読んだだけなので、本書を的確に書評できる段階ではないけど、読んだ話題はみんな面白かったので、この段階でエントリーしておこうと思う。
現段階で読んだトピックについて感想を簡単に言えば、「こんなことにも、線形代数が有効に使えるのか！」という驚きである。
もちろん、線形代数は微積分と並んで、最も多方面で役に立つアイテムであることは疑いない。物理学では言うまでもなく、統計学なんか線形代数の植民地と言っていいぐらいだし、経済学でさえところどころでお世話になる。
でも、それらの使用性は、「見るからに」なものなのだ。
それに対して、本書での線形代数の利用は、(離散数学の専門家以外には)かなり意表を突くものとなっている。
読んだ中で一番感心したのは、次の定理だ。
定理 平面上の四点で、どの二点間の距離も奇数のものはない。
これはもう、見るからに、離散数学(組み合わせ論、グラフ理論)の典型的な定理だ。そんなこの定理の証明に、まさか線形代数が大活躍するなんて思わないだろう。
詳しくは本書で厳密な証明を読んでもらうことにして、おおざっぱに証明の手筋をまとめよう。
まず、ベクトルの内積を用いて、「距離が奇数」という情報を「内積をmod.8で表したもの」に変換する。そのうえで、この情報を内積を並べた対称行列の階数の問題に書き換えるのである。そうすると、行列の積のよく知られた階数の性質に帰着され、鮮やかに解決される。
証明はトリッキーで意表を突くものだけど、それより何より、このような「定形外の問題」に対して、標準的な線形代数の技法が有効になる、ということ自体に感動する。
この例は「計算量」とは関係しないが、次のような問題が「計算量」の形となっている。
今、行列の積の計算を特定のアルゴリズムで計算機に実行させたとしよう。
脇道にそれるが、ファミコンの64かなんか買ったとき、スーパーマリオの新作のソフトだけまず入手した。そうしたら、そのCGがすごかった。3Ｄでまわりを簡単に見回すことができるのだ。当時、工学部で情報理論をやってる知り合いがいた。で、そいつとそのことについて話してたら、そいつが「小島さん。あれは、3Ｄの回転を瞬時に計算する行列計算のチップが入ってるんですよ」と教えてくれた。ゲーム用のチップに行列を直接計算するアルゴリズムが入っている、ということに心底驚いた経験をしたのだな。
さて、話戻って、行列の積の計算結果が正しいかどうかを検証するには、別のプログラムを組んで、実際に積をもう一度計算して答えを比較すればいいが、一般に行列の積のアルゴリズム実行には相当な時間がかかる。そこで、著者が提唱しているのは、1と0だけからなるベクトルを掛け算してみて、一致するかどうかを見ることだ。その際に、「計算間違いを検出できる確率は少なくとも1/2より大きい」ということが証明できるのである。だから、10個の01ベクトルで検証すれば、間違う確率は1/1000以下になる。01ベクトルとの積は簡単なアルゴリズムなので、これはかなり効率のいい検証法を与える。
行列の積に関する本書の別の話題もある。それは、「n次正方行列2個の積には、nの3乗回の積計算が必要だが、もう少し計算量を少なくできる」、という話題だ。これについては、訳者・徳重さんによる付録に、「Strassenの方法」が例示されている。2×2行列２個の積には、(2の3乗=)8回の積計算が必要なのだが、工夫をすれば、7回の積計算で済むというのである。ぼく自身は、計算機数学にはあまり関心がないが、「そういう風にやるのか」とちょっと驚いた。
本書の最も初歩の話題の中に、「フィボナッチ数」についてのものがある。フィボナッチ数列とは、
１項目と２項目が1
という出発で、
前の２項の和が次の項になる
という漸化式で与えられるものだ。
この数列が「ルート５」のかかわる無理数２個のべき乗を使って式表現されるのは、優秀な受験生ならだれでも知っている。また、その公式がいわゆる３項間漸化式の定番の解法で求められることも常識である。しかし、本書で著者は、「無限次元のベクトル」を使ってそれを線形代数の問題に帰着させて求めている。受験数学のテクニックとまっすぐ対応させることは可能であるけれど、線形空間の性質を無限次元ベクトルに適用するのを目の当たりにすると、線形代数を熟知していてもちょっとサプライズがある。「そっかあ、線形代数ってものごとをわかりやすくするなあ」とため息が出る。
以上は、本書のほんのわずかな部分にすぎないが、全体はさまざまなトピックで彩られているから、読んでいて飽きないと思う。ただし、ページをめくるごとに、トピックが難しくなることは覚悟しなければならない。そうではあるが、本書で使われる数学技術に通じていない人には訳者が詳しい補足解説を付録として書いてあるので、(意欲があれば)心配しなくていいと思う。
いやあ、線形代数ってほんとすごいんだな、と思い知らされる。是非、数学ファンには一読していただきたいものだ。
行列の理論についての図形的イメージを得たかったら、ぼくの『ゼロから学ぶ線形代数』講談社が大お勧めであることは言うまでもない。
