Нахождение ранга матрицы методом окаймляющих миноров.

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

Одним из таких методов является метод окаймляющих миноров.

Разберемся с понятием окаймляющего минора.

Говорят, что минор М_ок (k+1)-ого порядка матрицы А окаймляет минор M порядка k матрицы А, если матрица, соответствующая минору М_ок, «содержит» матрицу, соответствующую минору M.

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

Для примера рассмотрим матрицу и возьмем минор второго порядка . Запишем все окаймляющие миноры:

Метод окаймляющих миноров обосновывается следующей теоремой (приведем ее формулировку без доказательства).

Теорема.

Если все миноры, окаймляющие минор k-ого порядка матрицы А порядка p на n, равны нулю, то все миноры порядка (k+1) матрицы А равны нулю.

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

Перейдем к нахождению ранга матрицы методом окаймляющих миноров. Кратко опишем алгоритм этого метода.

Если матрица А ненулевая, то в качестве минора первого порядка берем любой элемент матрицы А, отличный от нуля. Рассматриваем его окаймляющие миноры. Если все они равны нулю, то ранг матрицы равен единице. Если же есть хотя бы один ненулевой окаймляющий минор (его порядок равен двум), то переходим к рассмотрению его окаймляющих миноров. Если все они равны нулю, то Rank(A) = 2. Если хотя бы один окаймляющий минор отличен от нуля (его порядок равен трем), то рассматриваем его окаймляющие миноры. И так далее. В итоге Rank(A) = k, если все окаймляющие миноры (k + 1)-ого порядка матрицы А равны нулю, либо Rank(A) = min(p, n), если существует ненулевой минор, окаймляющий минор порядка (min(p, n) – 1).

Разберем метод окаймляющих миноров для нахождения ранга матрицы на примере.

Пример.

Найдите ранг матрицы методом окаймляющих миноров.

Решение.

Так как элемент a_{1 1} матрицы А отличен от нуля, то возьмем его в качестве минора первого порядка. Начнем поиск окаймляющего минора, отличного от нуля:

Найден окаймляющий минор второго порядка, отличный от нуля . Переберем его окаймляющие миноры (их штук):

Все миноры, окаймляющие минор второго порядка , равны нулю, следовательно, ранг матрицы А равен двум.

Ответ:

Rank(A) = 2.

Пример.

Найдите ранг матрицы с помощью окаймляющих миноров.

Решение.

В качестве отличного от нуля минора первого порядка возьмем элемент a_{1 1} = 1 матрицы А. Окаймляющий его минор второго порядка не равен нулю. Этот минор окаймляется минором третьего порядка . Так как он не равен нулю и для него не существует ни одного окаймляющего минора, то ранг матрицы А равен трем.

Ответ:

Rank(A) = 3.

К началу страницы

Нахождение ранга с помощью элементарных преобразований матрицы (методом Гаусса).

Рассмотрим еще один способ нахождения ранга матрицы.

Следующие преобразования матрицы называют элементарными:

· перестановка местами строк (или столбцов) матрицы;

· умножение всех элементов какой-либо строки (столбца) матрицы на произвольное число k, отличное от нуля;

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

Матрица В называется эквивалентной матрице А, если В получена из А с помощью конечного числа элементарных преобразований. Эквивалентность матриц обозначается символом «~», то есть, записывается A ~ B.

Нахождение ранга матрицы с помощью элементарных преобразований матрицы основано на утверждении: если матрица В получена из матрицы А с помощью конечного числа элементарных преобразований, то Rank(A) = Rank(B).

Справедливость этого утверждения следует из свойств определителя матрицы:

· При перестановке строк (или столбцов) матрицы ее определитель меняет знак. Если он равен нулю, то при перестановке строк (столбцов) он остается равным нулю.

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

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

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

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

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

· Для прямоугольных матриц А порядка p на n, число строк которых больше числа столбцов (p > n).

или

· Для прямоугольных матриц А порядка p на n, число строк которых меньше числа столбцов (p < n).

или

· Для квадратных матриц А порядка n на n.

или

Эти иллюстрации являются шаблонами, к которым будем преобразовывать матрицу А.

Опишем алгоритм метода.

Пусть нам требуется найти ранг ненулевой матрицы А порядка (p может быть равно n).

Будем считать, что элемент a₁₁ отличен от нуля. В противном случае мы можем перестановкой строк и (или) столбцов преобразовать матрицу так, чтобы «новый» элемент a₁₁ стал ненулевым.

Итак, . Умножим все элементы первой строки матрицы А на . При этом получим эквивалентную матрицу, обозначим ее А⁽¹⁾:

К элементам второй строки полученной матрицы А⁽¹⁾ прибавим соответствующие элементы первой строки, умноженные на . К элементам третьей строки прибавим соответствующие элементы первой строки, умноженные на . И так далее до p-ой строки. Получим эквивалентную матрицу, обозначим ее А⁽²⁾:

Если все элементы полученной матрицы, находящиеся в строках со второй по p-ую, равны нулю, то ранг этой матрицы равен единице, а, следовательно, и ранг исходной матрицы равен единице.

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

Если , то переставляем строки и (или) столбцы матрицы А⁽²⁾ так, чтобы «новый» элемент стал ненулевым.

Итак, . Умножаем каждый элемент второй строки матрицы А⁽²⁾ на . Получаем эквивалентную матрицу А⁽³⁾:

К элементам третьей строки полученной матрицы А⁽³⁾ прибавим соответствующие элементы второй строки, умноженные на . К элементам четвертой строки прибавим соответствующие элементы второй строки, умноженные на . И так далее до p-ой строки. Получим эквивалентную матрицу, обозначим ее А⁽⁴⁾:

Если все элементы полученной матрицы, находящиеся в строках с третьей по p-ую, равны нулю, то ранг этой матрицы равен двум, а, следовательно, Rank(A) = 2.

Если же в строках с третьей по p-ую есть хотя бы один ненулевой элемент, то продолжаем проводить преобразования. Причем действуем абсолютно аналогично, но лишь с отмеченной на рисунке частью матрицы А⁽⁴⁾:

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

Разберем решения нескольких примеров.

Пример.

Найдите ранг матрицы с помощью элементарных преобразований.

Решение.

Так как элемент a_{1 1} отличен от нуля, то умножим элементы первой строки матрицы А на :

Прибавим к элементам второй строки соответствующие элементы первой строки, умноженные на (- 3). К элементам третьей строки прибавим элементы первой строки, умноженные на (- 1). И так далее:

Элемент отличен от нуля, поэтому мы можем умножить элементы второй строки матрицы А⁽²⁾ на :

К элементам третьей строки полученной матрицы прибавляем соответствующие элементы второй строки, умноженные на ; к элементам четвертой строки – элементы второй строки, умноженные на ; к элементам пятой строки – элементы второй строки, умноженные на :

Все элементы третьей, четвертой и пятой строк полученной матрицы равны нулю. Так с помощью элементарных преобразований мы привели матрицу А к трапецеидальному виду, откуда видно, что Rank(A⁽⁴⁾) = 2. Следовательно, ранг исходной матрицы также равен двум.

Замечание.

ОБРАТИТЕ ВНИМАНИЕ: при проведении элементарных преобразований не допускаются приближенные вычисления!

Рассмотрим еще один пример.

Пример.

Методом элементарных преобразований найдите ранг матрицы .

Решение.

Поменяем местами первую и вторую строки матрицы А, так как элемент a_{1 1} равен нулю, а элемент a₂₁ отличен от нуля:

В полученной матрице элемент равен единице, поэтому не нужно производить умножение элементов первой строки на . Сделаем все элементы первого столбца, кроме первого, нулевыми:

Так первый столбец преобразован к нужному виду.

Элемент в полученной матрице отличен от нуля. Умножим элементы второй строки на :

Второй столбец полученной матрицы имеет нужный вид, так как элемент уже равен нулю.

Так как , а , то поменяем местами третий и четвертый столбцы:

Умножим третью строку полученной матрицы на :

На этом заканчиваем преобразования. Получаем Rank(A⁽⁵⁾)=3, следовательно, Rank(A)=3.

Ответ:

ранг исходной матрицы равен трем.

9. Теоре́ма Кро́некера — Капе́лли — критерий совместности системы линейных алгебраических уравнений:

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

Для того чтобы линейная система являлась совместной, необходимо и достаточно, чтобы ранг расширенной матрицы этой системы был равен рангу её основной матрицы.

Пояснения

Система уравнений разрешима тогда и только тогда, когда , где — расширенная матрица, полученная из матрицы приписыванием столбца ^[1].

Доказательство (условия совместности системы)[править | править вики-текст]

Необходимость

Пусть система совместна. Тогда существуют числа такие, что . Следовательно, столбец является линейной комбинацией столбцов матрицы . Из того что ранг матрицы не изменится, если из системы его строк (столбцов) вычеркнуть или приписать строку (столбец), которая является линейной комбинацией других строк (столбцов) следует, что .

Достаточность

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

Следствия

· Количество главных переменных системы равно рангу системы.

· Совместная система будет определена (её решение единственно), если ранг системы равен числу всех её переменных.

· Система линейных уравнений является однородной, если свободный член каждого уравнения системы равен нулю. Например:

· Совершенно ясно, что однородная система всегда совместна, то есть всегда имеет решение. И, прежде всего, в глаза бросается так называемое тривиальное решение . Тривиальное, для тех, кто совсем не понял смысл прилагательного, значит, беспонтовое. Не академично, конечно, но зато доходчиво =) …Чего ходить вокруг да около, давайте выясним, нет ли у данной системы каких-нибудь других решений:

· Пример 1

· Решить однородную систему линейных уравнений

· Решение: чтобы решить однородную систему необходимо записать матрицу системы и с помощью элементарных преобразований привести её к ступенчатому виду. Обратите внимание, что здесь отпадает необходимость записывать вертикальную черту и нулевой столбец свободных членов – ведь что ни делай с нулями, они так и останутся нулями:

· (1) Ко второй строке прибавили первую строку, умноженную на –2. К третьей строке прибавили первую строку, умноженную на –3.

· (2) К третьей строке прибавили вторую строку, умноженную на –1.

· Делить третью строку на 3 не имеет особого смысла.

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

· Ответ:

· Сформулируем очевидный критерий: однородная система линейных уравнений имеет только тривиальное решение, если ранг матрицы системы (в данном случае 3) равен количеству переменных (в данном случае – 3 шт.).

· Разогреваемся и настраиваем свой радиоприёмник на волну элементарных преобразований:

· Пример 2

· Решить однородную систему линейных уравнений

· Из статьи Как найти ранг матрицы? вспоминаем рациональный приём попутного уменьшения чисел матрицы. В противном случае вам придётся разделывать крупную, а частенько и кусачую рыбу. Примерный образец оформления задания в конце урока.

· Нули – это хорошо и удобно, однако на практике гораздо более распространен случай, когда строки матрицы системы линейно зависимы. И тогда неизбежно появление общего решения:

· Пример 3

· Решить однородную систему линейных уравнений

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

· (1) К первой строке прибавили третью строку, умноженную на –1. Ко второй строке прибавили третью строку, умноженную на –2. Слева вверху я получил единицу с «минусом», что зачастую намного удобнее для дальнейших преобразований.

· (2) Первые две строки одинаковы, одну из них удалили. Честное слово, не подгонял решение – так получилось. Если выполнять преобразования шаблонно, то линейная зависимость строк обнаружилась бы чуть позже.

· (3) К третьей строке прибавили вторую строку, умноженную на 3.

· (4) У первой строки сменили знак.

· В результате элементарных преобразований получена эквивалентная система:

· Алгоритм работает точно так же, как и для неоднородных систем. Переменные , «сидящие на ступеньках» – главные, переменная , которой не досталось «ступеньки» – свободная.

· Выразим базисные переменные через свободную переменную:

· Ответ: общее решение:

· Тривиальное решение входит в общую формулу, и записывать его отдельно излишне.

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

· На этом можно было бы тихо-мирно закончить, но решение однородной системы уравнений часто требуется представить в векторной форме с помощью фундаментальной системы решений. Пожалуйста, временно забудьте об аналитической геометрии, поскольку сейчас речь пойдёт о векторах в алгебраическом смысле, который я немного приоткрыл в статье про ранг матрицы и окончательно расписал на уроке о линейных преобразованиях. Терминологии тушеваться не нужно, всё довольно просто:

· Фундаментальная система решений однородной системы уравнений

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

· Количество векторов фундаментальной системы рассчитывается по формуле:

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

· Представим общее решение Примера №3 в векторной форме. Свободная переменная в данном случае одна, поэтому фундаментальная система решений состоит из единственного вектора . Как его найти? Для этого свободной переменной нужно придать произвольное ненулевое значение. Проще всего, конечно же, выбрать и получить: .

· Координаты вектора должны удовлетворять каждому уравнению системы, и будет не лишним в этом убедиться.

· Ответ следует записать в виде линейной комбинации векторов фундаментальной системы. В нашей ситуации линейная комбинация состоит из одинокого слагаемого. Общее решение однородной системы я буду обозначать через вектор (подстрочный индекс расшифровывается «Общее Однородной»).

· Ответ: общее решение: , где (любое вещественное число)

· Придавая параметру различные действительные значения, можно получить бесконечно много частных решений, например, если , то вектор частного решения однородного уравнения («Частное Однородной») равен:
, то есть набор переменных удовлетворяет каждому уравнению системы.

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

· И тогда ответ запишется в эквивалентной форме:
, где (любое вещественное число)

Линейное многообразие

Линейным многообразием в линейном пространстве называется подмножество этого пространства вида

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

Если и , то тогда и только тогда, когда и .

В частности, является линейным подпространством тогда и только тогда, когда (т.е. содержит нулевой элемент). В этом случае .

Если — гильбертово пространство, а — его замкнутое подпространство, то можно выбрать вектор в определении () ортогональным подпространству . Такое представление , единственно.

Пересечение линейных многообразий всегда является линейным многообразием.

Размерность линейного многообразия — это размерность линейного подпространства : Для линейных многообразий в -мерном векторном пространстве или , или