Линейное уравнение по кольцу

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

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

$a\; 1\; x\; 1\; +\; \cdots \; +\; akxk\; =\; b\; \{\backslash \; displaystyle\; a\_\; \{1\}\; x\_\; \{1\}\; +\; \backslash \; cdots\; +\; a\_\; \{k\}\; x\_\; \{k\}\; =\; b\}$

с $a\; 1,\dots ,\; ak\; \{\backslash \; displaystyle\; a\_\; \{1\},\; \backslash \; ldots,\; a\_\; \{k\}\}$и b в заданном кольцо R, чтобы решить, есть ли у него решение с $x\; 1,\dots ,\; xk\; \{\backslash \; displaystyle\; x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{k\}\}$в R, и, если есть, предоставить один. Это позволяет решить, принадлежит ли b идеалу, порожденному a i. Самый простой пример этой проблемы - для k = 1 и b = 1 решить, является ли a единицей в R.

Задача сизигии состоит из заданных k элементов $a\; 1,\dots ,\; ak\; \{\backslash \; displaystyle\; a\_\; \{1\},\; \backslash \; ldots,\; a\_\; \{k\}\}$в R, чтобы обеспечить систему генераторов модуля из сизигии из $(a\; 1,\dots ,\; ak),\; \{\backslash \; displaystyle\; (a\_\; \{1\},\; \backslash \; ldots,\; a\_\; \{k\}),\}$то есть система генераторов подмодуль из тех элементов $(x\; 1,\dots ,\; xk)\; \{\backslash \; displaystyle\; (x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{k\})\}$в R, которые решение однородного уравнения

$a\; 1\; x\; 1\; +\; \cdots \; +\; akxk\; =\; 0.\; \{\backslash \; displaystyle\; a\_\; \{1\}\; x\_\; \{1\}\; +\; \backslash \; cdots\; +\; a\_\; \{k\}\; x\_\; \{k\}\; =\; 0.\}$

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

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

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

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

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

• 1 Общие положения
  • 1.1 Свойства эффективных колец
• 2 Линейные уравнения над целыми числами или область главного идеала
• 3 Ссылки

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

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

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

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

Пусть R - эффективное коммутативное кольцо.

• Существует алгоритм проверки того, является ли элемент a делителем нуля : это позволяет решить линейное уравнение ax = 0.
• Существует алгоритм проверки того, является ли элемент a - это unit, и если это так, вычисление обратного: это составляет решение линейного уравнения ax = 1.
• Учитывая идеал I, порожденный 1,..., a k, существует алгоритм проверки того, имеют ли два элемента R одно и то же изображение в R / I, и линейная алгебра эффективна над R / I: проверка равенства изображения a и b составляют решение уравнения a = b + a 1z1+ ⋅⋅⋅ + a kzk; для решения линейной системы над R / I достаточно записать ее над R и добавить к одной части i-го уравнения a 1zi, 1 + ⋅⋅⋅ + a kzi, k (для i = 1,...), где z i, j - новые неизвестные.

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

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

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

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

$[stuv]\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{bmatrix\}\; s\; t\; \backslash \backslash \; u\; v\; \backslash \; end\; \{bmatrix\}\}\}$

такое, что

$[stuv]\; [ab]\; =\; [gcd\; (a,\; b)\; 0].\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{bmatrix\}\; s\; t\; \backslash \backslash \; u\; v\; \backslash \; end\; \{bmatrix\}\}\; \{\backslash \; begin\; \{bmatrix\}\; a\; \backslash \backslash \; b\; \backslash \; end\; \{bmatrix\}\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; \backslash \; gcd\; (a,\; b)\; \backslash \; \backslash \; 0\; \backslash \; end\; \{bmatrix\}\}.\}$

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

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

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