リング上の線形方程式

代数学では、体上の線形方程式および線形方程式系が広く研究されています。「体上」とは、方程式の係数および求められる解が、一般的には実数または複素数である特定の体に属することを意味します。本稿では、「体」を「可換環」または「典型的にはネーター整域」に置き換えた、同様の問題を取り上げます。

単一の方程式の場合、問題は2つの部分に分かれます。まず、非同次方程式が与えられた場合の理想的なメンバーシップ問題です。

${\displaystyle a_{1}x_{1}+\cdots +a_{k}x_{k}=b}$

と${\displaystyle a_{1},\ldots ,a_{k}}$与えられた環Rのbに対して、解が存在するかどうかを判定する${\displaystyle x_{1},\ldots ,x_{k}}$Rにおいて、そしてもしあれば、それを提供する。これは、b がa _iによって生成されるイデアルに属するかどうかを判定することに等しい。この問題の最も単純な例は、k = 1およびb = 1の場合、 a がRの単位であるかどうかを判定することである。

シジジー問題は、k個の要素が与えられたときに成り立つ。${\displaystyle a_{1},\ldots ,a_{k}}$Rにおいて、シジジーのモジュールの生成器のシステムを提供する${\displaystyle (a_{1},\ldots ,a_{k}),}$それは、それらの要素のサブモジュールの生成器のシステムである。${\displaystyle (x_{1},\ldots ,x_{k})}$R ^kにおいて同次方程式の解である

${\displaystyle a_{1}x_{1}+\cdots +a_{k}x_{k}=0.}$

最も単純なケースであるk = 1の場合、 1の消滅器の生成器のシステムを見つけることに相当し_ます。

理想メンバーシップ問題の解が与えられた場合、それにシジジーモジュールの要素を加えることで、すべての解が得られる。言い換えれば、すべての解はこれら2つの部分問題の解によって得られる。

複数の方程式の場合、同様に部分問題への分解が行われます。最初の問題は部分モジュールメンバーシップ問題となり、2番目の問題はシジジー問題とも呼ばれます。

算術演算（加算、減算、乗算）および上記の問題に対するアルゴリズムが存在するような環は、計算可能環、または有効環と呼ばれる。また、その環上の線形代数は有効であるとも言える。

この記事では、線形代数が有効な主要な環について考察する。

シジジー問題を解決するためには、無限リストを出力することは不可能であるため、シジジーのモジュールが有限生成である必要があります。したがって、ここで検討する問題は、ネーター環、または少なくともコヒーレント環に対してのみ意味を持ちます。実際、この記事は次の結果によりネーター整域に限定されます。 ^{[ 1 ]}

ネーター積分領域が与えられたとき、単一の方程式に対する理想メンバーシップ問題とシジジー問題を解くアルゴリズムが存在するならば、それらのアルゴリズムから、方程式系に関する同様の問題に対するアルゴリズムを導き出すことができる。

この定理はアルゴリズムの存在を証明するのに役立つ。しかし実際には、システムのアルゴリズムは直接設計される。

加算、減算、乗算、および乗法逆元の計算のためのアルゴリズムが確立されると、体は有効環となる。実際、部分加群メンバーシップ問題を解くことは、一般に連立方程式を解くことと呼ばれ、シジジー問題を解くことは、連立一次方程式の行列の零空間を計算することである。これらの問題に対する基本的なアルゴリズムは、ガウス消去法である。

この記事で取り上げたすべての問題は、整数上で解くためのアルゴリズムが存在します。言い換えれば、線形代数は整数上で有効です。詳細は「線形ディオファントス体系」を参照してください。

より一般的には、加算、減算、乗算のアルゴリズムが存在する場合、線形代数は主イデアル領域で有効であり、

• ax = bの形の方程式を解く、つまりaがbの約数であるかどうかをテストし、そうであれば商a / bを計算する。
• ベズーの恒等式を計算する、つまり、aとbが与えられたとき、as + btがaとbの最大公約数となるようなsとtを計算する。

ユニモジュラー行列の概念を一般の場合に拡張し、行列式 が単位行列である正方行列をユニモジュラー行列と呼ぶことは有用である。これは、行列式が可逆であることを意味し、ユニモジュラー行列は、逆行列のすべての要素が定義域に属するような可逆行列と正確に一致することを意味する。

上記の2つのアルゴリズムは、主理想領域内のaとbが与えられた場合、ユニモジュラー行列を計算するアルゴリズムが存在することを示唆している。

${\displaystyle {\begin{bmatrix}s&t\\u&v\end{bmatrix}}}$

そのため

${\displaystyle {\begin{bmatrix}s&t\\u&v\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}={\begin{bmatrix}\gcd(a,b)\\0\end{bmatrix}}.}$

（このアルゴリズムは、sとtにベズーの恒等式の係数を、uとvに−bとaをas + btで割った商を用いることで得られます。この選択は、正方行列の行列式が1であることを意味します。）

このようなアルゴリズムがあれば、行列のスミス標準形を整数の場合と全く同じように計算でき、これによって線形ディオファントス系で説明した方法を適用して、あらゆる線形システムを解くためのアルゴリズムを得ることができます。

この手法が一般的に用いられる主なケースは、体上の単変数多項式環上の線形システムの場合です。この場合、上記のユニモジュラー行列を計算するために拡張ユークリッドアルゴリズムを使用できます。詳細は、「多項式の最大公約数 § ベズーの恒等式と拡張最大公約数アルゴリズム」を参照してください。

線形代数は多項式環上で有効である${\displaystyle k[x_{1},\ldots ,x_{n}]}$体k上で。これは 1926 年にGrete Hermannによって初めて証明されました。^{[ 2 ]} Hermann の結果から得られるアルゴリズムは、計算複雑度が高すぎて効果的なコンピュータ計算ができないため、歴史的な興味の対象にとどまります。

線形代数が多項式環上で有効であることの証明とコンピュータによる実装は、現在すべてグロブナー基底理論に基づいている。

• コックス、デイビッド A. ;リトル、ジョン;オシェア、ドナル(1997).理想、多様性、アルゴリズム(第 2 版).シュプリンガー・フェルラーク. ISBN 0-387-94680-2. Zbl 0861.13012 . 
• Aschenbrenner, Matthias (2004). "整数上の多項式環におけるイデアルメンバーシップ" (PDF) . J. Amer. Math. Soc . 17 (2). AMS: 407– 441. doi : 10.1090/S0894-0347-04-00451-5 . S2CID 8176473 . 2013年10月23日取得.