Jordan 標準形の教材作成について

きっかけ

Math & Coding という社会人の機械学習および数学の勉強会にて,

「Jordan 標準形ショートカット」という題目で解説

PC 持参の社会人を前に解説

1回で解説し切る. 概ね好評

具体例を web で生成することの有用性を実感.

目標

$\rightarrow$ Jordan 標準形の理論を理解するための web テキストの作成

$\rightarrow$ 具体例が解かれていく様子を観察することにより, 理解を深める

対象

$\rightarrow$ 大学初年級の学生, プログラマなど社会人

方針

$\rightarrow$ 単因子法を利用した解法.

（広義固有空間を利用したやつは, 却って回りくどく難解に感じる）

ゴール

$\rightarrow$ 解答が有理数係数行列となるよう問題を生成し,

ca.js の solver で解かれる様子を鑑賞する

①smith 標準形が出た時点でゴールとするのか

②$PAP^{-1}=$ Jordan標準形 となるような可逆行列 $P$ の導出でゴールとするのか

$\rightarrow$ ドリル的な問題と, その解答の自動生成はまだ先の話.

ca.js とは

JavaScript の多倍長整数ライブラリ big-integer.js のみを利用した

自作数式処理ライブラリ（四角い車輪の再発明）

web ブラウザの計算能力のみで計算したい

2016年頃から作り始める

元々自身の知的探求と数式処理の教科書の勉強のためにJSを利用したことが動機

SymPy がライブラリを利用せず Python のみで書かれているとのこと

具体的に何をしてきたのか

• Pell 方程式 [00-07]
• groebner 基底 [05-12]
  (丸山正樹著 「グレブナー基底とその応用」 p82 「性能の低い計算機代数のソフトでは相当待っても答えが出ない」)
• 単因子計算 [08-01], []
• Hensel 構成による因数分解 [02-15, 02-21]
• Schreier-Sims アルゴリズム [14-08]

$A\in \mathrm{Math}_n(\mathbb{C})$ の Jordan block への分解を構成を概観する.

$tI-A\in \mathrm{Math}_n(\mathbb{C}[t])$

$e_1(t)|e_2(t)|\cdots|e_n(t)$

となる $P(t),Q(t)\in\mathrm{GL}_n(\mathbb{C}[t])$ が存在する.

$P(t),Q(t)$ の導出を含め ca.js によって実装可能である

$\displaystyle{e_i(t)=\prod_{j=1}^r(t-\alpha_j)^{\lambda_{ij}} \quad (0\leq \lambda_{1j}\leq \lambda_{2j}\leq \cdots \leq \lambda_{nj})}$
$\displaystyle{\sum_{i=1}^n\sum_{j=1}^r\lambda_{ij}=n}\hspace{1cm}(\exists \alpha_1,\cdots,\alpha_m\in\mathbb{C})$
と因数分解される. (この式から, 殆どの $\lambda_{ij}$ が $0$ になることが分かる.) よって

$\displaystyle{P(t)(tI-A)Q(t)=\prod_{j=1}^m\left[\begin{array}{lll}(t-\alpha_j)^{\lambda_{1j}} & & \\ & \ddots & \\ & & (t-\alpha_j)^{\lambda_{nj}}\end{array}\right]}$

ca.js に因数分解のアルゴリズムを実装する必要がある.

一方 Jordan 細胞を

$\displaystyle{J_l(\alpha):=\left[\begin{array}{llllll}\alpha & 1 & & & & \\ & \alpha & 1 & & & \\ & & & \ddots & & \\ & & & & \alpha & 1 \\ & & & & & \alpha \end{array}\right]\in\mathrm{Mat}_l(\mathbb{C})}$
とすると,

$\displaystyle{J:=\oplus_{j=1}^m\oplus_{i=1}^nJ_{\lambda_{ij}(\alpha_j)}}$
とするとき,

$\displaystyle{R(t)(tI-J)S(t)=\prod_{j=1}^m\left[\begin{array}{lll}(t-\alpha_j)^{\lambda_{1j}} & & \\ & \ddots & \\ & & (t-\alpha_j)^{\lambda_{nj}}\end{array}\right]}$
となるような $R(t),S(t)\in\mathrm{GL}_n(\mathbb{C}[t])$ が存在する.

これは一般論である.

従って

$\displaystyle{R(t)^{-1}P(t)(tI-A)Q(t)S(t)^{-1} = tI-J}$

従って

$\displaystyle{R(t)^{-1}P(t)(tI-A)Q(t)S(t)^{-1} = tI-J}$
に対し,

$Q(t)S(t)^{-1} = U_1(t)(tI-J) + U$ となるような $U\in\mathrm{Mat}_n(\mathbb{C})$ を求めれば,

$\displaystyle{U^{-1}AU = J = \oplus_{j=1}^m\oplus_{i=1}^nJ_{\lambda_{ij}}(\alpha_j)}$
と Jordan block への分解と変換行列 $U$ が構成できる.

具体的な実装

解答となる Jordan 標準形 $J$ を与える.

可逆行列 $P$ をランダムに与えて, $A=P^{-1}JP$ とする.

$tI-A$ の smith 標準形を求める.

ca.js の [12-02] にて実演.

有理数上だと係数膨張して非現実的. ものすごく時間がかかる.

有限素体上だと現実的な時間で終わる. ca.js [13-03]

今後の目標

Jordan 標準形 の問題で, 演習書レベルの問題の自動生成と, その解説の自動化.

JavaScript で自力というのでは, あまりにも遅すぎるので, giac.js の利用にも取組始めなければ.