{"title":"Matrix Exponentiation","description":"","content":"Matrix exponentiation is a powerful technique used to optimize certain recursive and dynamic programming problems from linear time to logarithmic time. It is especially useful when a problem follows a recurrence relation, such as Fibonacci or similar sequences.\n\nInstead of computing each state one by one, matrix exponentiation lets you jump directly to the nth state by raising a transformation matrix to a power. This reduces time complexity from O(n) to O(log n), which is critical when n is very large.\n\nIn this chapter, we will build the intuition behind matrix exponentiation, understand how recurrence relations can be expressed as matrices, and apply this technique to common interview problems.\n\n---\n\n# From Recurrence to Matrix\n\nBefore we dive into matrix exponentiation, let us make sure matrix multiplication itself is clear.\n\n### Matrix Multiplication Refresher\n\nTo multiply two matrices A (of size p x q) and B (of size q x r), we produce a result matrix C of size p x r. Each entry C[i][j] is the dot product of row i of A and column j of B:\n\n\n```shell\nC[i][j] = A[i][0]*B[0][j] + A[i][1]*B[1][j] + ... + A[i][q-1]*B[q-1][j]\n```\n\n\nA few important properties to remember:\n\n- Matrix multiplication is **associative**: (A * B) * C = A * (B * C)\n- Matrix multiplication is **NOT commutative**: A * B is generally not equal to B * A\n- The **identity matrix** I acts like the number 1: A * I = I * A = A\n\n### The Key Insight: Fibonacci as Matrix Multiplication\n\nThe Fibonacci recurrence is:\n\n\n```shell\nF(n) = F(n-1) + F(n-2)\n```\n\n\nHere is the trick. We can express the transition from one pair of consecutive Fibonacci numbers to the next as a matrix multiplication:\n\n\n```shell\n| F(n) | | 1 1 | | F(n-1) |\n| | = | | * | |\n| F(n-1) | | 1 0 | | F(n-2) |\n```\n\n\nLet us call that 2x2 matrix T (the **transition matrix**). Starting from the base case:\n\n\n```shell\n| F(1) | | 1 |\n| | = | |\n| F(0) | | 0 |\n```\n\n\nApplying T once gives us F(2) and F(1). Applying T twice gives us F(3) and F(2). Applying T n times gives us F(n+1) and F(n). In other words:\n\n\n```shell\nT^n * | F(1) | | F(n+1) |\n | F(0) | = | F(n) |\n```\n\n\nThis means computing F(n) reduces to computing T^n, which we can do in O(log n) using binary exponentiation.\n\n\n```mermaid\nflowchart LR\n A[\"Base State
F(1) = 1
F(0) = 0\"]:::primary\n T1[\"Multiply by T\"]:::orange\n B[\"F(2) = 1
F(1) = 1\"]:::primary\n T2[\"Multiply by T\"]:::orange\n C[\"F(3) = 2
F(2) = 1\"]:::primary\n T3[\"Multiply by T^n\"]:::red\n D[\"F(n+1)
F(n)\"]:::green\n\n A --> T1 --> B --> T2 --> C --> T3 --> D\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\n---\n\n# Detailed Explanation\n\n### Matrix Multiplication Algorithm\n\nMultiplying two k x k matrices takes O(k^3) time. For the Fibonacci problem k = 2, so each multiplication is just 8 multiplications and 4 additions, which is essentially O(1).\n\nHere is how we multiply two 2x2 matrices:\n\n\n```shell\n| a b | | e f | | a*e+b*g a*f+b*h |\n| | * | | = | |\n| c d | | g h | | c*e+d*g c*f+d*h |\n```\n\n\n### Binary Exponentiation for Matrices\n\nBinary exponentiation (also called exponentiation by squaring) computes X^n in O(log n) multiplications. The idea works identically for numbers and matrices:\n\n- Start with result = identity matrix I\n- Look at the binary representation of n\n- For each bit (from least significant to most significant):\n - If the current bit is 1, multiply result by the current base\n - Square the current base\n- Return result\n\nFor example, to compute T^13 where 13 = 1101 in binary:\n\n\n```shell\nT^13 = T^8 * T^4 * T^1\n```\n\n\nWe compute T^1, T^2, T^4, T^8 by repeated squaring, and multiply together only the powers corresponding to set bits.\n\n\n```mermaid\nflowchart LR\n N[\"n = 13 = 1101₂\"]:::primary\n B0[\"Bit 0 = 1
result *= T¹\"]:::green\n B1[\"Bit 1 = 0
skip\"]:::red\n B2[\"Bit 2 = 1
result *= T⁴\"]:::green\n B3[\"Bit 3 = 1
result *= T⁸\"]:::green\n R[\"result = T¹ * T⁴ * T⁸ = T¹³\"]:::orange\n\n N --> B0 --> B1 --> B2 --> B3 --> R\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n### Generalizing to Any Linear Recurrence\n\nThe Fibonacci matrix is just one example. Any linear recurrence of the form:\n\n\n```shell\nf(n) = c1*f(n-1) + c2*f(n-2) + ... + ck*f(n-k)\n```\n\n\ncan be expressed as a k x k matrix multiplication. The transition matrix T is:\n\n\n```shell\n| c1 c2 c3 ... ck |\n| 1 0 0 ... 0 |\n| 0 1 0 ... 0 |\n| ... |\n| 0 0 0 1 0 |\n```\n\n\nThe first row contains the recurrence coefficients. The remaining rows form a \"shift\" that moves the state one step forward. The state vector holds the k most recent values of the recurrence.\n\n### State Transition Matrices\n\nLet us look at a slightly more complex example. Consider the recurrence:\n\n\n```shell\nf(n) = 2*f(n-1) + 3*f(n-2) + 1\n```\n\n\nThis has a constant term (+1), which does not fit the standard pattern directly. The trick is to add an extra dimension to the state vector to handle the constant:\n\n\n```shell\n| f(n) | | 2 3 1 | | f(n-1) |\n| f(n-1) | = | 1 0 0 | * | f(n-2) |\n| 1 | | 0 0 1 | | 1 |\n```\n\n\nThe extra row and column keep the constant \"1\" alive through each multiplication. This pattern generalizes: any time your recurrence has additive constants or polynomial terms, you can absorb them into the state vector.\n\n\n```mermaid\nflowchart LR\n subgraph State[\"State Vector\"]\n S1[\"f(n-1)\"]:::primary\n S2[\"f(n-2)\"]:::primary\n S3[\"1\"]:::teal\n end\n\n T[\"Transition
Matrix T\"]:::orange\n\n subgraph Next[\"Next State\"]\n N1[\"f(n)\"]:::green\n N2[\"f(n-1)\"]:::green\n N3[\"1\"]:::teal\n end\n\n State --> T --> Next\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n```\n\n\n### Applications Beyond Recurrences\n\n**Counting paths in graphs:** If A is the adjacency matrix of a graph, then A^k[i][j] gives the number of paths of exactly k edges from node i to node j. With matrix exponentiation, you can compute this in O(V^3 * log k) instead of O(V^3 * k).\n\n**Tiling problems:** Many tiling problems (e.g., \"how many ways to tile a 2xN board with 1x2 dominoes\") reduce to linear recurrences that matrix exponentiation handles efficiently.\n\n---\n\n# Example Walkthrough\n\nLet us trace through computing Fibonacci(6) step by step using matrix exponentiation.\n\nOur transition matrix is:\n\n\n```shell\nT = | 1 1 |\n | 1 0 |\n```\n\n\nOur base state vector is:\n\n\n```shell\nv = | F(1) | | 1 |\n | F(0) | = | 0 |\n```\n\n\nWe need T^6. Since 6 = 110 in binary, we need T^4 * T^2.\n\n**Step 1: Start with base = T, result = I (identity)**\n\n\n```shell\nbase = | 1 1 | result = | 1 0 |\n | 1 0 | | 0 1 |\n```\n\n\n**Step 2: Bit 0 of 6 is 0, so skip. Square the base.**\n\n\n```shell\nbase = T^2 = | 1 1 | * | 1 1 | = | 2 1 |\n | 1 0 | | 1 0 | | 1 1 |\n```\n\n\nLet us verify: T^2[0][0] = 1*1 + 1*1 = 2, T^2[0][1] = 1*1 + 1*0 = 1, T^2[1][0] = 1*1 + 0*1 = 1, T^2[1][1] = 1*1 + 0*0 = 1.\n\n**Step 3: Bit 1 of 6 is 1, so result = result * base. Then square the base**\n\n\n```shell\nresult = I * T^2 = T^2 = | 2 1 |\n | 1 1 |\n\nbase = T^4 = T^2 * T^2 = | 2 1 | * | 2 1 | = | 5 3 |\n | 1 1 | | 1 1 | | 3 2 |\n```\n\n\n**Step 4: Bit 2 of 6 is 1, so result = result * base**\n\n\n```shell\nresult = T^2 * T^4 = | 2 1 | * | 5 3 | = | 13 8 |\n | 1 1 | | 3 2 | | 8 5 |\n```\n\n\nSo T^6 is:\n\n\n```shell\n| 13 8 |\n| 8 5 |\n```\n\n\n**Step 5: Multiply T^6 by the base vector.**\n\n\n```shell\nT^6 * | 1 | = | 13*1 + 8*0 | = | 13 |\n | 0 | | 8*1 + 5*0 | | 8 |\n```\n\n\nThis gives us F(7) = 13 and F(6) = 8. Let us verify: the Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13... So F(6) = 8 is correct.\n\nWe computed F(6) using only 3 matrix multiplications (two squarings and one extra multiply) instead of 6 sequential additions. For large n, the savings are enormous.\n\n---\n\n# Implementation\n\nBelow is the complete implementation. The implementation provides three functions: matrix multiplication, matrix power using binary exponentiation, and Fibonacci computation using matrix exponentiation. All results are computed modulo 10^9 + 7 to prevent overflow.\n\n\n```java\npublic class MatrixExponentiation {\n static final long MOD = 1_000_000_007;\n\n static long[][] multiply(long[][] A, long[][] B) {\n int n = A.length;\n long[][] C = new long[n][n];\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n for (int k = 0; k < n; k++) {\n C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;\n }\n }\n }\n return C;\n }\n\n static long[][] matPow(long[][] M, long p) {\n int n = M.length;\n // Start with identity matrix\n long[][] result = new long[n][n];\n for (int i = 0; i < n; i++) result[i][i] = 1;\n\n while (p > 0) {\n if ((p & 1) == 1) {\n result = multiply(result, M);\n }\n M = multiply(M, M);\n p >>= 1;\n }\n return result;\n }\n\n static long fibonacci(long n) {\n if (n <= 0) return 0;\n if (n == 1) return 1;\n long[][] T = {{1, 1}, {1, 0}};\n long[][] res = matPow(T, n);\n return res[0][1];\n }\n\n public static void main(String[] args) {\n System.out.println(fibonacci(6)); // 8\n System.out.println(fibonacci(10)); // 55\n System.out.println(fibonacci(50)); // 12586269025 mod 10^9+7\n }\n}\n```\n\n```python\nMOD = 10**9 + 7\n\ndef multiply(A, B):\n n = len(A)\n C = [[0] * n for _ in range(n)]\n for i in range(n):\n for j in range(n):\n for k in range(n):\n C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD\n return C\n\ndef mat_pow(M, p):\n n = len(M)\n # Start with identity matrix\n result = [[1 if i == j else 0 for j in range(n)] for i in range(n)]\n\n while p > 0:\n if p & 1:\n result = multiply(result, M)\n M = multiply(M, M)\n p >>= 1\n return result\n\ndef fibonacci(n):\n if n <= 0:\n return 0\n if n == 1:\n return 1\n T = [[1, 1], [1, 0]]\n res = mat_pow(T, n)\n return res[0][1]\n\nprint(fibonacci(6)) # 8\nprint(fibonacci(10)) # 55\n```\n\n```cpp\n#include \n#include \nusing namespace std;\n\nconst long long MOD = 1e9 + 7;\nusing Matrix = vector>;\n\nMatrix multiply(const Matrix& A, const Matrix& B) {\n int n = A.size();\n Matrix C(n, vector(n, 0));\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n for (int k = 0; k < n; k++) {\n C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;\n }\n }\n }\n return C;\n}\n\nMatrix matPow(Matrix M, long long p) {\n int n = M.size();\n // Start with identity matrix\n Matrix result(n, vector(n, 0));\n for (int i = 0; i < n; i++) result[i][i] = 1;\n\n while (p > 0) {\n if (p & 1) {\n result = multiply(result, M);\n }\n M = multiply(M, M);\n p >>= 1;\n }\n return result;\n}\n\nlong long fibonacci(long long n) {\n if (n <= 0) return 0;\n if (n == 1) return 1;\n Matrix T = {{1, 1}, {1, 0}};\n Matrix res = matPow(T, n);\n return res[0][1];\n}\n\nint main() {\n cout << fibonacci(6) << endl; // 8\n cout << fibonacci(10) << endl; // 55\n return 0;\n}\n```\n\n```go\npackage main\n\nimport \"fmt\"\n\nconst MOD int64 = 1_000_000_007\n\nfunc multiply(A, B [][]int64) [][]int64 {\n\tn := len(A)\n\tC := make([][]int64, n)\n\tfor i := 0; i < n; i++ {\n\t\tC[i] = make([]int64, n)\n\t\tfor j := 0; j < n; j++ {\n\t\t\tfor k := 0; k < n; k++ {\n\t\t\t\tC[i][j] = (C[i][j] + A[i][k]*B[k][j]) % MOD\n\t\t\t}\n\t\t}\n\t}\n\treturn C\n}\n\nfunc matPow(M [][]int64, p int64) [][]int64 {\n\tn := len(M)\n\t// Start with identity matrix\n\tresult := make([][]int64, n)\n\tfor i := 0; i < n; i++ {\n\t\tresult[i] = make([]int64, n)\n\t\tresult[i][i] = 1\n\t}\n\n\tfor p > 0 {\n\t\tif p&1 == 1 {\n\t\t\tresult = multiply(result, M)\n\t\t}\n\t\tM = multiply(M, M)\n\t\tp >>= 1\n\t}\n\treturn result\n}\n\nfunc fibonacci(n int64) int64 {\n\tif n <= 0 {\n\t\treturn 0\n\t}\n\tif n == 1 {\n\t\treturn 1\n\t}\n\tT := [][]int64{{1, 1}, {1, 0}}\n\tres := matPow(T, n)\n\treturn res[0][1]\n}\n\nfunc main() {\n\tfmt.Println(fibonacci(6)) // 8\n\tfmt.Println(fibonacci(10)) // 55\n\tfmt.Println(fibonacci(50)) // 12586269025 mod 10^9+7\n}\n```\n\n```csharp\nusing System;\n\npublic class MatrixExponentiation {\n const long MOD = 1_000_000_007;\n\n static long[,] Multiply(long[,] A, long[,] B) {\n int n = A.GetLength(0);\n long[,] C = new long[n, n];\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n for (int k = 0; k < n; k++) {\n C[i, j] = (C[i, j] + A[i, k] * B[k, j]) % MOD;\n }\n }\n }\n return C;\n }\n\n static long[,] MatPow(long[,] M, long p) {\n int n = M.GetLength(0);\n // Start with identity matrix\n long[,] result = new long[n, n];\n for (int i = 0; i < n; i++) result[i, i] = 1;\n\n while (p > 0) {\n if ((p & 1) == 1) {\n result = Multiply(result, M);\n }\n M = Multiply(M, M);\n p >>= 1;\n }\n return result;\n }\n\n static long Fibonacci(long n) {\n if (n <= 0) return 0;\n if (n == 1) return 1;\n long[,] T = {{1, 1}, {1, 0}};\n long[,] res = MatPow(T, n);\n return res[0, 1];\n }\n\n public static void Main() {\n Console.WriteLine(Fibonacci(6)); // 8\n Console.WriteLine(Fibonacci(10)); // 55\n }\n}\n```\n\n```rust\nuse std::io::{self, Write};\n\npub struct MatrixExponentiation;\n\nimpl MatrixExponentiation {\n const MOD: i64 = 1_000_000_007;\n\n fn multiply(a: &Vec>, b: &Vec>) -> Vec> {\n let n = a.len();\n let mut c = vec![vec![0i64; n]; n];\n for i in 0..n {\n for j in 0..n {\n for k in 0..n {\n c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % Self::MOD;\n }\n }\n }\n c\n }\n\n fn mat_pow(mut m: Vec>, mut p: i64) -> Vec> {\n let n = m.len();\n // Start with identity matrix\n let mut result = vec![vec![0i64; n]; n];\n for i in 0..n {\n result[i][i] = 1;\n }\n\n while p > 0 {\n if (p & 1) == 1 {\n result = Self::multiply(&result, &m);\n }\n m = Self::multiply(&m, &m);\n p >>= 1;\n }\n result\n }\n\n fn fibonacci(n: i64) -> i64 {\n if n <= 0 {\n return 0;\n }\n if n == 1 {\n return 1;\n }\n let t = vec![vec![1, 1], vec![1, 0]];\n let res = Self::mat_pow(t, n);\n res[0][1]\n }\n}\n\nfn main() {\n let stdout = io::stdout();\n let mut out = io::BufWriter::new(stdout.lock());\n\n writeln!(out, \"{}\", MatrixExponentiation::fibonacci(6)).unwrap(); // 8\n writeln!(out, \"{}\", MatrixExponentiation::fibonacci(10)).unwrap(); // 55\n writeln!(out, \"{}\", MatrixExponentiation::fibonacci(50)).unwrap(); // 12586269025 mod 10^9+7\n}\n```\n\n```javascript\nconst MOD = 1_000_000_007n;\n\nfunction multiply(A, B) {\n const n = A.length;\n const C = Array.from({ length: n }, () => Array(n).fill(0n));\n for (let i = 0; i < n; i++) {\n for (let j = 0; j < n; j++) {\n for (let k = 0; k < n; k++) {\n C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;\n }\n }\n }\n return C;\n}\n\nfunction matPow(M, p) {\n const n = M.length;\n // Start with identity matrix\n const result = Array.from({ length: n }, (_, i) =>\n Array.from({ length: n }, (_, j) => (i === j ? 1n : 0n))\n );\n let res = result;\n\n while (p > 0n) {\n if (p & 1n) {\n res = multiply(res, M);\n }\n M = multiply(M, M);\n p >>= 1n;\n }\n return res;\n}\n\nfunction fibonacci(n) {\n if (n <= 0n) return 0n;\n if (n === 1n) return 1n;\n const T = [[1n, 1n], [1n, 0n]];\n const res = matPow(T, n);\n return res[0][1];\n}\n\nconsole.log(fibonacci(6n)); // 8n\nconsole.log(fibonacci(10n)); // 55n\n```\n\n```typescript\nconst MOD = 1_000_000_007n;\n\ntype Matrix = bigint[][];\n\nfunction multiply(A: Matrix, B: Matrix): Matrix {\n const n = A.length;\n const C: Matrix = Array.from({ length: n }, () => Array(n).fill(0n));\n for (let i = 0; i < n; i++) {\n for (let j = 0; j < n; j++) {\n for (let k = 0; k < n; k++) {\n C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;\n }\n }\n }\n return C;\n}\n\nfunction matPow(M: Matrix, p: bigint): Matrix {\n const n = M.length;\n let result: Matrix = Array.from({ length: n }, (_, i) =>\n Array.from({ length: n }, (_, j) => (i === j ? 1n : 0n))\n );\n\n while (p > 0n) {\n if (p & 1n) {\n result = multiply(result, M);\n }\n M = multiply(M, M);\n p >>= 1n;\n }\n return result;\n}\n\nfunction fibonacci(n: bigint): bigint {\n if (n <= 0n) return 0n;\n if (n === 1n) return 1n;\n const T: Matrix = [[1n, 1n], [1n, 0n]];\n const res = matPow(T, n);\n return res[0][1];\n}\n\nconsole.log(fibonacci(6n)); // 8n\nconsole.log(fibonacci(10n)); // 55n\n```\n\n\n---\n\n# Complexity Analysis\n\nLet k be the size of the transition matrix and n be the exponent.\n\n**Time Complexity: O(k^3 * log n)**\n\n- Each matrix multiplication takes O(k^3) for two k x k matrices.\n- Binary exponentiation performs O(log n) multiplications.\n- For Fibonacci, k = 2, so each multiplication is O(8) = O(1), giving O(log n) overall.\n- For a general linear recurrence of order k, the total is O(k^3 * log n).\n\n**Space Complexity: O(k^2)**\n\n- We store a constant number of k x k matrices (the base, the result, and temporary products).\n- For Fibonacci, this is just O(4) = O(1).\n\n\n| Approach | Time | Space | Works for n = 10^18? |\n|----------|------|-------|----------------------|\n| Naive recursion | O(2^n) | O(n) | No |\n| DP (iterative) | O(n) | O(1) | No |\n| Matrix exponentiation | O(log n) | O(1) | Yes |\n\n\nThe jump from O(n) to O(log n) is what makes this technique indispensable. For n = 10^18, O(n) would take roughly 30 years on a modern CPU. O(log n) finishes in about 60 matrix multiplications, which takes microseconds.","pageType":"dsa"}

Matrix Exponentiation

Get Premium