uniq 的な関数(Haskell)

Haskell のリストから重複要素を除去する関数はnubである.「同じかどうか」を判定する関数を引数に取る nubBy を使いたい場合もある.これらの関数はリスト全体を舐めて重複要素を除去する.

扱っている配列がソート済みである場合も多い.その場合,隣接要素だけ見ていけば重複要素を除去できるはずである.そうすれば少しだけ効率が良いかも知れない.そう考えてこんな関数を書いてみた:

uniq :: (Eq a) => [a] -> [a]
uniq = foldr  uniqAux []
  where uniqAux :: (Eq a) => a -> [a] -> [a]
        uniqAux t [] = [t]
        uniqAux t (u:us) = (if t == u then [u] else [t,u]) ++ us

uniqBy を作るのも簡単である.

※効率がどうこうと言ったが,性能比較はまだしていない.

広告

ブルバキの位相についてのメモ

大学二年生の夏休みはずっとブルバキの位相の本を読んでいたような記憶がある.Springer から出てた “General Toplogy Chapters 1-4” がそれ.いま思えば別にこれが位相空間を学ぶベストの本ではないと思うが,20歳の頃に悩みながら読んだ記憶が美化されてしまうせいもあってか不思議と嫌いになれず,いまだに手元にこの本が置いてある.

上で《嫌いになれない》と書いた.この本は多くの位相空間の教科書とはなんとなく書き方が違う.なにせ,肝心の位相空間の定義の仕方からして少し変わっている.ややクセがあるのは確かであり,人前で《この本が好き》というのは少し気恥ずかしい.どう書けば《変わってる》感じが伝わるかわからないが,ここでは二点

1.開集合系の定義の仕方
2.フィルターへの偏愛

に絞って説明する.

■1.開集合系の定義の仕方
ブルバキでは集合{X}上の位相構造{T}が次のよう性質を満たすものとして定義されている:
(O1) {T}の集合の合併は{T}に属する.
(O2) {T}の集合の有限交差は{T}に属する.

多くの教科書では{X,\varnothing \in T}も公理になっている.しかし,実はこれは(O1)(O2)から次のように導ける:

・空集合が{T}に属すること:{T}の空部分集合を考える.(O1)により{\bigcup \varnothing \in T}となることから成立.

{X}{T}に属すること:{T}の空部分集合を考える.(O2)により{\bigcap \varnothing \in T}となることから成立.

上の議論には納得が行くだろうか.空集合が{T}に属することの議論には問題がないが,{X}{T}に属することの議論はどうだろうか.そもそも{\bigcap \varnothing}の指示内容は何だろうか——それが存在するとして,それは果たして集合だろうか?

(念のために付言すれば,通常の集合論では{\bigcap \varnothing}を考えない.たとえばキューネン『キューネン数学基礎論講義』p.32とそこにおける議論を見よ).

■2.フィルターへの偏愛
位相空間はフィルターを用いて定義することもできる.この《フィルター》というのはブール代数などでも研究されるフィルターと大体同じ概念である.(Xの冪集合をブール代数とみなしたときの「ブール代数のフィルター」はこの本での「フィルター」になっている).フィルターを通して眺めると連続性の議論がやや代数的な雰囲気になる.とはいえ,この本で扱われている範囲ではあまりフィルターを持ち出して議論する旨味はそんなに感じられない.読んで理解するのが結構大変なわりにはどこへもたどり着けないようなもやもやした気持ちが残る.

■3.おまけ:公理(O3)
先述したように,ブルバキの位相空間の公理は(O1)(O2)で尽くされているのだが,しばらく読み進めるとChap 1 sec8.4 Regular Space Prop.11 に(O3)が登場している.なぜこの公理が(O3)と呼ばれるのにふさわしいのか,などは全く説明されていない.やはりこの本はクセが強い.

千円を崩す方法(Haskell)

次のような問題を考えてみましょう:

千円を両替して崩す方法は何通りあるだろうか.ただし,一円玉,五円玉,十円玉,五十円玉,百円玉,五百円玉を自由に(好きなだけ)使って良いものとする.

まず問題を一般化し,つぎのように考えます.{A_n}によって「{n}円を一円玉で崩す方法の数」を表すことにします.(と言っても{n\ge 0}ならば常に{A_n = 1}なのですが).

また,{B_n}によって「{n}円を一円玉と五円玉で崩す方法の数」を,

{C_n}によって「{n}円を一円玉と五円玉と十円玉で崩す方法の数」を,

{D_n}によって「{n}円を一円玉と五円玉と十円玉と五十円玉で崩す方法の数」を,

{E_n}によって「{n}円を一円玉と五円玉と十円玉と五十円玉と百円玉で崩す方法の数」を,

最後に{F_n}によって「{n}円を一円玉と五円玉と十円玉と五十円玉と百円玉と五百円玉で崩す方法の数」を表すことにします.

このように定式化すると,クイズの答えは{F_{1000}}と表されます.あとはこの具体的な数値を求めれば良いわけです.

さて,{F_n}はを「n円を五百円玉を一枚も使わないで表した場合の数」と「(n-500)円をすべてのコインを好きなだけ使って表した場合の数」の和だと考えられます.よって

{F_n = E_n + F_{n-500}}

となります.よって,{F_n}の計算を{E_{n},\,F_{n-500}}の計算に還元できます.

同様に考えれば
{E_n = D_n + E_{n-100}}などの式が得られます.ただし,負のインデックスに対しては{A_n, B_n, C_n, D_n, E_n, F_n}はいずれもゼロとします.この考えをそのままHaskellコードにすれば次のようになります:

fA n | (n < 0) = 0
     | otherwise = 1

fB n | (n < 0) = 0
     | otherwise = fA n + fB (n-5)

fC n | (n < 0) = 0
     | otherwise = fB n + fC (n-10)

fD n | (n < 0) = 0
     | otherwise = fC n + fD (n-50)

fE n | (n < 0) = 0
     | otherwise = fD n + fE (n-100)

fF n | (n < 0) = 0
     | otherwise = fE n + fF (n-500)

これらの定義を書いてGHCiで:l 1000yen.hs してやってから fF 1000 を計算させると248908という答えが得られます.

したがって,一円玉,五円玉,十円玉,五十円玉,百円玉,五百円玉を自由に(好きなだけ)使って千円を両替する方法は全部で248908通りあることになります.

この問題はポリア他『組合せ論入門』p.11(近代科学社)で扱われている問題を改変したものです.(元の問題は1ドルを1セント,5セント,10セント,25セント,50セントで崩す問題です.)この問題はポリアのお気に入りだったのか,Pólya & Szegö “Problems and Theorems in Analysis I” にも収録されています.)

この記事では漸化式を組み合わせ論的な考えで導きましたが,ポリアの本では母関数を利用して漸化式を導いています.興味のある方は是非ポリアの『組合せ論入門』を読んでみてください.

無限小を用いた記述を標準的な記述に還元することについて

これはMath Advent Calendar 2017の12/8の記事です: mathAdventCalendar2017  (←リンク先PDF)

改訂情報

  • 2017/12/09: 式(24), 式(26)の脱字と誤字を訂正しました.(@waidotto 様,ありがとうございました.)
  • 2017/12/20: ISTの公理図式などの記述において,「FV」のような用語を使わないようにしました.

 

cos(x)+sin(x√2)の「周期っぽい長さ」を作る方法

{f(x) := \cos(x)+\sin(\sqrt{2}x)}とすると,これは明らかに周期関数ではないが,「周期っぽい長さ」が存在する.ある{l_\varepsilon}{f(x)}の「{\varepsilon}精度で周期っぽい長さ」であるということを次の条件で定義しよう:

\displaystyle{\sup_{x\in\Bbb{R}}\lvert f(x) - f(x+l_\varepsilon) \rvert < \varepsilon.}

このような「周期っぽい長さ」を機械的に作ってみよう.{\cos(x)}は周期{2\pi}で,{\sin(\sqrt{2}x)}は周期{\sqrt{2}\pi}なので
{\cos(x+l_\varepsilon) \fallingdotseq \cos(x),}
{\sin(\sqrt{2}x + \sqrt{2}l_\varepsilon) \fallingdotseq \sin(\sqrt{2}x).}
であればよい.よって
{l_\varepsilon \fallingdotseq 0\enskip(\mod 2\pi),\enskip l_\varepsilon \fallingdotseq 0\enskip(\mod \sqrt{2}\pi).}
そこである{a,b\in\Bbb{Z}}があって
{l_\varepsilon \fallingdotseq 2a\pi \fallingdotseq \sqrt{2}b\pi}
となっていれば良いことになる.

補足:近似({\fallingdotseq})による「アバウトな」議論がうまく行く事は,{\cos(x)}{\sin(\sqrt{2}x)}{\Bbb{R}}上一様連続であることを使えばうまく説明できる.

このような整数{a,b}を上手く見つけるために{\Bbb{Z}[\sqrt{2}]}が積について閉じていることに注目する.また,{0 < \sqrt{2}-1 < 1}という不等式にも注目する.よく知られているように,絶対値が{1}より小さい数のべき乗はゼロに収束する.そこで例えば
{(\sqrt{2}-1)^{2n} = b_n - \sqrt{2}a_n}
としてやれば,{2a_n \fallingdotseq \sqrt{2}b_n}となるような整数{a_n,\,b_n}を作り出すことができるはずである.{(\sqrt{2}-1)^{2n}}の二項展開を利用して具体形を求めれば

\displaystyle{a_n = \sum_{k=1}^n \binom{2n}{2k-1}2^{k-1},}

\displaystyle{b_n = \sum_{k=1}^n \binom{2n}{2k} 2^k.}

となる.

Maybeの(>=>)を使って問題を解く

■マーティン・ガードナーのパズル本を見ていたらこんな問題が載っていた:

5人の男と一匹の猿が難破して無人島に漂着した。1日目、彼らは食糧としてたくさんのココナツを集めて回った。そしてその夜、すべてのココナツを積み上げて彼らは眠りについた。
 しかし全員が眠りについたあと、1人の男がふと目を覚ました。朝になってココナツを分けるとき、ひと悶着起きるかもしれないではないか。心配になった彼は自分の取り分を先取りしようと考えた。彼がココナツを5つの山に等分してみると、1つ余ったので、彼はそれを猿にあげてから、自分の取り分を隠して、残りを元通りに積んでおいた。
 しばらくして別の男が目を覚まして、同じことを考えた。やはりココナツは1つ余り、それは猿のものになった。こうして5人の男たちが順番に同じことをした。つまり1人ずつ目を覚ましては、ココナツの山を5つに分けて、残った1つを猿にあげて、自分の取り分を画した。朝になり、残ったココナツ全部を分けると、今度はきれいに5等分された。
(略) さて、最初にココナツはいくつあったのだろうか?

計算機で総当りしてももちろんこの問題は解ける。本には、これを少ない労力で解くためのトリックが紹介されていた。(「ガードナーの数学娯楽」/日本評論社)。そのトリックについてはこの記事では触れない。

この問題を見たとき、HaskellのMaybeモナドを使ったら素直に解けそうだと感じた。(そして実際に解けた)。ココナツの数をNとすると
N = 5A +1 ;  4A個の山を残す # 1人目の男
4A = 5B + 1 ; 4B個の山を残す # 2人目の男
4B = 5C + 1 ; 4C個の山を残す # 3人目の男
4C = 5D + 1 ; 4D個の山を残す # 4人目の男
4D = 5E +1 ; 4E個の山を残す # 5人目の男
4E = 5F ; きれいに5等分された
のようになる。「与えられた数から1を引いておけば5で割り切れる」という状況が続き、そうして得られた商の4倍だけ残すという操作が5回行われている。そこでこんな関数を考えてみよう:

g :: Int -> Int -> Maybe Int
g r n
    |  (n-r) `rem` 5 == 0  = Just( ((n-r) `quot` 5) * 4 )
    |  otherwise           = Nothing

こうすると、それぞれの男が行った操作は g 1 として表現できる:

g 1 :: Int -> Maybe Int

一般に、モナドMに対して X -> M Yの形の関数は、(>=>)で合成できるのだった。
(この記事では説明しないし、知っている必要もないが、この形の関数はこのモナドの与えるKleisli圏の射とみなす事ができ、(>=>)はこのタイプの射の「合成」とみなせるのだった)。

よって、5人の男がココナツに対して行った操作とその結果は

f :: Int -> Maybe Int
f = g 1 {- 1人目の男 -} >=> g 1{- 2人目の男 -} >=> g 1{- 3人目の男 -} >=> g 1{- 4人目の男 -} >=> g 1{- 5人目の男 -} >=> g 0

として表せる。もちろんこれはもっとコンパクトに

f = foldl1 (>=>) [g 1, g 1, g 1, g 1, g 1, g 0]

と書いてもいいし、さらにこれは

f = foldl1 (>=>) $ map g [1,1,1,1,1,0]

と書いてもいい。こうして得られたfInt -> Maybe Int という型シグネチャを持つ。元のクイズの答をNとするとき、 f N Just ...という形をしているはずである。そこで、こんな関数を用意してみよう:

--  f の答がNothing ではない場合の引数を得るように変形する
getJustArg :: (a -> Maybe b) -> (a -> Maybe a)
getJustArg f x
    | isJust (f x)  = Just x
    | otherwise     = Nothing

この関数を使えば、問題のNは map (getJustArg f) [1 ..] の最初の元から得られることがわかる。Data.List の

find :: (a -> Bool) -> [a] -> Maybe a

を使えば最初の元を取ってこられそうだ。findMaybeをかぶせて返してくるおかげで、
find isJust (map (getJustArg f) [1 ..])Maybe(Maybe Int) 値になる。そこで join してMaybe を一段に落としてやると、得られる答は Just n の形をしているので fromJustInt値を引っ張り出せる:

fromJust . join $ find isJust (map (getJustArg f) [1 ..])

以上をまとめると次のようなプログラムが得られる:

import Control.Monad
import Data.List
import Data.Maybe

g :: Int -> Int -> Maybe Int
g r n
    |  (n-r) `rem` 5 == 0  = Just( ((n-r) `quot` 5) * 4 )
    |  otherwise           = Nothing

f = foldl1 (>=>) $ map g [1,1,1,1,1,0]

getJustArg :: (a -> Maybe b) -> (a -> Maybe a)
getJustArg f x
    | isJust (f x)  = Just x
    | otherwise     = Nothing

main = do{
  print $ fromJust . join $ find isJust (map (getJustArg f) [1 ..])
  }

答は3121となる。

■まとめ
Maybeモナドに対するKleisli射の合成演算(>=>)を用いてクイズを解いてみた。

■おまけの問題

5人の男と一匹の猿が難破して無人島に漂着した。1日目、彼らは食糧としてたくさんのココナツを集めて回った。そしてその夜、すべてのココナツを積み上げて彼らは眠りについた。
 しかし全員が眠りについたあと、1人の男がふと目を覚ました。朝になってココナツを分けるとき、ひと悶着起きるかもしれないではないか。心配になった彼は自分の取り分を先取りしようと考えた。彼がココナツを5つの山に等分してみると、4つ余ったので、彼は余ったココナツを猿にあげてから、自分の取り分を隠して、残りを元通りに積んでおいた。
 しばらくして別の男が目を覚まして、同じことを考えた。今度は3つ余ったので、彼はやはり余ったココナツを猿に与え、自分の取り分を隠してから残りを積んでおいた。
三番目の男も同じことを考えたが、彼がココナツを5つの山に分けようとすると今度は2つ余った。やはり彼は余ったココナツを猿に与え、自分の取り分を隠してから残りを積んでおいた。
四番目の男も同じことを考えたが、彼がココナツを5つの山に分けようとすると今度は1つだけ余った。やはり彼は余ったココナツを猿に与え、自分の取り分を隠してから残りを積んでおいた。
五番目の男も同じことを考えたが、彼だけは仲間を裏切ることを恥ずかしく思い、結局何もしなかった。
朝になり、残ったココナツ全部を分けると、きれいに5等分された。
さて、最初にココナツはいくつあったのだろうか?

最小の答は3089個になるはずである。

C90: 「簡約!? λカ娘 9」 が出ます

C90の三日目(2016/08/14(日))に、サークル「参照透明な海を守る会」から『簡約!? λカ娘 9』が出ます。場所は「西地区f32a」です。

<簡約!? λカ娘 9> 内容紹介
第 1 章 λカ娘探索ファイナル (@ark_golgo)
第 2 章 変態する昆虫の観察 (@master_q)
第 3 章 IST(Internal Set Theory) 入門 (前編) (@dif_engine)

第 3 章の『 IST(Internal Set Theory) 入門 (前編) 』が私の記事です。

以下、いくつかの記事について簡単な紹介をします。自分が書いた記事以外はどれも「ちゃんと理解できていない」ので、自分の理解の程度に応じた紹介となります。ご了承ください。

第1章 λカ娘探索ファイナル
AlphaGo が凄いということはみなさんもご存知かと思いますが、では一体どこがどのように凄いのでしょうか?この記事ではコンピュータ囲碁の研究をしている荒木さんによって、コンピュータ囲碁の歴史とAlphaGoの強さの本質、そして将来のコンピュータ囲碁の展望が語られています。

第2章 変態する昆虫の観察
組み込み系のChibiOS/RT というOSは独自の(非POSIXの)スレッド機構を持ち、グローバルロック状態に応じて呼び出せるシステムAPIが変わるのだそうです。間違ったシステムAPIの呼び出しは未定義の挙動を引き起こすのですが、このたぐいのコーディングミスは実行時ではなく、コンパイル時にわかってほしいものです。そのための方法の一つはプログラムの静的なチェックを強化することです。岡部さんの方針は、この静的なチェックのためにATSを使うというものです。(この場合、ATSは最終的にC言語のソースコードを生成します。)

第3章 IST(Internal Set Theory) 入門 (前編)
Edward Nelson によって創始された超準集合論であるInternal Set Theory (以下、IST)という理論があります。
「ふつうの」超準解析、例えば齋藤正彦やM・デービスや中村徹の超準解析の本では、通常の集合論宇宙の超積を使って超準宇宙を作ります。
これに対し、NelsonによるISTにおいては、通常の集合論宇宙が超準宇宙に該当します。この宇宙の中に、一種のミニチュア宇宙が存在し、そこには空集合からスタートして集合論公理を有限回使って到達できるもの全てが含まれています。ISTでは、その意味で超準化という手続きは「すでに終わっている」ので超準宇宙の構成の議論は必要ありません。また、ISTはZFCの保存拡張になっているため、ZFC集合論での全ての定理はISTの定理でもあります。
(超積による超準宇宙の構成では正則性公理(基礎の公理)が省かれることがあります。したがって、ZFC集合論における議論を修正しないとZFC宇宙における定理を超準宇宙に輸入できないことがあります。)

このように言うとISTには良いことしかないようですが、NelsonのIST論文は若干読みにくいところがあります。それは、(1)読者に数理論理学の基礎的教養を要求している (2)ZFCにおける有限性のやや深い理解を要求している ところから来ているのではないかと思います。

(1)に関して言えば、ISTの公理図式は、量化子を「St付き」に変更するような操作を要求しており、論理式をオブジェクトとみなす視点が必要です。(2)に関して言えば、”直観的には”無限集合にしかなり得ない巨大な集合が有限集合であることがISTでは示されたりします。そして、そのようなことがISTにおける議論において有効に利用されたりする場面があります。このため、ISTを学ぶ人は「有限性とはなんだったのか」と悩むことになるでしょう。ISTにおける「有限性」の奇妙さに関連して、Nelson自身は次のような言葉を残しています:

—Perhaps it is fair to say that “finite” does not mean what we have always thought it to mean. What have we always thought it to mean?
I used to think that I knew what I had always thought it to mean, but I no longer think so. In any case, intuition changes with experience.

(1)も(2)もそれぞれ数理論理学と公理的集合論の基本的な教科書を読めば済む話なのですが、なかなか大変です(大変でした)。この章を読みこなせばNelsonによるISTの論文を読むための最低限の知識が得られる、そんな線を狙って執筆しました。なお、この(1)(2)を丁寧に説明しすぎて、肝心のISTの解説には入ることができなかったので「前編」とさせて頂きました。(後編は来年の予定です)。

表紙
久しぶりに表紙絵を描きました。「このすば」のめぐみんの衣装を着たイカ娘です。

簡約!? λカ娘 9 表紙

簡約!? λカ娘 9 表紙

atan2の引数順序をすぐ思い出すための恒等式

二次元直交座標系から極座標系に変換する際に、あるいは「ほとんど同じ話」ですが{x+iy} という形式の複素数を極形式に変換する際に二つの与えられた実数からある角度を得たい場合があります。そのような場合に便利なのが atan2 であることはご存知と思います。私はこの関数の引数の順序を数年に一度はネットで調べてる気がします:こういうのは全く無駄な時間です。

そこで、少し落ち着いて考え、次の恒等式を覚えておけばもう迷わなくなりそうだと思ったのでメモしておきます:

{\theta=\mathrm{atan2}(\sin(\theta), \cos(\theta))\quad(\theta \in [0,2\pi)).}

C88: 「簡約!? λカ娘 8」 が出ます

C88の三日目(2015/08/16(日))に、サークル「パスティヤージュλカ研究学院」から『簡約!? λカ娘 8』が出ます。場所は「東地区 O-47a」です。サークル名(旧名:参照透明な海を守る会)は変わりましたがよろしくおねがいいたします。

<簡約!? λカ娘 8> 内容紹介
第1章 エルエフ島漂流記(@master_q)
第2章 二重否定と継続(@nushio)
第3章 真の名を~データ設計とAlloy~(@osiire)
第4章 Lagrangeの未定乗数法(@dif_engine)  ←私の記事です

第四章の『Lagrangeの未定乗数法』が私の記事です。もはや関数プログラミングとか関係なく、純粋に数学の話になってしまいました。表題の通りLagrangeの未定乗数法についての記事です。数学の応用の場面で未定乗数法は頻繁に使われるのですが、制約条件が増えた場合についての未定乗数法がどうしてうまくいくのかよくわからなかったので勉強して整理してみました。内容は高度なものではありませんが、多変数の微積分に関する話なのでそのへんの復習とか整理だとかそんな話を述べながらゆったりと説明しています。

以下、いくつかの記事について簡単な紹介をします。自分が書いた記事以外はどれも「ちゃんと理解できていない」ので、自分の理解の程度に応じた紹介となります。ご了承ください。

第1章 エルエフ島漂流記
ATS/LFという、ATSのサブシステムがあります。これについての入門記事です。(ATSについてはhttp://jats-ug.metasepi.org/ を御覧ください。)

第2章 二重否定と継続
継続という、わかりづらいことで有名な概念があります。この継続がカリー・ハワード対応を通して二重否定と結びついているという話です。

第3章 真の名を~データ設計とAlloy~
現実世界を模倣したシステムを作るとき、大抵は大幅に単純化・抽象化を行います。そのようにして導入した抽象化が適切か?というのは重要です。多重度、依存性、一意性、など考慮すべき制約条件をきちんと記述できたかどうかを検証するツールとして Alloy Analyzer を使う方法が解説されています。

第4章 Lagrangeの未定乗数法
魔理沙がパチュリーに未定乗数法を教わります。線形代数の復習を行い、陰関数の定理を利用してLagrangeの未定乗数法の証明を追います。最後に、陰関数定理の証明を眺めます。

表紙
前回(簡約λカ娘~巻の七~)に引き続いてうさ叉吉様に絵をお願いいたしました。

行列式を行列のべき乗のトレースたちの多項式として表すこと

物理の本を読んでいたら、{3\times 3} 行列についての次のような公式が出てきた:
{3!|A| = (\mathrm{tr}A)^3 - 3\mathrm{tr}(A^2)\mathrm{tr}(A) + 2\mathrm{tr}(A^3).  }
気になってネットで調べると,{2\times 2} 行列のとき、次の関係式が成り立つのだそうだ:
{2!|A| = (\mathrm{tr}A)^2 - \mathrm{tr}(A^2).}
一般の{n} の場合はどうなるのか気になって考えた.

一般に,{n} 次正方行列 {A} は(適当に取った)ユニタリ行列 {U} によって,対角成分が {A} の固有値であるような上三角行列に変換できる:
{U^*AU = \left[      \begin{array}{ccc}        \lambda_1 & {} & * \\        {} & \ddots & {} \\       0 & {} & \lambda_n      \end{array}    \right].}
ユニタリ行列の性質から,任意の自然数 {k} に対して
{U^*A^kU = \left[      \begin{array}{ccc}        \lambda_1^k & {} & * \\        {} & \ddots & {} \\       0 & {} & \lambda_n^k      \end{array}    \right].}
固有多項式はユニタリ変換で不変なので,その {n-1} 次の項を比較することで次を得る:
{\mathrm{tr}(A^k) = \mathrm{tr}(U^*A^kU) = \lambda_1^k + \cdots+ \lambda_n^k.}
よって,行列のべき乗のトレースが固有値のニュートン多項式になっていることがわかる.ここで, {n} 変数の {k} 次ニュートン多項式 {S_k(x_1,...,x_n) := x_1^k + ... + x_n^k.}

さて, {n} 変数の {k} 次基本対称式 {B_k(x_1,...,x_n)} は次のように定義されるのだった:
{B_k(x_1,...,x_n) :=\sum_{1 \le j_1 < ...< j_k \le n} x_{j_1}\cdot ... \cdot x_{j_k}.}

特に,{B_n(\lambda_1, ..., \lambda_n) = |A|} となることに注意する.行列式もトレースも,ユニタリ変換で上三角化した行列の対角成分だけで決まる.このことから「行列式を行列のべき乗のトレースたちの関数として表す問題」は「{B_n}{S_1, ..., S_n} たちの関数として表す問題」に帰着できることがわかる.

基本対称式とニュートン多項式の間には次のような関係式が成り立つ:
{B_{k+1} = \frac{1}{k+1} \left\{  \left( \sum_{0\le s < k} B_{k-s} S_{s+1} \right) + (-1)^k S_{k+1} \right\}.} ただし {k=0, ..., n-1.}

順番に具体的な式を幾つか書いてみると:
{B_1=S_1.}

{B_2=\frac{1}{2}(B_1S_1 - S_2).}

{B_3 = \frac{1}{3}(B_2S_1 - B_1S_2 + S_3).}

最初の式を2番目の式に,最初と2番目の式を三番目に代入すると次のような式を得る:

{B_2=\frac{1}{2!}(S_1^2 - S_2).}

{B_3 = \frac{1}{3!}(S_1^3 - 3S_1S_2 + 2S_3 ).}

これらの式は最初に紹介した式と強く結びついていることがわかる.これ以上手計算でやるのは面倒なのでMaximaに続きをやらせることにしたいが,Maximaで関数の定義を書くのが面倒になったので次のようなHaskellの使い捨てコードを書いてみた:

(++#) :: String -> String -> String
(++#) a [] = a
(++#) a b = a ++ "," ++ b

sn :: Int -> String
sn n = "(" ++ foldr (++#) "" [ "S"++show k | k <- [1 .. n]] ++ ")"

f :: Int -> IO ()
f k =
	let out = 
		"B" ++ (show (k+1)) ++ sn(k+1) 
		++ ":=(1/" ++ (show (k+1)) ++ ")*("
		++ foldr (++) "" [ "(-1)^" ++ show t 
		++ "*B" ++ show(k-t) ++ sn(k-t) 
		++ "*S" ++ show(t+1) ++ "+" | t <- [0 .. k-1]]
		++ "(-1)^" ++ show k ++ "*S" ++ show(k+1) ++ ");"
	in putStrLn out
$ ghci
Prelude>:l a.hs
[1 of 1] Compiling Main             ( a.hs, interpreted )
Ok, modules loaded: Main.
*Main>  mapM_ f [0 .. 10]
B1(S1):=(1/1)*((-1)^0*S1);
B2(S1,S2):=(1/2)*((-1)^0*B1(S1)*S1+(-1)^1*S2);
B3(S1,S2,S3):=(1/3)*((-1)^0*B2(S1,S2)*S1+(-1)^1*B1(S1)*S2+(-1)^2*S3);
B4(S1,S2,S3,S4):=(1/4)*((-1)^0*B3(S1,S2,S3)*S1+(-1)^1*B2(S1,S2)*S2+(-1)^2*B1(S1)*S3+(-1)^3*S4);
B5(S1,S2,S3,S4,S5):=(1/5)*((-1)^0*B4(S1,S2,S3,S4)*S1+(-1)^1*B3(S1,S2,S3)*S2+(-1)^2*B2(S1,S2)*S3+(-1)^3*B1(S1)*S4+(-1)^4*S5);
B6(S1,S2,S3,S4,S5,S6):=(1/6)*((-1)^0*B5(S1,S2,S3,S4,S5)*S1+(-1)^1*B4(S1,S2,S3,S4)*S2+(-1)^2*B3(S1,S2,S3)*S3+(-1)^3*B2(S1,S2)*S4+(-1)^4*B1(S1)*S5+(-1)^5*S6);
B7(S1,S2,S3,S4,S5,S6,S7):=(1/7)*((-1)^0*B6(S1,S2,S3,S4,S5,S6)*S1+(-1)^1*B5(S1,S2,S3,S4,S5)*S2+(-1)^2*B4(S1,S2,S3,S4)*S3+(-1)^3*B3(S1,S2,S3)*S4+(-1)^4*B2(S1,S2)*S5+(-1)^5*B1(S1)*S6+(-1)^6*S7);
B8(S1,S2,S3,S4,S5,S6,S7,S8):=(1/8)*((-1)^0*B7(S1,S2,S3,S4,S5,S6,S7)*S1+(-1)^1*B6(S1,S2,S3,S4,S5,S6)*S2+(-1)^2*B5(S1,S2,S3,S4,S5)*S3+(-1)^3*B4(S1,S2,S3,S4)*S4+(-1)^4*B3(S1,S2,S3)*S5+(-1)^5*B2(S1,S2)*S6+(-1)^6*B1(S1)*S7+(-1)^7*S8);
B9(S1,S2,S3,S4,S5,S6,S7,S8,S9):=(1/9)*((-1)^0*B8(S1,S2,S3,S4,S5,S6,S7,S8)*S1+(-1)^1*B7(S1,S2,S3,S4,S5,S6,S7)*S2+(-1)^2*B6(S1,S2,S3,S4,S5,S6)*S3+(-1)^3*B5(S1,S2,S3,S4,S5)*S4+(-1)^4*B4(S1,S2,S3,S4)*S5+(-1)^5*B3(S1,S2,S3)*S6+(-1)^6*B2(S1,S2)*S7+(-1)^7*B1(S1)*S8+(-1)^8*S9);
B10(S1,S2,S3,S4,S5,S6,S7,S8,S9,S10):=(1/10)*((-1)^0*B9(S1,S2,S3,S4,S5,S6,S7,S8,S9)*S1+(-1)^1*B8(S1,S2,S3,S4,S5,S6,S7,S8)*S2+(-1)^2*B7(S1,S2,S3,S4,S5,S6,S7)*S3+(-1)^3*B6(S1,S2,S3,S4,S5,S6)*S4+(-1)^4*B5(S1,S2,S3,S4,S5)*S5+(-1)^5*B4(S1,S2,S3,S4)*S6+(-1)^6*B3(S1,S2,S3)*S7+(-1)^7*B2(S1,S2)*S8+(-1)^8*B1(S1)*S9+(-1)^9*S10);
B11(S1,S2,S3,S4,S5,S6,S7,S8,S9,S10,S11):=(1/11)*((-1)^0*B10(S1,S2,S3,S4,S5,S6,S7,S8,S9,S10)*S1+(-1)^1*B9(S1,S2,S3,S4,S5,S6,S7,S8,S9)*S2+(-1)^2*B8(S1,S2,S3,S4,S5,S6,S7,S8)*S3+(-1)^3*B7(S1,S2,S3,S4,S5,S6,S7)*S4+(-1)^4*B6(S1,S2,S3,S4,S5,S6)*S5+(-1)^5*B5(S1,S2,S3,S4,S5)*S6+(-1)^6*B4(S1,S2,S3,S4)*S7+(-1)^7*B3(S1,S2,S3)*S8+(-1)^8*B2(S1,S2)*S9+(-1)^9*B1(S1)*S10+(-1)^10*S11);

これらの式をMaximaにコピペしてやってから例えば

expand(ratsimp( 3! * B3(S1, S2, S3)));

としてやると {2\,S3-3\,S1\,S2+{S1}^{3}} が出てくるので,どうやらうまく行っている様子だ.
同様にして計算すれば,{n} 次正方行列についての {n!\, |A|} は次のように求まる:

{4!\, |A| = -6\,\mathrm{tr}(A^4)+8\,\mathrm{tr}(A)\,\mathrm{tr}(A^3)+3\,{\mathrm{tr}(A^2)}^{2}-6\,{\mathrm{tr}(A)}^{2}\,\mathrm{tr}(A^2)+{\mathrm{tr}(A)}^{4}.}

{5!\,|A| = 24\,\mathrm{tr}(A^5)-30\,\mathrm{tr}(A)\,\mathrm{tr}(A^4)-20\,\mathrm{tr}(A^2)\,\mathrm{tr}(A^3)}
{ +20\,{\mathrm{tr}(A)}^{2}\,\mathrm{tr}(A^3)+15\,\mathrm{tr}(A)\,{\mathrm{tr}(A^2)}^{2}-10\,{\mathrm{tr}(A)}^{3}\,\mathrm{tr}(A^2)}
{   +{\mathrm{tr}(A)}^{5}.}

{6!\,|A| = -120\,\mathrm{tr}(A^6)+144\,\mathrm{tr}(A)\,\mathrm{tr}(A^5)+90\,\mathrm{tr}(A^2)\,\mathrm{tr}(A^4)}
{    -90\,{\mathrm{tr}(A)}^{2}\,\mathrm{tr}(A^4)+40\,{\mathrm{tr}(A^3)}^{2}-120\,\mathrm{tr}(A)\,\mathrm{tr}(A^2)\,\mathrm{tr}(A^3)}
{    +40\,{\mathrm{tr}(A)}^{3}\,\mathrm{tr}(A^3)-15\,{\mathrm{tr}(A^2)}^{3}+45\,{\mathrm{tr}(A)}^{2}\,{\mathrm{tr}(A^2)}^{2}-15\,{\mathrm{tr}(A)}^{4}\,\mathrm{tr}(A^2)+{\mathrm{tr}(A)}^{6}.}

{7!\,|A| = 720\,\mathrm{tr}(A^7)-840\,\mathrm{tr}(A)\,\mathrm{tr}(A^6)-504\,\mathrm{tr}(A^2)\,\mathrm{tr}(A^5)}
{+504\,{\mathrm{tr}(A)}^{2}\,\mathrm{tr}(A^5)-420\,\mathrm{tr}(A^3)\,\mathrm{tr}(A^4)+630\,\mathrm{tr}(A)\,\mathrm{tr}(A^2)\,\mathrm{tr}(A^4)}
{-210\,{\mathrm{tr}(A)}^{3}\,\mathrm{tr}(A^4)+280\,\mathrm{tr}(A)\,{\mathrm{tr}(A^3)}^{2}+210\,{\mathrm{tr}(A^2)}^{2}\,\mathrm{tr}(A^3)}
{-420\,{\mathrm{tr}(A)}^{2}\,\mathrm{tr}(A^2)\,\mathrm{tr}(A^3)+70\,{\mathrm{tr}(A)}^{4}\,\mathrm{tr}(A^3)}
{-105\,\mathrm{tr}(A)\,{\mathrm{tr}(A^2)}^{3}+105\,{\mathrm{tr}(A)}^{3}\,{\mathrm{tr}(A^2)}^{2}-21\,{\mathrm{tr}(A)}^{5}\,\mathrm{tr}(A^2)}
{+{\mathrm{tr}(A)}^{7}.}

こうして眺めていても規則性がわからなかったが,WikipediaのExpressing elementary symmetric polynomials in terms of power sumsを見ると,一般項がどのような形になるか書いてある.興味が出てきたら考えてみることにする.