Найти ранг окаймляющим способом

Ранг матрицы. Метод окаймляющих миноров. Линейная независимость строк (столбцов) матрицы

Пусть в матрице А размеров (m; n) выбраны произвольно k строк и k столбцов (k ≤ min(m; n)). Элементы матрицы, стоящие на пересечении выбранных строк и столбцов, образуют квадратную матрицу порядка k, определитель которой называется минором M_kk порядка k_y или минором k-го порядка матрицы A.

Рангом матрицы называется максимальный порядок r отличных от нуля миноров матрицы A, а любой минор порядка r, отличный от нуля, — базисным минором. Обозначение: rang A = r. Если rang A = rang B и размеры матриц A и Bсовпадают, то матрицы A и B называются эквивалентными. Обозначение: A

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

Метод окаймляющих миноров

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

Линейная независимость строк (столбцов) матрицы

Понятие ранга матрицы тесно связано с понятием линейной независимости ее строк (столбцов).

Строки матрицы :

называют линейно зависимыми, если найдутся такие числа λ₁, λ₂, λ_k, что справедливо равенство:

Строки матрицы A называются линейно независимыми, если вышеприведённое равенство возможно лишь в случае, когда все числа λ₁ = λ₂ = … = λ_k = 0

Аналогичным образом определяется линейная зависимость и независимость столбцов матрицы A.

Если какая-либо строка (a_l) матрицы A (где (a_l)=(a_l1, a_l2,…, a_ln)) может быть представлена в виде

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

Базисные строчки и базисные столбцы линейно независимы. Любая строка (либо столбец) матрицы A является линейной комбинацией базисных строк (столбцов), т. е. строк (столбцов), пересекающих базисный минор. Таким образом, ранг матрицы A: rang A = k равен максимальному числу линейно независимых строк (столбцов) матрицы A.

Т.е. ранг матрицы — это размерность самой большой квадратной матрицы внутри той матрицы, для которой нужно определить ранг, для которой определитель не равен нулю. Если исходная матрица не является квадратной, либо если она квадратная, но её определитель равен нулю, то для квадратных матриц меньшего порядка строки и столбцы выбираются произвольно.

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

Примеры нахождения ранга матрицы

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

Р е ш е н и е. Минор второго порядка

окаймляющий минор M₂, также отличен от нуля. Однако оба минора четвёртого порядка, окаймляющие M₃.

равны нулю. Поэтому ранг матрицы A равен 3, а базисным минором является, например, представленный выше минор M₃.

Метод элементарных преобразований основан на том, что элементарные преобразования матрицы не меняют её ранга. Используя эти преобразования, можно привести матрицу к виду, когда все её элементы, кроме a₁₁, a₂₂, …, a_rr (r ≤min (m, n)), равны нулю. Это, очевидно, означает, что rang A = r. Заметим, что если матрица n-го порядка имеет вид верхней треугольной матрицы, т. е. матрицы, у которой все элементы под главной диагональю равны нулю, то её определитесь равен произведению элементов, стоящих на главной диагонали. Это свойство можно использовать при вычислении ранга матрицы методом элементарных преобразований: необходимо с их помощью привести матрицу к треугольной и тогда, выделив соответствующий определитель, найдём, что ранг матрицы равен числу элементов главной диагонали, отличных от нуля.

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

Р е ш е н и е. Обозначим i-ю строку матрицы A символом α_i. На первом этапе выполним элементарные преобразования

На втором этапе выполним преобразования

В результате получим

На третьем этапе мы переставили четвёртую строку на место третьей, а третью — на место четвёртой. На четвёртом этапе мы разделили элементы четвёртого и пятого столбцов на 4 и 2 и поменяли местами третий и четвёртый столбцы. Из вида матрицы, получившегося после четвёртого этапа преобразования, следует, что rang A = 3. Можно было бы продолжить преобразование матрицы A, добиваясь обнуления остальных элементов матрицы с различными индексами, но вряд ли это целесообразно при нахождении ранга матрицы. Заметим также, что получившуюся в результате элементарных преобразований нулевую строку можно было бы не писать при дальнейших преобразованиях матрицы, а просто вычеркнуть, что, очевидно, никак не повлияет на ранг исходной матрицы.

Как найти ранг матрицы в wxMaxima и Maxima

Для нахождения ранга матрицы используется функция rank:

Источник

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

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

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

Рангом системы строк (столбцов) называется максимальное количество линейно независимых строк (столбцов) этой системы.

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

1. Минор M k-того порядка не равен нулю.
2. Если окаймляющие миноры для минора M (k+1)-го порядка, составить невозможно (т.е. матрица содержит k строк или k столбцов), то ранг матрицы равен k. Если окаймляющие миноры существуют и все равны нулю, то ранг равен k. Если среди окаймляющих миноров есть хотя бы один, не равный нулю, то пробуем составить новый минор k+2 и т.д.

Разберем алгоритм более подробно. Сначала рассмотрим миноры первого (элементы матрицы) порядка матрицы A. Если все они равны нулю, то rangA = 0. Если есть миноры первого порядка (элементы матрицы) не равные нулю M₁ ≠ 0, то ранг rangA ≥ 1.

Проверим есть ли окаймляющие миноры для минора M₁. Если такие миноры есть, то они буду миноры второго порядка. Если все миноры окаймляющие минор M₁ равны нулю, то rangA = 1. Если есть хоть один минор второго порядка не равные нулю M₂ ≠ 0, то ранг rangA ≥ 2.

Проверим есть ли окаймляющие миноры для минора M₂. Если такие миноры есть, то они буду миноры третьего порядка. Если все миноры окаймляющие минор M₂ равны нулю, то rangA = 2. Если есть хоть один минор третьего порядка не равные нулю M₃ ≠ 0, то ранг rangA ≥ 3.

Проверим есть ли окаймляющие миноры для минора M₃. Если такие миноры есть, то они буду миноры четвертого порядка. Если все миноры окаймляющие минор M₃ равны нулю, то rangA = 3. Если есть хоть один минор четвертого порядка не равные нулю M₄ ≠ 0, то ранг rangA ≥ 4.

Проверяем есть ли окаймляющий минор для минора M₄, и так далее. Алгоритм прекращается, если на каком-то этапе окаймляющие миноры равны нулю или окаймляющий минор нельзя получить (в матрице «закончились» строки или столбцы). Порядок не нулевого минора, который получилось составить будет рангом матрицы.

Пример

Рассмотрим данный метод на примере. Дана матрицы 4х5:

У данной матрице ранг не может быть больше 4. Так же у этой матрице есть не нулевые элементы (минор первого порядка), значит ранг матрицы ≥ 1.

Составим минор 2-ого порядка. Начнем с угла.

Найдем определитель данного минора.

Так определитель равен нулю, составим другой минор.

Найдем определитель данного минора.

Определить данного минора равен -2. Значит ранг матрицы ≥ 2.

Если данный минор был равен 0, то составили бы другие миноры. До конца бы составили все миноры по 1 и второй строке. Потом по 1 и 3 строке, по 2 и 3 строке, по 2 и 4 строке, пока не нашли бы минор не равный 0, например:

Если все миноры второго порядка равны 0, то ранг матрицы был бы равен 1. Решение можно было бы остановить.

Продолжим поиска ранга матрицы. Составим минор 3-го порядка.

Найдем определитель этого минора.

Минор получился не нулевой. значит ранг матрицы ≥ 3.

Если бы данный минор был нулевым, то нужно было бы составить другие миноры. Например:

Если все миноры третьего порядка равны 0, то ранг матрицы был бы равен 2. Решение можно было бы остановить.

Продолжим поиска ранга матрицы. Составим минор 4-го порядка.

Найдем определитель этого минора.

Определитель минора получился равный 0. Построим другой минор.

Найдем определитель этого минора.

Минор получился равным 0.

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

Источник

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

В данной теме нам понадобятся такие понятия как минор матрицы и окаймляющий минор. В теме «Алгебраические дополнения и миноры. Виды миноров и алгебраических дополнений» есть подробное пояснение этих понятий.

В предыдущей теме было рассмотрено понятие ранга матрицы, а также на примерах показано, как находить ранг по определению. Конечно, находить ранг матрицы таким образом несколько затруднительно, – в первую очередь из-за объёма вычислений. Однако количество вычисляемых миноров можно существенно уменьшить, если использовать так называемый метод окаймляющих миноров.

Суть метода окаймляющих миноров выражается парой пунктов простого алгоритма:

1. Пусть некий минор $M$ k-го порядка не равен нулю.
2. Если окаймляющие миноры для минора $M$ (это уже будут миноры (k+1)-го порядка), составить невозможно (т.е. матрица содержит k строк или k столбцов), то ранг равен k. Если окаймляющие миноры существуют и все равны нулю, то ранг равен k. Если среди окаймляющих миноров есть хотя бы один, отличный от нуля, то повторяем для него пункт №1, приняв k+1 вместо k.

Наглядно всё вышеизложенное можно выразить следующей схемой:

Поясню эту схему более подробно. Станем рассуждать с самого начала, т.е. с миноров первого порядка. Если все миноры первого порядка некоей матрицы $A$ (миноры первого порядка – это элементы матрицы) равны нулю, то $\rang A=0$. Если в матрице есть минор первого порядка $M_1\neq 0$, то $\rang A≥ 1$.

Проверяем окаймляющие миноры для минора $M_1$. Это уже будут миноры второго порядка. Если все миноры, окаймляющие $M_1$, равны нулю, то $\rang A=1$. Если среди миноров второго порядка, окаймляющих $M_1$, есть хоть один минор $M_2 \neq 0$, то $\rang A≥ 2$.

Проверяем окаймляющие миноры для минора $M_2$. Это будут миноры третьего порядка. Если все миноры третьего порядка, окаймляющие $M_2$, равны нулю, то $\rang A=2$. Если среди миноров третьего порядка, окаймляющих $M_2$, есть хоть один минор $M_3\neq 0$, то $\rang A≥ 3$.

Проверяем окаймляющие миноры для минора $M_3$. Если все миноры четвёртого порядка, окаймляющие $M_3$, равны нулю, то $\rang A=3$. Если среди миноров четвёртого порядка, окаймляющих $M_3$, есть хоть один минор $M_4\neq 0$, то $\rang A≥ 4$.

Проверяем все окаймляющие миноры для минора $M_4$, и так далее. В конце концов возможны два случая: либо на каком-то шаге окажется, что все окаймляющие миноры равны нулю, либо окаймляющий минор составить просто не получится, так как в матрице «закончатся» строки или столбцы. Порядок последнего составленного ненулевого минора и будет равен рангу матрицы.

Найти ранг матрицы $A=\left(\begin -1 & 2 & 1 & 3 \\ -3 & 0 & 5 & 4 \\ -5 & 4 & 7 & 10 \end \right)$ методом окаймляющих миноров.

Можно, конечно, начать с миноров первого порядка, которые представляют собой просто элементы данной матрицы. Но лучше сразу выбрать какой-либо не равный нулю минор второго порядка, тем паче что такой выбор большой сложности не представляет. Например, на пересечении строк №1, №2 и столбцов №1, №2 расположены элементы минора $\left|\begin -1 & 2 \\ -3 & 0 \end \right|$, который несложно вычислить, используя формулу №1 из темы про вычисление определителей второго и третьего порядков:

$$ \left|\begin -1 & 2 \\ -3 & 0 \end \right|=-1\cdot 0-2\cdot (-3)=6. $$

Итак, существует минор второго порядка, не равный нулю, из чего следует, что $\rang A≥ 2$. Рассмотрим миноры третьего порядка, окаймляющие данный минор второго порядка. Как составить окаймляющий минор? Для этого к набору строк и столбцов, на пересечении которых лежат элементы минора второго порядка, нужно добавить ещё одну строку и ещё один столбец. Вспоминаем, что элементы записанного нами минора второго порядка расположены на пересечении строк №1, №2 и столбцов №1, №2. Добавим к строкам ещё строку №3, а к столбцам – столбец №3. Мы получим минор третьего порядка, элементы которого (они для наглядности показаны в матрице синим цветом) лежат на пересечении строк №1, №2, №3 и столбцов №1, №2, №3. Найдём значение этого минора, используя формулу №2 из темы про вычисление определителей второго и третьего порядков:

Окаймляющий минор равен нулю. О чём это говорит? Это говорит о том, что нам нужно продолжить нахождение окаймляющих миноров. Либо они все равны нулю (и тогда ранг будет равен 2), либо среди них найдётся хотя бы один, отличный от нуля.

Элементы второго окаймляющего минора лежат на пересечении строк №1, №2, №3 и столбцов №1, №2, №4. В матрице для наглядности элементы этого минора показаны зелёным цветом. Сразу вычислим данный минор, используя всё ту же формулу №2 из темы про вычисление определителей второго и третьего порядков:

И этот окаймляющий минор равен нулю. Иных окаймляющих миноров нет. Следовательно, все окаймляющие миноры равны нулю. Порядок последнего составленного ненулевого минора равен 2. Вывод: ранг равен 2, т.е. $\rang A=2$.

Найти ранг матрицы $A=\left(\begin 1 & 2 & 0 & 4 & 5\\ 3 & 6 & -2 & -1 & -3\\ -2 & -4 & 2 & 5 & 7\\ -1 & -2 & 2 & 9 & 11 \end \right)$ методом окаймляющих миноров.

Вновь, как и в предыдущем примере, начнём решение с выбора минора второго порядка, не равного нулю. Например, на пересечении строк №1, №2 и столбцов №1, №2 расположены элементы минора $\left|\begin 1 & 2 \\ 3 & 6 \end \right|$, который несложно вычислить, используя формулу №1 из темы про вычисление определителей второго и третьего порядков:

$$ \left|\begin 1 & 2 \\ 3 & 6 \end \right|=1\cdot 6-2\cdot 3=0. $$

Данный минор второго порядка равен нулю, т.е. выбор неудачен. Возьмём иной минор второго порядка. Например, тот, элементы которого расположены на пересечении строк №1, №2 и столбцов №2, №3:

Итак, ненулевой минор второго порядка существует, поэтому $\rang A≥ 2$. Обозначим этот минор как $M_2$ и станем окаймлять его минорами третьего порядка. Например, добавим к строкам и столбцам, на которых расположены элементы $M_2$, ещё строку №3 и столбец №1. Т.е. найдём минор третьего порядка, элементы которого находятся на пересечении строк №1, №2, №3 и столбцов №1, №2, №3. Используем для этого формулу №2 из темы про вычисление определителей второго и третьего порядков. Подробные вычисления я приводить не стану, запишем лишь ответ:

$$ \left|\begin 1 & 2 & 0 \\ 3 & 6 & -2 \\ -2 & -4 & 2 \end \right|=0. $$

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

Рассмотрим минор третьего порядка, элементы которого лежат на пересечении строк №1, №2, №3 и столбцов №2, №3, №4. Этот минор тоже окаймляет $M_2$:

$$ \left|\begin 2 & 0 & 4 \\ 6 & -2 & -1 \\ -4 & 2 & 5 \end \right|=0. $$

И вновь минор третьего порядка, окаймляющий $M_2$, равен нулю. Значит, переходим к иному минору третьего порядка. Возьмём минор третьего порядка, элементы которого лежат на пересечении строк №1, №2, №3 и столбцов №2, №3, №5. Этот минор тоже окаймляет $M_2$:

$$ \left|\begin 2 & 0 & 5 \\ 6 & -2 & -3 \\ -4 & 2 & 7 \end \right|=4. $$

Итак, среди миноров третьего порядка, окаймляющих $M_2$, есть минор, не равный нулю, откуда следует $\rang A≥ 3$. Обозначим этот ненулевой минор как $M_3$. Элементы минора $M_3$ лежат на пересечении строк №1, №2, №3 и столбцов №2, №3, №5. Станем окаймлять минор $M_3$ минорами четвёртого порядка. Для начала возьмём минор четвёртого порядка, элементы которого лежат на пересечении строк №1, №2, №3, №4 и столбцов №1, №2, №3, №5. Этот минор окаймляет $M_3$. Его значение найти несложно, если использовать, например, разложение по строке или по столбцу:

$$ \left|\begin 1 & 2 & 0 & 5\\ 3 & 6 & -2 & -3\\ -2 & -4 & 2 & 7\\ -1 & -2 & 2 & 11 \end \right|=0. $$

Аналогично, рассматривая минор четвёртого порядка, элементы которого расположены на пересечении строк №1, №2, №3, №4 и столбцов №2, №3, №4, №5, получим:

$$ \left|\begin 2 & 0 & 4 & 5\\ 6 & -2 & -1 & -3\\ -4 & 2 & 5 & 7\\ -2 & 2 & 9 & 11 \end \right|=0.$$

Иных окаймляющих миноров для минора $M_3$ нет. Все миноры четвёртого порядка, окаймляющие $M_3$, равны нулю. Последний ненулевой минор, т.е. $M_3$, был третьего порядка. Вывод: ранг равен 3, т.е. $\rang A=3$.

Найти ранг матрицы $A=\left(\begin -1 & 3 & 2 & 4 & 1\\ 0 & -2 & 5 & 0 & -3\\ 1 & -5 & 3 & 7 & 6 \end \right)$ методом окаймляющих миноров.

Снова начинаем решение с выбора минора второго порядка, не равного нулю. Например, на пересечении строк №1, №2 и столбцов №1, №2 расположены элементы минора $\left|\begin -1 & 3 \\ 0 & -2 \end \right|$, который вычисляем, используя формулу №1 из темы про вычисление определителей второго и третьего порядков:

Данный минор (обозначим его $M_2$) не равен нулю, посему именно его мы и станем окаймлять минорами третьего порядка. Например, добавим к строкам и столбцам, на которых расположены элементы $M_2$, ещё строку №3 и столбец №3. Т.е. найдём минор третьего порядка, элементы которого расположены на пересечении строк №1, №2, №3 и столбцов №1, №2, №3. Используем для этого формулу №2 из темы про вычисление определителей второго и третьего порядков:

$$ \left|\begin -1 & 3 & 2 \\ 0 & -2 & 5 \\ 1 & -5 & 3 \end \right|=0. $$

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

Рассмотрим минор третьего порядка, элементы которого лежат на пересечении строк №1, №2, №3 и столбцов №1, №2, №4. Этот минор тоже окаймляет $M_2$:

$$ \left|\begin -1 & 3 & 4 \\ 0 & -2 & 0 \\ 1 & -5 & 7 \end \right|=22. $$

Итак, среди миноров третьего порядка, окаймляющих $M_2$, есть хоть один, не равный нулю. Миноры четвёртого порядка мы образовать уже не можем, так как для них потребуется 4 строки, а в матрице $A$ всего 3 строки. Посему, так как последний ненулевой минор был третьего порядка, то ранг равен 3, т.е. $\rang A=3$.

Заметили ошибку, опечатку, или некорректно отобразилась формула? Отпишите, пожалуйста, об этом в данной теме на форуме (регистрация не требуется).

Источник