代数的性質を構造化行列で記述する
この記事は 日曜数学 Advent Calendar 2025 の19日目の記事です．
はじめに
この記事では，構造化行列と呼ばれる，とあるAffine空間に含まれる行列を用いて，既約性や互いに素といった代数的性質を線形代数の言葉で記述していきます．構造化行列はsymbolic-numeric computation(以後，SNC)という分野の様々な問題で現れ，アルゴリズムの開発に活用されています（線形代数と数理最適化の話に帰着するので，非常に計算機向き）．考える問題は多項式GCD，多変数多項式の因数分解，グレブナー基底で，それぞれSylvester行列，Ruppert行列，Macaulay行列，という構造化行列が現れます．グレブナー基底のパートではグレブナー基底の定義やBuchbergerアルゴリズムは知っている前提で進めるので注意してください．
この記事で伝えたいのは，代数的に特異な状況（非自明GCDを持つ，可約等）が構造化行列のランクから分かるのが嬉しい！ってことです．
そもそもsymbolic-numeric computationって何？
という読者がほとんどだと思います．
本題に入る前に，数値計算と計算機代数という分野について簡単に解説しましょう．両方ともコンピュータに数学の計算をさせたいというモチベーションは同じですが，思想は大きく異なります．
数値計算とは
数値計算は，数学の問題を近似的に解くことを目的とした分野です．厳密に解くことが難しい・できないものに対して，誤差が入ることを許容して近似解を求めていきます．例えば，$x^2-2=0$の解を求めよ，という問題に対して，数値計算ではNewton法等を使って$x=\pm1.41421\ldots$と近似解を計算します．
計算機代数とは
計算機代数は，数学の問題を厳密（記号的）に解くことを目的とした分野です．数値計算とは異なり，誤差が入ることを許容しません．$x^2-2=0$の解を求めよ，と言われたなら，誤差の入るNewton法等は御法度で，計算機代数では$x=\pm \sqrt{2}$と二乗して2になるものとして扱います．実際，計算機上で$\sqrt{2},-\sqrt{2}$は，$(x^2-2,[1,2]),(x^2-2,[-2,-1])$と，最小多項式と根の分離区間（最小多項式の根をちょうど一つだけ含む区間）の組として表現することがあります．
数値計算と計算機代数を合体させよう！
計算機代数では厳密計算を扱えることが大きなメリットですが，数値計算に比べると計算コストが重く，問題を解く上では実用性に欠けることが多々あります．そこで，高速な数値計算を計算機代数に組み込むことで，良いとこどりをしよう，という考えから，SNCという融合領域が生まれました．SNCの一例として，従来のアルゴリズムに区間演算とゼロ書き換えを導入し，十分な精度で数値計算を行うことで厳密解を得る，あるいは近似する，安定化理論があります．ちなみに，安定化理論の概要は こっち に書いているので，ぜひ見てください．
第一種の問題と第二種の問題
先ほどの解説は，正確な入力に対して，計算過程で数値計算を活用しよう，という話でした．これは第一種の問題と呼ばれており，SNCの一面にすぎません．第二種の問題では，そもそも入力多項式の係数に誤差が含まれており，正確でないという状況を考えます．
この場合，誤差のせいで代数的に特異な（＝面白い）性質が埋もれてしまいます．
本来$f=x^2-y^2=(x+y)(x-y)$のはずが，何らかの影響で係数に誤差が混入し，$g=1.000001x^2-1.0000002y^2+0.0000005$となってしまった！元の$f$は可約なのに，$g$は既約...
第二種の問題では，入力に含まれた誤差を除去して，本来あったであろう特異な代数的性質を取り戻すことが目的となります．
誰の言葉か忘れてしまいましたが，第二種の問題を宝探しだ！と言う人もいます．お宝は本来の性質のことで，とてもいい表現です．構造化行列はお宝を探し当てるための，地図・コンパスにあたるものだと思っています．
さて，未定義語をいつまでも使っているとよろしくないので，そろそろ構造化行列を定義しましょう．たいして難しいものではありません．
$S_0,\ldots,S_k\in \mathbb{C}^{m\times n}$とし，$\mathcal{S}=\{S_0+\sum_{i=1}^kc_iS_i\mid c_1,\ldots,c_k\in \mathbb{C}\}$と定める．このとき，$\mathcal{S}$をAffine構造といい，$A\in \mathcal{S}$なら，AはAffine構造を持つという．
これから紹介する行列は，いずれもAffine構造を持っています．
記事の構成
まず，計算機代数の問題と関連する構造化行列について紹介します．その後，入力に誤差がある場合，構造化行列にどのような変化があるか概説し，誤差を許容した第二種の問題としての定式化を与えます．
最後に，第二種の問題を解くのに，構造化行列が活用できることを紹介します．
GCDとSylvester行列
まず，多項式GCDについて考えていきましょう．GCDの計算アルゴリズムは色々ありますが，今回はとある行列のkernelから求める手法について考えていきます．まず，Sylvester写像というものを定義します．
$P_n$を$n$次未満の実（あるいは複素）係数多項式全体の集合とする．$f,g$をそれぞれ次数$m,n$として，写像$\varphi_{f,g}:P_n\times P_m \to P_{n+m}$を，$\varphi_{f,g}(s,t)=sf+tg$と定める．$\varphi_{f,g}$を$f,g$に対するSylvester写像という．
Sylvester写像から，$f,g$の共通因子についての情報を得ることができます．
$f,g$が非自明な共通因子を持つ$\Longleftrightarrow$ $\varphi_{f,g}$が単射でない．
$(\Rightarrow)$$h=\gcd(f,g)$とする．$s=g/h,t=f/h$とすれば，$\varphi_{f,g}(s,t)=0$となり，単射でないと分かる．
$(\Leftarrow)$$sf+tg=0$なる$s\in P_n,t\in P_m, (s,t)\neq (0,0)$が存在する．$f,g$が互いに素と仮定すると，
$sf=-tg$より，$f\mid tg$となる．ゆえに$f\mid t$となるが，$\deg f>\deg t$よりこれはあり得ない．
従って，$f,g$は非自明な共通因子を持つと分かる．
Sylvester写像のままだと扱いづらいので，ここから行列を取り出します．
$f=\sum_{i=0}^mf_ix^i,g=\sum_{i=0}^ng_ix^i,s=\sum_{i=0}^{n-1}a_ix^i,t=\sum_{i=0}^{m-1}b_ix^i$と表示すると，$sf+tg$は以下のようになります．
\begin{align*}
&(a_{n-1}x^{n-1}+\cdots+a_0)(f_mx^m+\cdots+f_0)+(b_{m-1}x^{m-1}+\cdots+b_0)(g_nx^n+\cdots+g_0)\\
&=(a_{n-1}f_m+b_{m-1}g_n)x^{m+n-1}+(a_{n-1}f_{m-1}+a_{n-2}f_{m}+b_{m-1}g_{n-1}+b_{m-2}g_n)x^{n+m-2}+\cdots+(a_0f_0+b_0g_0).
\end{align*}
Sylvester写像の単射性が関わるわけなので，$sf+tg=0$となる$s,t$を与える係数$a_n,\ldots,a_0,b_m,\ldots,b_0$が存在するか否かを判別したいです．$sf+tg$の係数が全てゼロになるときを考えましょう．
\begin{cases}
a_{n-1}f_m+b_{m-1}g_n=0,\\
a_{n-1}f_{m-1}+a_{n-2}f_{m}+b_{m-1}g_{n-1}+b_{m-2}g_n=0,\\
\vdots\\
a_0f_0+b_0g_0=0.
\end{cases}
ここから，行列を取り出しましょう．$a_{n-1},\ldots,a_0,b_{m-1},\ldots,b_0$を変数として，以下のように行列表現できます．
\begin{equation*}
\begin{pmatrix}
f_m & & & & g_n & & & \\
f_{m-1} & f_m & & & g_{n-1} & g_n & & \\
\vdots & f_{m-1}& \ddots & & \vdots & g_{n-1}& \ddots & \\
f_0 & \vdots & \ddots & f_m & g_0 & \vdots & \ddots & g_n \\
& f_0 & & f_{m-1}& & g_0 & & g_{n-1}\\
& & \ddots & \vdots & & & \ddots & \vdots \\
& & & f_0 & & & & g_0
\end{pmatrix}
\begin{pmatrix}
a_{n-1}\\
a_{n-2}\\
\vdots \\
a_0 \\
b_{m-1}\\
b_{m-2}\\
\vdots \\
b_0
\end{pmatrix}=
\begin{pmatrix}
0\\
\vdots\\
\vdots \\
\vdots \\
\vdots\\
\vdots \\
0
\end{pmatrix}
\end{equation*}
この係数行列を$f,g$のSylvester行列といい，$\mathrm{Syl}(f,g)$と書きます．$f$に対応する列は$n$本，$g$に対応する列は$m$本あるので，$(m+n)\times (m+n)$正方行列となります．
先ほどの命題から，以下が成り立つことが分かります．
$\mathrm{Syl}(f,g)$がランク落ちする $\Longleftrightarrow$ $f,g$は非自明な共通因子を持つ．
写像を直接扱うよりはずいぶんやりやすくなりました．さらに，いくつかの仮定の下で共通因子もSylvester行列から計算できます．
$\mathrm{Syl}(f,g)$はランク落ちしているとする．$\mathrm{Syl}(f,g)\vb{x}=\vb{0}$の非自明解$\vb{x}=(a_{n-1},\ldots,a_0,b_{m-1},\ldots,b_0)$から，$s=\sum_{i=0}^{n-1}a_ix^i,s=\sum_{i=0}^{m-1}b_ix^i$と定める．このとき，$f/t,-g/s$が多項式となるならば，$f,g$の共通因子となる．
定め方から，$sf+tg=0$となり，$sf=-tg$が成り立つ．$sf/t=-g$より$f/t$は$g$を割り切る．また，明らかに$f$も割り切るので，$f,g$の共通因子となる．$f/t=-g/s$より，$-g/s$も同様．
命題3，色々惜しいところがあることにお気づきでしょうか．まず「$f/t,-g/s$が多項式となるならば」という仮定ですが，結構強い仮定ですよね．有理関数になってしまう例は作れますか？（Geminiは一発で出しました，賢い...）．
もう一つ，「$f,g$の共通因子となる」ですが，GCDが出てくる保証がないという点も困ります．共通因子がGCDとなっているか，判定する方法を我々は知りませんので．
これらの惜しいところを解決するには，$s,t$にもう少し制約が必要です．一つ目は，$s,t$が互いに素という条件です．互いに素であれば，$s$が$g$を，$t$が$f$を割り切らなければならないので，多項式になるという条件が満たされます．二つ目は，できる限り次数を小さくとる，ということです．$f/t,-g/s$がGCDの候補なので，次数を上げるためには，分母に出てくる$s,t$は次数を小さくとるべきなのです．
制約が必要なのは分かったけど，どうやって制約を反映させるんだよ，と思われるかもしれません．実は，Sylvester行列から必要な部分だけ取り出すことで，どちらも達成できるようになります．
$k\in \mathbb{N}$とする．以下の行列を$f,g$の$k$次Sylvester行列といい，$\mathrm{Syl}_k(f,g)$と定める．
\begin{array}{c} \begin{pmatrix} f_m & & & & g_n & & & \\ f_{m-1} & f_m & & & g_{n-1} & g_n & & \\ \vdots & f_{m-1}& \ddots & & \vdots & g_{n-1}& \ddots & \\ f_0 & \vdots & \ddots & f_m & g_0 & \vdots & \ddots & g_n \\ & f_0 & & f_{m-1}& & g_0 & & g_{n-1}\\ & & \ddots & \vdots & & & \ddots & \vdots \\ & & & f_0 & & & & g_0 \end{pmatrix}\\ \underbrace{ }_{n-k} \quad \underbrace{ }_{m-k} \end{array}
Sylvester行列の$f,g$に対応する部分から，$k$列ずつ削除したものです．$k=0$のとき，通常のSylvester行列と一致します．この行列から，GCDを計算することができます．
$r\in \mathbb{N}$を$\mathrm{Syl}_k(f,g)$がランク落ちするような$k$のうち，最大のものとする．$\mathrm{Syl}_r(f,g)\vb{x}=\vb{0}$の非自明解$\vb{x}$に対し，$s$を$\vb{x}$の最初の$n-r$個の成分を係数とする$n-r-1$次式，$t$を$\vb{x}$の最後から$m-r$個の成分を係数とする$m-r-1$次式とする．このとき，$f/t,-g/s$は$f,g$のGCDとなる．
$h=\gcd(s,t)$とし，$u=\deg h \geq 1$と仮定する．$s=s_1h,t=t_1h$とかけるので，$0=sf+tg=h(s_1f+t_1g)$より，$s_1f+t_1g=0$となる．$ \deg s_1=n-r-u-1,\deg t_1=m-r-u-1$より，$Syl_{r+u}(f,g)$もランク落ちする．しかし，これは$r$の最大性に矛盾．よって$s,t$は互いに素となる．
次に，$f/t,-g/s$が$f,g$のGCDとなることを示す．$d=\gcd(f,g)$とし$f=f_1d,g=g_1d$と書くと，$0=sf+tg=d(sf_1+tg_1)$より，$sf_1+tg_1=0$となる．$f_1/t,-g_1/s$は$f_1,g_1$の共通因子となるが，$\gcd(f_1,g_1)=1$より，$f_1/t=-g_1/s=1$となる．ゆえに，$f/t=-g/s=d.$
$s,t$が互いに素が示せていますね．$s,t$の次数についても，なるべく小さくなるように定められていることが分かるでしょうか．これで，Sylvester行列からGCDを計算する方法がわかりました．
近似GCD
さて，厳密な場合のGCDとSylvester行列の関係について見ていきました．入力に誤差が含まれる場合を考えていきましょう．このとき，多項式の係数を用いて構成されるSylvester行列も本来のものから少しズレます．すると，どうなるでしょう？以下の例のような状況がおきます．
$f=x^5-1,g=x^3-1$とする．これらの多項式に何らかの原因で係数に誤差が混じり，$\tilde{f}=x^5 - 1.00004,\tilde{g}=1.00005 x^3 - 1$となったとしよう．本来は$\gcd(f,g)=x-1$となるはずだが，$\mathrm{Syl}(\tilde{f},\tilde{g})$は以下の通りになり，$\rank\mathrm{Syl}(\tilde{f},\tilde{g})=8$となり，フルランクである．これはGCDが$1$となることを意味する．
$
\mathrm{Syl}(\tilde{f},\tilde{g})=\begin{pmatrix}
1 & 0 & 0 & 0 & 0 & -1.00004 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 & -1.00004 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & -1.00004 \\
1.00005 & 0 & 0 & -1 & 0 & 0 & 0 & 0 \\
0 & 1.00005 & 0 & 0 & -1 & 0 & 0 & 0 \\
0 & 0 & 1.00005 & 0 & 0 & -1 & 0 & 0 \\
0 & 0 & 0 & 1.00005 & 0 & 0 & -1 & 0 \\
0 & 0 & 0 & 0 & 1.00005 & 0 & 0 & -1 \\
\end{pmatrix}.
$
本来のSylvester行列はランク落ちしていたのに，誤差によってランクが上がってしまったようです．
例1や例2のように，入力に誤差が含まれる場合，多くの場合本来の代数的に特異な性質は埋もれてしまいます．また，この状況で厳密な場合のアルゴリズムを適用しても，本来の性質を知ることはできません．厳密な意味で既約，互いに素というのもそれはそれで正しいですからね，入力の時点でおかしい状況など想定していないのです．しかし，このままでは入力の持つ性質について何も分かっていないも同然なので，本来の性質を少しでも知るために，入力に誤差があることは前提として，GCDっぽいものを定義すること，それを計算するアルゴリズムを考えること，が必要となります．誤差を許容した定義を考えたことで，以下の近似GCDの概念が生まれました．
$f,g\in \mathbb{C}[x], \varepsilon\geq 0$に対し，以下を満たす次数最大の$h$を$f,g$の許容度$\varepsilon$の近似GCDという．
\begin{align*}
&\exists \Delta_f,\Delta_g,f_1,g_1\in \mathbb{C}[x], f+\Delta_f=f_1h, g+\Delta_g=g_1h,\\
&\deg\Delta_f\leq \deg f, \deg \Delta_g \leq \deg g, \quad \|\Delta_f\|_2\leq \varepsilon \|f\|_2,\|\Delta_g\|_2\leq \varepsilon \|g\|_2.
\end{align*}
ただし，$\|p\|_2$は$p$の係数ベクトルの$2$ノルムとする．
他の定義として，次数指定型の近似GCDといったものもあります．
因数分解とRuppert行列
多変数多項式の因数分解の計算法について考えましょう．係数が$\mathbb{Q}$か$\mathbb{C}$かで状況が随分変わりますが，今回は$\mathbb{C}$の場合です．今回は二変数の場合のみ考えますが，三変数以上でも同じようにできます(参考：appmulfac)．
本節では，$\gcd(f,\frac{\partial f}{\partial x})=1$が成り立つとします．成り立たない場合は，$f$の代わりに$f/\gcd(f,\frac{\partial f}{\partial x})$を考えればよいです（ただし，因子の重複度が消えることに注意）．
因数分解を考える上で，既約性の必要十分条件を考察することは自然な発想かと思います．Ruppertは，ある偏微分方程式の非自明解の有無と既約性が関係していることを示しました．
$f\in \mathbb{C}[x,y]$が$\mathbb{C}$上既約であることと，次の偏微分方程式が非自明解$g,h\in \mathbb{C}[x,y]$を持たないことが同値である．
\begin{equation}
\frac{\partial}{\partial y}\Bigl(\frac{g}{f}\Bigr)=\frac{\partial}{\partial x}\Bigl(\frac{h}{f} \Bigr ).
\end{equation}
ただし，$g,h$は以下を満たす．
$\deg_x g\leq \deg f-1, \quad \deg_y g\leq \deg_y f, $
$\deg_x h\leq \deg_x f,\quad \deg_y h\leq \deg_y f-2.$
この偏微分方程式から，構造化行列を作ることができます．$g,h$の各変数に関する次数が上からおさえられているため，係数を未知数として，以下のように表すことができます．
$g=a_{m-1,n}x^{m-1}y^n+a_{m-1,n-1}x^{m-1}y^{n-1}+\cdots+a_{0,0},$
$h=b_{m,n-2}x^my^{n-2}+\cdots+b_{0,0}.$
ただし，$m=\deg_x f,n=\deg_y f$である．
偏微分方程式を整理すると，$f\frac{\partial g}{\partial y}-g\frac{\partial f}{\partial y}-f\frac{\partial h}{\partial x}+h\frac{\partial f}{\partial x}=0$となります．左辺の多項式の係数は$g,h$の係数について線形であることに注意してください．ゆえに，両辺の係数を比較することで，$g,h$の係数を変数とする連立線形方程式が定まります（GCDのパートでSylvester行列を抽出したときとやり方は同じです）．この係数行列をRuppert行列と呼び，$R(f)$と書きます．
先ほどの命題から，$f$が既約であることと，上述の連立線形方程式が非自明解を持たないことが同値となります．ゆえに，$f$の可約性は$R(f)$がランク落ちするかどうかで分かります．さらに嬉しいこととして，$f$が可約であるとき，$f$の既約因子の個数までRuppert行列から分かります．
$f=f_1\cdots f_r$を$f$の因数分解とする．このとき，$\ker R(f)=r-1$となる．
さらにさらに，kernelの基底から$f$の因数分解まで計算できてしまうのですが，結構ややこしいので本記事ではここまでとしておきます．気になったら参考文献appmulfacを見てください．
近似因数分解
因数分解とRuppert行列の関係について見ていきました．入力に誤差が含まれる場合を考えましょう．このとき，誤差によりRuppert行列のランクが上がる（=kernelの次元が下がる）ことで，既約因子の個数が減少し，たいてい既約となってしまいます．本来の因数分解の形が知りたいので，近似GCD同様，近似因数分解を定義しましょう．
$f\in \mathbb{C}[x,y],\varepsilon \geq 0$に対し，以下を満たす$\tilde{f}$の分解を$f$の許容度$\varepsilon$の近似因数分解という．
$\exists f_1,\ldots,f_r,\Delta_f\in \mathbb{C}[x,y], $
$\tilde{f}=f+\Delta_f=f_1\cdots f_r, \quad \|\Delta_f\|_2<\varepsilon \|f\|_2$.
他にも，許容度を指定せず，$\|\Delta_f\|_2$を最小化する，という定義の仕方もあります．
近似因数分解の計算アルゴリズムには，近似GCDを求めるパートがあります．近似因数分解は近似GCDの応用先の一つというわけです．また，近似因数分解自体も他の近似⚪︎⚪︎の計算アルゴリズムに利用されています．どこで使われるか分からないので，できるだけ近似⚪︎⚪︎の定式化やアルゴリズムの整備はしておくべきなんでしょうね．
グレブナー基底とMacaulay行列
次に，グレブナー基底について考えましょう．Buchbergerアルゴリズムはそのままだと遅いので，高速化のために不必要ペアの除去やペアの選択戦略等，様々な工夫が考えられてきました．そのうちの一つとして，S多項式の簡約を掃き出し法を用いて一括で実行する手法が知られているので，それを紹介します（ここにも構造化行列が現れます）．
まず，S多項式と簡約化について振り返っておきます．$f_1,f_2\in K[x_1,\ldots,x_n]$のS多項式は以下の形でかけるのでした．
$S(f_1,f_2)=m_1f_1-m_2f_2,\quad m_i=\frac{LCM(LT(f_1), LT(f_2))}{LM(f_i)}.$
$m_1f_1$と$m_2f_2$の差の形になっていますね．すぐ分かることですが，$F=\{f_1,\ldots,f_m\}$に対し，Buchbergerアルゴリズムを適用した際に現れるS多項式は，$t$を単項式として，$tf_i$の形の多項式の線型結合で書けます．また，$f$の項$t$の$g$による単項簡約は，$f-t/LT(g)g$と，項と多項式の積による引き算の形で書けます．以上からわかることは，十分な数の単項式集合$T$があれば，$\{tf_i\mid t\in T,i=1,\cdots,m\}$によってBuchbergerアルゴリズムにおけるS多項式や簡約化を表現することができるということです．
さらに，$\{tf_i\mid t\in T,i=1,\cdots,m\}$に現れる単項式と，適当な単項式順序を用いて，$tf_i$とその係数ベクトルを同一視することができます．これらの係数ベクトルを積み上げた行列をMacaulay行列と呼び，$M_T(F)$と表します．
$F=\{f_1=x^2-y,f_2=xy-2\}$とする．$T=\{x,y,1\}$とすると，$\{xf_1,yf_1,f_1,xf_2,yf_2,f_2\}$に現れる単項式は$\{x^3,x^2y,xy^2,x^2,xy,y^2,x,y,1\}$となり，$M_T(F)$は以下の通りになる．
$M_T(F)=\begin{pmatrix}
1 & 0&0&0&-1&0&0&0&0\\
0&1&0&0&0&-1&0&0&0\\
0&0&0&1&0&0&0&-1&0\\
0&1&0&0&0&0&-2&0&0\\
0&0&1&0&0&0&0&-2&0\\
0&0&0&0&1&0&0&0&-2
\end{pmatrix}.$
例えば，一行目は$xf_1$の係数ベクトルに対応する．
- 通常は$\{tf_i\mid t\in T,i=1,\cdots,m\}$の部分集合（次数制限付き等）に対応するものをMacaulay行列とするが，今回はさぼって上のように定める．
- Buchbergerアルゴリズムをシミュレートするのに十分な大きさの単項式集合を前もって知ることは難しい．素朴なやり方として，考慮する単項式の最大次数を順次大きくしていく方法がある．
Macaulay行列の作り方から，S多項式の計算や簡約化は(計算に必要な行があれば)行基本変形でできます．
$F$は例3の通りとする．$f_3=S(f_1,f_2)=yf_1-xf_2=-y^2+2x$の係数ベクトルは$M_T(F)$の第二行から第四行を引くことで求められる．
それでは，十分な大きさのMacaulay行列に掃き出し法をしたら，何が得られるでしょうか？その答えが以下のlemmaです．
$\overline{M_T(F)}$を$M_T(F)$の行階段形とする．$T$が十分大きければ，$\overline{M_T(F)}$の各行に対応する多項式からなる集合$G=\{g_1,\ldots,g_l\}$は$I=\langle F\rangle$のグレブナー基底となる．
行簡約の過程でBuchbergerアルゴリズムをシミュレートしている部分があるので，まあそうなるわな，という感じです．$G$は冗長な表現になっているので，簡約化するとよいでしょう．
近似グレブナー基底
入力に誤差がある場合，誤差の影響で本来は行簡約で零行となるものが非零行となり，ランクが上がります．また，誤差なしの場合は$G$に$0$が追加されるだけで影響のなかったものが，ゼロでない多項式が追加され，グレブナー基底が本来のものと大きく変わる（簡約グレブナー基底が$\{1\}$になる）ことがあります．
本来あったであろうグレブナー基底のことが知りたいですよね．近似GCD，近似因数分解同様，近似グレブナー基底を定義したいです．近似グレブナー基底にもいくつか定義の仕方があり，この記事に最も合うのは構造化グレブナー基底による定義ですが，定義のために色々記号を導入する必要があります．主題ではないので，条件の詳細は書かず，お気持ちを書いておきます．詳細は参考文献appGBを見てください．
$G$が以下の条件を満たす時，$F$の許容度$\varepsilon\in \mathbb{R}_{\geq 0},$ランク落ち$d\in \mathbb{Z}_{\geq 0},$単項式集合$T$に関する$\mathfrak{S}$-構造化グレブナー基底という．
- $G$は$F_{st}=\{f_{st,1},\ldots,f_{st,k}\}$の生成するイデアルのグレブナー基底.
（お気持ち：$G$は$F$をズラした多項式系の生成するイデアルのグレブナー基底になってるよ） - $F,F_{st}$はともに$\mathfrak{S}$-多項式系.
（お気持ち：Macaulay行列のサイズが合うように，$F,F_{st}$に出てくる単項式は同じとするよ） - $\|(\vec{p_1},\ldots,\vec{p_k})-(\vec{{p_{st}}}_1,\ldots,\vec{{p_{st}}}_k)\|=\varepsilon$.
（お気持ち：$F,F_{st}$はちょっとだけしかズレてないよ） - $T$は$F,F_{st}$のグレブナー基底を求めるのに十分な大きさの単項式集合.
（お気持ち：Macaulay行列はBuchbergerアルゴリズムをシミュレートできる大きさだよ） - $\rank (M_T(F_{st}))=\rank(M_T(F))-d$.
（お気持ち：$F$に含まれた誤差で上がったランクを，指定した分だけ落とすことができているよ）
最適な$\varepsilon$や$d$ってどう決める？という疑問が出るかと思いますが，これは難しい問題となります．
私は特異値からざっくり決める方法しか知りません．
構造化行列を用いた誤差の除去
さて，これまで三つの問題と，それらに関係する構造化行列を紹介してきました．分かったことは，代数的に特異な状況では構造化行列のランクが落ちていること，入力に誤差がある場合ランクが上がることで，特異な性質が埋もれるということです．そのため，構造化行列を低ランクの近接行列で近似することが，誤差を除去することに繋がる気がします．低ランク近似に関する有名な定理として，Ecart-Youngの定理が知られています．
A$\in \mathbb{C}^{m\times n},\rank A=r$とし，$U\Sigma V^\ast=\sum_{i=1}^r \sigma_i u_iv_i^\ast,\sigma_1\geq \sigma_2\geq\cdots\geq \sigma_r$をAの特異値分解とする．$k< r$として，$A_k=\sum_{i=1}^k \sigma_i u_i v_i^\ast$とすると，ランク$k$の行列$B$に対し，$\|A-A_k\|_2\leq\|A-B\|_2$，すなわち，$ A_k$は$A$のランク$k$の行列における最良近似となる．
素朴なアイデアとして，構造化行列の特異値分解から，低ランク近似を求めればよさそうです．しかし，これはうまくいきません．何故でしょうか？
構造のことをまったく考慮していないからです．つまり，低ランク近似行列が元の行列と同じ構造を持つ保証が何もありません．例えば近似GCDの場合，入力のSylvester行列の低ランク近似行列でありつつ，何らかの多項式の組のSylvester行列にもなっている行列を探す必要があります．このように，構造を保ったまま低ランク近似を考える問題をStructured Low-Rank Approximation(SLRA)といいます．
$S$を$\mathbb{C}^{m\times n}$のAffine部分空間，$K_r\subset \mathbb{C}^{m\times n}$をランクが$r< \min\{m,n\}$の行列全体とする．このとき，$M\in S$に対し，$\|M-M^\ast\|_F$を最小とする$M^\ast\in S \cap K_r$を求めよ．
SLRAを解くアルゴリズムはいくつか提案されており，例えばSLRAがあります（雑な説明をすると，低ランク近似行列をAffine構造にいい感じに射影し，その射影をまた低ランク近似...を繰り返す）．今回紹介した問題は，SLRA＋αの処理でアルゴリズムを設計することができます（+αの処理の方が複雑であることもよくありますが...）．
おわりに
SNCの三つの問題と構造化行列の関係，関連する話題としてSLRAという問題について紹介しました．GCD，因数分解，グレブナー基底と異なる問題を扱っているのに，共通して構造化行列が関わっているというのが面白いです．他の問題にも同じように構造化行列が隠れており，これを見つけることが新たなアルゴリズムの設計に繋がると考えています．
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
