# TDA | practica 2 ejercicio 5
## Enunciado
Suponga que se tiene un método `potencia` que, dada una matriz cuadrada $A$ de orden $4 \times 4$ y un número $n$, computa la matriz $A^n$. Dada una matriz cuadrada $A$ de orden $4 \times 4$ y un número natural $n$ que es potencia de $2$ (i.e., $n = 2^k$ para algún $k \geq 1$), desarrollar, utilizando la técnica de dividir y conquistar y el método `potencia`, un algoritmo que permita calcular
$$ A^1 + A^2 + A^3 + \ldots + A^n. $$
## Resolución
- Dada una matriz cuadrada $A$ de orden $4 \times 4$ y un número natural $n$ que es potencia de $2$ (es decir, $n = 2^k$ para algún $k \geq 1$), queremos calcular la suma de las potencias de $A$ desde $A^1$ hasta $A^n$. Esto se puede expresar como:
$$ S = \sum_{i=1}^{n} A^i $$
- Para calcular esto de manera eficiente, utilizamos la técnica de dividir y conquistar. Dividimos $S$ en dos sumatorias, $\text{Sumatoria}_1$ y $\text{Sumatoria}_2$:
$$ \text{Sumatoria}_1 = \sum_{i=1}^{n/2} A^i $$
$$ \text{Sumatoria}_2 = \sum_{i=n/2+1}^{n} A^i $$
- La suma total $S$ sería entonces:
$$ S = \text{Sumatoria}_1 + \text{Sumatoria}_2 $$
- Ahora, podemos reescribir $\text{Sumatoria}_2$ utilizando la propiedad de las potencias de matrices, tomando en cuenta que podemos calcular $A^{n/2 + i}$ como $A^{n/2} \cdot A^i$:
$$ \text{Sumatoria}_2 = \sum_{i=1}^{n/2} A^{n/2} \cdot A^i $$
- Dado que ya calculamos $\text{Sumatoria}_1 = \sum_{i=1}^{n/2} A^i$, podemos simplificar $\text{Sumatoria}_2$ como:
$$ \text{Sumatoria}_2 = A^{n/2} \cdot \text{Sumatoria}_1 $$
- Entonces, la suma total de potencias de $A$ es:
$$ S = \text{Sumatoria}_1 + A^{n/2} \cdot \text{Sumatoria}_1 $$
$$ S = (I + A^{n/2}) \cdot \text{Sumatoria}_1 $$
- Donde $I$ es la matriz identidad de orden $4 \times 4$. Esto nos permite calcular $S$ de forma eficiente utilizando la técnica de dividir y conquistar.
### Implementación
```python
import numpy as np
# Función "potencia" que hablan en la consigna sería algo así:
def potencia(A, n):
return np.linalg.matrix_power(A, n)
def potenciaSum(A, n):
if n == 1:
return A
else:
# Dividir:
mitad = n // 2
# Conquistar:
primeraMitad = potenciaSum(A, mitad)
# Resuelvo la 1ra mitad del problema.
A_mitad = potencia(A, mitad)
# Calcular A^(n/2)
# Utilizo propiedad distributiva de la multiplicación de matrices para calcular la 2da mitad
segundaMitad = A_mitad @ primeraMitad
# Combinar:
# Sumar la primera mitad y la segunda mitad que ya incluye desde A^(n/2 + 1) hasta A^n
resultado = primeraMitad + segundaMitad
return resultado
# Ejemplo de uso
A = np.array([[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]])
n = 4 # Aquí n debe ser una potencia de 2
S = potenciaSum(A, n)
print(S)
```