Lineární rovnice nad prstencem - Linear equation over a ring - Wikipedia

Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) Tento článek může vyžadovat vyčištění setkat se s Wikipedií standardy kvality. Specifický problém je: Musí splňovat standardy formátu wiki. Prosím pomozte vylepšit tento článek jestli můžeš. (Červen 2015) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek může být pro většinu čtenářů příliš technická na to, aby je pochopili. Prosím pomozte to vylepšit na aby to bylo srozumitelné pro neodborníky, aniž by byly odstraněny technické podrobnosti. (Červen 2015) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v algebra, lineární rovnice a soustavy lineárních rovnic přes pole jsou široce studovány. „Přes pole“ znamená, že koeficienty rovnic a řešení, která hledáme, patří do daného pole, obvykle nemovitý nebo komplexní čísla. Tento článek je věnován stejným problémům, kde je „pole“ nahrazeno „komutativní prsten „nebo obvykle“Noetherian integrální doména ".

V případě jediné rovnice se problém rozdělí na dvě části. Nejprve ideální problém s členstvím, který se skládá z dané nehomogenní rovnice

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

s ${ displaystyle a_ {1}, ldots, a_ {k}}$ a b v daném kruhu R, rozhodnout, zda má řešení s ${ displaystyle x_ {1}, ldots, x_ {k}}$ v R, a pokud existuje, jeden poskytnout. To rozhoduje o tom, zda b patří k ideálu generovanému A_i. Nejjednodušší příklad tohoto problému je pro k = 1 a b = 1, rozhodnout, zda A je jednotka v R.

The syzygy problém sestává, daný k elementy ${ displaystyle a_ {1}, ldots, a_ {k}}$ v R, poskytnout systém generátorů modul z syzygies z ${ displaystyle (a_ {1}, ldots, a_ {k}),}$ to je systém generátorů submodul těchto prvků ${ displaystyle (x_ {1}, ldots, x_ {k})}$ v R^k které jsou řešením homogenní rovnice

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

Nejjednodušší případ, když k = 1 představuje systém generátorů zničit z A₁.

Při řešení ideálního problému členství získá člověk všechna řešení přidáním prvků modulu syzygies. Jinými slovy, všechna řešení poskytuje řešení těchto dvou dílčích problémů.

V případě několika rovnic dochází ke stejnému rozkladu na dílčí problémy. Prvním problémem se stává problém členství v submodulu. Druhý z nich se také nazývá syzygy problém.

Kroužek takový, že existují algoritmy pro aritmetické operace (sčítání, odčítání, násobení) a pro výše uvedené problémy lze nazvat a vypočítatelný prstennebo efektivní prsten. Lze také říci, že lineární algebra na prstenci je efektivní.

Článek se zabývá hlavními kruhy, pro které je účinná lineární algebra.

Obecné informace

Abychom mohli vyřešit problém syzygy, je nutné, aby byl modul syzygies definitivně generován, protože je nemožné vytvořit nekonečný seznam. Proto zde uvažované problémy mají smysl pouze pro Noetherian prsteny, nebo alespoň a koherentní kroužek. Ve skutečnosti je tento článek omezen na noetherian integrální domény z důvodu následujícího výsledku.^[1]

Vzhledem k tomu, že existuje netherianská integrální doména algoritmy k řešení ideálního problému členství a problému syzygies pro jednu rovnici, lze z nich odvodit algoritmy pro podobné problémy týkající se systémů rovnic.

Tato věta je užitečná k prokázání existence algoritmů. V praxi se však algoritmy pro systémy navrhují přímo, jak se to dělá pro systémy lineárních rovnic nad polem.

Vlastnosti efektivních kroužků

Nechat R být efektivním komutativním kruhem.

• Existuje algoritmus pro testování prvku A je nulový dělitel: to znamená řešení lineární rovnice sekera = 0.
• Existuje algoritmus pro testování prvku A je jednotka, a pokud ano, výpočet jeho inverzní funkce: to znamená řešení lineární rovnice sekera = 1.
• Vzhledem k ideálu Já generováno uživatelem A₁, ..., A_k, existuje algoritmus pro testování, zda jsou dva prvky R mít stejný obrázek v R/Jáa lineární algebra je účinná R/Já: testování rovnosti obrázků A a b částky k vyřešení rovnice A = b + A₁z₁ + ⋅⋅⋅ + A_kz_k; pro řešení lineárního systému R/Já, stačí to přepsat R a přidat na jednu stranu ith rovnice A₁z_i,1 + ⋅⋅⋅ + A_kz_i,k (pro i = 1, ...), kde z_i,j jsou nové neznámé.

Lineární rovnice přes celá čísla nebo hlavní ideální doménu

Existují algoritmy k vyřešení všech problémů řešených v tomto článku přes celá čísla. Jinými slovy, lineární algebra je účinná na celá čísla. Vidět Lineární diofantický systém pro detaily.

Stejné řešení platí pro stejné problémy jako a hlavní ideální doména, s následujícími úpravami.

Pojem unimodulární matice celých čísel musí být prodloužena voláním unimodulární matice nad integrální doména jehož určující je jednotka. To znamená, že determinant je invertibilní a znamená, že unimodulární matice jsou invertibilní matice takové všechny položky inverzní matice patří do domény.

Chcete-li mít algoritmické řešení lineárních systémů, je zjevně nutné řešení pro jedinou lineární rovnici ve dvou neznámých. V případě celých čísel takové řešení poskytuje rozšířený euklidovský algoritmus. Proto je třeba, aby pro uvažovanou hlavní ideální doménu existoval algoritmus s podobnou specifikací jako rozšířený euklidovský algoritmus. To je dané A a b v hlavní ideální doméně existuje algoritmus počítající unimodulární matici

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

takhle

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

Mít takový algoritmus, Smith normální forma matice lze vypočítat přesně jako v případě celého čísla, a to stačí k použití metody Lineární diofantický systém.

Hlavním případem, kde se to běžně používá, je případ lineárních systémů přes kruh jednorozměrné polynomy přes pole. V tomto případě lze použít rozšířený euklidovský algoritmus. Vidět polynomiální největší společný dělitel # Bézoutova identita a rozšířený algoritmus GCD pro detaily.

Reference

• Hermann, Grete (1926), „Die Frage der endlich vielen Schritte in der Theorie der Polynomideale“, Mathematische Annalen, 95: 736–788, doi:10.1007 / BF01206635, S2CID  115897210. Anglický překlad v dokumentu Communications in Computer Algebra 32/3 (1998): 8–30.
• David A. Cox; John Little; Donal O'Shea (1997). Ideály, odrůdy a algoritmy (druhé vydání). Springer-Verlag. ISBN  0-387-94680-2. Zbl  0861.13012.
• Aschenbrenner, Matthias (2004). „Ideální členství v polynomiálních kruzích přes celá čísla“ (PDF). J. Amer. Matematika. Soc. AMS. 17 (2): 407–441. doi:10.1090 / S0894-0347-04-00451-5. S2CID  8176473. Citováno 23. října 2013.