Potenciação de Matrizes

O objetivo desta postagem é apresentar dois algoritmos para calcular a potência de uma matriz: um algoritmo com tempo linear e outro com tempo logarítmico. Também apresento os algoritmos implementados em Java.

Índice

• A Potência de uma Matriz
• Algoritmo de Potenciação de Matrizes Linear
• Algoritmo de Potenciação de Matrizes por Quadrados
• Matrizes Singulares
• Código em Java
  • Potenciação Linear
  • Potenciação por Quadrados
• Referências

A Potência de uma Matriz

A potenciação de matrizes é análoga à potenciação de números reais

$$A^4 = A\times A\times A\times A.$$

A operação de base é a multiplicação. No entanto, algumas sutilezas devem ser consideradas.

Primeiramente, a matriz deve ser quadrada. Essa restrição é uma consequência da definição do produto de matrizes: o produto de A_{n × p} por B_{m × r} exige que p seja igual a m, isto é, o número de colunas de A deve ser igual ao número de linhas de B.

Suponha que desejamos calcular A². Então, teremos:

$$A^2 = A_{n\times p}\times A_{n\times p}.$$

Pela definição do produto de matrizes, a seguinte condição é necessária: $n = p$. Logo,

$$A^2 = A_{n\times n}\times A_{n\times n}.$$

Ou seja, A deve ser uma matriz quadrada, senão o produto é impossível. Obviamente, isso é válido para qualquer expoente.

Outra sutileza é o expoente zero. Um número (diferente de zero) elevado a zero é igual a 1, que é justamente o elemento neutro da multiplicação. O elemento neutro da multiplicação de matrizes é a matriz identidade:

$$\begin{align*}&AI=IA=A\\&A^0=I.\end{align*}$$

Observe que estamos lidando apenas com expoentes inteiros positivos. A potência de matrizes para expoentes não inteiros é mais complexa e foge do escopo deste artigo. No caso dos inteiros negativos, é necessário ter um algoritmo para calcular a matriz inversa da matriz A, portanto não vou apresentar neste artigo para não estendê-lo.

Ir para o índice

Algoritmo de Potenciação de Matrizes Linear

O algoritmo mais simples de potenciação consiste em realizar as multiplicações conforme a definição:

$$A^n=A\times A\times A\times \ldots \times A$$

1. potLinearMatrix(Am × m, n)
2.      P ← Im × m
3.      para i ← 1 até n
4.           P ← matrixMult(P, A)
5.      fim_para
6.      retorne P
7. fim_potLinearMatrix

A notação Im × m indica a matriz identidade de ordem m. A função matrixMult(P, A) calcula o produto das matrizes P e A, utilizando algum algoritmo (lembre-se que existe mais de um algoritmo capaz de realizar a multiplicação de matrizes).

Se utilizarmos o algoritmo de multiplicação convencional, então a complexidade será O(m³n), onde m é a ordem da matriz.

Ir para o índice

Algoritmo de Potenciação de Matrizes por Quadrados

O algoritmo de potenciação por quadrados é um algoritmo que calcula a potência $A^n$ da seguinte forma:

$$\begin{align*}A^n=(A^{n/2})^2\quad (n\text{ é par})\\A^n=A\times(A^{(n-1)/2})^2\quad(n\text{ é ímpar})\end{align*}.$$

O algoritmo é baseado no algoritmo de potenciação por quadrados para números reais. As potências dentro dos parênteses são calculadas recursivamente. O caso base é o expoente zero ($A^0=I$). O algoritmo é apresentado a seguir:

1. potQuadMatrix(Am × m, n)
2.      se(n = 0)
3.           retorne Im × m
4.      fim_se
5.      P ← potQuadMatrix(A, n/2)
6.      se (n é par)
7.           retorne matrixMult(P, P)
8.      senão
9.           P2 ← matrixMult(P, P)
10.          retorne matrixMult(A, P2)
11.     fim_se
12.fim_potQuadMatrix

O algoritmo de potenciação por quadrados já foi apresentado no blog, porém para números reais. No entanto, o algoritmo para matrizes é praticamente o mesmo, inclusive eu sugiro que o leitor acesse o artigo do algoritmo para números reais para obter maiores informações sobre o funcionamento do mesmo: Potenciação por Quadrados.

Se a multiplicação de matrizes for realizada pelo algoritmo convencional, então a complexidade de potQuadMatrix(Am × m, n) será O(m³ log n), ou seja, a potenciação por quadrados é mais rápida do que o algoritmo de potenciação linear.

Ir para o índice

Matrizes Singulares

Uma das consequências do teorema de Binet é a igualdade a seguir:

$$\det(A^n) = (\det A)^n$$

Os algoritmos deste artigo assumem que $A^0=I$. E, de fato, a fórmula anterior é válida:

$$\begin{align*}&\det(A^0) = \det I = 1\\&\det(A^0) = (\det A)^0 = 1.\end{align*}$$

Mas e se A for uma matriz singular? Nesse caso, nos depararíamos com a indeterminação 0⁰. Portanto, se A for singular, então teremos que encarar o caso A⁰ como um erro/indeterminação.

Observação 1: uma matriz é singular quando o seu determinante é igual a zero.

Observação 2: em algumas situações excepcionais, é necessário assumir que A⁰ = I, mesmo quando A é uma matriz singular. Alguns sistemas de computação algébrica (como o GNU Octave) fazem isso.

Ir para o índice

Código em Java

Os algoritmos codificados em Java são apresentados a seguir. A única validação realizada é a verificação do sinal do expoente, pois os algoritmos apresentados não funcionam com expoentes negativos (para isso, seria necessário inverter a matriz com outro algoritmo). Aqui, assume-se que A⁰ = I, mesmo quando A é uma matriz singular.

Ambos os códigos já possuem um método de multiplicação de matrizes e um método para gerar matrizes identidades.

Potenciação Linear

//Código por Henrique Felipe (GitHub: HenriqueIni)
public class LinearPowerMatrix {    
    //Calcula A elevado a n. A matriz precisa ser quadrada.
    public static double[][] powLinear(double A[][], int n){
        if(n < 0){
            throw new IllegalArgumentException("n < 0");
        }
        int order = A.length;
        double[][] p = I(order);
        for(int i = 0; i < n; i++){
            p = matrixMult(p, A);
        }
        return p;
    }
    //Retorna uma matriz identidade n x n
    private static double[][] I(int n){
        if(n <= 0){
            throw new IllegalArgumentException("n <= 0");
        }
        double[][] I = new double[n][n];
        for(int i = 0; i < n; i++){
            I[i][i] = 1;
        }
        return I;
    }
    //Multiplica duas matrizes A e B
    private static double[][] matrixMult(double[][] A, double[][] B){        
        int n = A[0].length;        
        if(n != B.length){
            throw new IllegalArgumentException("A.columns != B.rows");
        }
        int rows = A.length;
        int cols = B[0].length;
        double[][] C = new double[rows][cols];
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                for(int k = 0; k < n; k++){
                    C[i][j] = C[i][j] + A[i][k] * B[k][j];
                }
            }
        }        
        return C;
    }
}

Ir para o índice

Potenciação por Quadrados

//Código por Henrique Felipe (GitHub: HenriqueIni)
public class SqrPowerMatrix {
    //Calcula A elevado a n. A matriz precisa ser quadrada
    public static double[][] powQuad(double A[][], int n) {
        if (n < 0) throw new IllegalArgumentException("n < 0");
        if(n == 0) return I(A.length);
        
        double[][] p = powQuad(A, n/2);
        if(n % 2 == 0){
            return matrixMult(p, p);
        }else{
            double[][] p2 = matrixMult(p, p);
            return matrixMult(A, p2);
        }        
    }
    //Retorna uma matriz identidade n x n
    private static double[][] I(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException("n <= 0");
        }
        double[][] I = new double[n][n];
        for (int i = 0; i < n; i++) {
            I[i][i] = 1;
        }
        return I;
    }

    //Multiplica duas matrizes A e B
    private static double[][] matrixMult(double[][] A, double[][] B) {
        int n = A[0].length;
        if (n != B.length) {
            throw new IllegalArgumentException("A.columns != B.rows");
        }
        int rows = A.length;
        int cols = B[0].length;
        double[][] C = new double[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                for (int k = 0; k < n; k++) {
                    C[i][j] = C[i][j] + A[i][k] * B[k][j];
                }
            }
        }
        return C;
    }
}

Ir para o índice

Referências

• FELIPE, H. Potenciação por Quadrados. Acesso em 18 de outubro de 2017.
• FELIPE, H. Algoritmo Clássico de Multiplicação de Matrizes. Acesso em 18 de outubro de 2017.