Repository: TheAlgorithms/Python
Pull request: Added Matrix Exponentiation
Fixes #1180  Added the **matrix_exponentiation.py** file in **maths directory**

Problem statement:
Adding Matrix Exponentiation
I was just browsing through  the algorithms and data structures but couldn't find Matrix Exponentiation, which is useful for solving linear recurrences in logarithmic time. So, is this something you guys think should be added? If yes then I can work on it and submit a PR. Thanks

Hints from issue discussion:
👍 Go for it!
sure
Please show us side-by-sige benchmarks (using [timeit](https://docs.python.org/3.7/library/timeit.html) or similar) of the two methods running on the same square matrices so we can see the performance.
Initially I thought of using the simple problem of finding the nth element of fibonacci series in O(logn) using Matrix Exponentiation as the base example to use because this is the most common problem in competitive programing sites to introduce matrix exponentiation. So, do you think this problem is enough or do I go for some more general linear recurrence?
@cclauss I used the example of finding the nth element in the Fibonacci series in O(logn) to demonstrate Matrix Exponentiation. For performance evaluation, I compared the simple linear method of finding the nth element with the same using Matrix Exponentiation for random numbers in range of 10**4. Is anything else you would like me to add? otherwise I will submit the PR. Thanks
https://github.com/TheAlgorithms/Python/issues/1180#issuecomment-531466471  submit the PR

Commit message: Added the matrix_exponentiation.py file in maths directory

Patch to review:
diff --git a/maths/matrix_exponentiation.py b/maths/matrix_exponentiation.py
new file mode 100644
index 000000000000..17b243baf7ca
--- /dev/null
+++ b/maths/matrix_exponentiation.py
@@ -0,0 +1,134 @@
+"""Matrix Exponentiation"""
+
+import timeit
+
+"""
+Matrix Exponentiation is a technique to solve linear recurrences in logarithmic time.
+You read more about it here: 
+http://zobayer.blogspot.com/2010/11/matrix-exponentiation.html
+https://www.hackerearth.com/practice/notes/matrix-exponentiation-1/
+"""
+
+
+class Matrix(object):
+	def __init__(self, arg):
+		if isinstance(arg,list): #Initialzes a matrix identical to the one provided.
+			self.t = arg
+			self.n = len(arg)
+
+		else: #Initializes a square matrix of the given size and set the values to zero.
+			self.n = arg
+			self.t = [[0 for _ in range(self.n)] for _ in range(self.n)]
+
+	def __mul__(self, b):
+		c = Matrix(self.n)
+
+		for i in range(self.n):
+			for j in range(self.n):
+				for k in range(self.n):
+					c.t[i][j] += self.t[i][k]*b.t[k][j]
+
+		return c
+
+def modular_exponentiation(a, b):
+	ret = Matrix([[1,0], [0,1]])
+
+	while b > 0:
+		if b&1:
+			ret = ret*a
+
+		a = a*a
+		b >>= 1
+
+	return ret
+
+def fibonacci_with_matrix_exponentiation(n, f1, f2):
+	
+	#Trivial Cases
+	if n == 1:
+		return f1
+
+	if n == 2:
+		return f2
+
+	a = Matrix([[1,1], [1,0]])
+
+	m = modular_exponentiation(a, n-2)
+
+	return f2*m.t[0][0] + f1*m.t[0][1]
+
+def simple_fibonacci(n, f1, f2):
+
+	#Trival Cases
+	if n == 1:
+		return f1
+
+	if n == 2:
+		return f2
+
+	fn_1 = f1
+	fn_2 = f2
+
+	n -= 2
+
+	while n > 0:
+		fn = fn_1 + fn_2
+
+		fn_2 = fn_1
+		fn_1 = fn
+
+		n -= 1
+
+	return fn
+
+def matrix_exponentiation_time():
+	setup = '''
+from random import randint
+from __main__ import fibonacci_with_matrix_exponentiation
+'''
+
+	code = '''
+n = randint(1,70000)
+
+f1 = 1
+f2 = 1
+
+
+fibonacci_with_matrix_exponentiation(n, f1, f2)
+'''
+	exec_time = timeit.timeit(setup = setup,
+						  stmt = code,
+						  number = 100)
+
+	print ("With matrix exponentiation the average execution time is ", exec_time/100)
+
+
+def simple_fibonacci_time():
+	setup = '''
+from random import randint
+from __main__ import simple_fibonacci
+'''
+
+	code = '''
+n = randint(1,70000)
+
+f1 = 1
+f2 = 1
+
+
+simple_fibonacci(n, f1, f2)
+'''
+	exec_time = timeit.timeit(setup = setup,
+						  stmt = code,
+						  number = 100)
+
+	print ("Without matrix exponentiation the average execution time is ", exec_time/100)
+
+	
+def main():
+	matrix_exponentiation_time()
+	simple_fibonacci_time()
+
+
+if __name__ == "__main__":
+	main()
\ No newline at end of file


Code review comments:
diff_hunk: @@ -0,0 +1,134 @@
+"""Matrix Exponentiation"""
+
+import timeit
+
+"""
+Matrix Exponentiation is a technique to solve linear recurrences in logarithmic time.
+You read more about it here: 
+http://zobayer.blogspot.com/2010/11/matrix-exponentiation.html
+https://www.hackerearth.com/practice/notes/matrix-exponentiation-1/
+"""
+
+
+class Matrix(object):
+	def __init__(self, arg):
+		if isinstance(arg,list): #Initialzes a matrix identical to the one provided.
+			self.t = arg
+			self.n = len(arg)
+
+		else: #Initializes a square matrix of the given size and set the values to zero.
+			self.n = arg
+			self.t = [[0 for _ in range(self.n)] for _ in range(self.n)]
+
+	def __mul__(self, b):
+		c = Matrix(self.n)
+
+		for i in range(self.n):
+			for j in range(self.n):
+				for k in range(self.n):
+					c.t[i][j] += self.t[i][k]*b.t[k][j]
+
+		return c
+
+def modular_exponentiation(a, b):
+	ret = Matrix([[1,0], [0,1]])
+
+	while b > 0:
+		if b&1:
+			ret = ret*a
+
+		a = a*a
+		b >>= 1
+
+	return ret
+
+def fibonacci_with_matrix_exponentiation(n, f1, f2):
+	
+	#Trivial Cases
+	if n == 1:
+		return f1
+
+	if n == 2:
+		return f2
+
+	a = Matrix([[1,1], [1,0]])
+
+	m = modular_exponentiation(a, n-2)
+
+	return f2*m.t[0][0] + f1*m.t[0][1]
+
+def simple_fibonacci(n, f1, f2):
+
+	#Trival Cases
+	if n == 1:
+		return f1
+
+	if n == 2:
+		return f2
+
+	fn_1 = f1
+	fn_2 = f2
+
+	n -= 2
+
+	while n > 0:
+		fn = fn_1 + fn_2
+
+		fn_2 = fn_1
+		fn_1 = fn
+
+		n -= 1
+
+	return fn
+
+def matrix_exponentiation_time():
+	setup = '''
+from random import randint
+from __main__ import fibonacci_with_matrix_exponentiation
+'''
+
+	code = '''
+n = randint(1,70000)
+
+f1 = 1
+f2 = 1
+
+
+fibonacci_with_matrix_exponentiation(n, f1, f2)
+'''
path: maths/matrix_exponentiation.py
text: @user1:
For readability, simplify this to:
__code = "fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)"__