Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Методы вычисления ранга матрицы
ОглавлениеЛинейная алгебра

Методы вычисления ранга матрицы


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


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


Пусть дана матрица [math]A[/math] размеров [math]m\times n[/math]. Будем говорить, что минор [math]M_{i_1i_2\ldots i_ki_{k+1}}^{j_1j_2\ldots j_kj_{k+1}}[/math] (k+l)-ro порядка окаймляет (содержит в себе) минор [math]M_{i_1i_2\ldots i_k}^{j_1j_2\ldots j_k}[/math] k-го порядка. При описании метода индексы выбранных строк и столбцов, в которых располагается минор, будем указывать, не упорядочивая их по возрастанию. При этом рассматриваемый минор и минор с упорядоченными индексами равны по абсолютной величине и, быть может, отличаются по знаку, но это для метода окаймляющих миноров не имеет никакого значения, поскольку нас интересует только ответ на вопрос: равен минор нулю или нет.


1. Выбираем строку [math]i_1[/math] и столбец [math]j_1[/math] так, чтобы минор 1-го порядка [math]M_{j_1}^{i_1}=a_{i_1j_1}[/math] был не равен нулю. Если это возможно, то [math]\operatorname{rg}A\geqslant1[/math], иначе процесс завершается и [math]\operatorname{rg}A=1[/math].


2. Окаймляем минор [math]M_{j_1}^{i_1}\ne0[/math], добавляя к выбранным [math]i_1[/math]-ой строке и [math]j_1[/math]-му столбцу еще строку [math]i_2\ne i_1[/math] и столбец [math]j_2\ne j_1[/math] так, чтобы минор


[math]M_{j_1j_2}^{i_1i_2}=\begin{vmatrix}a_{i_1j_1}&a_{i_1j_2}\\ a_{i_2j_1}& a_{i_2j_2} \end{vmatrix}\ne0.[/math]

Если это возможно, то [math]\operatorname{rg}A\geqslant2[/math], иначе процесс завершается и [math]\operatorname{rg}A=2[/math].


3. Окаймляем минор [math]M_{j_1j_2}^{i_1i_2}\ne0[/math], добавляя к выбранным ранее строкам и столбцам новую строку [math]i_3[/math] и новый столбец [math]j_3[/math] так, чтобы получить минор [math]M_{j_1j_2j_3}^{i_1i_2i_3}\ne0[/math]. Если это удалось, то [math]\operatorname{rg}A\geqslant3[/math], иначе процесс завершается и [math]\operatorname{rg}A=3[/math].


Продолжаем процесс окаймления, пока он не завершится. Пусть найден минор r-го порядка [math]M_{j_1\ldots j_r}^{i_1\ldots i_r}\ne0[/math], т.е. [math]\operatorname{rg}A\geqslant r[/math]. Однако, все миноры (r+l)-ro порядка, окаймляющие его, равны нулю [math]M_{j_1j_2\ldots j_rj_{r+1}}^{i_1i_2\ldots i_ri_{r+1}}=0[/math] или не существуют (при [math]r=m[/math] или [math]r=n[/math]). Тогда процесс завершается и [math]\operatorname{rg}A=r[/math].




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


[math]O=\begin{pmatrix}0&0\\0&0\end{pmatrix}\!,\quad A=\begin{pmatrix}3&9\\ 2&4 \end{pmatrix}\!,\quad B=\begin{pmatrix}0&2&3\\ 2&4&6\end{pmatrix}\!,\quad C=\begin{pmatrix} 1&0&2&1&3\\ 2&0&1&1&3\\ 3&0&3&2&5\end{pmatrix}\!.[/math]

Решение. Матрица [math]O[/math]. 1. В этой матрице нет отличных от нуля миноров первого порядка, так как все ее элементы равны нулю. Поэтому [math]\operatorname{rg}O=o[/math].


Матрица [math]A[/math]. 1. Выбираем первую строку [math](i_1=1)[/math] и первый столбец [math](j_1=1)[/math] матрицы [math]A[/math], на пересечении которых стоит ненулевой элемент [math]a_{11}=3\ne0[/math]. Получили минор [math]M_1^1=3\ne0[/math]. Следовательно, [math]\operatorname{rg}A\geqslant1[/math].


2. Добавляем к выбранным строке и столбцу еще одну строку [math]i_2=2[/math] и еще один столбец [math]j_2=2[/math]. Получаем отличный от нуля минор второго порядка


[math]M_{12}^{12}= \det{A}= \begin{vmatrix}3&9\\2&4\end{vmatrix}=-6\ne0[/math] Следовательно, [math]\operatorname{rg}A\geqslant2[/math].

3. Поскольку исчерпаны все строки и все столбцы матрицы [math]A[/math], миноров, окаймляющих [math]M_12}^{12}\ne0[/math], нет. Следовательно, [math]\operatorname{rg}A=2[/math].


Матрица [math]B[/math]. 1. Выбираем первую строку и второй столбец матрицы [math]B[/math], на пересечении которых стоит ненулевой элемент [math]b_{12}=2\ne0[/math]. Получили минор [math]M_2^1=2\ne0[/math]. Следовательно, [math]\operatorname{rg}B\geqslant1[/math].


2. Добавляем к уже выбранным вторую строку и третий столбец. Получаем минор второго порядка [math]M_{{}_{23}}^{{}^{12}}=\begin{vmatrix}2&3\\4&6\end{vmatrix}=0[/math]. Выбор оказался неудачным, так как получили нулевой минор. Вместо третьего столбца возьмем первый. Тогда получим отличный от нуля минор второго порядка [math]M_{{}_{21}}^{{}^{12}}= \begin{vmatrix}2&0\\4&2\end{vmatrix}=4\ne0[/math]. Следовательно, [math]\operatorname{rg}B\geqslant2[/math].


3. Все строки матрицы [math]B[/math] исчерпаны. Миноров третьего порядка нет. Поэтому [math]\operatorname{rg}B=2[/math].


Матрица [math]C[/math]. 1. Выбираем первую строку [math](i_1=1)[/math] и первый столбец [math](j_1=1)[/math] матрицы [math]C[/math], на пересечении которых стоит ненулевой элемент [math]a_{11}=1\ne0[/math]. Получили минор [math]M_{{}_{1}}^{{}^{1}}=1\ne0[/math]. Следовательно, [math]\operatorname{rg}C\geqslant1[/math].


2. Добавляем к выбранным строке и столбцу еще одну строку [math]i_2=2[/math] и еще один столбец [math]j_2=2[/math]. Получили минор второго порядка [math]M_{{}_{12}}^{{}^{12}}= \begin{vmatrix}1&0\\2&0\end{vmatrix}[/math]. Выбор второго столбца оказался неудачным, так как получили минор, равный нулю. Возьмем вместо второго третий столбец [math](j_2=3)[/math]. Получим минор [math]M_{{}_{13}}^{{}^{12}}= \begin{vmatrix}1&2\\2&1\end{vmatrix}=-3\ne0[/math]. Следовательно, [math]\operatorname{rg}C\geqslant2[/math].


3. Окаймляем минор [math]M_{{}_{13}}^{{}^{12}}\ne0[/math]. Имеется три окаймляющих минора


[math]M_{{}_{1\,3\,4}}^{{}^{1\,2\,3}}= \begin{pmatrix}1&2&1\\ 2&1&1\\ 3&3&2\end{pmatrix}=0,\quad M_{{}_{1\,3\,5}}^{{}^{1\,2\,3}}= \begin{pmatrix}1&2&3\\ 2&1&2\\ 3&3&5\end{pmatrix}=0,\quad M_{{}_{1\,3\,2}}^{{}^{1\,2\,3}}= \begin{pmatrix}1&2&0\\ 2&1&0\\ 3&3&0\end{pmatrix}=0.[/math]

Три определителя равны нулю, так как третья строка равна сумме первых двух строк. Следовательно, нельзя найти отличный от нуля окаймляющий минор 3-го порядка, т.е. ранг матрицы [math]C[/math] равен 2.


Замечание 3.4. Метод окаймляющих миноров позволяет уменьшить по сравнению с определением количество рассматриваемых миноров. Если в матрице размеров [math]m\times n[/math] выбран минор r-го порядка [math](r<\min\{m,n\})[/math], то количество окаймляющих его миноров (r+l)-ro порядка равно [math](m-r)(n-r)[/math], а общее количество миноров (r+1)-го порядка гораздо больше.




Метод Гаусса нахождения ранга матрицы


Пусть дана матрица [math]A[/math] размеров [math]m\times n[/math]. Для нахождения ее ранга нужно выполнить следующие действия.


1. Привести матрицу к ступенчатому виду (см. метод Гаусса).


2. В полученной матрице вычислить количество [math]r[/math] ненулевых строк. Это число равно рангу матрицы [math]A[/math].


Замечания 3.5.


1. Обоснованием этого метода служит следствие 2 теоремы 3.4. Базисным минором в матрице ступенчатого вида (см. рис. 1.4) является минор


[math]M=\begin{vmatrix}1&\ast&\cdots&\ast\\ 0&1&\cdots&\ast\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&1 \end{vmatrix},[/math]

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

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




Пример 3.7. Методом Гаусса найти ранги матриц


[math]O=\begin{pmatrix}0&0\\0&0\end{pmatrix}\!,\quad A=\begin{pmatrix}3&9\\2&4 \end{pmatrix}\!,\quad B=\begin{pmatrix}0&2&3\\2&4&6\end{pmatrix}\!,\quad C=\begin{pmatrix} 1&0&2&1&3\\ 2&0&1&1&2\\ 3&0&3&2&5\end{pmatrix}\!,\quad D=\begin{pmatrix}1&2&3\\ 0&0&0\\ 2&1&3\\ 1&1&2\\ 3&2&5 \end{pmatrix}\!.[/math]

Решение. Матрица [math]O[/math]. 1. Нулевая матрица уже имеет ступенчатый вид (см. п.2 замечаний 1.8).


2. Количество ненулевых строк равно нулю. Следовательно, [math]\operatorname{rg}O=0[/math].


Матрица [math]A[/math]. 1. Приводим матрицу [math]A[/math] к ступенчатому виду (см. пример 1.29):


[math]A\sim \begin{pmatrix}1&3\\0&1\end{pmatrix}\!.[/math]

2. В этой матрице две ненулевые строки. Следовательно, [math]\operatorname{rg}A=2[/math].


Матрица [math]B[/math]. 1. Приводим матрицу В к ступенчатому виду (см. пример 1.29):


[math]B\sim \begin{pmatrix}1&2&3\\0&1&1,\!5\end{pmatrix}\!.[/math]

В этой матрице две ненулевые строки. Следовательно, [math]\operatorname{rg}B=2[/math].


Матрица [math]C[/math]. 1. Приводим матрицу [math]C[/math] к ступенчатому виду. Взяв в качестве ведущего элемента [math]a_{11}=1[/math], делаем равными нулю остальные элементы первого столбца: ко второй строке прибавляем первую, умноженную на (-2), к третьей строке — первую, умноженную на (-3). Получаем матрицу


[math]C=\begin{pmatrix}1&0&2&1&3\\ 2&0&1&1&2\\ 3&0&3&2&5\end{pmatrix}\sim \begin{pmatrix}1&0&2&1&3\\ 0&0&-3&-1&-4\\ 0&0&-3&-1&-4\end{pmatrix}\!,[/math]

У которой имеются две равные строки. По следствию 1 теоремы 3.3 одну из равных строк вычеркиваем:

[math]C\sim \begin{pmatrix}1&0&2&1&3\\ 0&0&-3&-1&-4\end{pmatrix}\!.[/math]

Получили матрицу ступенчатого вида (см. п. 1 замечаний 1.8).

2. В этой матрице две ненулевые строки. Следовательно, [math]\operatorname{rg}C=2[/math].


Матрица [math]D[/math]. 1. Приводим матрицу [math]D[/math] к ступенчатому виду. Вычеркнув предварительно нулевую строку, берем в качестве ведущего элемента [math]a_{11}=1[/math], и делаем равными нулю остальные элементы первого столбца:


[math]D\sim \begin{pmatrix}1&2&3\\ 2&1&3\\ 1&1&2\\ 3&2&5 \end{pmatrix}\sim \begin{pmatrix}1&2&3\\ 0&-3&-3\\ 0&-1&-1\\ 0&-4&-4\end{pmatrix}\!.[/math]

Последние три строки матрицы пропорциональны. По следствию 1 теоремы 3.3 две из них можно вычеркнуть:


[math]D\sim \begin{pmatrix}1&2&3\\ 0&-1&-1\end{pmatrix}\!.[/math]

Получили матрицу ступенчатого вида (см. п. 1 замечаний 1.8).


2. В этой матрице две ненулевые строки. Следовательно, [math]\operatorname{rg}D=2[/math].


Заметим, что [math]\operatorname{rg}C=\operatorname{rg}D[/math], так как [math]D=C^T[/math] (см. следствие 1 теоремы 3.4).




Пример 3.8. Даны матрицы


[math]A=\begin{pmatrix}1&0\\0&0\end{pmatrix}\!,\quad B=\begin{pmatrix}0&0\\0&1 \end{pmatrix}\!,\quad C=\begin{pmatrix}0&1\\1&1\end{pmatrix}\!.[/math]

Найти ранги матриц: [math]A+B;~A+C;~AB;~AC[/math].


Решение. По определению имеем [math]\operatorname{rg}A=1,~ \operatorname{rg}B=1,~ \operatorname{rg}C=2[/math]. Находим суммы и произведения данных матриц, а также их ранги:


[math]A+B= \begin{pmatrix}1&0\\0&0\end{pmatrix}+ \begin{pmatrix}0&0\\0&1\end{pmatrix}= \begin{pmatrix}1&0\\0&1\end{pmatrix}= \operatorname{rg}(A+B)=2[/math], то есть [math]\operatorname{rg}(A+B)= \operatorname{rg}A+ \operatorname{rg}B[/math];

[math]A+C= \begin{pmatrix}1&0\\0&0\end{pmatrix}+ \begin{pmatrix}0&1\\1&1\end{pmatrix}= \begin{pmatrix}1&1\\1&1\end{pmatrix}= \operatorname{rg}(A+C)=1[/math], то есть [math]\operatorname{rg}(A+C)< \operatorname{rg}A+ \operatorname{rg}C[/math];

[math]A\cdot B= \begin{pmatrix}1&0\\0&0\end{pmatrix}\!\cdot \!\begin{pmatrix}0&0\\0&1\end{pmatrix}= \begin{pmatrix}0&0\\0&0\end{pmatrix}= \operatorname{rg}(A\cdot B)=0[/math], то есть [math]\operatorname{rg}(A\cdot B)< \min\{\operatorname{rg}A, \operatorname{rg}B\}[/math];

[math]A\cdot C= \begin{pmatrix}1&0\\0&0\end{pmatrix}\!\cdot \!\begin{pmatrix}0&1\\1&1\end{pmatrix}= \begin{pmatrix}0&1\\0&0\end{pmatrix}= \operatorname{rg}(A\cdot C)=1[/math], то есть [math]\operatorname{rg}(A\cdot C)= \min\{\operatorname{rg}A, \operatorname{rg}C\}[/math];

Полученные результаты иллюстрируют справедливость теорем 3.5, 3.6.


См. также Ранг системы столбцов (строк)


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved