Nhân ma trận

Một phép toán cơ bản nhưng quan trọng trong nhiều bài toán lập trình là phép nhân ma trận. Để thực hiện phép nhân giữa hai ma trận \( A \) và \( B \), điều kiện cần là số cột của \( A \) phải bằng số hàng của \( B \). Cụ thể, nếu \( A \) có kích thước \( n \times m \) và \( B \) có kích thước \( m \times k \), thì kết quả \( C = A \times B \) sẽ là một ma trận \( n \times k \).

Phần tử \( C[i][j] \) được tính bằng tổng tích của từng cặp phần tử tương ứng từ hàng thứ \( i \) của \( A \) và cột thứ \( j \) của \( B \):
\( C[i][j] = \sum_{k=1}^{m} A[i][k] \times B[k][j] \)

Dưới đây là đoạn mã minh họa việc nhân hai ma trận:

#include <iostream>
using namespace std;

const int MAX = 105;
int n, m, p;
long long A[MAX][MAX], B[MAX][MAX], C[MAX][MAX];

int main() {
    cin >> n >> m >> p;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> A[i][j];
    
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= p; ++j)
            cin >> B[i][j];
    
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= p; ++j)
            for (int k = 1; k <= m; ++k)
                C[i][j] += A[i][k] * B[k][j];
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= p; ++j)
            cout << C[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

Lũy thừa ma trận nhanh

Tương tự như lũy thừa nhanh trên số nguyên, ta có thể áp dụng kỹ thuật chia để trị cho việc tính lũy thừa của một ma trận. Điều kiện then chốt ở đây là phép nhân ma trận có tính kết hợp: \( (A \times B) \times C = A \times (B \times C) \), tuy nhiên không có tính giao hoán: \( A \times B \neq B \times A \). Vì vậy, thứ tự nhân ma trận khi triển khai rất quan trọng.

Ý tưởng: Thay vì nhân ma trận liên tiếp \( n \) lần (độ phức tạp \( O(n) \)), ta dùng kỹ thuật bình phương liên tiếp để giảm xuống \( O(\log n) \).

Ví dụ: Tính \( M^n \), với \( M \) là ma trận vuông. Ta khởi tạo ma trận đơn vị làm kết quả, sau đó duyệt các bit của \( n \), mỗi khi bit là 1 thì nhân vào kết quả.

Bài toán cầu thang – Áp dụng ma trận nhanh

Phiên bản đơn giản: Có bao nhiêu cách để leo lên bậc thang thứ \( n \), biết mỗi bước có thể đi 1 hoặc 2 bậc? Đây chính là dãy Fibonacci: \( f(n) = f(n-1) + f(n-2) \).

Để tối ưu, ta biểu diễn công thức truy hồi dưới dạng ma trận:

\[ \begin{bmatrix} f(n) \\ f(n-1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} f(n-1) \\ f(n-2) \end{bmatrix} \]

Vậy nên:

\[ \begin{bmatrix} f(n) \\ f(n-1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1} \times \begin{bmatrix} f(1) \\ f(0) \end{bmatrix} \]

Khởi tạo: \( f(1) = 1, f(2) = 1 \), suy ra ma trận ban đầu là \( [1, 1] \).

Phiên bản mở rộng: Mỗi bước có thể đi tối đa \( m \) bậc. Khi đó, công thức trở thành:
\( f(n) = f(n-1) + f(n-2) + \dots + f(n-m) \)

Ma trận chuyển trạng thái sẽ có kích thước \( m \times m \). Dưới đây là cách khởi tạo ma trận chuyển tiếp \( T \) và ma trận kết quả ban đầu (ma trận đơn vị):

// Khởi tạo ma trận chuyển tiếp T cho bài toán tổng quát
for (int i = 1; i <= m; ++i) {
    result[i][i] = 1;         // Ma trận kết quả (ban đầu là đơn vị)
    transition[i][m] = 1;     // Cột cuối cùng chứa toàn 1
    if (i < m) transition[i+1][i] = 1;
}

Trong đó, result là ma trận lưu lũy thừa, transition là ma trận cơ sở.

Khi nào nên nghĩ đến lũy thừa ma trận?

• Có công thức truy hồi tuyến tính.
• Giá trị \( n \) rất lớn (ví dụ: \( 10^9 \)) khiến không thể dùng vòng lặp thông thường.
• Bài toán DP có thể biểu diễn dưới dạng biến đổi trạng thái bằng ma trận.
• Trong lý thuyết đồ thị: số đường đi độ dài \( k \) giữa các đỉnh có thể tính bằng lũy thừa ma trận kề.
• Sử dụng ma trận kề hoặc ma trận chuyển tiếp để mô phỏng quá trình.

Lưu ý đặc biệt: Luôn kiểm tra kích thước ma trận và thứ tự nhân — do tính không giao hoán, sai thứ tự sẽ dẫn đến kết quả sai.

Kết luận

Lũy thừa ma trận là công cụ mạnh để tối ưu các bài toán truy hồi tuyến tính. Chìa khóa nằm ở việc xác định đúng:

• Vector trạng thái ban đầu.
• Ma trận chuyển tiếp.
• Thứ tự nhân ma trận khi sử dụng phép lũy thừa.

Khi gặp bài toán có truy hồi và \( n \) lớn, hãy lập tức cân nhắc khả năng áp dụng lũy thừa ma trận.