Persamaan linear gelanggang

Dalam aljabar, persamaan linear dan sistem persamaan linier lebih dari satu bidang dipelajari secara luas. "Di atas bidang "berarti bahwa koefisien persamaan dan solusi yang dicari termasuk dalam bidang tertentu, biasanya nyata atau bilangan kompleks s. Artikel ini dikhususkan untuk masalah yang sama di mana "bidang" diganti dengan "gelanggang komutatif", atau, biasanya "Noetherian domain integral".

Dalam kasus persamaan tunggal, masalahnya terbagi menjadi dua bagian. Pertama, masalah keanggotaan ideal, yang terdiri dari persamaan yang tidak homogen

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

dengan ${\displaystyle a_{1},\ldots ,a_{k}}$ dan b di cincin tertentu R , untuk memutuskan apakah ada solusi dengan ${\displaystyle x_{1},\ldots ,x_{k}}$ pada R, dan, jika ada, untuk menyediakannya. Jumlah ini untuk memutuskan apakah b milik ideal yang dihasilkan oleh a_i. Contoh paling sederhana dari masalah ini adalah, untuk k = 1 dan b = 1, untuk memutuskan apakah a adalah satuan dalam R.

Masalah syzygy terdiri, diberi elemen k ${\displaystyle a_{1},\ldots ,a_{k}}$ di R , untuk menyediakan sistem generator dari modul dari syzygies dari ${\displaystyle (a_{1},\ldots ,a_{k}),}$ itu adalah sistem generator submodul dari elemen tersebut ${\displaystyle (x_{1},\ldots ,x_{k})}$ in R^k itu adalah solusi dari persamaan homogen

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

Kasus paling sederhana, ketika k = 1 sama dengan mencari sistem generator dari annihilator dari a₁.

Diberikan solusi dari masalah keanggotaan yang ideal, seseorang memperoleh semua solusi dengan menambahkan elemen modul syzygies ke dalamnya. Dengan kata lain, semua solusi disediakan oleh solusi.

Persamaan linear di atas bilangan bulat atau domain ideal utama

Ada algoritma untuk menyelesaikan semua masalah yang dibahas dalam artikel ini melalui bilangan bulat. Dengan kata lain, aljabar linier efektif di atas bilangan bulat . Lihat Sistem Diofantin Linear untuk detailnya.

Solusi yang sama berlaku untuk masalah yang sama di domain ideal utama, dengan modifikasi berikut.

Gagasan matriks unimodular bilangan bulat harus diperpanjang dengan memanggil unimodular sebagai matriks di atas domain integral yang determinan adalah unit. Ini berarti bahwa determinannya adalah dapat dibalik dan menyiratkan bahwa matriks unimodular adalah matriks yang invers sehingga semua entri dari matriks invers termasuk dalam domain tersebut.

Untuk mendapatkan solusi algoritmik dari sistem linier, solusi untuk persamaan linier tunggal dalam dua variabel yang tidak diketahui jelas diperlukan. Dalam kasus bilangan bulat, solusi seperti itu disediakan oleh algoritma Euklides diperpanjang. Jadi seseorang membutuhkan itu, untuk domain ideal utama yang dianggap, ada algoritme dengan spesifikasi yang serupa dengan algoritme Euclidean yang diperluas. Itu adalah, diberikan a dan b dalam domain ideal utama, ada algoritma yang menghitung matriks unimodular

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

such that

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

Memiliki algoritme seperti itu, bentuk normal Smith dari matriks dapat dihitung persis seperti dalam kasus integer, dan ini cukup untuk menerapkan metode Sistem Diofantin Linear.

Kasus utama di mana ini biasanya digunakan adalah kasus sistem linier di atas gelanggang polinomial univariat di atas suatu medan. Dalam kasus ini, algoritma Euclidean yang diperluas dapat digunakan. Lihat identitas pembagi umum terbesar polinomial#Bézout dan algoritme GCD tambahan untuk detailnya.