Skip to main content
Mapagam

Using Matrix Exponentiation Pattern

1. Implementing Matrix Exponentiation

Operation Description Code Example
Matrix Multiplication Multiplies two matrices to produce a new matrix. 
function multiplyMatrices(A, B) {
  const rowsA = A.length;
  const colsA = A[0].length;
  const colsB = B[0].length;
  const result = Array(rowsA).fill().map(() => Array(colsB).fill(0));

  for (let i = 0; i < rowsA; i++) {
    for (let j = 0; j < colsB; j++) {
      for (let k = 0; k < colsA; k++) {
        result[i][j] += A[i][k] * B[k][j];
      }
    }
  }

  return result;
}
Matrix Exponentiation Computes matrix raised to a power using fast exponentiation (binary exponentiation). 
function matrixPower(matrix, power) {
  const n = matrix.length;
  let result = Array(n).fill().map(() => Array(n).fill(0));
  for (let i = 0; i < n; i++) result[i][i] = 1; // Identity matrix

  let base = matrix.map(row => [...row]);

  while (power > 0) {
    if (power % 2 === 1) {
      result = multiplyMatrices(result, base);
    }
    base = multiplyMatrices(base, base);
    power = Math.floor(power / 2);
  }

  return result;
}

Example: Fibonacci using Matrix Exponentiation

const fibMatrix = [[1, 1], [1, 0]];
function fibonacci(n) {
  if (n === 0) return 0;
  if (n === 1) return 1;

  const resultMatrix = matrixPower(fibMatrix, n - 1);
  return resultMatrix[0][0];
}

console.log(fibonacci(10)); // Output: 55

2. Solving Fibonacci with Matrices

The matrix exponentiation pattern is a powerful technique for solving linear recurrence relations efficiently, such as the Fibonacci sequence.

Property Description Value
Fibonacci Relation Matrix representation of Fibonacci recurrence 
[F(n)]   [1 1] [F(n-1)]
[F(n-1)] = [1 0] [F(n-2)]
Matrix Power Computing Fibonacci using matrix exponentiation 
[F(n)]   [1 1]^(n-1) [F(1)]
[F(n-1)] = [1 0]      [F(0)]

Example: Computing Fibonacci Using Matrix Exponentiation

function matrixMultiply(a, b) {
  return [
    [a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
    [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]]
  ];
}

function matrixPower(matrix, n) {
  if (n === 1) return matrix;
  if (n % 2 === 0) {
    const half = matrixPower(matrix, n / 2);
    return matrixMultiply(half, half);
  } else {
    return matrixMultiply(matrix, matrixPower(matrix, n - 1));
  }
}

function fibonacci(n) {
  if (n === 0) return 0;
  if (n === 1) return 1;

  const baseMatrix = [[1, 1], [1, 0]];
  const resultMatrix = matrixPower(baseMatrix, n);
  return resultMatrix[0][1];
}

console.log(fibonacci(10)); // Output: 55
Note: This approach reduces time complexity from O(n) to O(log n).

3. Implementing Matrix Multiplication

Property Description Example
matrixA First matrix to be multiplied [ [1, 2], [3, 4] ]
matrixB Second matrix to be multiplied [ [5, 6], [7, 8] ]
result Result of matrix multiplication [ [19, 22], [43, 50] ]

Example: Matrix Multiplication in JavaScript

function multiplyMatrices(A, B) {
  const rowsA = A.length;
  const colsA = A[0].length;
  const colsB = B[0].length;
  const result = Array(rowsA).fill().map(() => Array(colsB).fill(0));

  for (let i = 0; i < rowsA; i++) {
    for (let j = 0; j < colsB; j++) {
      for (let k = 0; k < colsA; k++) {
        result[i][j] += A[i][k] * B[k][j];
      }
    }
  }

  return result;
}

const A = [[1, 2], [3, 4]];
const B = [[5, 6], [7, 8]];
console.log(multiplyMatrices(A, B)); // [[19, 22], [43, 50]]

4. Solving Linear Recurrences

Matrix exponentiation is a powerful technique for solving linear recurrences efficiently. It allows us to compute the n-th term of a linear recurrence in O(log n) time, which is much faster than the naive iterative approach that takes O(n) time.

Recurrence Matrix Form Time Complexity Space Complexity
F(n) = F(n-1) + F(n-2) [[F(n)], [F(n-1)]] = [[1, 1], [1, 0]] * [[F(n-1)], [F(n-2)]] O(log n) O(1)
F(n) = a*F(n-1) + b*F(n-2) [[F(n)], [F(n-1)]] = [[a, b], [1, 0]] * [[F(n-1)], [F(n-2)]] O(log n) O(1)

Example: Fibonacci Using Matrix Exponentiation

function matrixMultiply(A, B) {
  return [
    [A[0][0] * B[0][0] + A[0][1] * B[1][0], A[0][0] * B[0][1] + A[0][1] * B[1][1]],
    [A[1][0] * B[0][0] + A[1][1] * B[1][0], A[1][0] * B[0][1] + A[1][1] * B[1][1]]
  ];
}

function matrixPower(matrix, n) {
  if (n === 1) return matrix;
  if (n % 2 === 0) {
    const half = matrixPower(matrix, n / 2);
    return matrixMultiply(half, half);
  } else {
    return matrixMultiply(matrix, matrixPower(matrix, n - 1));
  }
}

function fibonacci(n) {
  if (n === 0) return 0;
  if (n === 1) return 1;

  const baseMatrix = [[1, 1], [1, 0]];
  const resultMatrix = matrixPower(baseMatrix, n);
  return resultMatrix[0][1];
}

console.log(fibonacci(10)); // Output: 55
Note: The matrix exponentiation approach is particularly useful for recurrences with constant coefficients. For more complex recurrences, the transformation might be more involved.

5. Finding Nth Term

Matrix exponentiation is a powerful technique for computing the nth term of linear recurrence relations efficiently. It's particularly useful when dealing with sequences like Fibonacci, where direct computation becomes inefficient for large values of n.

Property Description Example
Recurrence Relation Represents the sequence as a linear combination of previous terms. F(n) = F(n-1) + F(n-2)
Matrix Representation Transforms the recurrence into matrix multiplication form. 
[F(n)]   [1 1] [F(n-1)]
[F(n-1)] = [1 0] [F(n-2)]
Time Complexity With fast matrix exponentiation, O(log n) per query. Instead of O(n), which is too slow for large n.

Example: Computing Fibonacci Using Matrix Exponentiation

function matrixMultiply(A, B) {
  const [[a, b], [c, d]] = A;
  const [[e, f], [g, h]] = B;
  return [
    [a * e + b * g, a * f + b * h],
    [c * e + d * g, c * f + d * h]
  ];
}

function matrixPower(matrix, n) {
  if (n === 1) return matrix;
  if (n % 2 === 0) {
    const half = matrixPower(matrix, n / 2);
    return matrixMultiply(half, half);
  } else {
    return matrixMultiply(matrix, matrixPower(matrix, n - 1));
  }
}

function fibonacci(n) {
  if (n === 0) return 0;
  if (n === 1) return 1;

  const baseMatrix = [[1, 1], [1, 0]];
  const resultMatrix = matrixPower(baseMatrix, n);
  return resultMatrix[0][1];
}

console.log(fibonacci(10)); // Output: 55
Note: The base matrix for Fibonacci is [[1, 1], [1, 0]]. For other linear recurrences, the matrix must be adjusted accordingly.

6. Implementing Binary Exponentiation

Binary exponentiation is an efficient algorithm to compute a^n in O(log n) time instead of the naive O(n) approach.

Property Description Example
Base case When exponent is 0, result is 1 a^0 = 1
Even exponent If n is even, compute a^(n/2) and square it a^4 = (a^2)^2
Odd exponent If n is odd, compute a^(n-1) and multiply by a a^5 = a^4 * a

Example: Binary Exponentiation in JavaScript

function binaryExponentiation(base, exp) {
  if (exp === 0) return 1;
  if (exp % 2 === 0) {
    const half = binaryExponentiation(base, exp / 2);
    return half * half;
  } else {
    return base * binaryExponentiation(base, exp - 1);
  }
}

// Example usage:
console.log(binaryExponentiation(2, 10)); // Output: 1024
Note: This recursive implementation can be optimized using an iterative approach to avoid stack overflow for large exponents.

7. Solving Graph Path Counting

Matrix exponentiation is a powerful technique for solving graph path counting problems, particularly when you need to compute the number of paths of a specific length between nodes in a directed graph.

This approach leverages the adjacency matrix of the graph and raises it to a power to count paths:

  • Let A be the adjacency matrix of a graph with n nodes.
  • The element A^k[i][j] represents the number of paths of length k from node i to node j.

Example: Computing Paths of Length 2

const adjacencyMatrix = [
  [0, 1, 1, 0],
  [0, 0, 1, 1],
  [1, 0, 0, 1],
  [0, 0, 0, 0]
];

// Matrix multiplication function
function multiplyMatrices(a, b) {
  const size = a.length;
  const result = Array(size).fill().map(() => Array(size).fill(0));
  for (let i = 0; i < size; i++) {
    for (let j = 0; j < size; j++) {
      for (let k = 0; k < size; k++) {
        result[i][j] += a[i][k] * b[k][j];
      }
    }
  }
  return result;
}

// Compute A^2 to get paths of length 2
const matrixSquared = multiplyMatrices(adjacencyMatrix, adjacencyMatrix);
console.log(matrixSquared);
Operation Description Time Complexity Space Complexity
Matrix Exponentiation Raise adjacency matrix to power k O(n^3 * log k) O(n^2)
Path Counting Extract value from A^k[i][j] O(1) O(1)
Note: For large values of k, use fast exponentiation (binary exponentiation) to reduce time complexity.

Key Points

  • Matrix exponentiation allows efficient computation of path counts in directed graphs.
  • The adjacency matrix is raised to the power of the desired path length.
  • Fast exponentiation reduces time complexity from O(k * n^3) to O(log k * n^3).

8. Finding Catalan Numbers

The Catalan numbers are a sequence of natural numbers that have many applications in combinatorial mathematics. They can be computed using matrix exponentiation for efficient calculation.

Property Value Description
Cn 1/(n+1) * (2n choose n) Formula for the nth Catalan number
Recurrence Relation C<sub>n+1</sub> = Σ<sub>i=0</sub><sup>n</sup> C<sub>i</sub> * C<sub>n-i</sub> Recursive definition of Catalan numbers

Example: Matrix Exponentiation for Catalan Numbers

function matrixMultiply(A, B) {
    const n = A.length;
    const C = Array(n).fill().map(() => Array(n).fill(0));
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            for (let k = 0; k < n; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return C;
}

function matrixPower(matrix, power) {
    const n = matrix.length;
    let result = Array(n).fill().map(() => Array(n).fill(0));
    for (let i = 0; i < n; i++) result[i][i] = 1;

    let base = matrix;
    while (power > 0) {
        if (power % 2 === 1) result = matrixMultiply(result, base);
        base = matrixMultiply(base, base);
        power = Math.floor(power / 2);
    }
    return result;
}

function getCatalan(n) {
    if (n === 0) return 1;

    const matrix = [
        [0, 1],
        [1, 1]
    ];
    const resultMatrix = matrixPower(matrix, n);
    return resultMatrix[0][1];
}

console.log(getCatalan(5)); // Output: 42
Note: The matrix exponentiation approach allows for efficient computation of Catalan numbers in O(log n) time complexity, which is much faster than the naive recursive approach.

9. Implementing Modulo Operations

Operation Description Formula Example
Modulo Addition Addition under modulo arithmetic (a + b) mod m 
const a = 15, b = 20, m = 7;
const result = (a + b) % m; // 1
Modulo Multiplication Multiplication under modulo arithmetic (a * b) mod m 
const a = 12, b = 13, m = 5;
const result = (a * b) % m; // 1
Modulo Power Exponentiation under modulo arithmetic (a^b) mod m 
const a = 3, b = 4, m = 5;
const result = Math.pow(a, b) % m; // 2
Modulo Inverse Find x such that (a * x) mod m = 1 Extended Euclidean Algorithm 
function modInverse(a, m) {
  let [gcd, x] = extendedGCD(a, m);
  if (gcd !== 1) return null;
  return (x % m + m) % m;
}

Example: Matrix Exponentiation with Modulo

function matrixMultiply(A, B, mod) {
  const rows = A.length;
  const cols = B[0].length;
  const result = Array(rows).fill().map(() => Array(cols).fill(0));
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      for (let k = 0; k < A[0].length; k++) {
        result[i][j] = (result[i][j] + (A[i][k] * B[k][j]) % mod) % mod;
      }
    }
  }
  return result;
}

function matrixPower(matrix, power, mod) {
  const size = matrix.length;
  let result = Array(size).fill().map(() => Array(size).fill(0));
  for (let i = 0; i < size; i++) result[i][i] = 1;
  let base = matrix;

  while (power > 0) {
    if (power % 2 === 1) {
      result = matrixMultiply(result, base, mod);
    }
    base = matrixMultiply(base, base, mod);
    power = Math.floor(power / 2);
  }
  return result;
}

10. Solving Tribonacci Sequence

The Tribonacci sequence is a generalization of the Fibonacci sequence where each term is the sum of the three preceding terms. The sequence starts with:

  • T(0) = 0
  • T(1) = 1
  • T(2) = 1

For n > 2, T(n) = T(n-1) + T(n-2) + T(n-3)

Using matrix exponentiation, we can compute the nth Tribonacci number efficiently in O(log n) time.

Example: Computing Tribonacci Using Matrix Exponentiation

function matrixMultiply(A, B) {
  const rows = A.length;
  const cols = B[0].length;
  const result = Array(rows).fill().map(() => Array(cols).fill(0));
  
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      for (let k = 0; k < B.length; k++) {
        result[i][j] += A[i][k] * B[k][j];
      }
    }
  }
  return result;
}

function matrixPower(matrix, n) {
  if (n === 1) return matrix;
  if (n % 2 === 0) {
    const half = matrixPower(matrix, n / 2);
    return matrixMultiply(half, half);
  } else {
    return matrixMultiply(matrix, matrixPower(matrix, n - 1));
  }
}

function tribonacci(n) {
  if (n === 0) return 0;
  if (n === 1 || n === 2) return 1;

  const baseMatrix = [
    [1, 1, 1],
    [1, 0, 0],
    [0, 1, 0]
  ];

  const resultMatrix = matrixPower(baseMatrix, n - 2);
  return resultMatrix[0][0];
}

console.log(tribonacci(5)); // Output: 7
Property Description Value
Base Matrix Transition matrix for Tribonacci sequence 
[
  [1, 1, 1],
  [1, 0, 0],
  [0, 1, 0]
]
Time Complexity Efficient computation using matrix exponentiation O(log n)
Space Complexity Recursive stack space for matrix exponentiation O(log n)

11. Optimizing Space Complexity

Approach Description Space Complexity Notes
Standard Matrix Exponentiation Compute matrix powers using repeated multiplication and caching intermediate results. O(n^3 log k) Requires storing all intermediate matrices; space grows with matrix size and exponent.
Binary Exponentiation with Memoization Use binary exponentiation to reduce steps, cache only necessary matrices. O(n^3) Significantly reduces space usage by avoiding redundant computations.
State Space Reduction Transform problem to a smaller state space using mathematical properties. O(n^2) Applicable when transition matrices can be simplified or compressed.

Example: Binary Exponentiation with Memoization

function matrixMultiply(A, B) {
  const n = A.length;
  const C = Array(n).fill().map(() => Array(n).fill(0));
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        C[i][j] += A[i][k] * B[k][j];
      }
    }
  }
  return C;
}

function matrixPower(matrix, power) {
  const n = matrix.length;
  let result = Array(n).fill().map(() => Array(n).fill(0));
  for (let i = 0; i < n; i++) result[i][i] = 1;

  let base = matrix;
  while (power > 0) {
    if (power % 2 === 1) {
      result = matrixMultiply(result, base);
    }
    base = matrixMultiply(base, base);
    power = Math.floor(power / 2);
  }
  return result;
}
Note: For very large exponents, consider modular arithmetic to prevent overflow and further optimize memory.

Was this article helpful?

Related Cheat Sheets