Produto de matrizes

Para a multiplicação de matrizes, o número de colunas na primeira matriz deve ser igual ao número de linhas na segunda matriz. A matriz resultante tem o número de linhas da primeira e o número de colunas da segunda matriz.

Em matemática, especificamente em álgebra linear, a multiplicação de matrizes é uma operação binária que produz uma matriz a partir de duas matrizes. Para a multiplicação de matrizes, o número de colunas na primeira matriz deve ser igual ao número de linhas na segunda matriz. A matriz resultante, conhecida como produto matricial, tem o número de linhas da primeira e o número de colunas da segunda matriz. O produto das matrizes A e B é denotado como AB.

A multiplicação de matrizes foi descrita pela primeira vez pelo matemático francês Jacques Philippe Marie Binet em 1812, para representar a composição de aplicações lineares que são representadas por matrizes. A multiplicação de matrizes é, portanto, uma ferramenta básica da álgebra linear e, como tal, tem inúmeras aplicações em muitas áreas da matemática, bem como na matemática aplicada, estatística, física, economia e engenharia. Calcular produtos de matrizes é uma operação central em todas as aplicações computacionais da álgebra linear.

Notação

Este artigo usará as seguintes convenções de notação: matrizes são representadas por letras maiúsculas em negrito, e.g. A; vetores em minúsculas em negrito, e.g. a; e as entradas de vetores e matrizes são itálicas (são números de um corpo), e.g. A e a. A notação de índices é frequentemente a maneira mais clara de expressar definições e é usada como padrão na literatura. A entrada na linha i, coluna j da matriz A é indicada por (A)ij, Aij ou aij. Em contraste, um único subscrito, e.g. A1, A2, é usado para selecionar uma matriz (não uma entrada de matriz) de uma coleção de matrizes.

Definições

Matriz vezes matriz

Se A é uma matriz m × n e B é uma matriz n × p, 𝐀=(a11a12⋯a1na21a22⋯a2n⋮⋮⋱⋮am1am2⋯amn),𝐁=(b11b12⋯b1pb21b22⋯b2p⋮⋮⋱⋮bn1bn2⋯bnp) o produto matricial C = AB (denotado sem sinais de multiplicação ou pontos) é definido como a matriz m × p 𝐂=(c11c12⋯c1pc21c22⋯c2p⋮⋮⋱⋮cm1cm2⋯cmp) tal que cij=ai1b1j+ai2b2j+⋯+ainbnj=∑k=1naikbkj, para i = 1, ..., m e j = 1, ..., p.

Isto é, a entrada ⁠cij⁠ do produto é obtida multiplicando termo a termo as entradas da i-ésima linha de A e da j-ésima coluna de B, e somando esses n produtos. Em outras palavras, ⁠cij⁠ é o produto escalar da i-ésima linha de A e da j-ésima coluna de B.

Portanto, AB também pode ser escrito como 𝐂=(a11b11+⋯+a1nbn1a11b12+⋯+a1nbn2⋯a11b1p+⋯+a1nbnpa21b11+⋯+a2nbn1a21b12+⋯+a2nbn2⋯a21b1p+⋯+a2nbnp⋮⋮⋱⋮am1b11+⋯+amnbn1am1b12+⋯+amnbn2⋯am1b1p+⋯+amnbnp)

Assim, o produto AB é definido se e somente se o número de colunas em A for igual ao número de linhas em B, neste caso n.

Na maioria dos cenários, as entradas são números, mas podem ser qualquer tipo de objetos matemáticos para os quais uma adição e uma multiplicação são definidas, que são associativas, e tais que a adição é comutativa, e a multiplicação é distributiva em relação à adição. Em particular, as entradas podem ser próprias matrizes (ver matriz bloco).

Matriz vezes vetor

Um vetor 𝐱 de comprimento n pode ser visto como um vetor coluna, correspondendo a uma matriz n×1 𝐗 cujas entradas são dadas por 𝐗i1=𝐱i. Se 𝐀 é uma matriz m×n, o produto matriz-vetor denotado por 𝐀𝐱 é então o vetor 𝐲 que, visto como um vetor coluna, é igual à matriz m×1 𝐀𝐗. Em notação de índices, isso equivale a:

yi=∑j=1naijxj.

Uma maneira de ver isso é que as mudanças de vetor "simples" para vetor coluna e vice-versa são assumidas e deixadas implícitas.

Vetor vezes matriz

Similarmente, um vetor 𝐱 de comprimento n pode ser visto como um vetor linha, correspondendo a uma matriz 1×n. Para deixar claro que um vetor linha é pretendido, é costume neste contexto representá-lo como a transposta de um vetor coluna; assim, ver-se-ão notações como 𝐱T𝐀. A identidade 𝐱T𝐀=(𝐀T𝐱)T é válida. Em notação de índices, se 𝐀 é uma matriz n×p, 𝐱T𝐀=𝐲T equivale a: yk=∑j=1nxjajk.

Vetor vezes vetor

Um vetor com n componentes pode ser representado como uma matriz 1 × n (um vetor linha) ou como uma matriz n × 1 (um vetor coluna). Supondo que 𝐚 e 𝐛 são ambos vetores coluna, o produto escalar (ou produto interno) 𝐚⋅𝐛 é igual à única entrada da matriz 1×1 resultante da multiplicação matricial do vetor linha 𝐚T com o vetor coluna 𝐛, i.e. 𝐚T𝐛.

A multiplicação matricial entre o vetor coluna 𝐚 e o vetor linha 𝐛T, também conhecida como produto externo 𝐚𝐛T, dará, em vez disso, uma matriz n × n.

Ilustração

A figura à direita ilustra diagramaticamente o produto de duas matrizes A e B, mostrando como cada interseção na matriz produto corresponde a uma linha de A e uma coluna de B. [a11a12⋅⋅a31a32⋅⋅]4×2 matriz[⋅b12b13⋅b22b23]2×3 matriz=[⋅c12⋅⋅⋅⋅⋅⋅c33⋅⋅⋅]4×3 matriz

Os valores nas interseções, marcados com círculos na figura à direita, são: c12=a11b12+a12b22c33=a31b13+a32b23.

Aplicações fundamentais

Historicamente, a multiplicação de matrizes foi introduzida para facilitar e esclarecer cálculos em álgebra linear. Esta forte relação entre multiplicação de matrizes e álgebra linear permanece fundamental em toda a matemática, bem como na física, química, engenharia e ciência da computação.

Aplicações lineares

Se um espaço vetorial tem uma base finita, seus vetores são cada um representados de forma única por uma sequência finita de escalares, chamada de vetor de coordenadas, cujos elementos são as coordenadas do vetor na base. Esses vetores de coordenadas formam outro espaço vetorial, que é isomorfo ao espaço vetorial original. Um vetor de coordenadas é comumente organizado como uma matriz coluna (também chamada de vetor coluna), que é uma matriz com apenas uma coluna. Assim, um vetor coluna representa tanto um vetor de coordenadas quanto um vetor do espaço vetorial original.

Uma aplicação linear A de um espaço vetorial de dimensão n para um espaço vetorial de dimensão m aplica um vetor coluna

𝐱=(x1x2⋮xn)

no vetor coluna

𝐲=A(𝐱)=(a11x1+⋯+a1nxna21x1+⋯+a2nxn⋮am1x1+⋯+amnxn).

A aplicação linear A é, portanto, definida pela matriz

𝐀=(a11a12⋯a1na21a22⋯a2n⋮⋮⋱⋮am1am2⋯amn),

e aplica o vetor coluna 𝐱 no produto matricial

𝐲=𝐀𝐱.

Se B é outra aplicação linear do espaço vetorial precedente de dimensão m para um espaço vetorial de dimensão p, ela é representada por uma matriz ⁠p×m⁠ 𝐁. Um cálculo direto mostra que a matriz da aplicação composta ⁠B∘A⁠ é o produto matricial 𝐁𝐀. A fórmula geral ⁠(B∘A)(𝐱)=B(A(𝐱))⁠) que define a composição de funções é instanciada aqui como um caso específico da associatividade do produto matricial (ver § Associatividade abaixo):

(𝐁𝐀)𝐱=𝐁(𝐀𝐱)=𝐁𝐀𝐱.

Rotações geométricas

Usando um sistema de coordenadas cartesianas em um plano euclidiano, a rotação por um ângulo α em torno da origem é uma aplicação linear. Mais precisamente, [x′y′]=[cos⁡α−sin⁡αsin⁡αcos⁡α][xy], onde o ponto de origem (x,y) e sua imagem (x′,y′) são escritos como vetores coluna.

A composição da rotação por α e por β corresponde então ao produto matricial [cos⁡β−sin⁡βsin⁡βcos⁡β][cos⁡α−sin⁡αsin⁡αcos⁡α]=[cos⁡βcos⁡α−sin⁡βsin⁡α−cos⁡βsin⁡α−sin⁡βcos⁡αsin⁡βcos⁡α+cos⁡βsin⁡α−sin⁡βsin⁡α+cos⁡βcos⁡α]=[cos⁡(α+β)−sin⁡(α+β)sin⁡(α+β)cos⁡(α+β)], onde identidades trigonométricas apropriadas são empregadas para a segunda igualdade. Ou seja, a composição corresponde à rotação pelo ângulo α+β, como esperado.

Alocação de recursos em economia

O cálculo da entrada inferior esquerda de 𝐀𝐁 corresponde à consideração de todos os caminhos (destacados) do bem básico b4 ao produto final f1 no grafo de fluxo de produção.

Como exemplo, uma fábrica fictícia usa 4 tipos de bens básicos, b1,b2,b3,b4 para produzir 3 tipos de bens intermediários, m1,m2,m3, que por sua vez são usados para produzir 3 tipos de produtos finais, f1,f2,f3. As matrizes

𝐀=(101211011112)   e   𝐁=(121231422)

fornecem a quantidade de bens básicos necessários para uma dada quantidade de bens intermediários, e a quantidade de bens intermediários necessários para uma dada quantidade de produtos finais, respectivamente. Por exemplo, para produzir uma unidade do bem intermediário m1, uma unidade do bem básico b1, duas unidades de b2, nenhuma unidade de b3 e uma unidade de b4 são necessárias, correspondendo à primeira coluna de 𝐀.

Usando a multiplicação de matrizes, calcula-se

𝐀𝐁=(543895 6531196);

esta matriz fornece diretamente as quantidades de bens básicos necessários para determinadas quantidades de bens finais. Por exemplo, a entrada inferior esquerda de 𝐀𝐁 é calculada como 1⋅1+1⋅2+2⋅4=11, refletindo que 11 unidades de b4 são necessárias para produzir uma unidade de f1. De fato, uma unidade de b4 é necessária para m1, uma para cada uma das duas m2, e 2 para cada uma das quatro unidades de m3 que entram na unidade de f1, veja a figura.

Para produzir, por exemplo, 100 unidades do produto final f1, 80 unidades de f2 e 60 unidades de f3, as quantidades necessárias de bens básicos podem ser calculadas como

(𝐀𝐁)(1008060)=(1000182011802180),

isto é, 1000 unidades de b1, 1820 unidades de b2, 1180 unidades de b3, 2180 unidades de b4 são necessárias. Da mesma forma, a matriz produto 𝐀𝐁 pode ser usada para calcular as quantidades necessárias de bens básicos para outros dados de quantidade de produtos finais.

Sistema de equações lineares

A forma geral de um sistema de equações lineares é

a11x1+⋯+a1nxn=b1,a21x1+⋯+a2nxn=b2,⋮am1x1+⋯+amnxn=bm.

Usando a mesma notação acima, tal sistema é equivalente à única equação matricial

𝐀𝐱=𝐛.

Produto escalar, forma bilinear e forma sesquilinear

O produto escalar de dois vetores coluna é a única entrada do produto matricial

𝐱𝖳𝐲,

onde 𝐱𝖳 é o vetor linha obtido por transpondo 𝐱. (Como de costume, uma matriz 1×1 é identificada com sua única entrada.)

Mais geralmente, qualquer forma bilinear sobre um espaço vetorial de dimensão finita pode ser expressa como um produto matricial

𝐱𝖳𝐀𝐲,

e qualquer forma sesquilinear pode ser expressa como

𝐱†𝐀𝐲,

onde 𝐱† denota a transposta conjugada de 𝐱 (conjugado da transposta, ou equivalentemente transposta do conjugado).

Propriedades gerais

A multiplicação de matrizes compartilha algumas propriedades com a multiplicação usual. No entanto, a multiplicação de matrizes não é definida se o número de colunas do primeiro fator difere do número de linhas do segundo fator, e é não comutativa, mesmo quando o produto permanece definido após mudar a ordem dos fatores.

Não comutatividade

Uma operação é comutativa se, dados dois elementos A e B tais que o produto 𝐀𝐁 é definido, então 𝐁𝐀 também é definido, e 𝐀𝐁=𝐁𝐀.

Se A e B são matrizes de tamanhos respectivos ⁠m×n⁠ e ⁠p×q⁠, então 𝐀𝐁 é definido se ⁠n=p⁠, e 𝐁𝐀 é definido se ⁠m=q⁠. Portanto, se um dos produtos é definido, o outro não precisa ser definido. Se ⁠m=q≠n=p⁠, os dois produtos são definidos, mas têm tamanhos diferentes; portanto, não podem ser iguais. Somente se ⁠m=q=n=p⁠, isto é, se A e B são matrizes quadradas do mesmo tamanho, ambos os produtos são definidos e do mesmo tamanho. Mesmo neste caso, tem-se em geral

𝐀𝐁≠𝐁𝐀.

Por exemplo

(0100)(0010)=(1000),

mas

(0010)(0100)=(0001).

Este exemplo pode ser expandido para mostrar que, se A é uma matriz ⁠n×n⁠ com entradas em um corpo F, então 𝐀𝐁=𝐁𝐀 para toda matriz ⁠n×n⁠ B com entradas em F, se e somente se 𝐀=c𝐈 onde ⁠c∈F⁠, e I é a ⁠n×n⁠ matriz identidade. Se, em vez de um corpo, as entradas devem pertencer a um anel, então deve-se adicionar a condição de que c pertence ao centro do anel.

Um caso especial onde a comutatividade ocorre é quando D e E são duas matrizes diagonais (do mesmo tamanho); então DE = ED. Novamente, se as matrizes são sobre um anel geral em vez de um corpo, as entradas correspondentes em cada uma também devem comutar entre si para que isso seja válido.

Distributividade

O produto matricial é distributivo em relação à adição de matrizes. Isto é, se A, B, C, D são matrizes de tamanhos respectivos m × n, n × p, n × p e p × q, respectivamente, tem-se (distributividade à esquerda)

𝐀(𝐁+𝐂)=𝐀𝐁+𝐀𝐂,

e (distributividade à direita)

(𝐁+𝐂)𝐃=𝐁𝐃+𝐂𝐃.

Isso resulta da distributividade para coeficientes por

∑kaik(bkj+ckj)=∑kaikbkj+∑kaikckj
∑k(bik+cik)dkj=∑kbikdkj+∑kcikdkj.

Produto com um escalar

Se A é uma matriz e c um escalar, então as matrizes c𝐀 e 𝐀c são obtidas multiplicando à esquerda ou à direita todas as entradas de A por c. Se os escalares têm a propriedade comutativa, então c𝐀=𝐀c.

Se o produto 𝐀𝐁 é definido (isto é, o número de colunas de A é igual ao número de linhas de B), então

c(𝐀𝐁)=(c𝐀)𝐁 e (𝐀𝐁)c=𝐀(𝐁c).

Se os escalares têm a propriedade comutativa, então todas as quatro matrizes são iguais. Mais geralmente, todas as quatro são iguais se c pertence ao centro de um anel contendo as entradas das matrizes, porque neste caso, cX = Xc para todas as matrizes X.

Essas propriedades resultam da bilinearidade do produto de escalares:

c(∑kaikbkj)=∑k(caik)bkj
(∑kaikbkj)c=∑kaik(bkjc).

Transposição

Se os escalares têm a propriedade comutativa, a transposta de um produto de matrizes é o produto, na ordem inversa, das transpostas dos fatores. Isto é

(𝐀𝐁)𝖳=𝐁𝖳𝐀𝖳

onde T denota a transposta, isto é, a troca de linhas e colunas.

Esta identidade não é válida para entradas não comutativas, pois a ordem entre as entradas de A e B é invertida, quando se expande a definição do produto matricial.

Conjugado complexo

Se A e B têm entradas complexas, então

(𝐀𝐁)∗=𝐀∗𝐁∗

onde * denota o conjugado complexo entrada a entrada de uma matriz.

Isso resulta da aplicação à definição de produto matricial do fato de que o conjugado de uma soma é a soma dos conjugados das parcelas e o conjugado de um produto é o produto dos conjugados dos fatores.

A transposição atua sobre os índices das entradas, enquanto a conjugação atua independentemente sobre as próprias entradas. Resulta que, se A e B têm entradas complexas, tem-se

(𝐀𝐁)†=𝐁†𝐀†,

onde † denota a transposta conjugada (conjugado da transposta, ou equivalentemente transposta do conjugado).

Associatividade

Dadas três matrizes A, B e C, os produtos (AB)C e A(BC) são definidos se e somente se o número de colunas de A for igual ao número de linhas de B, e o número de colunas de B for igual ao número de linhas de C (em particular, se um dos produtos é definido, então o outro também é definido). Neste caso, tem-se a propriedade associativa

(𝐀𝐁)𝐂=𝐀(𝐁𝐂).

Como para qualquer operação associativa, isso permite omitir parênteses e escrever os produtos acima como ⁠𝐀𝐁𝐂.⁠

Isso se estende naturalmente ao produto de qualquer número de matrizes, desde que as dimensões coincidam. Isto é, se A1, A2, ..., An são matrizes tais que o número de colunas de Ai é igual ao número de linhas de Ai + 1 para i = 1, ..., n – 1, então o produto

∏i=1n𝐀i=𝐀1𝐀2⋯𝐀n

é definido e não depende da ordem das multiplicações, se a ordem das matrizes for mantida fixa.

Essas propriedades podem ser provadas por manipulações de somatório diretas, embora complicadas. Este resultado também segue do fato de que as matrizes representam aplicações lineares. Portanto, a propriedade associativa das matrizes é simplesmente um caso específico da propriedade associativa da composição de funções.

A complexidade computacional depende do parêntese

Embora o resultado de uma sequência de produtos de matrizes não dependa da ordem das operações (desde que a ordem das matrizes não seja alterada), a complexidade computacional pode depender dramaticamente dessa ordem.

Por exemplo, se A, B e C são matrizes de tamanhos respectivos 10×30, 30×5, 5×60, calcular (AB)C precisa de 10×30×5 + 10×5×60 = 4.500 multiplicações, enquanto calcular A(BC) precisa de 30×5×60 + 10×30×60 = 27.000 multiplicações.

Algoritmos foram projetados para escolher a melhor ordem de produtos; veja Multiplicação de cadeia de matrizes. Quando o número n de matrizes aumenta, foi mostrado que a escolha da melhor ordem tem uma complexidade de O(nlog⁡n).

Aplicação à similaridade

Qualquer matriz invertível 𝐏 define uma transformação de similaridade (sobre matrizes quadradas do mesmo tamanho que 𝐏)

S𝐏(𝐀)=𝐏−1𝐀𝐏.

Transformações de similaridade mapeiam produtos em produtos, isto é

S𝐏(𝐀𝐁)=S𝐏(𝐀)S𝐏(𝐁).

De fato, tem-se

𝐏−1(𝐀𝐁)𝐏=𝐏−1𝐀(𝐏𝐏−1)𝐁𝐏=(𝐏−1𝐀𝐏)(𝐏−1𝐁𝐏).

Matrizes quadradas

Denotemos ℳn(R) o conjunto de matrizes quadradas n×n com entradas em um anel R, que, na prática, é frequentemente um corpo.

Em ℳn(R), o produto é definido para cada par de matrizes. Isso torna ℳn(R) um anel, que tem a matriz identidade I como um elemento identidade (a matriz cujas entradas diagonais são iguais a 1 e todas as outras entradas são 0). Este anel é também uma R-álgebra associativa.

Se n > 1, muitas matrizes não têm um inverso multiplicativo. Por exemplo, uma matriz tal que todas as entradas de uma linha (ou coluna) são 0 não tem inverso. Se existir, o inverso de uma matriz A é denotado A−1 e, portanto, verifica

𝐀𝐀−1=𝐀−1𝐀=𝐈.

Uma matriz que tem um inverso é uma matriz invertível. Caso contrário, é uma matriz singular.

Um produto de matrizes é invertível se e somente se cada fator é invertível. Neste caso, tem-se

(𝐀𝐁)−1=𝐁−1𝐀−1.

Quando R é comutativo, e, em particular, quando é um corpo, o determinante de um produto é o produto dos determinantes. Como os determinantes são escalares, e os escalares comutam, tem-se assim

det⁡(𝐀𝐁)=det⁡(𝐁𝐀)=det⁡(𝐀)det⁡(𝐁).

Os outros invariantes matriciais não se comportam tão bem com produtos. No entanto, se R é comutativo, AB e BA têm o mesmo traço, o mesmo polinômio característico e os mesmos autovalores com as mesmas multiplicidades. No entanto, os autovetores são geralmente diferentes se AB ≠ BA.

Potências de uma matriz

Pode-se elevar uma matriz quadrada a qualquer potência inteira não negativa multiplicando-a por si mesma repetidamente da mesma forma que para números ordinários. Isto é,

𝐀0=𝐈,
𝐀1=𝐀,
𝐀k=𝐀𝐀⋯𝐀⏟k vezes.

Calcular a k-ésima potência de uma matriz precisa de k – 1 vezes o tempo de uma única multiplicação de matrizes, se for feito com o algoritmo trivial (multiplicação repetida). Como isso pode ser muito demorado, geralmente se prefere usar a exponenciação por quadratura, que requer menos de 2 log2 k multiplicações de matrizes e é, portanto, muito mais eficiente.

Um caso fácil para a exponenciação é o de uma matriz diagonal. Como o produto de matrizes diagonais equivale simplesmente a multiplicar os elementos diagonais correspondentes entre si, a k-ésima potência de uma matriz diagonal é obtida elevando as entradas à potência k:

[a110⋯00a22⋯0⋮⋮⋱⋮00⋯ann]k=[a11k0⋯00a22k⋯0⋮⋮⋱⋮00⋯annk].

Álgebra abstrata

A definição de produto matricial requer que as entradas pertençam a um semianel e não exige que a multiplicação de elementos do semianel seja comutativa. Em muitas aplicações, os elementos da matriz pertencem a um corpo, embora o semianel tropical também seja uma escolha comum para problemas de caminho mais curto em grafos. Mesmo no caso de matrizes sobre corpos, o produto não é comutativo em geral, embora seja associativo e seja distributivo sobre a adição de matrizes. As matrizes identidades (que são as matrizes quadradas cujas entradas são zero fora da diagonal principal e 1 na diagonal principal) são elementos identidade do produto matricial. Segue-se que as matrizes n × n sobre um anel formam um anel, que é não comutativo, exceto se n = 1 e o anel de base for comutativo.

Uma matriz quadrada pode ter um inverso multiplicativo, chamado de matriz inversa. No caso comum em que as entradas pertencem a um anel comutativo R, uma matriz tem um inverso se e somente se seu determinante tem um inverso multiplicativo em R. O determinante de um produto de matrizes quadradas é o produto dos determinantes dos fatores. As matrizes n × n que têm um inverso formam um grupo sob a multiplicação de matrizes, cujos subgrupos são chamados de grupos matriciais. Muitos grupos clássicos (incluindo todos os grupos finitos) são isomorfos a grupos matriciais; este é o ponto de partida da teoria das representações de grupos.

As matrizes são os morfismos de uma categoria, a categoria de matrizes. Os objetos são os números naturais que medem o tamanho das matrizes, e a composição de morfismos é a multiplicação de matrizes. A fonte de um morfismo é o número de colunas da matriz correspondente, e o alvo é o número de linhas.

Complexidade computacional

 Nota: Para técnicas de implementação (em particular algoritmos paralelos e distribuídos), veja Algoritmo de multiplicação de matrizes.
Melhoria das estimativas do expoente ω ao longo do tempo para a complexidade computacional da multiplicação de matrizes O(nω)

O algoritmo de multiplicação de matrizes que resulta da definição requer, no pior caso, ⁠n3⁠ multiplicações e ⁠(n−1)n2⁠ adições de escalares para calcular o produto de duas matrizes quadradas n×n. Sua complexidade computacional é, portanto, ⁠O(n3)⁠, em um modelo de computação para o qual as operações escalares levam tempo constante.

Surpreendentemente, essa complexidade não é ótima, como mostrado em 1969 por Volker Strassen, que forneceu um algoritmo, agora chamado de algoritmo de Strassen, com uma complexidade de O(nlog27)≈O(n2.8074). O algoritmo de Strassen pode ser paralelizado para melhorar ainda mais o desempenho. Desde janeiro de 2024 (2024 -01), o melhor algoritmo de multiplicação de matrizes revisado por pares é de Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu e Renfei Zhou e tem complexidade O(n2.371552). Não se sabe se a multiplicação de matrizes pode ser realizada em tempo n2 + o(1). Isso seria ótimo, pois deve-se ler os ⁠n2⁠ elementos de uma matriz para multiplicá-la por outra matriz.

Como a multiplicação de matrizes forma a base para muitos algoritmos, e muitas operações sobre matrizes têm até a mesma complexidade que a multiplicação de matrizes (a menos de uma constante multiplicativa), a complexidade computacional da multiplicação de matrizes aparece em toda a álgebra linear numérica e na ciência da computação teórica.

Generalizações

Outros tipos de produtos de matrizes incluem:

Algoritmos para a multiplicar matrizes eficientemente

Problema em aberto na ciência da computação
Qual é o algoritmo mais rápido para a multiplicação de matrizes?

O tempo de execução da multiplicação de matrizes quadradas, se efetuada de forma intuitiva, é O(n3). O tempo de execução para a multiplicação de matrizes retangulares (uma matriz m×p e outra p×n) é O(mnp), no entanto, existem algoritmos mais eficientes, tais como o algoritmo de Strassen, concebido por Volker Strassen em 1969, e chamado frequentemente de "multiplicação rápida de matrizes". Ele baseia-se em uma forma de multiplicar matrizes 2×2 que exige apenas 7 multiplicações (em vez das 8 usuais), em troca de fazer algumas oprerações de adição e subtração. A aplicação recursiva desse método produz um algoritmo cujo custo multiplicativo é O(nlog27)≈O(n2.807). O algoritmo de Strassen é mais complexo se comparado com o algoritmo intuitivo, e ele carece de estabilidade numérica. Mesmo assim, está disponível em diversas bibliotecas, tais como BLAS, em que sua eficiência é significativamente maior para matrizes de dimensão n > 100, e é muito útil para matrizes grandes sobre domínios exatos tais como corpos finitos, em que a estabilidade numérica não é um problema.

Ver também