【世にも奇妙な関数】行列の指数関数とは?
実数の指数関数は
と書けるように、行列の指数関数は
に書ける。時々思うけど級数って連続な関数を離散の和形式に変換して扱いやすいだろう。
この指数関数はなにかおかしい!
この関数はを満たしていない。まずはを展開してみよう。
何の変哲もない級数ですね。それからとを展開してみよう。
簡単な例を考えましょう。上の二式を掛けたら三次の項は、やなどの三次以下の項から由来する。特にとからそれぞれ一項取り出して次数の和が3になる取り方全部漏れなく一回やる。これにより、
が分かる。勘が鋭い人は気づいたかもしれないけど、この式を整理して
の形になる。内のシグマに「二項定理使ってになるじゃん」と言いたい人もいるだろうけど、二項定理は行列に対して必ずしも成立しない。を考えましょう。式を展開したらになる。行列の掛け算は交換不可なのでとをまとめることができない。なので一般的にがある。
が成立する場合
容易に想像するけど、の時に限って が成立する。だががある。この極限を使って量子回路合成する手法も存在する。
おまけ:正規行列の関数
正規行列はのようにスペクトル分解できる。結論を先に言うと関数を正規行列に対して適用したらが得られる。
正規行列のべき乗は固有値だけ変える
を自乗して
に違う固有ベクトル乗算したら相殺する。同じ固有ベクトルは乗算した後1になるので影響はない。それにより をk乗して
になることが分かる。
冪級数で関数を定義する
ここでは関数を冪級数に展開したものは
と定める。行列をそのまま代入すると
がある。シグマの位置を変えて射影行列を括りだす。
大学の線形代数で扱う帰納法
帰納法は証明手法として極めて重要なものです。特に証明する途中、証明する目標となる命題と似たような形の子問題がでる時帰納法は定番化される。帰納法は特に自然数などの構造で役立つけど、線形代数の場合はそう簡単ではない。行列や線形変換や線形空間などは自明的な帰納的構造を持たないため、帰納法を適用しようとしてもなかなか難しいだろう。これから自分が見かけたいくつかの帰納法の考え方を紹介する。
掃出しを使った帰納法
こちらの帰納法は一番簡単で、やり方としてまず行と列の足し引きによって一行と一列の要素を一つ以外全部0にする。その後残りの部分に対して帰納法を適用。典型として任意の行列は標準形に移せることの証明に使われる。標準形はつまり1が対角線上にだけ並ぶ形です。行列の一行目と一列目を掃き出すと以下の形になる。
つまりにのみ1が存在してそれ以外の一列目と一行目の要素は全部0になる。この時右下のはサイズがより小さいがため帰納法の仮定を適用できる。この方法は主に正則変換の影響を受けない性質持つ命題の証明に使われる。
正値エルミートの場合
正値エルミート行列の場合、正値行列をとする。
この時が以下の形になる。
この変換は行列式に影響が出ない上掃き出すことができる。これを使って二次形式やアダマールの不等式などを証明することが楽です。
部分集合に関する帰納法
名前通りにベクトル集合の要素に対して帰納する。なおこの時集合のすべての要素を表せるベクトルの組は基底ではなく、極大線形独立系と呼ばれる。簡単で理解しやすい反面に行列や変換に対してあまり効かないので一回だけ見たことある。では次の命題を考えましょう。
集合Sがn個のベクトルからなる極大線形独立系を持つときn個より多いベクトルは必ず線形従属
集合Sに対してとの二つの極大線形独立系がある時。はn個のベクトルがある。はm-1個のベクトルがある。にないにあるベクトルを考える。Sからを取り除いてS'を得る。集合は線形空間の効率を満たさなくでもいいのでとても便利です。この時はまたn個のベクトルを有する。でもはm-1個の線形独立なベクトルしかない。 S'に対して帰納法の仮定を適用するとはすぐに分かる。イコールの場合に対して証明すれば大丈夫です。
T-不変部分空間に関する帰納法
ある線形変換Tに対して命題を証明する時にT-不変部分空間を使って線形空間を帰納的に構築する。これは行列の形式にも出てくる。行列を対称区分けする時上三角行列のような行列は不変部分空間を持つ。実は任意の行列は上三角化出来るがため任意の線形変換Tは帰納的にできると言えるでしょう。
n次元線形空間の線形変換Tが冪零の時、
Tは冪零であることから、ある基底の元で以下の形をする。
この行列は対角線以下が全部0で、自乗するたびに0が右上に蔓延るなのでせいぜいn回自乗したらゼロ行列になる。
実計量空間Vの実対称変換Tの固有空間の直和はVです
固有値と対応する固有空間を取り出す。はT不変で次元数が低いがため帰納法で分解できることがわかる。なおと直交するため、直和である。
【線形代数あるある】行列の掛け算とベクトル内積はどんな関係?
最近卒論関係で、論理行列と01列の掛け算に触れる。そこで思ったが、実ベクトルと実行列の掛け算は行列の行とベクトルの内積に掛ける。01列と論理行列はなかなかそうとはいかない。
01列からなる線形空間と論理行列
01列の集合は線形空間なり
長さが3の01列の集合は線形空間だったことは以下の手順で証明できる。まずはベクトルの足し算定義です。
つまり二つの01列の足し算はビットごとのxorとして定義される。例えば010と110の足し算は101で。値の異なるビットは計算後1になる。そうでないビットは0になる。そして整数01とベクトルの掛け算は
として定義する。ただし、ここの足し算は全てxorで線形空間の公理と一致する。ちなみに長さがN(N=1 2 ... )の01列の集合全て線形空間だったことはこの方法で証明できる。これから論理行列と01列の掛け算に入る。
論理行列と01列の掛け算
前と同じく、三次元01列の場合を説明してN次元に持っていく。との掛け算を次のように定義する。
変換される二進数はとみなせる。つまり基底の線形組み合わせだ。そして行列は一つの100を個の100、個の010と個の001に変換する。010と001に対しての変換もこうやって定められる。先のプロセスを見ると、線形変換はベクトルと数(スカラー)の掛け算あとベクトル同士の足し算しか使わない。そのため内積の定義がなくても、基底の線形組み合わせを別の線形組み合わせに書き換えれば行列の掛け算は成り立つ。
実線形空間の場合
結論を先に言うと、実行列とベクトルの積は偶々内積と定義が一致する。行列とn次元ベクトルの積の番目の成分はで与えられる。直交正規座標系の元でとの内積は
になる。よく見れば、直交正規基底を取った時の行列表示だけ内積と行列掛け算の定義は一致する。
おまけの複素線形空間
本当に困惑することは複素線形空間の場合。複素線形空間の内積は一つのベクトルをその共役ベクトルにしてから、掛け算する。そこで複素行列の掛け算も共役行列取るじゃないかと思うかもしれないが、先言った通り行列は線形組み合わせを表す。それ故に足したり掛けたり出来れば、別に内積と関係していないわけです。
よく出るあの級数!情報系なら絶対覚えるべき計算量の話!
皆さん、久しぶり!競プロを始めてから実装の話ばかりしていた。いよいよアルゴリズムの原点に戻った!今回は例のを見に行きたいと思う。
この級数はどこで出るの?
まずは結論から言うと、この級数はクラスに属す。これでちょっと見覚えがあるのか?セットを使って配列から重複を取るアルゴリズムは配列の要素を順に見て行き、そしてセットにいるかどうかをチェックする。配列の長さをNとして、セットのサイズをKとする。クエリごとの時間がかかる。その結果、全体の計算量はこの級数になる。
その他にもLIS問題、最短経路問題など超有名問題で出てくる大人気級数である。
いきなり現れるは一体なんだ?
授業ではビッグOを教えることが多いですが、ビッグOはあくまで最悪の場合を指す。実際ももなので、ビッグOは厳密ではない。その代わりに、はちょうどこのクラスにいる関数の集合。
前の例を持ち上げると、セットを使ったあのアルゴリズムは最悪だけじゃなくて、これ以上早くなることもない。
数学コーナーはみんな大嫌いだけど見ないと背が伸びない
まずここで証明したい命題を貼りましょう!
この問題は二つの問題に分けて考えましょう!まずは
これは自明的だ。から、は明らかなことだ。では難しい方へ進むぞ!
今回は帰納法でやる。まずはあるに対して、が成立とする。これを仮説1と呼ぶ。そしての時の式を見てください。
今からはただを式(1.2)にかけたものは依然式(1.1)より大きいことを示せば万事解決。今の式を見れば、ほどんど見たことある顔で安心した。でも待って、式(1.1)のはどんどん大きくなるじゃないかっと思うと、実際は上限がある!
調和級数の時使った技を思い出してね!はと等しい。この積分の区間での最大値はイコールの時から、がわかる。さらに式(1.1)は式(1.3)より小さいことが分かった。
定数を式(1.2)に掛けるとが得られる。仮説1を使えばとを式1.2と式1.3から消せる。残る部分はとだけ。定数を予め大きくしたらも成立する。 当然のことことなんですが、の時が成立するので証明終了。Q.E.D
あとがき
今回の記事いかがでしょうか。私もこれでまた一つ賢くなった気がしたので、これからももっとしんかしていくぜ!それじゃまたね、bye~bye~
RE:ゼロから始めるLIS問題
最長部分増加列(LIS)問題は序列の単調増加の部分列の中で一番長い部分列の長さを求める問題である。最近ARC 104の問題
を見ていたらLIS問題を振り替えようと思います。
貪欲アルゴリズム
配列]があるとする。dp[i]は長さがiの部分増加列の最後の要素の最小値を表す。例えば列全体に対して、長さが4になる部分増加列はなどの五通りある。その中で最後の要素の最小値は4なのでdp[4]=4になる。
このアルゴリズムは配列の要素ごとに以下のプロセスを繰り返す。
- 配列の要素をみる
- 今の最長増加列の長さをmとすると、二分探索でより大きい要素をdpから探す。
- 見つかったらその要素をと置き換える。
- 見つからなかった場合は長さを1増やして、dp配列の最後をと置く。
このアルゴリズムは簡単で、ツリー上のLIS問題にも適用する。
BITを用いたdpアルゴリズム
また配列dpを用意して、今回はを「iが最後となる部分増加列の長さ」にする。BITを使って効率よくからまでの最大値を探す。アルゴリズムは元の配列要素ごとに以下のプロセスを繰り返す。
- 配列の要素をみる
- からまでの最大値tmpを探す
- をにする
この方法が成立する前提は全ての要素更新は要素を大きくすること。そして区間最大値は全部初めから計算したもの。この方法は貪欲アルゴリズムより複雑だけど、LISだけでなくより複雑な制約を扱える。例えばこのLaIS問題。
シュミット分解を軽く証明した
まずはシュミット分解は何かを軽く説明する。ある純粋量子状態があるとする。元の量子システムをAとBの二つのシステムに分けた後、サブシステムの基底をととする。が成立する。ここのrはAとBの中で次元数が低いシステムの次元数に相当する。
AとBが同じ次元の場合
元のシステムはで表されるので、は成立する。この形は目標と似ているが、加算する項が多い。を並べて幅と高さが一致する行列Aにする。Aはユニタリー行列U,Vと対角行列Dの積に書ける。ここではaijをAのi行目j列の要素とする。前の分解によると、が成立する。これを代入すれば、がわかる。
そこで、Aシステムの基底をとして、Bシステムの基底をとする。そしてDの対角成分をにする。そうしたら、が得られる。
AとBが異なる次元の場合。
その場合、を並べた行列Aの幅と高さは異なる。従って、Aをユニタリー行列UVと対角行列Dの積に分解することはできない。具体例を挙げると、システムAを三次元にしてシステムBを二次元とする。この場合行列Aは幅が3で高さが2になる。
ここではBシステムの次元数が低い場合を考える。システムBに仮想な補助システムCを導入して。システムCの状態をにする。元の量子システムと合わせて全体の状態がになった。この状態をシステムAとシステムに均等に分けることができる。さらに、Aの基底をとしての基底をとする。
AとBが同じ次元の場合を参考してが成立する。従ってはシュミット分解ができることはわかる。ここで導入した補助システムCは0状態にいるので、の中のCの成分が0でない時。そこからわかることは。末尾のを除き取ると、シュミット分解ができた。