Em geral, dadas matrizes quadradas
, quantas operações aritmética são necessárias para o cálculo de
, usando exatamente a definição dada em sala?
Passo 1
O enunciado pergunta quantas operações aritméticas são necessárias para calcular
usando exatamente a definição clássica de multiplicação de matrizes, onde
são matrizes quadradas de ordem
.
Informações dadas e objetivo claro:
Informações dadas e objetivo claro:
- As matrizes são quadradas de ordem
. - 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
.
Passo 2
Escrevendo a definição por entradas: o produto
tem entradas
dadas por
Explique por que essa fórmula exige certo número de multiplicações e adições para cada par
: para calcular a soma de
termos
precisamos primeiro obter cada produto
(uma multiplicação por termo) e depois somar esses
produtos. Somar
números exige exatamente
adições (porque cada adição reduz o número de parcelas em 1).
Passo 3
Contagem por entrada
:
- Multiplicações necessárias:
(uma para cada ). - Adições necessárias para somar os
produtos: .
Mostre com um exemplo pequeno (para fixar): se
, cada
. Isso pede
multiplicações e
adições por entrada.
Passo 4
Agora multiplicamos pela quantidade de entradas da matriz resultado. Há
entradas
no total, então:
- Total de multiplicações:
- Total de adições:
Passo 5
Somando as operações aritméticas (multiplicações + adições) obtemos
Comente rapidamente: frequentemente, em análise assintótica, diz-se que a multiplicação de matrizes pela definição custa
operações, porque termos de ordem inferior (como
) são desprezados; mas aqui demos a contagem exata.
Resposta
Multiplicações:
Adições:
Total de operações aritméticas:
Adições:
Total de operações aritméticas: