Tác giả: Trần Quốc Huy - sinh viên năm 3, chuyên ngành Trí tuệ nhân tạo, khoa Công nghệ thông tin 2, Học viện Công nghệ Bưu Chính Viễn Thông - cơ sở tại Thành phố Hồ Chí Minh.
Trước hết tôi xin cảm ơn bạn Nguyễn Nguyễn Gia Bảo, Nguyễn Khánh Phúc, Nguyễn Phú Trọng, Nguyễn Duy Quân, Võ Đức Đoàn và Bảo Quý Định Tân ****đã nhận xét và đóng góp bài blog này.
Đại số tuyến tính là một trong những môn đại cương quen thuộc đối với các sinh viên của khối ngành kĩ thuật, tuy nó là một bộ môn khá khó (quan điểm tác giả), nhưng với lập trình thi đấu, chúng ta có thể “sử dụng được vài trò trong bộ môn Đại số tuyến tính” để có thể giải quyết được các bài toán “khá vui”.
Khái niệm lũy thừa ma trận là một trong những chủ đề rất là hữu ích trong việc giải quyết các câu hỏi liên quan đến việc tính toán số thứ n trong phương trình hồi quy tuyến tính với độ phức tạp thời gian của thuật toán là $O(log(n))$.
Đây là dạng mà tác giả cảm thấy là cơ bản nhất để có thể xử lí bằng lũy thừa ma trận.
Đầu tiên, chúng ta biết, phương trình hồi quy tuyến tính (phương trình sai phân tuyến tính) có dạng tổng quát như sau (phương trình 1):
<aside> 💡
$$
f_n = \sum_{i = 1}^{k}c_i * f_{n - i}
$$
</aside>
Ví dụ minh họa, các phương trình sau sẽ được gọi là phương trình hồi quy tuyến tính:
$$ f_n = 2 * f_{n - 1} + 3 * f_{n - 2} $$
$$ f_n = 6 * f_{n - 1} + 7 * f_{n - 2} + 3 * f_{n - 3} $$
Lưu ý là $c_i$ trong phương trình 1 có thể là giá trị $0$ .
(1) Từ đây, ta gọi ma trận $T$ với kích thước $k * k$ dựa trên phương trình 1 như sau:
$$ \begin{bmatrix} 0 & 1 & 0 & 0 & . & . \\ 0 & 0 & 1 & 0 & . & . \\ 0 & 0 & 0 & 1 & . & . \\ . & . & . & . & . & . \\ c_k & c_{k - 1} & c_{k - 2} & . & . & c_1 \end{bmatrix} $$