Системы сравнений
Системы сравненийСистемы линейных сравнений могут быть решены используя методы линейной алгебры: обращение матриц, правило Крамера, или сокращение ряда. В случае, если модуль простой, все, что вы знаете, от линейной алгебры переходит к системам линейных сравнений. ( причина в том, что поле , для p простое, и линейная алгебра работает нормально над любым полем — не только и .)
Также возможно преобразовать систему в линейную диофантову. уравнение.
Я буду придерживаться простых модулей для простоты. Я предполагаю, что вы знать немного линейной алгебры, даже если вы не видели, как это делается с модульная арифметика.
В первом примере я буду использовать хорошо известный факт, что матрица обратим тогда и только тогда, когда его определитель отличен от нуля.
Пример. Решить
Запишите систему в матричной форме:
Определитель матрицы коэффициентов равен .
В частности, это
ненулевой мод 7, поэтому система имеет решение. Для системы проще всего использовать формулу для
инвертирование матрицы:
Если я применю эту формулу к матрице коэффициентов для системы, я получать
Обратное 3 по модулю 7 равно 5, так как .
Все, что мне нужно сделать, это умножить обе части уравнения на оставил по обратной матрице коэффициентов:
Решение
Вы также можете решить это уравнение, используя правило Крамера, или по строке снижение. Вы даже можете использовать базовую алгебру, хотя это немного скучный. Решите первое уравнение для одной из переменных:
Подставляем это во второе уравнение:
Включение этого обратно в x-уравнение дает .
В некоторых случаях можно преобразовать систему в линейную диофантову. уравнение, которое мы уже умеем решать.
Пример.
Решите следующую систему над:
Обратите внимание, однако, что первое уравнение в 4 раза больше второго:
Так что достаточно решить
Это эквивалентно диофантову уравнению
Позволять . Это дает
Общее решение
z — это просто вспомогательная переменная, поэтому игнорируйте ее. Используя w-уравнение, я имеют
Общее решение
Напомним, что исходной системой был мод 7:
Обратите внимание, что это параметризованное решение. Вы также можете сделать это задача по сокращению строк.
Пример. Решить
Как и прежде, умножение второго уравнения на 4 дает
Но два уравнения теперь подразумевают » «, и это противоречие подразумевает, что система не имеет решений.
Пример. Решить
В такой большой системе лучше использовать сокращение строк.
Решение
Пример. Решить
Я сделаю это путем сокращения строки:
Уравнения
Есть несколько решений — на самом деле, так как есть одно бесплатное переменной (z), будет 5 различных решений по модулю 5. Как и обычно, когда система имеет несколько решений, я напишу решение в параметрической форме.
Поставил . Тогда , так (прибавляя к обеим сторонам). Так же, так. Решение
Как отмечалось выше, линейной алгеброй можно заняться по модулю n. Вот пример.
Пример. Вычисление обратного модуса 3 матрица
Таким образом,
Пример. Является ли следующая матрица обратимой мод 6?
Когда модуль не является простым, результаты линейной алгебры должны быть
используется с осторожностью.
В этом случае я хотел бы использовать определитель, чтобы сказать
обратима ли матрица.
Обычно ненулевой определитель означает, что матрица обратима. Однако по модулю n критерий состоит в том, что определитель должен быть относительно простого относительно n. Так как матрица необратима. Таким образом, для Например, если вы попытаетесь применить стандартный алгоритм обращения матриц к найдите обратное, вы обнаружите, что это не сработает.
Контактная информация
Домашняя страница Брюса Икенаги
Copyright 2019 by Bruce Ikenaga
Линейные уравнения ADS над целыми числами Mod 2
Подраздел 12.6.1 Сокращение ряда, мод 2
Методы, которые мы изучали для решения систем уравнений до этого момента, могут быть применены к системам, в которых вся арифметика выполняется над другими алгебраическими системами, включая целые числа по модулю 2. Случай по модулю 2 станет особенно полезным в нашем более позднем изучении теория кодирования.
{n-m}\) различных решений.
Давайте рассмотрим пример, который сразу преобразуется в матричный вид.
\begin{уравнение*} \begin{array}{r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{} р@{}} x_1 &{}+{} &x_2 & & &{}+{} & x_4 & & & & & &= 1 \\ x_1 & & & {}+{}&x_3 & & &{}+{} & x_5& & &= 0 \\ & & x_2& {}+{}&x_3 & & & & &{}+{}&x_6&= 0 \\ \конец{массив} \end{уравнение*}
Расширенная матрица системы
\begin{уравнение*} \левый( \begin{массив}{cccccc|c} 1 и 1 и 0 и 1 и 0 и 0 и 1 \\ 1 и 0 и 1 и 0 и 1 и 0 и 0 \\ 0 и 1 и 1 и 0 и 0 и 1 и 0 \\ \конец{массив} \правильно) \end{уравнение*}
Ниже приведены шаги по уменьшению строки этой матрицы. Записи, на которых мы «поворачиваемся», выделены жирным шрифтом, чтобы было легче идентифицировать основные переменные.
\begin{уравнение*} \начать{разделить} \левый( \begin{массив}{cccccc|c} 1 и 1 и 0 и 1 и 0 и 0 и 1 \\ 1 и 0 и 1 и 0 и 1 и 0 и 0 \\ 0 и 1 и 1 и 0 и 0 и 1 и 0 \\ \конец{массив} \right) & \overset{\textrm{добавить}R_1\textrm{ к}R_2}{\text{}\longrightarrow}\text{} \левый( \begin{массив}{cccccc|c} \textbf{1} & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 и 1 и 1 и 1 и 1 и 0 и 1 \\ 0 и 1 и 1 и 0 и 0 и 1 и 0 \\ \конец{массив} \правильно)\\ & \text{}\overset{\textrm{добавить}R_2\textrm{ к}R_1}{\text{}\longrightarrow}\text{}\left( \begin{массив}{cccccc|c} \textbf{1} & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & \textbf{1} & 1 & 1 & 1 & 0 & 1 \\ 0 и 1 и 1 и 0 и 0 и 1 и 0 \\ \конец{массив} \правильно) \\ & \overset{\textrm{добавить}R_2\textrm{ к}R_3}{\text{}\longrightarrow}\text{} \левый( \begin{массив}{cccccc|c} \textbf{1} & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 &\textbf{1} & 1 & 1 & 1 & 0 & 1 \\ 0 и 0 и 0 и 1 и 1 и 1 и 1 \\ \конец{массив} \правильно) \конец{разделить} \end{уравнение*}
Обратите внимание, что в этот момент мы не можем выполнить поворот по третьей строке, третьему столбцу, так как эта запись равна нулю.
Поэтому мы переходим к следующему столбцу, делая \(x_4\) основным.
\begin{уравнение*} \начать{разделить} \text{}&\overset{\textrm{добавить}R_3\textrm{ к}R_2}{\text{}\longrightarrow}\text{} \левый( \begin{массив}{cccccc|c} \textbf{1} & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & \textbf{1} & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & \textbf{1} & 1 & 1 & 1 \\ \конец{массив} \правильно) \конец{разделить} \end{уравнение*}
На этом сокращение строк завершено, и теперь мы можем идентифицировать набор решений. Имейте в виду, что, поскольку сложение — это вычитание, термины можно перемещать по обе стороны от знака равенства без изменения знака. Базовыми переменными являются \(x_1\text{,}\) \(x_2\text{,}\) и \(x_4\text{,}\), а остальные три переменные свободны. Общее решение системы равно
. \begin{уравнение*}
\начать{массив}{с}
х_1 = х_3+х_5\\
х_2 = х_3+х_6 \\
х_3 = х_3 \\
х_4 = 1+ х_5+х_6 \\
х_5 = х_5\
х_6 = х_6\
\конец{массив}
\end{уравнение*} 93=8\) решений этой системы. Например, один из них получается установкой \(x_3=1\text{,}\) \(x_5=1\text{,}\) и \(x_6=0\text{,}\), что дает \ ((x_1, x_2, x_3, x_4, x_5, x_6) = (0,1,1,0,1,0)\текст{.
Мы можем проверить сокращение строк с помощью SageMath:
Упражнения 12.6.2 Упражнения
Во всех последующих упражнениях системы уравнений переписаны \(\mathbb{Z}_2\text{,}\), поэтому при их решении следует использовать арифметику по модулю 2.
1.
Решите следующие системы, полностью описав наборы решений:
\(\displaystyle \begin{array}{r@{}r@{}r@{}r@{}r@{}r@{}} x_1 & {}+{} & x_2 & & & = 0 \\ x_1 & & & {}+{} & x_3 & = 0 \\ \конец{массив} \)
\(\displaystyle \begin{array}{r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}} x_1 & {}+{} & x_2 & & & & & & = 0 \\ & & x_2 & {}+{} & x_3& & & = 0\\ & & & & x_3& {}+{} & x_4 & = 1 \\ x_1 & {}+{} & x_2 & {}+{} & x_3& & & = 1 \\ \конец{массив} \)
Ответ.
\(\displaystyle \{(0,0,0),(1,1,1)\}\)
\(\displaystyle \{(1,1,1,0)\}\)
2.
В этом упражнении приведен пример, в котором количество основных переменных меньше количества уравнений.
\(\displaystyle \begin{array}{r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}} x_1 & {}+{} &x_2 & & &{}+{} & x_4 &= 1 \\ x_1 & & & {}+{} &x_3 & {}+{} & x_4 &= 0 \\ & & x_2 & {}+{} &x_3 & & &= 1 \\ \конец{массив}\)
\(\displaystyle \begin{array}{r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}} x_1 & {}+{} &x_2 & & &{}+{} & x_4 &= 1 \\ x_1 & & & {}+{} &x_3 & {}+{} & x_4 &= 0 \\ & & x_2 & {}+{} &x_3 & & &= 0 \\ \конец{массив}\)
Ответ.
Здесь предлагается расширенная матрица с обеими правыми сторонами и сокращением ее строк:
\begin{equation*} \начать{разделить} \левый( \begin{массив}{cccc|cc} 1 и 1 и 0 и 1 и 1 и 1 \\ 1 и 0 и 1 и 1 и 0 и 0 \\ 0 и 1 и 1 и 0 и 1 и 0 \\ \конец{массив} \right) & \text{ }\longrightarrow \text{ } \левый( \begin{массив}{cccc|cc} \textbf{1} & 0 & 1 & 1 & 0 & 0 \\ 0 & \textbf{1} & 1 & 0 & 1 & 0 \\ 0 и 0 и 0 и 0 и 0 и 1 \\ \конец{массив} \правильно)\\ \конец{разделить} \end{уравнение*}
Здесь только две основные переменные, потому что левая часть последнего уравнения является суммой левых частей первых двух уравнений.
Игнорируя последний столбец обеих матриц, мы видим, что последнее уравнение первой системы сводится к \(0=0\text{,}\), что всегда верно, а первые два уравнения дают две свободные переменные , \(x_3\) и \(x_4\text{.}\) Общее решение представляет собой набор четверок \(\{(x_3 +_2 x_4,x_3 +_2 1, x_3, x_4) \mid x_3, x_4 \ in \mathbb{Z}_2 \}\text{.}\) Мощность набора решений равна 4. 9{5}\) при покоординатном сложении по модулю 2.
\begin{уравнение*} \begin{array}{r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}} x_1 & {}+{} &x_2 & & & & & &{}+{} & x_5&= 0 \\ x_1 & & & {}+{} &x_3 & & &{}+{} & x_5&= 0 \\ x_1 & & & {}+{} &x_3 &{}+{} & x_4 & & &= 0 \\ & & x_2 & {}+{} &x_3 &{}+{} & x_4 & & &= 0 \\ \конец{массив} \end{уравнение*}
Опишите набор решений для следующей системы, поскольку он связан с набором решений для системы в предыдущей части этого упражнения.
\begin{уравнение*} \begin{array}{r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}} x_1 & {}+{} &x_2 & & & & & &{}+{} & x_5&= 1 \\ x_1 & & & {}+{} &x_3 & & &{}+{} & x_5&= 0 \\ x_1 & & & {}+{} &x_3 &{}+{} & x_4 & & &= 1 \\ & & x_2 & {}+{} &x_3 &{}+{} & x_4 & & &= 0 \\ \конец{массив} \end{уравнение*} 9{5}\) — конечная группа, множество решений — подгруппа, поскольку оно замкнуто относительно покоординатного сложения по модулю 2.
