Блог

Учитывая матрицу полного ранга m на n с n> m, каков эффективный алгоритм выбора m строк из матрицы для формирования обратимой (полного ранга) подматрицы m на m?

Попробуйте это:

Пусть M — матрица, M(j) j -й столбец и M(i,j) запись в строке i и столбце j .

для j от 1 до m :

1. Выберите первую строку с ненулевой записью M(i,j) в столбце j . Эта строка называется i .
2. Используется M(i,j) для установки каждой другой записи этой строки в ноль путем вычисления

     M(k) = M(k) - M(i,k)/M(i,j) * M(j) for 1 <= k <= n and k != j
    

3. обновите матрицу столбцами, вычисленными на шаге 2.

Поскольку матрица имеет ранг m , вы найдете m строки с ненулевой записью.
Этот алгоритм выполняется O(n*m^2) .

Вы хотели выбрать m столбцов, а не m строк.

Строка — уменьшите транспонирование и выберите сводные строки транспонирования. Они соответствуют одному допустимому выбору столбцов.