Линейное уравнение над кольцом - Linear equation over a ring - Wikipedia

В алгебра, линейные уравнения и системы линейных уравнений через поле широко изучаются. «Над полем» означает, что коэффициенты уравнений и искомые решения принадлежат заданной области, обычно настоящий или сложные числа. Эта статья посвящена тем же проблемам, в которых «поле» заменено на «коммутативное кольцо "или, как правило,"Нётерян область целостности ".

В случае одного уравнения задача разбивается на две части. Во-первых, проблема идеального членства, состоящий из неоднородного уравнения

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

с ${\displaystyle a_{1},\ldots ,a_{k}}$ и б в данном кольце р, чтобы решить, есть ли у него решение с ${\displaystyle x_{1},\ldots ,x_{k}}$ в р, и, если есть, предоставить его. Это составляет решение, если б принадлежит идеалу, порожденному а_я. Самый простой пример этой проблемы - для k = 1 и б = 1, чтобы решить, если а единица в р.

В проблема сизигии состоит, учитывая k элементы ${\displaystyle a_{1},\ldots ,a_{k}}$ в р, чтобы обеспечить систему генераторов модуль из сизигии из ${\displaystyle (a_{1},\ldots ,a_{k}),}$ это система генераторов подмодуль этих элементов ${\displaystyle (x_{1},\ldots ,x_{k})}$ в р^k которые являются решением однородного уравнения

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

Самый простой случай, когда k = 1 составляет систему генераторов аннигилятор из а₁.

Если дано решение идеальной проблемы принадлежности, все решения получаются добавлением к нему элементов модуля сизигий. Другими словами, все решения обеспечиваются решением этих двух частичных проблем.

В случае нескольких уравнений происходит одинаковое разбиение на подзадачи. Первой проблемой становится проблема членства в подмодуле. Второй еще называют проблема сизигии.

Кольцо, в котором есть алгоритмы для арифметических операций (сложение, вычитание, умножение) и для вышеуказанных задач, можно назвать вычислимое кольцо, или же эффективное кольцо. Можно также сказать, что линейная алгебра на кольце эффективный.

В статье рассматриваются основные кольца, для которых линейная алгебра эффективна.

Общие

Чтобы иметь возможность решить проблему сизигий, необходимо, чтобы модуль сизигий был конечно порожден, потому что невозможно вывести бесконечный список. Поэтому рассмотренные здесь проблемы имеют смысл только для Нётерские кольца, или хотя бы связное кольцо. Фактически, эта статья ограничена Нётерианом. целостные области из-за следующего результата.^[1]

Для нётеровой области целостности, если есть алгоритмы чтобы решить проблему идеальной принадлежности и проблему сизигий для одного уравнения, то из них можно вывести алгоритмы для аналогичных задач, касающихся систем уравнений.

Эта теорема полезна для доказательства существования алгоритмов. Однако на практике алгоритмы для систем разрабатываются напрямую, как это делается для систем линейных уравнений над полем.

Свойства эффективных колец

Позволять р - эффективное коммутативное кольцо.

• Существует алгоритм проверки наличия элемента а это делитель нуля: это составляет решение линейного уравнения топор = 0.
• Существует алгоритм проверки наличия элемента а это единица измерения, и если это так, вычисление обратного: это составляет решение линейного уравнения топор = 1.
• Учитывая идеал я создано а₁, ..., а_k, существует алгоритм проверки наличия двух элементов р иметь такое же изображение в р/я, а линейная алгебра эффективна над р/я: проверка равенства изображений а и б составляет решение уравнения а = б + а₁z₁ + ⋅⋅⋅ + а_kz_k; для решения линейной системы над р/я, достаточно его переписать р и добавить к одной стороне яое уравнение а₁z_я,1 + ⋅⋅⋅ + а_kz_я,k (за я = 1, ...), где z_я,j новые неизвестные.

Линейные уравнения над целыми числами или область главных идеалов

Есть алгоритмы для решения всех проблем, рассматриваемых в этой статье, над целыми числами. Другими словами, линейная алгебра эффективна над целыми числами. Видеть Линейная диофантова система для подробностей.

То же решение применимо к тем же проблемам над главная идеальная область, со следующими изменениями.

Понятие унимодулярная матрица целых чисел должны быть расширены путем вызова унимодулярный матрица над область целостности чей детерминант это единица измерения. Это означает, что определитель обратимый и следует, что унимодулярные матрицы являются обратимые матрицы такие все записи обратная матрица принадлежат домену.

Очевидно, что для алгоритмического решения линейных систем требуется решение одного линейного уравнения с двумя неизвестными. В случае целых чисел такое решение дается расширенный алгоритм Евклида. Таким образом, необходимо, чтобы для рассматриваемой области главных идеалов существовал алгоритм со спецификацией, аналогичной расширенному алгоритму Евклида. То есть, учитывая а и б в области главных идеалов существует алгоритм, вычисляющий унимодулярную матрицу

${\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}}.}$

Имея такой алгоритм, Нормальная форма Смита матрицы можно вычислить точно так же, как в целочисленном случае, и этого достаточно, чтобы применить метод Линейная диофантова система.

Основной случай, когда это обычно используется, - это случай линейных систем над кольцом одномерные многочлены над полем. В этом случае можно использовать расширенный алгоритм Евклида. Видеть полиномиальный наибольший общий делитель # тождество Безу и расширенный алгоритм НОД для подробностей.

Рекомендации

1. Ричман, Фред (1974). «Конструктивные аспекты нётеровых колец». Proc. Амер. Математика. Soc. 44 (2): 436–441. Дои:10.1090 / с0002-9939-1974-0416874-9.

• Герман, Грете (1926), "Die Frage der endlich vielen Schritte in der Theorie der Polynomideale", Mathematische Annalen, 95: 736–788, Дои:10.1007 / BF01206635, S2CID  115897210. Английский перевод в Коммуникациях в компьютерной алгебре 32/3 (1998): 8–30.
• Дэвид А. Кокс; Джон Литтл; Донал О'Ши (1997). Идеалы, разновидности и алгоритмы (второе изд.). Springer-Verlag. ISBN  0-387-94680-2. Zbl  0861.13012.
• Ашенбреннер, Матиас (2004). «Идеальная принадлежность к кольцам многочленов над целыми числами» (PDF). J. Amer. Математика. Soc. AMS. 17 (2): 407–441. Дои:10.1090 / S0894-0347-04-00451-5. S2CID  8176473. Получено 23 октября 2013.