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

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

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

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

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

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

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

Простейший случай, когда $k = 1,$ поиск системы образующих аннулятора a $составляет 1$ .

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

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

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

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

Общие сведения [ править ]

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

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

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

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

Свойства эффективных колец [ править ]

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

Существует алгоритм проверки того, $ли элемент a$ является делителем нуля : это равносильно решению линейного уравнения $ax = 0$ .
Существует алгоритм проверки того, $ли элемент a$ является единицей , и если да, то вычисления его обратного значения: это равносильно решению линейного уравнения $ax = 1$ .
Учитывая идеал I, , ... _{порожденный 1} , a _k ,
- существует алгоритм проверки того, имеют ли два элемента $R$ одинаковый образ в $R / I$ : проверка равенства образов $a$ и $b$ сводится к решению уравнения $a = b + a 1 z 1 + \dots + a k z k$ ;
- линейная алгебра эффективна над $R / I$ : для решения линейной системы над $R / I$ достаточно записать ее над $R$ и добавить к одной части $i$ -го уравнения $a 1 z i,1 + \dots + a k z i, k$ (для $i = 1, ...$ ), где $z i, j$ — новые неизвестные.
Линейная алгебра эффективна на кольце многочленов $R[x_{1},\ldots ,x_{n}]$ тогда и только тогда, когда у вас есть алгоритм, который вычисляет верхнюю границу степени многочленов , которые могут возникнуть при решении линейных систем уравнений: если у вас есть алгоритмы решения, их выходные данные дают степени. И наоборот , если известна верхняя граница степеней, встречающихся в решении, можно записать неизвестные многочлены как многочлены с неизвестными коэффициентами. Тогда, поскольку два многочлена равны тогда и только тогда, когда их коэффициенты равны, уравнения задачи становятся линейными уравнениями относительно коэффициентов, которые можно решить над эффективным кольцом.

Над целыми числами или областью главного идеала [ править ]

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

В более общем смысле, линейная алгебра эффективна в области главных идеалов, если существуют алгоритмы сложения, вычитания и умножения, а также

Решение уравнений вида $ax = b$ , то есть проверка того, является ли $и$ , , если $a делителем b$ это так, вычисление частного $a / b$ ,
Вычисление тождества Безу , то есть по заданным $a$ и $b$ , вычисление $s$ и $t$ таких, что $+ bt является$ наибольшим общим делителем a $и$ as $b$ .

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

Из двух вышеуказанных алгоритмов следует, что для данных $a$ и $b$ в области главных идеалов существует алгоритм вычисления унимодулярной матрицы.

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

такой, что

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

(Этот алгоритм получается путем взятия в качестве $s$ и $t$ коэффициентов тождества Безу, а для $u$ и $v$ фактора $- b$ и $a$ на $as + bt$ ; этот выбор подразумевает, что определитель квадратной матрицы равен $1.$ )

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

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

Над полиномами кольца над полем [ править ]

Линейная алгебра эффективна на кольце полиномов. $k[x_{1},\ldots ,x_{n}]$ над полем $k$ . Впервые это было доказано в 1926 году Гретой Германн . ^[2] Алгоритмы, полученные на основе результатов Германа, представляют лишь исторический интерес, поскольку их вычислительная сложность слишком высока для обеспечения эффективных компьютерных вычислений.

Доказательства эффективности линейной алгебры на кольцах полиномов и компьютерные реализации в настоящее время основаны на теории базиса Грёбнера .

Ссылки [ править ]

^ Ричман, Фред (1974). «Конструктивные аспекты нётеровых колец» . Учеб. амер. Математика. Соц . 44 (2): 436–441. дои : 10.1090/s0002-9939-1974-0416874-9 .
^ Германн, Грета (1926). «Вопрос о конечном числе шагов в теории полиномиальных идеалов». Математические летописи . 95 :736-788. дои : 10.1007/BF01206635 . S2CID 115897210 . . Английский перевод в журнале Communications in Computer Algebra 32/3 (1998): 8–30.

Внешние ссылки [ править ]

Дэвид А. Кокс; Джон Литтл; Донал О'Ши (1997). Идеалы, разновидности и алгоритмы (второе изд.). Спрингер-Верлаг . ISBN 0-387-94680-2 . Збл 0861.13012 .
Ашенбреннер, Матиас (2004). «Идеальное членство в кольцах полиномов над целыми числами» (PDF) . Дж. Амер. Математика. Соц . 17 (2). АМС: 407–441. дои : 10.1090/S0894-0347-04-00451-5 . S2CID 8176473 . Проверено 23 октября 2013 г.

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

[2] Германн, Грета (1926). «Вопрос о конечном числе шагов в теории полиномиальных идеалов». Математические летописи . 95 :736-788. дои : 10.1007/BF01206635 . S2CID 115897210 . . Английский перевод в журнале Communications in Computer Algebra 32/3 (1998): 8–30.

[1]

[2]