Алгебра : Теоремы и алгоритмы. Яцкин Н.И. - 241 стр.

§ 30                 Минорный ранг матрицы                     241

   30.4. Метод окаймляющих миноров для вычисления ран-
га матрицы. Как должно быть понятно из п. 30.1, количество ми-
норов заданного порядка может быть очень большим и их непосред-
ственный перебор может оказаться затруднительным. В этом пунк-
те мы опишем алгоритм вычисления минорного ранга матрицы (с
отысканием рангового минора), использующий некоторое сокраще-
ние перебора миноров.
  Определение 30.4. Окаймляющим минором для некоторого
минора порядка k называется всякий минор порядка k + 1, вклю-
чающий (см. замечание 30.1) данный.
  Замечание 30.7. Легко подсчитать, что количество миноров, окай-
мляющих заданный минор порядка k, равно (m − k)(n − k).
    Предложение 30.4. Если все миноры (k +1)-го порядка, окайм-
                          k
ляющие заданный минор M 6= 0, равны нулю, то вообще все миноры
(k + 1)-го порядка равны нулю.
   Доказательство. Докажем, что rank(A) = k; тогда утверждение
предложения получится автоматически.
   Предположим противное, т. е. предположим, что rank(A) = r > k.
   Дальше рассуждение аналогично проведенному при доказатель-
стве предложения 30.3, но мы добавим к столбцам, пересекающим
минор, не r−k столбцов (вплоть до достижения базиса), а лишь один
из них. Таким же образом мы поступим при добавлении строк.
   В итоге мы получим матрицу размера (k+1)×(k+1), определитель
которой будет ненулевым минором, окаймляющим данный минор,
что противоречит условию. ¤
  Переходим к описанию алгоритма отыскания ранга матрицы ме-
тодом окаймляющих миноров.

    Д а н о: матрица A размера m × n.

  Т р е б у е т с я: вычислить rank(A) и указать какой-либо ранговый
минор.

    О п и с а н и е р а б о т ы а л г о р и т м а:
    1. Если A = O, то rank(A) = 0, рангового минора не существует.
    2. Если A 6= O, то выбираем какой-либо минор первого порядка
1
M (т. е. элемент матрицы A), отличный от нуля.