Encontrando o ranque de uma matriz

O ranque de uma matriz é o maior número de linhas / colunas linearmente independentes da matriz. Essa classificação não é definida apenas para matrizes quadradas.

O ranque de uma matriz também pode ser definido como a maior ordem de qualquer "minor"(um "minor" é o determinante da matriz quadrada formada pela exclusão de uma linha e uma coluna de alguma matriz quadrada maior; como existem muitas linhas e colunas na matriz original, você pode fazer muitos "minors" com isso) diferente de zero na matriz.

Deixe que a matriz seja retangular e tenha tamanho $N \times M$. Observe que se a matriz for quadrada e seu determinante for diferente de zero, o ranque dela será $N$ ($=M$); caso contrário, será menor. Geralmente, o ranque de uma matriz não excede $\min (N, M)$.

Algoritmo

Você pode procurar o ranque usando a eleminação de Guass. Realizaremos as mesmas operações de quando resolver o sistema ou encontrar seu determinante. Mas se, em qualquer etapa da $i$-ésima coluna não houver linhas com uma entrada não vazia entre as que não foram selecionadas, pularemos esta etapa. Caso contrário, se encontrarmos uma linha com um elemento diferente de zero na $i$-ésima coluna durante a $i$-ésima etapa, marcaremos essa linha como a selecionada, aumentamos o ranque em um (inicialmente o ranque é definido como $0$), e executamos as operações usuais de remover esta linha do resto.

Complexidade

Esse algoritmo é executado em $\mathcal{O}(n^3)$.

Implementação

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