Produto de matrizes
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.
Imagem: Portuguese_eyes · BY-SA · Openverse
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.
Imagem: Portuguese_eyes · BY-SA · Openverse
Matriz vezes matriz
Se A é uma matriz m × n e B é uma matriz n × p, A = ( a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a m 1 a m 2 ⋯ a m n ) , B = ( b 11 b 12 ⋯ b 1 p b 21 b 22 ⋯ b 2 p ⋮ ⋮ ⋱ ⋮ b n 1 b n 2 ⋯ b n p ) {\displaystyle \mathbf {A} ={\begin{pmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}\\\end{pmatrix}},\quad \mathbf {B} ={\begin{pmatrix}b_{11}&b_{12}&\cdots &b_{1p}\\b_{21}&b_{22}&\cdots &b_{2p}\\\vdots &\vdots &\ddots &\vdots \\b_{n1}&b_{n2}&\cdots &b_{np}\\\end{pmatrix}}} o produto matricial C = AB (denotado sem sinais de multiplicação ou pontos) é definido como a matriz m × p C = ( c 11 c 12 ⋯ c 1 p c 21 c 22 ⋯ c 2 p ⋮ ⋮ ⋱ ⋮ c m 1 c m 2 ⋯ c m p ) {\displaystyle \mathbf {C} ={\begin{pmatrix}c_{11}&c_{12}&\cdots &c_{1p}\\c_{21}&c_{22}&\cdots &c_{2p}\\\vdots &\vdots &\ddots &\vdots \\c_{m1}&c_{m2}&\cdots &c_{mp}\\\end{pmatrix}}} tal que c i j = a i 1 b 1 j + a i 2 b 2 j + ⋯ + a i n b n j = ∑ k = 1 n a i k b k j , {\displaystyle c_{ij}=a_{i1}b_{1j}+a_{i2}b_{2j}+\cdots +a_{in}b_{nj}=\sum _{k=1}^{n}a_{ik}b_{kj},} para i = 1, ..., m e j = 1, ..., p.
Matriz vezes vetor
Um vetor x {\displaystyle \mathbf {x} } de comprimento n {\displaystyle n} pode ser visto como um vetor coluna, correspondendo a uma matriz n × 1 {\displaystyle n\times 1} X {\displaystyle \mathbf {X} } cujas entradas são dadas por X i 1 = x i . {\displaystyle \mathbf {X} _{i1}=\mathbf {x} _{i}.} Se A {\displaystyle \mathbf {A} } é uma matriz m × n {\displaystyle m\times n} , o produto matriz-vetor denotado por A x {\displaystyle \mathbf {Ax} } é então o vetor y {\displaystyle \mathbf {y} } que, visto como um vetor coluna, é igual à matriz m × 1 {\displaystyle m\times 1} A X . {\displaystyle \mathbf {AX} .} Em notação de índices, isso equivale a:
Vetor vezes matriz
Similarmente, um vetor x {\displaystyle \mathbf {x} } de comprimento n {\displaystyle n} pode ser visto como um vetor linha, correspondendo a uma matriz 1 × n {\displaystyle 1\times 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 x T A . {\displaystyle \mathbf {x} ^{\mathrm {T} }\mathbf {A} .} A identidade x T A = ( A T x ) T {\displaystyle \mathbf {x} ^{\mathrm {T} }\mathbf {A} =(\mathbf {A} ^{\mathrm {T} }\mathbf {x} )^{\mathrm {T} }} é válida. Em notação de índices, se A {\displaystyle \mathbf {A} } é uma matriz n × p {\displaystyle n\times p} , x T A = y T {\displaystyle \mathbf {x} ^{\mathrm {T} }\mathbf {A} =\mathbf {y} ^{\mathrm {T} }} equivale a: y k = ∑ j = 1 n x j a j k . {\displaystyle y_{k}=\sum _{j=1}^{n}x_{j}a_{jk}.}
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 a {\displaystyle \mathbf {a} } e b {\displaystyle \mathbf {b} } são ambos vetores coluna, o produto escalar (ou produto interno) a ⋅ b {\displaystyle \mathbf {a} \cdot \mathbf {b} } é igual à única entrada da matriz 1 × 1 {\displaystyle 1\times 1} resultante da multiplicação matricial do vetor linha a T {\displaystyle \mathbf {a} ^{\mathrm {T} }} com o vetor coluna b {\displaystyle \mathbf {b} } , i.e. a T b {\displaystyle \mathbf {a} ^{\mathrm {T} }\mathbf {b} } . A multiplicação matricial entre o vetor coluna a {\displaystyle \mathbf {a} } e o vetor linha b T {\displaystyle \mathbf {b} ^{\mathrm {T} }} , também conhecida como produto externo a b T {\displaystyle \mathbf {a} \mathbf {b} ^{\mathrm {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. [ a 11 a 12 ⋅ ⋅ a 31 a 32 ⋅ ⋅ ] 4 × 2 matriz [ ⋅ b 12 b 13 ⋅ b 22 b 23 ] 2 × 3 matriz = [ ⋅ c 12 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ c 33 ⋅ ⋅ ⋅ ] 4 × 3 matriz {\displaystyle {\overset {4\times 2{\text{ matriz}}}{\begin{bmatrix}a_{11}&a_{12}\\\cdot &\cdot \\a_{31}&a_{32}\\\cdot &\cdot \\\end{bmatrix}}}{\overset {2\times 3{\text{ matriz}}}{\begin{bmatrix}\cdot &b_{12}&b_{13}\\\cdot &b_{22}&b_{23}\\\end{bmatrix}}}={\overset {4\times 3{\text{ matriz}}}{\begin{bmatrix}\cdot &c_{12}&\cdot \\\cdot &\cdot &\cdot \\\cdot &\cdot &c_{33}\\\cdot &\cdot &\cdot \\\end{bmatrix}}}}
Imagem: CasalMALY · BY · Openverse
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
Sistema de equações lineares
A forma geral de um sistema de equações lineares é 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 x T {\displaystyle \mathbf {x} ^{\mathsf {T}}} é o vetor linha obtido por transpondo x {\displaystyle \mathbf {x} } . (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 x † {\displaystyle \mathbf {x} ^{\dagger }} denota a transposta conjugada de x {\displaystyle \mathbf {x} } (conjugado da transposta, ou equivalentemente transposta do conjugado).
Imagem: CasalMALY · BY · Openverse
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 A B {\displaystyle \mathbf {A} \mathbf {B} } é definido, então B A {\displaystyle \mathbf {B} \mathbf {A} } também é definido, e A B = B A . {\displaystyle \mathbf {A} \mathbf {B} =\mathbf {B} \mathbf {A} .} Se A e B são matrizes de tamanhos respectivos m × n {\displaystyle m\times n} e p × q {\displaystyle p\times q} , então A B {\displaystyle \mathbf {A} \mathbf {B} } é definido se n = p {\displaystyle n=p} , e B A {\displaystyle \mathbf {B} \mathbf {A} } é definido se m = q {\displaystyle m=q} . Portanto, se um dos produtos é definido, o outro não precisa ser definido. Se m = q ≠ n = p {\displaystyle m=q\neq 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 {\displaystyle 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
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) Isso resulta da distributividade para coeficientes por
Produto com um escalar
Se A é uma matriz e c um escalar, então as matrizes c A {\displaystyle c\mathbf {A} } e A c {\displaystyle \mathbf {A} 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 A = A c . {\displaystyle c\mathbf {A} =\mathbf {A} c.} Se o produto A B {\displaystyle \mathbf {AB} } é definido (isto é, o número de colunas de A é igual ao número de linhas de B), então 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.
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
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 A B C . {\displaystyle \mathbf {ABC} .} 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
Imagem: Portuguese_eyes · BY-SA · Openverse
Denotemos M n ( R ) {\displaystyle {\mathcal {M}}_{n}(R)} o conjunto de matrizes quadradas n×n com entradas em um anel R, que, na prática, é frequentemente um corpo. Em M n ( R ) {\displaystyle {\mathcal {M}}_{n}(R)} , o produto é definido para cada par de matrizes. Isso torna M n ( R ) {\displaystyle {\mathcal {M}}_{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 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
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 é, 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:
Imagem: Portuguese_eyes · BY-SA · Openverse
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.
Imagem: Vitor Oliveira from Torres Vedras, PORTUGAL · BY-SA · Openverse
O algoritmo de multiplicação de matrizes que resulta da definição requer, no pior caso, n 3 {\displaystyle n^{3}} multiplicações e ( n − 1 ) n 2 {\displaystyle (n-1)n^{2}} adições de escalares para calcular o produto de duas matrizes quadradas n×n. Sua complexidade computacional é, portanto, O ( n 3 ) {\displaystyle O(n^{3})} , 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 ( n log 2 7 ) ≈ O ( n 2.8074 ) . {\displaystyle O(n^{\log _{2}7})\approx O(n^{2.8074}).} O algoritmo de Strassen pode ser paralelizado para melhorar ainda mais o desempenho. Desde janeiro de 2024 (2024 -01)[update], 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 n 2 {\displaystyle n^{2}} elementos de uma matriz para multiplicá-la por outra matriz.
Imagem: André Koehne · BY-SA · Openverse
Outros tipos de produtos de matrizes incluem:
Imagem: Portuguese_eyes · BY-SA · Openverse
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 ( n 3 ) . {\displaystyle O(n^{3}).} 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 ( n log 2 7 ) ≈ O ( n 2.807 ) . {\displaystyle O(n^{\log _{2}7})\approx O(n^{2.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.
