Возведение Матрицы в степень

Определение

$A^{x} = A^{x - 1}\cdot A = A \cdot A \cdot \dots \cdot A$

Быстрое возведение в степень

Мы уже знаем, что такое быстрое возведение в степень, заметим что для его применения мы требовали одну вещь $((A \cdot A) \cdot A) \cdot A = A^2 \cdot A^2$, но как мы знаем для матриц верно свойство $A \cdot (B \cdot C) = (A \cdot B) \cdot C$

Тогда мы можем просто написать для матриц быстрое возведение в степень - Оно будет работать за $O(log(n) \cdot size^3)$, если нужно матрицу $A \in Mat_{size \ size}$ возвести в $n$-ую степень

---

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin