Tutorial: Matrix Exponentiation

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.