‹-- Назад

Ранг матрицы

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

        Определение 14.10   Пусть дана матрица $ A$ размеров $ m\times n$ и число $ k$ , не превосходящее наименьшего из чисел $ m$ и $ n$ : $ {k\leqslant \min(m,n)}$ . Выберем произвольно $ k$ строк матрицы $ A$ и $ k$ столбцов (номера строк могут отличаться от номеров столбцов). Определитель матрицы, составленной из элементов, стоящих на пересечении выбранных $ k$ строк и $ k$ столбцов, называется минором порядка $ k$ матрицы $ A$ .         

        Пример 14.9   Пусть $ {A=\left(\begin{array}{rrrr}1&2&-1&0\\ 3&4&-5&6\\ 5&-2&-3&-4\end{array}\right)}$ .

Минором первого порядка является любой элемент матрицы. Так 2, $ -5$ , $ -4$  -- миноры первого порядка.

Миноры второго порядка:

  1. возьмем строки 1, 2, столбцы 1, 2, получим минор $ {\left\vert\begin{array}{rr}1&2\\ 3&4
\end{array}\right\vert=-2}$ ;
  2. возьмем строки 1, 3, столбцы 2, 4, получим минор $ {\vphantom{\begin{array}{r}1\\ 2\\ 3\end{array}}\left\vert\begin{array}{rr}2&0\\ -2&-4\end{array}\right\vert=-8}$ ;
  3. возьмем строки 2, 3, столбцы 1, 4, получим минор $ {\left\vert\begin{array}{rr}3&6\\ 5&-4
\end{array}\right\vert=-42}.$

Миноры третьего порядка:

строки здесь можно выбрать только одним способом,

  1. возьмем столбцы 1, 3, 4, получим минор $ {\vphantom{\begin{array}{r}1\\ 2\\ 3\\ 1\end{array}}\left\vert\begin{array}{rrr}1&-1&0\\ 3&-5&6\\ 5&-3&-4\end{array}\right\vert=-4}$ ;
  2. возьмем столбцы 1, 2, 3, получим минор $ {\left\vert\begin{array}{rrr}1&2&-1\\ 3&4&-5\\ 5&-2&-3\end{array}\right\vert=-28}$ .
        

        Предложение 14.23   Если все миноры матрицы $ A$ порядка $ k$ равны нулю, то все миноры порядка $ {k+1}$ , если такие существуют, тоже равны нулю.

        Доказательство.     Возьмем произвольный минор порядка $ {k+1}$ . Это определитель матрицы порядка $ {k+1}$ . Разложим его по первой строке. Тогда в каждом слагаемом разложения один из множителей будет являться минором порядка $ k$ исходной матрицы. По условию миноры порядка $ k$ равны нулю. Поэтому и минор порядка $ {k+1}$ будет равен нулю.     

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

Единое, стандартное, обозначение ранга матрицы отсутствует. Следуя учебнику  [1], мы будем обозначать его $ {\rm Rg}A$ .

        Пример 14.10   Матрица $ A$ примера 14.9 имеет ранг 3, так как есть минор третьего порядка, отличный от нуля, а миноров четвертого порядка нет.

Ранг матрицы $ B=\left(\begin{array}{rrr}0&0&1\\ 0&0&0\end{array}\right)$ равен 1, так как есть ненулевой минор первого порядка (элемент матрицы $ b_{13}$ ), а все миноры второго порядка равны нулю.

Ранг невырожденной квадратной матрицы порядка $ n$ равен $ n$ , так как ее определитель является минором порядка $ n$ и у невырожденной матрицы отличен от нуля.         

        Предложение 14.24   При транспонировании матрицы ее ранг не меняется, то есть $ {{\rm Rg}A={\rm Rg}A^\top}$ .

        Доказательство.     Транспонированный минор исходной матрицы $ A$ будет являться минором транспонированной матрицы $ A^\top$ , и наоборот, любой минор $ A^\top$ является транспонированным минором исходной матрицы $ A$ . При транспонировании определитель (минор) не меняется ( предложение 14.6). Поэтому если все миноры порядка $ {r+1}$ в исходной матрице равны нулю, то все миноры того же порядка в $ A^\top$ тоже равны нулю. Если же минор порядка $ r$ в исходной матрице отличен от нуля, то в $ A^\top$ есть минор того же порядка, отличный от нуля. Следовательно, $ {{\rm Rg}A={\rm Rg}A^\top}$ .     

        Определение 14.12   Пусть ранг матрицы равен $ r$ . Тогда любой минор порядка $ r$ , отличный от нуля, называется базисным минором.         

        Пример 14.11   Пусть $ {A=\left(\begin{array}{rrr}1&3&6\\ 2&1&2\\ 3&4&8\end{array}\right)}$ . Определитель матрицы $ A$ равен нулю, так как третья строка равна сумме первых двух. Минор второго порядка, расположенный в первых двух строках и первых двух столбцах, равен $ {\left\vert\begin{array}{rr}1&3\\ 2&1\end{array}\right\vert=-5\ne0}$ . Следовательно, ранг матрицы равен двум, и рассмотренный минор является базисным.

Базисным минором является также минор, расположенный, скажем, в первой и третьей строках, первом и третьем столбцах: $ {\left\vert\begin{array}{rr}1&6\\ 3&8\end{array}\right\vert=-10\ne0}$ . Базисным будет минор во второй и третьей строках, первом и третьем столбцах: $ {\left\vert\begin{array}{rr}2&2\\ 3&8\end{array}\right\vert=-10\ne0}$ .

Минор в первой и второй строках, втором и третьем столбцах $ \left\vert\begin{array}{rr}3&6\\ 1&2\end{array}\right\vert$ равен нулю и поэтому не будет базисным. Читатель может самостоятельно проверить, какие еще миноры второго порядка будут базисными, а какие нет.         

Так как столбцы (строки) матрицы можно складывать, умножать на числа, образовывать линейные комбинации, то можно ввести определения линейной зависимости и линейной независимости системы столбцов (строк) матрицы. Эти определения аналогичны таким же определениям 10.14, 10.15 для векторов.

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

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

Верно также следующеее предложение, аналогичное предложению 10.6.

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

Сформулируем теорему, которая называется теорема о базисном миноре.

        Теорема 14.2   Любой столбец матрицы является линейной комбинацией столбцов, проходящих через базисный минор.     

Доказательство можно найти в учебниках по линейной алгебре, например, в [1], [3].

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

        Доказательство.     Пусть ранг матрицы $ A$ равен $ r$ . Возьмем столбцы, проходящие через базисный минор. Предположим, что эти столбцы образуют линейно зависимую систему. Тогда один из столбцов является линейной комбинацией других. Поэтому в базисном миноре один столбец будет линейной комбинацией других столбцов. По предложениям 14.15 и 14.18 этот базисный минор должен быть равен нулю, что противоречит определению базисного минора. Следовательно, предположение о том, что столбцы, проходящие через базисный минор, линейно зависимы, не верно. Итак, максимальное число столбцов, образующих линейно независимую систему, больше либо равно $ r$ .

Предположим, что $ {r+1}$ столбцов образуют линейно независимую систему. Составим из них матрицу $ B$ . Все миноры матрицы $ B$ являются минорами матрицы $ A$ . Поэтому базисный минор матрицы $ B$ имеет порядок не больше $ r$ . По теореме о базисном миноре, столбец, не проходящий через базисный минор матрицы $ B$ , является линейной комбинацией столбцов, проходящих через базисный минор, то есть столбцы матрицы $ B$ образуют линейно зависимую систему. Это противоречит выбору столбцов, образующих матрицу $ B$ . Следовательно, максимальное число столбцов, образующих линейно независимую систему, не может быть больше $ r$ . Значит, оно равно $ r$ , что и утверждалось.     

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

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

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

        Доказательство.     Пусть порядок матрицы $ A$ равен $ n$ . Определитель является единственным минором квадратной матрицы, имеющим порядок $ n$ . Так как он равен нулю, то $ {{\rm Rg}A<n}$ . Следовательно, система из $ n$ столбцов (строк) является линейно зависимой, то есть один из столбцов (одна из строк) является линейной комбинацией остальных.     

Результаты предложений 14.15, 14.18 и 14.28 дают следующую теорему.

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

Нахождение ранга матрицы с помощью вычисления всех ее миноров требует слишком большой вычислительной работы. (Читатель может проверить, что в квадратной матрице четвертого порядка 36 миноров второго порядка.) Поэтому для нахождения ранга применяется другой алгоритм. Для его описания потребуется ряд дополнительных сведений.

        Определение 14.15   Назовем элементарными преобразованиями матриц следующие действия над ними:

1) перестановка строк или столбцов;
2) умножение строки или столбца на число отличное от нуля;
3) добавление к одной из строк другой строки, умноженной на число или добавление к одному из столбцов другого столбца, умноженного на число.
        

        Предложение 14.29   При элементарных преобразованиях ранг матрицы не меняется.

        Доказательство.     Пусть ранг матрицы $ A$ равен $ r$ , $ A'$  -- матрица, получившаяся в результате выполнения элементарного преобразования.

Рассмотрим перестановку строк. Пусть $ M$  -- минор матрицы $ A$ , тогда в матрице $ A'$ есть минор $ M'$ , который или совпадает с $ M$ , или отличается от него перестановкой строк. И наоборот, любому минору $ N'$ матрицы $ A'$ можно сопоставить минор матрицы $ A$ или совпадающий с $ N'$ , или отличающийся от него порядком строк. Поэтому из того, что в матрице $ A$ все миноры порядка $ {r+1}$ равны нулю, следует, что в матрице $ A'$ тоже все миноры этого порядка равны нулю. И так как в матрице $ A$ есть минор порядка $ r$ , отличный от нуля, то и в матрице $ A'$ тоже есть минор порядка $ r$ , отличный от нуля, то есть $ {{\rm Rg}A'=r}$ .

Рассмотрим умножение строки на число $ {\alpha}$ , отличное от нуля. Минору $ M$ из матрицы $ A$ соответствует минор $ M'$ из матрицы $ A'$ или совпадающий с $ M$ , или отличающийся от него только одной строкой, которая получается из строки минора $ M$ умножением на число, отличное от нуля. В последнем случае $ {M'={\alpha}M}$ . Во всех случаях или $ M$ и $ M'$ одновременно равны нулю, или одновременно отличны от нуля. Следовательно, $ {{\rm Rg}A'=r}$ .

Пусть к $ i$ -ой строке матрицы $ A$ прибавлена ее $ j$ -ая строка, умноженная на число $ {\lambda}$ . Рассмотрим миноры порядка $ {r+1}$ в матрице $ A'$ . Если через минор $ M'$ не проходит $ i$ -ая строка, то он совпадает с минором $ M$ , расположенным в тех же строках и столбцах в матрице $ A$ , и следовательно, равен нулю.

Если через минор $ M'$ проходят и $ i$ -ая и $ j$ -ая строки, то он получается из минора $ M$ , расположенного в тех же строках и столбцах матрицы $ A$ , прибавлением к $ i$ -ой строке минора $ M$ $ j$ -ой строки, умноженной на $ {\lambda}$ . По свойству определителя $ {M=M'}$ . Следовательно, $ {M'=0}$ .

Пусть через минор $ M'$ проходит $ i$ -ая строка и не проходит $ j$ -ая. Тогда $ M'$ отличается от $ M$ $ i$ -ой строкой. Эта строка в $ M'$ является строкой $ M$ , к которой добавлены элементы $ j$ -ой строки, умноженные на $ {\lambda}$ . По свойствам определителей $ {M'=M+{\lambda}(\pm N)}$ , где $ N$  -- минор порядка $ {r+1}$ матрицы $ A$ , стоящий в $ j$ -ой строке и в тех же строках, что и минор $ M$ , исключая $ i$ -ую, а знак "$ \pm$ " связан с возможным изменением порядка строк. Так как все миноры порядка $ {r+1}$ в матрице $ A$ равны нулю, то $ {M'=0}$ .

Итак, в матрице $ A'$ все миноры порядка $ {r+1}$ равны нулю. Следовательно, $ {{\rm Rg}A'\leqslant r}$ , то есть при выполнении элементарного преобразования третьего типа ранг не может повыситься. Предположим, что $ {{\rm Rg}A'=k}$ , и $ {k<r}$ . Тогда в матрице $ A'$ к $ i$ -ой строке прибавим $ j$ -ую строку, умноженную на число $ (-{\lambda})$ . В результате получим исходную матрицу $ A$ . По только что доказанному $ {{\rm Rg}A\leqslant k<r}$ . Получили противоречие: $ {r<r}$ . Предположение $ {k<r}$ не верно, следовательно, $ {{\rm Rg}A'=r}$ .     

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

Алгоритм нахождения ранга матрицы.

Пусть требуется вычислить ранг матрицы $ A$ размеров $ m\times n$ . Если матрица $ A$ нулевая, то по определению $ {{\rm Rg}A=0}$ . В противном случае с помощью перестановки строк и столбцов матрицы добиваемся того, чтобы в левом верхнем углу матрицы стоял ненулевой элемент. Итак, считаем, что $ {a_{11}\ne0}$ .

Первую строку оставляем без изменений. Ко второй строке прибавляем первую, умноженную на число $ \left(-\dfrac{a_{21}}{a_{11}}\right)$ . В результате вторая строка принимает вид

$\displaystyle \left(\begin{array}{cccc}0&a_{22}^{(1)}&\dots&a_{2n}^{(1)}\end{array}\right).$

Затем к третьей строке прибавляем первую строку, умноженную на число $ \left(-\dfrac{a_{31}}{a_{11}}\right)$ . В результате третья строка принимает вид

$\displaystyle \left(\begin{array}{cccc}0&a_{32}^{(1)}&\dots&a_{3n}^{(1)}\end{array}\right).$

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

Преобразованная матрица имеет вид

$\displaystyle A^{(1)}=\left(\begin{array}{ccccc}a_{11}&a_{12}&a_{13}&\dots&a_{1...
...ots&\dots\\
0&a_{m2}^{(1)}&a_{m3}^{(1)}&\dots&a_{mn}^{(1)}\end{array}\right).$

Если все строки, начиная со второй, в полученной матрице нулевые, то ее ранг равен 1, так как есть минор первого порядка, отличный от нуля $ a_{11}$ . В противном случае перестановкой строк и столбцов матрицы с номерами, большими единицы, добиваемся, чтобы второй элемент второй строки был отличен от нуля. Итак, считаем, что $ {a_{22}^{(1)}\ne0}$ .

Первую и вторую строки оставляем без изменений. К третьей строке прибавляем вторую, умноженную на число $ \left(-\dfrac{a_{32}^{(1)}}{a_{22}^{(1)}}\right)$ . В результате получим, что второй элемент третьей строки равен нулю. Затем к четвертой строке прибавляем вторую, умноженную на число $ \left(-\dfrac{a_{42}^{(1)}}{a_{22}^{(1)}}\right)$ , и т.д. В результате получаем матрицу

$\displaystyle A^{(2)}=\left(\begin{array}{ccccc}a_{11}&a_{12}&a_{13}&\dots&a_{1...
...ts&\dots&\dots&\dots\\
0&0&a_{m3}^{(2)}&\dots&a_{mn}^{(2)}\end{array}\right).$

Если все строки, начиная с третьей, нулевые, то $ {{\rm Rg}A^{(2)}=2}$ , так как минор $ {\left\vert\begin{array}{cc}a_{11}&a_{12}\\ 0&a_{22}^{(1)}\end{array}\right\vert=a_{11}a_{22}^{(1)}\ne0}$ . В противном случае перестановкой строк и столбцов с номерами, большими двух, добиваемся, чтобы третий элемент третьей строки был отличен от нуля. Далее, добавлением третьей строки, умноженной на соответствующие числа, к строкам с большими номерами получаем нули в третьем столбце, начиная с четвертого элемента, и т.д.

На каком-то этапе мы придем к матрице, у которой все строки, начиная с $ {(r+1)}$-ой , равны нулю (или отсутствуют при $ {r=m\leqslant n}$ ), а минор в первых $ r$ строках и первых $ r$ столбцах является определителем треугольной матрицы с ненулевыми элементами на диагонали. Ранг такой матрицы равен $ r$ . Следовательно, $ {{\rm Rg}A=r}$ .     

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

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

        Пример 14.12   Найдите ранг матрицы $ A=\left(\begin{array}{rrrr}2&2&-1&0\\ 3&1&4&-1\\ 5&9&-13.5&1\\ 3&5&-7&1\end{array}\right)$ .

Решение. Первую строку оставляем без изменений. Чтобы избежать появления дробей, умножим вторую, третью и четвертую строки на 2:

$\displaystyle A^{(1)}=\left(\begin{array}{rrrr}2&2&-1&0\\ 6&2&8&-2\\ 10&18&-27&2\\ 6&10&-14&2\end{array}\right).$

Первую строку умножим на $ (-3)$ и прибавим ко второй. Получим строку $ {\left(\begin{array}{rrrr}0&-4&11&-2\end{array}\right)}$ . Первую строку умножим на $ (-5)$ и прибавим к третьей. Получим строку $ {\left(\begin{array}{rrrr}0&8&-22&2\end{array}\right)}$ . Первую строку умножим на $ (-3)$ и прибавим к четвертой. Получим строку $ {\left(\begin{array}{rrrr}0&4&-11&2\end{array}\right)}$ . В итоге имеем матрицу

$\displaystyle A^{(2)}=\left(\begin{array}{rrrr}2&2&-1&0\\ 0&-4&11&-2\\ 0&8&-22&2\\ 0&4&-11&2\end{array}\right).$

Вторую строку оставляем без изменений. К третьей строке прибавляем вторую, умноженную на 2. Получим строку $ {\left(\begin{array}{rrrr}0&0&0&-2\end{array}\right)}$ . К четвертой строке прибавляем вторую. Получим нулевую строку. Преобразованная матрица имеет вид

$\displaystyle A^{(3)}=\left(\begin{array}{rrrr}2&2&-1&0\\ 0&-4&11&-2\\ 0&0&0&-2\\ 0&0&0&0\end{array}\right).$

Поменяем местами третий и четвертый столбцы:

$\displaystyle A^{(4)}=\left(\begin{array}{rrrr}2&2&0&-1\\ 0&-4&-2&11\\ 0&0&-2&0\\ 0&0&0&0\end{array}\right).$

Базисный минор матрицы $ A^{(4)}$ стоит в первых трех столбцах и первых трех строках, $ {{\rm Rg}A^{(4)}=3}$ . Следовательно, $ {{\rm Rg}A=3}$ .         

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