Em geral, dadas matrizes quadradas A, B \in \mathcal{M}_{n}, quantas operações aritmética são necessárias para o cálculo de A B, usando exatamente a definição dada em sala?

Passo 1

O enunciado pergunta quantas operações aritméticas são necessárias para calcular AB usando exatamente a definição clássica de multiplicação de matrizes, onde A,B\in\mathcal{M}_{n} são matrizes quadradas de ordem n.
Informações dadas e objetivo claro:
  • As matrizes são quadradas de ordem n.
  • Queremos contar operações aritméticas (aqui vamos contar multiplicações e adições elementares).
  • Deve-se usar a definição por entradas para formar o produto AB.

Passo 2

Escrevendo a definição por entradas: o produto C=AB tem entradas c_{ij} dadas por
c_{ij}=\sum_{k=1}^{n} a_{ik}\,b_{kj}.
Explique por que essa fórmula exige certo número de multiplicações e adições para cada par (i,j): para calcular a soma de n termos a_{i1}b_{1j},a_{i2}b_{2j},\dots,a_{in}b_{nj} precisamos primeiro obter cada produto a_{ik}b_{kj} (uma multiplicação por termo) e depois somar esses n produtos. Somar n números exige exatamente n-1 adições (porque cada adição reduz o número de parcelas em 1).

Passo 3

Contagem por entrada (i,j):
  • Multiplicações necessárias: n (uma para cada k=1,\dots,n).
  • Adições necessárias para somar os n produtos: n-1.
Mostre com um exemplo pequeno (para fixar): se n=3, cada c_{ij}=a_{i1}b_{1j}+a_{i2}b_{2j}+a_{i3}b_{3j}. Isso pede 3 multiplicações e 2 adições por entrada.

Passo 4

Agora multiplicamos pela quantidade de entradas da matriz resultado. Há n^2 entradas (i,j) no total, então:
  • Total de multiplicações:
n^2\cdot n = n^3.
  • Total de adições:
n^2\cdot (n-1)=n^3-n^2.

Passo 5

Somando as operações aritméticas (multiplicações + adições) obtemos
n^3 + (n^3-n^2) = 2n^3 - n^2.
Comente rapidamente: frequentemente, em análise assintótica, diz-se que a multiplicação de matrizes pela definição custa \mathcal{O}(n^3) operações, porque termos de ordem inferior (como -n^2) são desprezados; mas aqui demos a contagem exata.

Resposta

Multiplicações: n^3
Adições: n^3-n^2
Total de operações aritméticas: 2n^3-n^2

Exercícios relacionados