ミケ猫の小部屋

情報学、数学、語学および料理（暫定）について発信します

【世にも奇妙な関数】行列の指数関数とは？

実数の指数関数 \exp(x)は

\displaystyle \exp(x)=\sum_{i=0}^{\infty} \frac{x^i}{i!}

と書けるように、行列の指数関数 \exp(X)は

\displaystyle \exp(X)=\sum_{i=0}^{\infty} \frac{X^i}{i!}

に書ける。時々思うけど級数って連続な関数を離散の和形式に変換して扱いやすいだろう。

この指数関数はなにかおかしい！

この関数は \exp(X+Y) = \exp(X) \exp(Y)を満たしていない。まずは \exp(X+Y)を展開してみよう。

\displaystyle \exp(X+Y)=\sum_{i=0}^{\infty} \frac{(X+Y)^i}{i!}

何の変哲もない級数ですね。それから \exp(X)と \exp(Y)を展開してみよう。

\displaystyle \exp(X)=\sum_{i=0}^{\infty} \frac{X^i}{i!}\\ \displaystyle \exp(Y)=\sum_{i=0}^{\infty} \frac{Y^i}{i!}

簡単な例を考えましょう。上の二式を掛けたら三次の項は \frac{X^0}{0!}、 \frac{X^1}{1!}や \frac{Y^2}{2!}などの三次以下の項から由来する。特に \exp(X)と \exp(Y)からそれぞれ一項取り出して次数の和が3になる取り方全部漏れなく一回やる。これにより、

\displaystyle \exp(X)\exp(Y)=\sum_{i=0}^{\infty}\sum_{j=0}^i \frac{X^j Y^{i-j}}{j!(i-j)!}

が分かる。勘が鋭い人は気づいたかもしれないけど、この式を整理して

\displaystyle \exp(X)\exp(Y)=\sum_{i=0}^{\infty} \frac{1}{i!} \sum_{j=0}^i \frac{i!}{j!(i-j)!} X^j Y^{i-j} \\ =\sum_{i=0}^{\infty} \frac{1}{i!} \sum_{j=0}^i C_i^j X^j Y^{i-j}

の形になる。内のシグマに「二項定理使って (X+Y)^iになるじゃん」と言いたい人もいるだろうけど、二項定理は行列に対して必ずしも成立しない。(X+Y)^2を考えましょう。式を展開したらX^2+XY+YX+Y^2になる。行列の掛け算は交換不可なのでXYとYXをまとめることができない。なので一般的に \exp(X+Y) \neq \exp(X) \exp(Y)がある。

\exp(X+Y) = \exp(X) \exp(Y)が成立する場合

容易に想像するけど、XY=YXの時に限って \exp(X+Y) = \exp(X) \exp(Y)が成立する。だが \displaystyle \lim_{n\rightarrow \infty} (exp(\frac{X}{n})\exp(\frac{Y}{n})) ^n=\exp(X+Y) がある。この極限を使って量子回路合成する手法も存在する。

おまけ：正規行列の関数

正規行列は \displaystyle \sum_{i} x_i |i>\lt i|のようにスペクトル分解できる。結論を先に言うと関数fを正規行列 \displaystyle \sum_{i} x_i |i>\lt i|に対して適用したら \displaystyle \sum_{i} f(x_i) |i>\lt i|が得られる。

正規行列のべき乗は固有値だけ変える

\displaystyle \sum_{i} x_i |i>\lt i|を自乗して

\displaystyle \sum_{i} x_i |i>\lt i| \sum_{j} x_j |j>\lt j|

に違う固有ベクトル乗算したら相殺する。同じ固有ベクトルは乗算した後1になるので影響はない。それにより \displaystyle \sum_{i} x_i |i>\lt i|をk乗して

\displaystyle (\sum_{i} x_i |i>\lt i|)^k= \sum_{i} x_i^k |i>\lt i|

になることが分かる。

冪級数で関数を定義する

ここでは関数fを冪級数に展開したものは

\displaystyle f(x)=\sum_{i=0}^{\infty} a_i x^i

と定める。行列Xをそのまま代入すると

\displaystyle f(X)=\sum_{i=0}^{\infty} a_i X^i=\sum_{i=0}^{\infty} a_i \sum_{j} x_j^k |j>\lt j|

がある。シグマの位置を変えて射影行列を括りだす。

\displaystyle \sum_{j} (\sum_{i=0}^{\infty} a_i x_j^k ) |j>\lt j|

がある。そこの \displaystyle \sum_{i=0}^{\infty} a_i x_j^k に注目するとこれは固有値 x_jを関数fの冪級数に代入したものになる。証明完了。

大学の線形代数で扱う帰納法

帰納法は証明手法として極めて重要なものです。特に証明する途中、証明する目標となる命題と似たような形の子問題がでる時帰納法は定番化される。帰納法は特に自然数などの構造で役立つけど、線形代数の場合はそう簡単ではない。行列や線形変換や線形空間などは自明的な帰納的構造を持たないため、帰納法を適用しようとしてもなかなか難しいだろう。これから自分が見かけたいくつかの帰納法の考え方を紹介する。

掃出しを使った帰納法

こちらの帰納法は一番簡単で、やり方としてまず行と列の足し引きによって一行と一列の要素を一つ以外全部0にする。その後残りの部分に対して帰納法を適用。典型として任意の行列は標準形に移せることの証明に使われる。標準形はつまり1が対角線上にだけ並ぶ形です。行列 Aの一行目と一列目を掃き出すと以下の形になる。

\begin{pmatrix} 1 & 0 \\ 0 & A_{m,n} \\ \end{pmatrix}

つまり (1,1)にのみ1が存在してそれ以外の一列目と一行目の要素は全部0になる。この時右下の A_{m,n}はサイズが Aより小さいがため帰納法の仮定を適用できる。この方法は主に正則変換の影響を受けない性質持つ命題の証明に使われる。

正値エルミートの場合

正値エルミート行列の場合、正値行列を Hとする。

H= \begin{pmatrix} A_{n-1} & b \\ b^t & c \\ \end{pmatrix} P= \begin{pmatrix} E_{n-1} & A_{n-1}^{-1}b \\ 0^t & 1 \\ \end{pmatrix}

この時 B=P^t A Pが以下の形になる。

B=\begin{pmatrix} A_{n-1} & 0 \\ 0^t & c-A_{n-1}^{-1}[b] \\ \end{pmatrix}

この変換は行列式に影響が出ない上掃き出すことができる。これを使って二次形式やアダマールの不等式などを証明することが楽です。

部分集合に関する帰納法

名前通りにベクトル集合の要素に対して帰納する。なおこの時集合のすべての要素を表せるベクトルの組は基底ではなく、極大線形独立系と呼ばれる。簡単で理解しやすい反面に行列や変換に対してあまり効かないので一回だけ見たことある。では次の命題を考えましょう。

集合Sがn個のベクトルからなる極大線形独立系を持つときn個より多いベクトルは必ず線形従属

集合Sに対して E_1と E_2の二つの極大線形独立系がある時。 E_1はn個のベクトルがある。 E_2はm-1個のベクトルがある。 E_1にない E_2にあるベクトル vを考える。Sからvを取り除いてS'を得る。集合は線形空間の効率を満たさなくでもいいのでとても便利です。この時E_1はまたn個のベクトルを有する。でもE_2はm-1個の線形独立なベクトルしかない。 S'に対して帰納法の仮定を適用すると n \geq m-1はすぐに分かる。イコールの場合に対して証明すれば大丈夫です。

T-不変部分空間に関する帰納法

ある線形変換Tに対して命題を証明する時にT-不変部分空間を使って線形空間を帰納的に構築する。これは行列の形式にも出てくる。行列を対称区分けする時上三角行列のような行列は不変部分空間を持つ。実は任意の行列は上三角化出来るがため任意の線形変換Tは帰納的にできると言えるでしょう。

n次元線形空間の線形変換Tが冪零の時、T^n=O

Tは冪零であることから、ある基底の元で以下の形をする。

B=\begin{pmatrix} 0 & \cdots & c \\ \vdots & \ddots & \vdots \\ 0 & \cdots & 0\\ \end{pmatrix}

この行列は対角線以下が全部0で、自乗するたびに0が右上に蔓延るなのでせいぜいn回自乗したらゼロ行列になる。

実計量空間Vの実対称変換Tの固有空間の直和はVです

固有値 \beta_1と対応する固有空間 W_1を取り出す。 W_1^\perpはT不変で次元数が低いがため帰納法で分解できることがわかる。なおW_1と直交するため、直和である。

正則線形変換Tを分解してみた

ユニタリー空間の任意の正則線形変換 Tは正値エルミート変換HとユニタリーUの積として表せる。この定理の証明では H =\sqrt{T T^*}と置いた後ひたすら式変形したら証明できる。しかし、そこから生み出した疑問は「なぜHはこういう形を持つの？」。

この疑問を解くには[tex: T^]を考えましょう。 T=HUなら当然のこと[tex: T^=U^{-1}H]がある。[tex: TT^ = H H]も当然成立する。従って[tex: H=\sqrt{T T^}]のも当然のことなので、この形を代入して証明できる。なおこの方法だとこの分解の一意性が簡単に見えてくる。

【線形代数あるある】行列の掛け算とベクトル内積はどんな関係？

最近卒論関係で、論理行列と01列の掛け算に触れる。そこで思ったが、実ベクトルと実行列の掛け算は行列の行とベクトルの内積に掛ける。01列と論理行列はなかなかそうとはいかない。

01列からなる線形空間と論理行列

01列の集合は線形空間なり

長さが3の01列の集合は線形空間だったことは以下の手順で証明できる。まずはベクトルの足し算定義です。

\begin{pmatrix} x1 \\ x2 \\ x3 \\ \end{pmatrix} + \begin{pmatrix} y1 \\ y2 \\ y3 \\ \end{pmatrix} = \begin{pmatrix} x1 \oplus y1 \\ x2 \oplus y2 \\ x3 \oplus y3 \\ \end{pmatrix}

つまり二つの01列の足し算はビットごとのxorとして定義される。例えば010と110の足し算は101で。値の異なるビットは計算後1になる。そうでないビットは0になる。そして整数01とベクトルの掛け算は

1\begin{pmatrix} x1 \\ x2 \\ x3 \\ \end{pmatrix} = \begin{pmatrix} x1 \\ x2 \\ x3 \\ \end{pmatrix} \\ 0\begin{pmatrix} x1 \\ x2 \\ x3 \\ \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ \end{pmatrix}

として定義する。ただし、ここの足し算は全てxorで線形空間の公理と一致する。ちなみに長さがN(N=1 2 ... )の01列の集合全て線形空間だったことはこの方法で証明できる。これから論理行列と01列の掛け算に入る。

論理行列と01列の掛け算

前と同じく、三次元01列の場合を説明してN次元に持っていく。 A_{3,3}=(a_{ij})と x_1 x_2 x_3 の掛け算を次のように定義する。

\begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3\\ \end{pmatrix} = \begin{pmatrix} a_{11}x_1+a_{12}x_2+a_{13}x_3 \\ a_{21}x_1+a_{22}x_2+a_{23}x_3 \\ a_{31}x_1+a_{32}x_2+a_{33}x_3 \\ \end{pmatrix}

変換される二進数x_1x_2x_3はx_1 100 \oplus x_2 010 \oplus x_3 001とみなせる。つまり基底 E=\lt 100 , 010 , 001 \gt の線形組み合わせだ。そして行列A_{3,3}は一つの100をa_{11}個の100、a_{21}個の010とa_{31}個の001に変換する。010と001に対しての変換もこうやって定められる。先のプロセスを見ると、線形変換はベクトルと数（スカラー）の掛け算あとベクトル同士の足し算しか使わない。そのため内積の定義がなくても、基底の線形組み合わせを別の線形組み合わせに書き換えれば行列の掛け算は成り立つ。

実線形空間の場合

結論を先に言うと、実行列とベクトルの積は偶々内積と定義が一致する。行列A_{n,n}=(a_{ij})とn次元ベクトル \vec{x}の積のi番目の成分は y_i = \sum_{k=1}^{n} a_{ik}x_{k}で与えられる。直交正規座標系 E = \lt e_1 \dots e_n　\gtの元で a_i=\sum_{k=1}^{n} a_{ik}e_kと x=\sum_{k=1}^{n} x_{k}e_kの内積は

(a_i ,x)=(\sum_{k=1}^{n} a_{ik}e_k ,\sum_{k=1}^{n} x_{k}e_k ) \\ =\sum_{j k} a_{ij}x_{k} (e_j,e_k) \\ = \sum_{k} a_{ik}x_{k}

になる。よく見れば、直交正規基底を取った時の行列表示だけ内積と行列掛け算の定義は一致する。

おまけの複素線形空間

本当に困惑することは複素線形空間の場合。複素線形空間の内積は一つのベクトルをその共役ベクトルにしてから、掛け算する。そこで複素行列の掛け算も共役行列取るじゃないかと思うかもしれないが、先言った通り行列は線形組み合わせを表す。それ故に足したり掛けたり出来れば、別に内積と関係していないわけです。

よく出るあの級数！情報系なら絶対覚えるべき計算量の話！

皆さん、久しぶり！競プロを始めてから実装の話ばかりしていた。いよいよアルゴリズムの原点に戻った！今回は例の \displaystyle \sum_{i=1}^N \log{N}を見に行きたいと思う。

この級数はどこで出るの？

まずは結論から言うと、この級数は \Theta (N \log{N} )クラスに属す。これでちょっと見覚えがあるのか？セットを使って配列から重複を取るアルゴリズムは配列の要素を順に見て行き、そしてセットにいるかどうかをチェックする。配列の長さをNとして、セットのサイズをKとする。クエリごと O(log{K})の時間がかかる。その結果、全体の計算量はこの級数になる。

その他にもLIS問題、最短経路問題など超有名問題で出てくる大人気級数である。

いきなり現れる\Thetaは一体なんだ？

授業ではビッグOを教えることが多いですが、ビッグOはあくまで最悪の場合を指す。実際 Nも N \log{N}も O(N \log{N} )なので、ビッグOは厳密ではない。その代わりに、 \Theta(N \log{N})はちょうどこのクラスにいる関数の集合。

前の例を持ち上げると、セットを使ったあのアルゴリズムは最悪 O(N log{N} )だけじゃなくて、これ以上早くなることもない。

数学コーナーはみんな大嫌いだけど見ないと背が伸びない

まずここで証明したい命題を貼りましょう！

☆証明していくぞ☆：\log{N!} = \Theta \left(N \log{N} \right) \\

この問題は二つの問題に分けて考えましょう！まずは

\log{N!} =O \left(N \log{N} \right) \\

これは自明的だ。 N \log{N} = \log{N^N}から、 \log{N!} \leq \log{N^N}は明らかなことだ。では難しい方へ進むぞ！

N \log{N} =O \left( \log{N\!}\right) \\

今回は帰納法でやる。まずはある Xに対して、X \log{X} \leq k\log{X!}が成立とする。これを仮説1と呼ぶ。そして N=X+1の時の式を見てください。

\displaystyle \left(X+1\right) \log{\left( X+1 \right) } = X \log{ X } + X \log{ \frac{X+1}{X}} + \log{\left( X+1 \right)} \quad (1.1)\\ \log{\left( X+1 \right) ! } = \log{X!} + \log{\left( X+1 \right)} \quad (1.2) \\

今からはただkを式(1.2)にかけたものは依然式(1.1)より大きいことを示せば万事解決。今の式を見れば、ほどんど見たことある顔で安心した。でも待って、式(1.1)の X \log{ \frac{X+1}{X}} はどんどん大きくなるじゃないかっと思うと、実際は上限がある！

補助定理：X \log{ \frac{X+1}{X}} \leq 1　\\

調和級数の時使った技を思い出してね！ \log{ \frac{X+1}{X}} は \displaystyle \int_{X}^{X+1} \frac{1}{t} dtと等しい。この積分の区間での最大値はtイコールXの時から、 \log{ \frac{X+1}{X}} \leq \frac{1}{X}がわかる。さらに式(1.1)は式(1.3)より小さいことが分かった。

X \log{ X } + 1 + \log{\left( X+1 \right)} \quad (1.3)\\

定数kを式(1.2)に掛けると k \log{X!} + k \log{\left( X+1 \right)} が得られる。仮説1を使えば k\log{X!}と X \log{ X } を式1.2と式1.3から消せる。残る部分は 1 + \log{\left( X+1 \right)}と k \log{\left( X+1 \right)}だけ。定数 kを予め大きくしたら k \log{\left( X+1 \right)} \gt 1 + \log{\left( X+1 \right)}も成立する。 当然のことことなんですが、N=2の時 k\log 2 \gt \log 4が成立するので証明終了。Q.E.D

あとがき

今回の記事いかがでしょうか。私もこれでまた一つ賢くなった気がしたので、これからももっとしんかしていくぜ！それじゃまたね、bye~bye~

RE：ゼロから始めるLIS問題

最長部分増加列（LIS）問題は序列a_1 a_2 a_3 \dots a_nの単調増加の部分列の中で一番長い部分列の長さを求める問題である。最近ARC 104の問題

atcoder.jp

を見ていたらLIS問題を振り替えようと思います。

貪欲アルゴリズム

配列dp[i]があるとする。dp[i]は長さがiの部分増加列の最後の要素の最小値を表す。例えば列1 2 3 4 5全体に対して、長さが4になる部分増加列は1 2 3 4などの五通りある。その中で最後の要素の最小値は４なのでdp[4]=4になる。

このアルゴリズムは配列の要素ごとに以下のプロセスを繰り返す。

  1. 配列の要素a_iをみる
  2. 今の最長増加列の長さをmとすると、二分探索でa_iより大きい要素をdpから探す。
  3. 見つかったらその要素をa_iと置き換える。
  4. 見つからなかった場合は長さを1増やして、dp配列の最後をa_iと置く。

このアルゴリズムは簡単で、ツリー上のLIS問題にも適用する。

atcoder.jp

BITを用いたdpアルゴリズム

また配列dpを用意して、今回は dp_iを「iが最後となる部分増加列の長さ」にする。BITを使って効率よく dp_1から dp_kまでの最大値を探す。アルゴリズムは元の配列要素ごとに以下のプロセスを繰り返す。

  1. 配列の要素a_iをみる
  2. dp_1 から dp_{a_i-1}までの最大値tmpを探す
  3. dp_{a_i}をtmp+1にする

この方法が成立する前提は全ての要素更新は要素を大きくすること。そして区間最大値は全部初めから計算したもの。この方法は貪欲アルゴリズムより複雑だけど、LISだけでなくより複雑な制約を扱える。例えばこのLaIS問題。

codeforces.com

シュミット分解を軽く証明した

まずはシュミット分解は何かを軽く説明する。ある純粋量子状態 |\psi>があるとする。元の量子システムをAとBの二つのシステムに分けた後、サブシステムの基底を|i>と|j>とする。 |\psi>=\sum \lambda_{r} |i>|j> が成立する。ここのrはAとBの中で次元数が低いシステムの次元数に相当する。

AとBが同じ次元の場合

元のシステムは A \otimes Bで表されるので、|\psi >=\displaystyle \sum_i \sum_j a_{ij} |i> |j>は成立する。この形は目標と似ているが、加算する項が多い。 a_{ij}を並べて幅と高さが一致する行列Aにする。Aはユニタリー行列U,Vと対角行列Dの積UDVに書ける。ここではaijをAのi行目j列の要素とする。前の分解によると、 a_{ij}= \sum u_{ik} d_{kk} v_{kj} が成立する。これを代入すれば、|\psi>=\displaystyle \sum_i\sum_j \sum_k u_{ik} d_{kk} v_{kj} |i>|j>がわかる。

そこで、Aシステムの基底|i^k>を \displaystyle \sum_i u_{ik} |i>として、Bシステムの基底|j^k>を\displaystyle \sum_j v_{kj} |j>とする。そしてDの対角成分d_{kk}を\lambda_rにする。そうしたら、 | \psi > = \displaystyle \sum_k d_{kk} |i^k>|j^k> が得られる。

AとBが異なる次元の場合。

その場合、 a_{ij}を並べた行列Aの幅と高さは異なる。従って、Aをユニタリー行列UVと対角行列Dの積に分解することはできない。具体例を挙げると、システムAを三次元にしてシステムBを二次元とする。この場合行列Aは幅が3で高さが2になる。

ここではBシステムの次元数が低い場合を考える。システムBに仮想な補助システムCを導入して。システムCの状態を | 0 > にする。元の量子システムと合わせて全体の状態が |\psi 0>になった。この状態をシステムAとシステム B \otimes Cに均等に分けることができる。さらに、Aの基底を {|i>}としてB \otimes Cの基底を {|j>}とする。

AとBが同じ次元の場合を参考して | \psi 0>=\displaystyle \sum_i \sum_j a_{ij} |i>|j>が成立する。従って | \psi 0 >はシュミット分解ができることはわかる。ここで導入した補助システムCは0状態にいるので、|j>の中のCの成分が0でない時a_{ij}=0。そこからわかることは |\psi 0>=\displaystyle \sum_r \lambda |i>|j>|0>。末尾の|0>を除き取ると、シュミット分解ができた。