# Tutorial: Matrix Exponentiation

July 04, 2017

**Prerequisites**: Matrix in algebra, Matrix multiplication

**Introduction**: Matrix Exponentiation (also known as matrix power, repeated squaring) is a technique used to solve linear recurrences. This technique is very useful in competitive programming when dealing with linear recurrences (appears along Dynamic Programming). This technique also solves a lot of problems in graph theory. Only solving recurrences is covered here, applications on graph theory will be discussed later.

**Video tutorial**: This video shows how you can use matrices to calculate the n-th fibonacci number (where n is very large ~10^18). You should be able to understand the technique after watching this video. Exercises will be added soon.

**Text tutorial**: It’s highly recommended to take a look at this tutorial by Fushar (even if you watched the video): Solving Linear Recurrence for Programming Contest.