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

$a_1{x}_1+\cdots +a_k{x}_k=b$

dengan $a_1,\dots ,a_k$ dan Templat:Math di cincin tertentu Templat:Math, untuk memutuskan apakah ada solusi dengan $x_1,\dots ,x_k$ pada Templat:Math, dan, jika ada, untuk menyediakannya. Jumlah ini untuk memutuskan apakah Templat:Math milik ideal yang dihasilkan oleh Templat:Math. Contoh paling sederhana dari masalah ini adalah, untuk k = 1 dan Templat:Math, untuk memutuskan apakah Templat:Math adalah satuan dalam Templat:Math.

Masalah syzygy terdiri, diberi elemen k $a_1,\dots ,a_k$ di Templat:Math, untuk menyediakan sistem generator dari modul dari syzygies dari $(a_1,\dots ,a_k),$ itu adalah sistem generator submodul dari elemen tersebut $(x_1,\dots ,x_k)$ in Templat:Math^k itu adalah solusi dari persamaan homogen

$a_1{x}_1+\cdots +a_k{x}_k=0.$

Kasus paling sederhana, ketika k = 1 sama dengan mencari sistem generator dari annihilator dari Templat:Math.

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

$\left[\begin{array}{cc}s& t\\ u& v\end{array}\right]$

such that

$\left[\begin{array}{cc}s& t\\ u& v\end{array}\right]\left[\begin{array}{c}a\\ b\end{array}\right]=\left[\begin{array}{c}\gcd (a,b)\\ 0\end{array}\right].$

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.