はじめに

この解説に出てくる行列は、特に断りがない場合は3x3です。

また、\(I\)は単位行列,\(O\)は零行列です。

つまり、

\[I=\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\\\end{pmatrix},O=\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\\\end{pmatrix}\]

事前知識

対称式を行列で管理することを考えます。

\[A=\begin{pmatrix}0&1&0\\0&0&1\\u&-t&s\\\end{pmatrix}\]

という行列は、固有多項式が\(\lambda ^3-s\lambda ^2+t\lambda -u=(\lambda -\alpha)(\lambda -\beta)(\lambda -\gamma)\)であるため、固有値が\(\alpha,\beta,\gamma\)であることがわかります。ここで、\(A\)は固有多項式が重根を持たないため対角化可能となります。

\[\Lambda =\begin{pmatrix}\alpha&0&0\\0&\beta&0\\0&0&\gamma\\\end{pmatrix}\]

としたとき、ある正則行列\(P\)が存在して、

\[A=P\Lambda P^{-1}\]

と書けます。

ここで、有理数係数多項式\(f(x)=a_0+\cdots +a_nx^n\)があったとき、

\[f(A)=\sum_{j=0}^{n}a_jA^j=\sum_{j=0}^{n}a_jP\Lambda^j P^{-1}=Pf(\Lambda)P^{-1}=P\begin{pmatrix}f(\alpha)&0&0\\0&f(\beta)&0\\0&0&f(\gamma)\\\end{pmatrix}P^{-1}\]

よって、\(f(A)\)の固有値は\(f(\alpha),f(\beta),f(\gamma)\)となります。

また、\(A\)と\(f(A)\)は、\(P^{-1}AP,P^{-1}f(A)P\)がともに対角行列となることから、同時対角化可能となります。

また、有理数係数多項式\(f(x)\)があったとき、\(f(\alpha)+f(\beta)+f(\gamma)\)を求めたいならば\(f(A)\)のトレースを、\(f(\alpha)f(\beta)f(\gamma)\)を求めたいならば\(f(A)\)の行列式を求めればよいことがわかります。

また、 \(f,g\)という2つの多項式があったとき、 \(f(A)+g(A)\)の固有値は

\[f(\alpha)+g(\alpha),f(\beta)+g(\beta),f(\gamma)+g(\gamma)\]

\(f(A)g(A)\)の固有値は

\[f(\alpha)g(\alpha),f(\beta)g(\beta),f(\gamma)g(\gamma)\]

となります。（これも\(A\)と同時対角化可能）

さらに、\(f(\alpha),f(\beta),f(\gamma)\neq 0\) の場合、\(f(A)\)の逆行列は固有値が\(1/f(\alpha),1/f(\beta),1/f(\gamma)\)となって、\(A\)と同時対角化可能となります。

解法

以上を踏まえて、この問題を解くことを考えます。

これは、

\[-\dfrac{\beta^m-\gamma^m}{(\beta-\gamma)}\cdot \dfrac{\alpha^n}{(\alpha-\beta)(\alpha-\gamma)},-\dfrac{\gamma^m-\alpha^m}{(\gamma-\alpha)}\cdot \dfrac{\beta^n}{(\beta-\gamma)(\beta-\alpha)},-\dfrac{\alpha^m-\beta^m}{(\alpha-\beta)}\cdot \dfrac{\gamma^n}{(\gamma-\alpha)(\gamma-\beta)}\]

を固有値に持つような行列を作って、それのトレースを求めればよいです。

そしてこの行列は以下の行列の積によって構成されます。

• 固有値が\(\dfrac{\beta^m-\gamma^m}{(\beta-\gamma)},\dfrac{\gamma^m-\alpha^m}{(\gamma-\alpha)},\dfrac{\alpha^m-\beta^m}{(\alpha-\beta)}\)となるような行列
• 固有値が\(-\alpha^n,-\beta^n,-\gamma^n\)となるような行列
• 固有値が\(\dfrac{1}{(\alpha-\beta)(\alpha-\gamma)},\dfrac{1}{(\beta-\gamma)(\beta-\alpha)},\dfrac{1}{(\gamma-\alpha)(\gamma-\beta)}\)となるような行列

これらについて順番に考えていきましょう。

1. \(\dfrac{\beta^m-\gamma^m}{(\beta-\gamma)}\)について

   条件を満たすような行列を\(S_m\)と書くことにします。

   結論から言うと、以下のように再帰的に計算することができます。

   • \(S_0=O\)
   • \(S_{2k}=((\mathrm{tr} A^k)\cdot I-A^k)S_k\quad (k\geq 1)\)
   • \(S_{2k+1}=((\mathrm{tr} A^{k+1})\cdot I-A^{k+1})S_k+(tI-sA+A^2)^k\quad(k\geq 0)\)

   このとき、この部分の計算量は\(O(\log{m})\)となって十分間に合います。

   証明

   偶奇で場合分けします。
   
   $m=2k$のとき、 これは $$\beta^{2k-1}+\beta^{2k-2}\gamma+\cdots +\beta\gamma^{2k-2}+\gamma^{2k-1}$$ であり、これは因数分解ができて $$=(\beta^k+\gamma^k)(\beta^{k-1}+\beta^{k-2}\gamma+\cdots +\beta\gamma^{k-2}+\gamma^{k-1})$$ ここで、$\beta^k+\gamma^k,\ldots$を固有値に持つような行列は、 $\left(\mathrm{tr} A^k\right)\cdot I-A^k$と書けます。（$I$は単位行列） また、$\beta^{k-1}+\cdots +\gamma^{k-1}$は$S_k$となります。
   
   $m=2k+1$のとき、 これは $$\beta^{2k}+\beta^{2k-1}\gamma+\cdots +\beta^k\gamma^k+\cdots +\beta\gamma^{k-1}+\gamma^k$$ となり、これは $$(\beta^{k+1}+\gamma^{k+1})(\beta^{k-1}+\beta^{k-2}\gamma+\cdots +\beta\gamma^{k-2}+\gamma^{k-1})+\beta^k\gamma^k$$ と書けます。 ここで、$tI-sA+A^2$は$\beta\gamma,\gamma\alpha,\alpha\beta$を固有値に持つため、 、$(tI-sA+A^2)^k$は$\beta^k\gamma^k,\gamma^k\alpha^k,\alpha^k\beta^k$を固有値に持ちます。

2. \(-\alpha^n\)について

   これについては \(-A^n\)とすればよいです。
   計算量についても、二分累乗のテクニックを使えば\(O(\log{n})\)で計算できて十分間に合います。

3. \(\dfrac{1}{(\alpha-\beta)(\alpha-\gamma)}\)について

   結論から言うと、

   \[(3A^2-2sA+tI)^{-1}\]

   となります。逆行列の存在性も保証されます。
   計算量についてもこの部分は\(n,m\)に対して定数時間で計算することができます。

   証明

   これについては、固有値が $$(\alpha-\beta)(\alpha-\gamma),(\beta-\gamma)(\beta-\alpha),(\gamma-\alpha)(\gamma-\beta)$$ であるような行列の逆行列を求めればよいです。 $\varphi(x)=x^3-sx^2+tx-u$とします。 ここで、 $$(\alpha-\beta)(\alpha-\gamma)=\lim_{x\to\alpha}\dfrac{(x-\alpha)(x-\beta)(x-\gamma)}{x-\alpha}=\lim_{x\to\alpha}\dfrac{\varphi(x)-\varphi(\alpha)}{x-\alpha}=\varphi'(\alpha)$$ ここで、$\varphi'(x)=3x^2-2sx+t$であるため、 $$3A^2-2sA+tI$$ は$\varphi'(\alpha),\varphi'(\beta),\varphi'(\gamma)$を固有値に持ちます。 また、$\alpha,\beta,\gamma$は相異なることから、この行列は正則であり、逆行列が存在します。

以上の1,2,3を踏まえると

\[-S_mA^n(3A^2-2sA+tI)^{-1}\]

のトレースが答えとなります。全体の時間計算量も\(O(\log{n}+\log{m})\)となるため十分間に合います。

補足

行列の掛け算の順番についてですが、\(S_m,A^n,(3A^2-2sA+tI)^{-1}\)はどれも\(A\)についての有理式で書くことができて、これらは互いに可換となります。 よって行列の掛け算の順番については入れ替わっても構いません。