<р>2. Имеем, что A(i,j)=B(i,j)+C(i,j) для каждого j =1,2. н. Рассмотрим выражение для det( A ). Каждое слагаемое в этом выражении содержит ровно один множитель из i-й строки A . Рассмотрим один из этих терминов:
Если мы добавим только термины, содержащие B, мы получим определитель B; если мы сложим все термины, содержащие C, мы получим определитель C. Таким образом, det( A )=det( B )+det( C ).
<р>3. Предположим, что
-я строка в A равна j-й строке A , то есть A(i,k)=A(j,k) для каждого k =1,2. н . Рассмотрим произвольное произведение в выражении det( A ):
эти термины равны. Но они встречаются в выражении det( A ) с противоположными знаками (помните, что p ' получается из p одной транспозицией). Таким образом, эти продукты убивают друг друга в det(A). Поэтому каждый член в det( A ) уничтожается, когда мы объединяем одинаковые члены в det( A ), поэтому det( A )=0.
<р>4. Пусть матрица B получена из матрицы A добавлением j-й строки, умноженной на k, к i-й строке. Представим A в виде столбца строк:
По свойству 2 мы можем заключить, что det( B ) равно сумме определителей двух матриц:
Первая из этих матриц — A . Обозначим второй через C . Таким образом, det(B)=det(A)+det(C). По свойству 1 det( C ) в k раз больше определителя следующей матрицы:
Но эта матрица имеет две равные строки, поэтому ее определитель равен 0 (свойство 3). Таким образом, det( C )=0 и det( B )=det( A ). Доказательство завершено.
Каждое уравнение в системе становится строкой. Каждая переменная в системе становится столбцом. Переменные отбрасываются, а коэффициенты помещаются в матрицу. Если правая часть включена, это называется расширенной матрицей. Если правая часть не включена, она называется матрицей коэффициентов.
Система линейных уравнений.
становится расширенной матрицей .
| x | y | z | rhs |
|---|
| 1 | 1 | < td >-1 1 |
| 3 | -2 | 1 | 3 |
| 4 | 1 | -2 | 9 |
Элементарные операции со строками
Элементарные операции со строками — это операции, которые можно выполнять над матрицей и получать матрицу, эквивалентную строкам. Если матрица представляет собой расширенную матрицу, построенную из системы линейных уравнений, то матрица, эквивалентная строкам, будет иметь тот же набор решений, что и исходная матрица.
При работе с системами линейных уравнений можно было выполнить три операции, которые не изменили бы набор решений.
- Поменять местами два уравнения.
- Умножение уравнения на ненулевую константу.
- Умножить уравнение на ненулевую константу и добавить его к другому уравнению, заменив это уравнение.
Когда система линейных уравнений преобразуется в расширенную матрицу, каждое уравнение становится строкой. Итак, теперь есть три элементарные операции со строками, которые создадут эквивалентную по строкам матрицу.
- Поменять местами две строки
- Умножение строки на ненулевую константу
- Умножить строку на ненулевую константу и добавить ее к другой строке, заменив эту строку.
Формы строк-эшелонов и сокращенные формы строк-эшелонов
Это строковые эквивалентные формы матрицы. Можно легко решить систему линейных уравнений, когда матрицы находятся в одной из этих форм.
Форма ряда-эшелона
Матрица находится в форме строки-эшелона, когда выполняются следующие условия.
- Если есть строка, состоящая только из нулей, то она находится внизу матрицы.
- Первый ненулевой элемент любой строки равен единице. Этот элемент называется ведущим.
- Лидер любой строки находится справа от ведущего элемента предыдущей строки.
Примечания
- Ведущий в строке не обязательно должен быть непосредственно справа от ведущего в предыдущей строке.
- Матрица в форме строки-эшелона будет иметь нули ниже ведущих единиц.
- Исключение Гаусса переводит матрицу в форму строки-эшелона, а затем требуется обратная подстановка, чтобы завершить поиск решений системы.
- Эшелонно-строковая форма матрицы не обязательно уникальна.
Уменьшенная форма строки-эшелона
Матрица находится в редуцированной ступенчато-строковой форме, когда выполняются все условия ступенчато-строковой формы и все элементы выше, а также ниже ведущих равны нулю.
- Если есть строка, состоящая только из нулей, то она находится внизу матрицы.
- Первый ненулевой элемент любой строки равен единице. Этот элемент называется ведущим.
- Лидер любой строки находится справа от ведущего элемента предыдущей строки.
- Все элементы выше и ниже ведущей единицы равны нулю.
Примечания
- Ведущий в строке не обязательно должен быть непосредственно справа от ведущего в предыдущей строке.
- Матрица в форме строки-эшелона будет иметь нули как выше, так и ниже ведущих единиц.
- Исключение Гаусса-Жордана переводит матрицу в сокращенную ступенчато-строковую форму.
- Для завершения поиска решений системы не требуется обратной замены.
- Сокращенная форма строки-эшелона матрицы уникальна.
Исключение по Гауссу
- Запишите систему линейных уравнений в виде расширенной матрицы
- Выполните элементарные операции со строками, чтобы преобразовать матрицу в эшелонированную форму.
- Преобразуйте матрицу обратно в систему линейных уравнений
- Используйте обратную замену, чтобы получить все ответы
Исключение Гаусса-Джордана
- Запишите систему линейных уравнений в виде расширенной матрицы
- Выполните элементарные операции со строками, чтобы преобразовать матрицу в уменьшенную ступенчатую форму.
- Преобразуйте матрицу обратно в систему линейных уравнений
- Обратная замена не требуется
Поворот
- Сводка – это процесс, который автоматизирует операции со строками, необходимые для помещения матрицы в эшелонированную или сокращенную форму.
- В частности, поворот превращает элементы выше или ниже ведущей единицы в нули.
Типы решений
При решении системы линейных уравнений возможны три типа решений
Независимый
Когда вы преобразуете расширенную матрицу обратно в форму уравнения, вы получаете x=3, y=1 и z=2.
Зависимый
Первое уравнение будет x + 3z = 4. Решение для x дает x = 4 - 3z.
Второе уравнение будет y - 2z = 3. Решение для y дает y = 3 + 2z.
Столбец z не очищается (все нули, кроме одного числа), поэтому остальные переменные будут определены через z. Следовательно, z будет параметром t, а решение будет .
x = 4–3t, y = 3 + 2t, z = t
Несовместимо
Здесь нет решения. Вы можете записать это как нулевое множество Ø, пустое множество <> или отсутствие решения.
Данная матрица M × N состоит только из 0 или 1 , измените все элементы строки i и столбца j на 0, если ячейка (i, j) имеет значение 0 . Сделайте это, не используя дополнительное пространство для каждого (i, j), имеющего значение 0 .
Ввод:
[ 1 1 0 1 1 ]
[ 1 1 1 1 1 ]
[ 1 1 1 0 1 ]
[ 1 1 1 1 1 ]
[ 0 1 1 1 1 ]
Вывод:
[ 0 0 0 0 0 ]
[ 0 1 0 0 1 ]
[ 0 0 0 0 0 ]
[ 0 1 0 0 1 ]
[ 0 0 0 0 0 ]
Пояснение:
0 присутствуют в (0, 2), (4, 0) и (2, 3) во входной матрице. Итак, мы меняем все элементы следующих ячеек на 0:
- строка 0 и столбец 2
- строка 4 и столбец 0
- строка 2 и столбец 3
Простое решение состоит в том, чтобы пройтись по матрице и, если мы встретим любую ячейку (i, j), имеющую значение 0 , изменить каждый элемент в строке i и столбце j на произвольное значение, отличное от 0 или 1 . Позже снова пройдитесь по матрице и замените все элементы с присвоенным значением на 0 .
Алгоритм может быть реализован на C++, Java и Python следующим образом:
Вывод:
0 0 0 0 0
0 1 0 1 1
0 0 0 0 0
0 1 0 1 1
0 0 0 0 0
Вывод:
[0, 0, 0, 0, 0]
[0, 1, 0, 1, 1]
[0, 0, 0, 0, 0]
[0, 1, 0, 1, 1]
[0, 0, 0, 0, 0]
Питон
Вывод:
[0, 0, 0, 0, 0]
[0, 1, 0, 1, 1]
[0, 0, 0, 0, 0]
[0, 1, 0, 1, 1]
[0, 0, 0, 0, 0]
Временная сложность предлагаемого решения составляет O(M × N × (M + N)) , что неэффективно для матрицы M × N.
Мы также можем решить эту задачу за время O(M × N). Идея состоит в том, чтобы пройти матрицу один раз и использовать первую строку и первый столбец (или последнюю строку и последний столбец), чтобы отметить, имеет ли какая-либо ячейка в соответствующей строке или столбце значение 0 или нет.Прежде чем сделать это, сначала отметьте, присутствуют ли в выбранной строке/столбце 0 в двух разных флагах.
Ниже представлена реализация этой идеи на C++, Java и Python. Обратите внимание, что этот метод будет работать для любой целочисленной матрицы (не только для двоичной матрицы).
В этом разделе мы представим алгоритм «решения» системы линейных уравнений.
Мы будем решать системы линейных уравнений алгебраически, используя метод исключения. Другими словами, мы будем комбинировать уравнения различными способами, чтобы попытаться исключить из каждого уравнения как можно больше переменных. Есть три допустимые операции, которые мы можем выполнить с нашей системой уравнений:
Масштабирование: мы можем умножать обе части уравнения на ненулевое число.
Пример
Дополненные матрицы и операции со строками
Решение уравнений методом исключения требует записи переменных
и знак равенства
снова и снова, просто в качестве заполнителей: все, что меняется в уравнениях, — это числа коэффициентов. Мы можем облегчить себе жизнь, извлекая только числа и помещая их в рамку:
Это называется расширенная матрица. Слово «расширенный» относится к вертикальной линии, которую мы рисуем, чтобы напомнить себе, где находится знак равенства; матрица – это сетка чисел без вертикальной линии. В этих обозначениях наши три допустимых способа манипулирования нашими уравнениями становятся операциями со строками:
Масштабирование: умножить все записи в строке на ненулевое число.
означает просто «первый ряд», а также для
Примечание
Когда мы писали наши операции со строками выше, мы использовали такие выражения, как
Конечно, это не означает, что вторая строка равна второй строке минус удвоенная первая строка. Вместо этого это означает, что мы заменяем вторую строку второй строкой минус удвоенная первая строка. Такой синтаксис часто используется в компьютерном программировании, когда мы хотим изменить значение переменной.
Пример
Процесс выполнения операций со строками над матрицей не меняет набор решений соответствующих линейных уравнений!
Действительно, весь смысл выполнения этих операций заключается в решении уравнений методом исключения.
Определение
Две матрицы называются эквивалентными по строкам, если одну можно получить из другой, выполнив некоторое количество операций со строками.
Таким образом, линейные уравнения матриц, эквивалентных строкам, имеют один и тот же набор решений.
Пример (несогласованная система)
В предыдущем подразделе мы увидели, как преобразовать систему линейных уравнений в расширенную матрицу. Мы хотим найти алгоритм для «решения» такой расширенной матрицы. Сначала мы должны решить, что означает «решение» расширенной матрицы.
Определение
Матрица находится в эшелонированной форме строк, если:
- Все нулевые строки находятся внизу.
- Первая ненулевая запись строки находится справа от первой ненулевой записи строки выше.
- Ниже первой ненулевой записи в строке все записи равны нулю.
Вот изображение матрицы в форме эшелона строк:
Определение
Сводка – это первая ненулевая запись строки матрицы в форме эшелона строк.
Матрицу в виде эшелона строк обычно легко решить с помощью обратной подстановки. Например,
Мы сразу это видим
Определение
Матрица находится в уменьшенной ступенчатой форме строк, если она находится в ступенчатой форме строк, и, кроме того:
- Каждая опорная точка равна 1.
- Каждая сводная точка — это единственная ненулевая запись в своем столбце.
Вот изображение матрицы в сокращенной эшелонированной форме строки:
Матрица в сокращенной ступенчатой форме строк в некотором смысле полностью решена. Например,
Пример
При принятии решения о том, находится ли расширенная матрица в (уменьшенной) эшелонированной форме строк, нет ничего особенного в расширенном столбце (столбцах). Просто игнорируйте вертикальную линию.
Если расширенная матрица представлена в виде редуцированного эшелона строк, соответствующая линейная система рассматривается как решенная. Ниже мы увидим, почему это так, и покажем, что любую матрицу можно привести к сокращенной эшелонированной форме строк, используя только операции со строками.
Примечание (Почему слово «поворотный»?)
Рассмотрите следующую систему уравнений:
Мы можем представить эту систему как пару строк в
(красный и синий соответственно на картинке ниже), которые пересекаются в точке
Если мы вычтем первое уравнение из второго, мы получим уравнение
Это приводит к системе уравнений:
Что касается операций со строками над матрицами, это можно записать так:
Геометрически произошло то, что исходная синяя линия была заменена новой синей линией
Мы можем думать о синей линии как о вращении вокруг решения
Мы использовали положение точки поворота в матрице, чтобы сделать синюю линию такой. Это одно из возможных объяснений терминологии «разворот».
Теорема
Каждая матрица эквивалентна по строкам одной и только одной матрице в сокращенной эшелонированной форме строк.
Мы предоставим алгоритм, называемый редукция строк или исключение по Гауссу, который демонстрирует, что каждая матрица эквивалентна строке по крайней мере одной матрице. в виде уменьшенного эшелона строк.
Утверждение уникальности интересно: оно означает, что независимо от того, как вы уменьшаете количество строк, вы всегда получаете одну и ту же матрицу в сокращенной эшелонированной форме строк.
Это, конечно, предполагает, что вы выполняете только три допустимые операции со строками и не делаете никаких арифметических ошибок.
Читайте также:
