What are Matrices?

A matrix is a rectangular array of numbers arranged in rows and columns. In competitive programming, matrices are powerful tools for solving linear recurrences, graph problems, and optimization tasks efficiently.

Basic Matrix Operations

Let's implement fundamental matrix operations:

Matrix Representation

typedef vector<vector<long long>> Matrix;

// Create a matrix with given dimensions
Matrix createMatrix(int rows, int cols, long long value = 0) {
    return Matrix(rows, vector<long long>(cols, value));
}

// Identity matrix
Matrix identity(int n) {
    Matrix result = createMatrix(n, n);
    for(int i = 0; i < n; i++) {
        result[i][i] = 1;
    }
    return result;
}
                    

Matrix Addition

Matrix add(Matrix A, Matrix B) {
    int rows = A.size(), cols = A[0].size();
    Matrix result = createMatrix(rows, cols);
    
    for(int i = 0; i < rows; i++) {
        for(int j = 0; j < cols; j++) {
            result[i][j] = A[i][j] + B[i][j];
        }
    }
    return result;
}
                    

Matrix Multiplication

Matrix multiply(Matrix A, Matrix B, long long mod = 1e9 + 7) {
    int rows = A.size(), cols = B[0].size(), common = B.size();
    Matrix result = createMatrix(rows, cols);
    
    for(int i = 0; i < rows; i++) {
        for(int j = 0; j < cols; j++) {
            for(int k = 0; k < common; k++) {
                result[i][j] = (result[i][j] + (A[i][k] * B[k][j]) % mod) % mod;
            }
        }
    }
    return result;
}
                    

Matrix Exponentiation

Matrix exponentiation allows us to compute A^n efficiently in O(k³ log n) time, where k is the matrix dimension:

Matrix matrixPower(Matrix base, long long exp, long long mod = 1e9 + 7) {
    int n = base.size();
    Matrix result = identity(n);
    
    while(exp > 0) {
        if(exp & 1) {
            result = multiply(result, base, mod);
        }
        base = multiply(base, base, mod);
        exp >>= 1;
    }
    return result;
}
                    

Linear Recurrence Relations

Matrix exponentiation excels at solving linear recurrences like Fibonacci sequences:

Fibonacci with Matrix Exponentiation

long long fibonacci(long long n) {
    if(n <= 1) return n;
    
    // Transition matrix for F(n) = F(n-1) + F(n-2)
    Matrix transition = {{1, 1}, {1, 0}};
    Matrix result = matrixPower(transition, n - 1);
    
    // [F(n), F(n-1)] = [F(1), F(0)] * transition^(n-1)
    return result[0][0]; // F(n)
}
                    

General Linear Recurrence

For recurrence: f(n) = c₁×f(n-1) + c₂×f(n-2) + ... + cₖ×f(n-k)

// Solve f(n) = c[0]*f(n-1) + c[1]*f(n-2) + ... + c[k-1]*f(n-k)
long long linearRecurrence(vector<long long> coeffs, vector<long long> initial, long long n) {
    int k = coeffs.size();
    if(n < k) return initial[n];
    
    // Create transition matrix
    Matrix transition = createMatrix(k, k);
    for(int i = 0; i < k; i++) {
        transition[0][i] = coeffs[i];
    }
    for(int i = 1; i < k; i++) {
        transition[i][i-1] = 1;
    }
    
    Matrix result = matrixPower(transition, n - k + 1);
    
    long long answer = 0;
    for(int i = 0; i < k; i++) {
        answer = (answer + (result[0][i] * initial[k-1-i]) % MOD) % MOD;
    }
    return answer;
}
                    

Graph Applications

Matrices are powerful for graph problems:

Counting Paths

If A is the adjacency matrix, then A^k gives the number of paths of length k between vertices:

// Count paths of length k from vertex u to vertex v
long long countPaths(vector<vector<int>>& adj, int u, int v, int k) {
    int n = adj.size();
    Matrix adjMatrix = createMatrix(n, n);
    
    // Convert adjacency list to matrix
    for(int i = 0; i < n; i++) {
        for(int neighbor : adj[i]) {
            adjMatrix[i][neighbor] = 1;
        }
    }
    
    Matrix result = matrixPower(adjMatrix, k);
    return result[u][v];
}
                    

Advanced Techniques

Some advanced matrix operations for competitive programming:

Matrix Determinant

long long determinant(Matrix A, long long mod = 1e9 + 7) {
    int n = A.size();
    long long det = 1;
    
    for(int i = 0; i < n; i++) {
        int pivot = -1;
        for(int j = i; j < n; j++) {
            if(A[j][i] != 0) {
                pivot = j;
                break;
            }
        }
        
        if(pivot == -1) return 0; // Determinant is 0
        
        if(pivot != i) {
            swap(A[i], A[pivot]);
            det = (mod - det) % mod; // Change sign
        }
        
        det = (det * A[i][i]) % mod;
        
        long long inv = modInverse(A[i][i], mod);
        for(int j = i + 1; j < n; j++) {
            long long factor = (A[j][i] * inv) % mod;
            for(int k = i; k < n; k++) {
                A[j][k] = (A[j][k] - (factor * A[i][k]) % mod + mod) % mod;
            }
        }
    }
    
    return det;
}