Hallar el rango de una matriz

El rango de una matriz es el mayor número de filas/columnas linealmente independientes de la matriz. El rango no está definido solo para matrices cuadradas.

El rango de una matriz también se puede definir como el mayor orden de cualquier menor no nulo de la matriz.

Sea la matriz rectangular y de tamaño $N \times M$. Nótese que si la matriz es cuadrada y su determinante es no nulo, entonces el rango es $N$ ($=M$); en caso contrario será menor. En general, el rango de una matriz no supera $\min (N, M)$.

Algoritmo

Se puede buscar el rango usando eliminación gaussiana. Realizaremos las mismas operaciones que al resolver el sistema o hallar su determinante. Pero si en cualquier paso en la $i$-ésima columna no hay filas con una entrada no vacía entre las que aún no seleccionamos, entonces saltamos este paso. En caso contrario, si hallamos una fila con un elemento no nulo en la $i$-ésima columna durante el $i$-ésimo paso, entonces marcamos esta fila como seleccionada, aumentamos el rango en uno (inicialmente el rango se pone igual a $0$) y realizamos las operaciones habituales de restar esta fila del resto.

Complejidad

Este algoritmo corre en $\mathcal{O}(n^3)$.

Implementación

const double EPS = 1E-9;

int compute_rank(vector<vector<double>> A) {
    int n = A.size();
    int m = A[0].size();

    int rank = 0;
    vector<bool> row_selected(n, false);
    for (int i = 0; i < m; ++i) {
        int j;
        for (j = 0; j < n; ++j) {
            if (!row_selected[j] && abs(A[j][i]) > EPS)
                break;
        }

        if (j != n) {
            ++rank;
            row_selected[j] = true;
            for (int p = i + 1; p < m; ++p)
                A[j][p] /= A[j][i];
            for (int k = 0; k < n; ++k) {
                if (k != j && abs(A[k][i]) > EPS) {
                    for (int p = i + 1; p < m; ++p)
                        A[k][p] -= A[j][p] * A[k][i];
                }
            }
        }
    }
    return rank;
}

Problemas

• TIMUS1041 Nikifor