Các Khái Niệm Cơ Bản
Hoán vị chẵn lẻ:
Xác định dựa trên số lượng cặp nghịch thế trong một hoán vị.
Ma trận đơn vị E:
Là ma trận vuông có các phần tử trên đường chéo chính đều bằng 1, các phần tử còn lại bằng 0. Khi nhân ma trận này với bất kỳ ma trận nào khác cùng kích thước, kết quả vẫn giữ nguyên giá trị của ma trận ban đầu.
Tính độc lập tuyến tính:
Giả sử ta coi một vectơ n-chiều như một phương trình đa biến bậc nhất. Ví dụ, vectơ (2, 1, 3) tương đương với biểu thức $2x + 1y + 3z$. Hai vectơ được gọi là độc lập tuyến tính nếu không thể thu được vectơ này từ vectơ kia thông qua các phép cộng hoặc nhân vô hướng. Với $n$ vectơ độc lập tuyến tính, tổng quát hóa điều kiện là không tổ hợp nào của $n-1$ vectơ có thể tạo ra vectơ thứ $n$. Điều này cũng đồng nghĩa với việc hệ phương trình tuyến tính $n$ ẩn $n$ phương trình chỉ có nghiệm duy nhất khi các vectơ tương ứng là độc lập tuyến tính.
Bậc (Rank) của ma trận:
Bao gồm hàng bậc và cột bậc. Giá trị rank chính là số lượng tối đa của các vectơ con độc lập tuyến tính.
Ví dụ minh họa:
Hàng bậc của ma trận A là số lượng cột tối đại mà tại đó các vectơ cột độc lập tuyến tính. Ký hiệu thường gặp: r(A)
Tính chất của Định thức:
- Giá trị định thức không đổi sau khi chuyển vị ma trận.
- Khoảng cách hai hàng bất kỳ sẽ làm thay đổi dấu của định thức.
- Cộng bội số của một hàng vào hàng khác không làm thay đổi giá trị định thức.
- Nếu hai hàng tỉ lệ với nhau, định thức bằng 0.
- Nhân tất cả phần tử trong một hàng với hằng số $k$, thì định thức mới bằng $k$ lần định thức cũ.
Một số ứng dụng mở rộng của định thức:
- Số lượng cây khung của đồ thị vô hướng (tính bằng định thức của ma trận Laplacian đã xóa bớt một hàng và một cột).
- Mô phỏng thể tích siêu hình học của khối đa diện tạo bởi $n$ vectơ $n$ chiều (mở rộng của tích có hướng).
Vectơ, Tổ Hợp Tuyến Tính và Không Gian
Vectơ có thể được tưởng tượng như mũi tên hoặc biểu diễn dưới dạng ma trận cột, ví dụ $\begin{bmatrix} 2 \\ -5\\ 8 \end{bmatrix}$.
- Tổ hợp tuyến tính: Phép cộng hoặc trừ giữa các vectơ.
- Không gian sinh bởi tập vectơ: Tập hợp tất cả các vectơ có thể nhận được từ việc kết hợp tuyến tính các vectơ cho trước.
- Cơ sở: Một tập hợp các vectơ độc lập tuyến tính nằm trong không gian đó.
Biến Đổi Tuyến Tính (Ma Trận)
Ma trận thực chất là hiện thân của một biến đổi tuyến tính. Biến đổi này hoạt động tương tự hàm số: nhận vào một vectơ và trả về một vectơ mới. Có thể hiểu là ánh xạ không gian tọa độ này sang không gian khác (như quay, lật...). Tuy nhiên, nó phải tuân thủ tính chất cộng tính ($f(x+y)=f(x)+f(y)$) và thuần nhất ($f(ax)=af(x)$).
Để mô tả biến đổi, ta thường dùng sự thay đổi của các vectơ cơ sở. Ma trận được xây dựng từ các cột chính là ảnh của các vectơ cơ sở. Phép nhân ma trận vectơ sẽ cho biết vị trí mới của vectơ đó trong hệ quy chiếu mới hoặc kết quả biến đổi:
Lưu ý quy tắc nhân: ma trận bên trái nhân với vectơ bên phải.
Ví dụ: Chuyển đổi khoảng cách Manhattan sang Chebyshev bằng cách xoay phẳng 45 độ ngược chiều kim đồng hồ và co giãn $\sqrt 2$ lần. Các vectơ cơ sở $(0,1),(1,0)$ sẽ biến thành $(1,1),(1,-1)$, tạo nên ma trận biến đổi $\begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix}$.
Biến đổi tuyến tính có thể hợp thành. Nếu thực hiện biến đổi A rồi B, ma trận tương ứng là tích của hai ma trận.
Ý Nghĩa Hình Học Của Định Thức
Định thức biểu thị mức độ co giãn không gian của biến đổi tuyến tính đối với thể tích. Ví dụ $det(\dots) = 2$ nghĩa là diện tích sau biến đổi tăng gấp đôi. Nếu định thức bằng 0, biến đổi làm mất chiều (co không gian xuống thấp hơn). Nếu âm, nó kèm theo sự đảo ngược hướng.
Tính chất quan trọng: $det(M_1M_2)=det(M_1)det(M_2)$.
Hệ Phương Trình Tuyến Tính Và Ma Trận
Hệ phương trình viết gọn dưới dạng ma trận: $Ax=v$ ($x,v$ là vectơ, $A$ là ma trận hệ số).
Các Không Gian Con
- Bậc: Chiều không gian sau khi biến đổi.
- Không gian cột: Tập các điểm đến từ việc nhân vô hướng các cột.
- Không gian null: Tập các vectơ bị biến đổi về gốc tọa độ.
Ma trận không vuông: Biểu thị ánh xạ từ không gian $n$ chiều sang $m$ chiều. Dù vậy, chiều tối đa của ảnh vẫn giới hạn bởi bậc của ma trận.
Tích Vô Hướng và Đối Đẳng Cấu
Tích vô hướng có thể xem như một phép chiếu tuyến tính. Về mặt hình học, nó liên quan đến độ dài phép chiếu nhân với chuẩn của vectơ.
Chuyển Đổi Cơ Sở
Trong nhiều bài toán, cần chuyển đổi về hệ trục quen thuộc, thực hiện biến đổi, rồi chuyển về hệ cũ. Công thức tổng quát sử dụng ma trận nghịch đảo: $A^{-1}MA$.
Vectơ Riêng và Trị Riêng
Là những vectơ đặc biệt không đổi hướng sau khi biến đổi (chỉ có độ dài thay đổi). Độ thay đổi đó gọi là trị riêng $\lambda$.
Công thức tính: $Av = \lambda v \Rightarrow det(A-\lambda I)=0$.
Việc này hữu ích để tối ưu lũy thừa ma trận nhanh.
Thuật Toán Thực Tế
Phương Pháp Khử Gauss
Mục tiêu: Biến ma trận hệ số thành dạng bậc thang hoặc chéo. Xử lý từng cột, loại bỏ các phần tử ở dòng dưới.
Kiểm tra nghiệm:
- Nếu xuất hiện hàng $0 = \text{số khác } 0$: Hệ vô nghiệm.
- Nếu số phương trình độc lập nhỏ hơn ẩn: Có vô số nghiệm.
- Còn lại: Nghiệm duy nhất.
Bậc ma trận bằng số hàng không toàn 0 sau khi khử.
Dưới đây là mẫu mã giả lập thuật toán xử lý số thực:
#include <cmath>
const double EPS = 1e-9;
// Hàm giải hệ phương trình Ax = b
void solveSystem(int n, double a[N][N+1]) {
for (int col = 0; col < n; ++col) { // Duyệt từng cột
int pivot = col;
// Tìm hàng dẫn tố lớn nhất trong cột hiện tại
for (int row = col + 1; row < n; ++row) {
if (fabs(a[row][col]) > fabs(a[pivot][col]))
pivot = row;
}
// Nếu pivot quá bé, coi như vô số nghiệm hoặc sai
if (fabs(a[pivot][col]) < EPS) continue;
// Hoán vị dòng pivot lên vị trí hiện tại
std::swap(a[col], a[pivot]);
// Khử các phần tử ở cột col tại các dòng khác
for (int row = 0; row < n; ++row) {
if (row != col && fabs(a[row][col]) > EPS) {
double factor = a[row][col] / a[col][col];
for (int k = col; k <= n; ++k) {
a[row][k] -= factor * a[col][k];
}
}
}
}
// Trích xuất nghiệm
for (int i = 0; i < n; ++i) {
printf("%.6f ", a[i][n] / a[i][i]);
}
}
Dạng xử lý trên trường modulo (ví dụ $10^9+7$):
typedef long long ll;
const ll MOD = 1e9 + 7;
ll matrix[N][N];
// Hàm tính nghịch đảo modular
ll modInverse(ll a) {
return power(a, MOD - 2);
}
void gaussModular(int n) {
for (int col = 0; col < n; ++col) {
int pivot = col;
for (int row = col + 1; row < n; ++row) {
if (abs(matrix[row][col]) > abs(matrix[pivot][col]))
pivot = row;
}
if (!matrix[pivot][col]) continue; // Trường hợp đặc biệt
std::swap(matrix[col], matrix[pivot]);
// Chia dòng pivot cho phần tử chủ chốt để đưa lên 1
ll inv = modInverse(matrix[col][col]);
for (int k = col; k < n; ++k)
matrix[col][k] = (matrix[col][k] * inv) % MOD;
// Khử cột
for (int row = 0; row < n; ++row) {
if (row != col && matrix[row][col]) {
ll factor = matrix[row][col];
for (int k = col; k < n; ++k) {
matrix[row][k] = (matrix[row][k] - factor * matrix[col][k]) % MOD;
if (matrix[row][k] < 0) matrix[row][k] += MOD;
}
}
}
}
}
Ma Trận Nghịch Đảo
Phương pháp Gauss-Jordan mở rộng: Ghép ma trận gốc với ma trận đơn vị $W = [A | I]$. Khử A thành $I$, lúc đó phần ghép bên phải sẽ trở thành $A^{-1}$.
// Giả sử có sẵn hàm khử Gauss
void calculateInverse(int n, double mat[][2*N]) {
// Khởi tạo: Nửa bên trái là A, nửa bên phải là I
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) mat[i][n+j] = 1.0;
else mat[i][n+j] = 0.0;
}
}
// Thực hiện khử Gauss
for (int i = 0; i < n; ++i) {
// Tìm pivot... (giống thuật toán trên)
int pivot = i;
for (int j = i + 1; j < n; ++j)
if (fabs(mat[j][i]) > fabs(mat[pivot][i])) pivot = j;
std::swap(mat[i], mat[pivot]);
double factor = mat[i][i];
for (int k = 0; k < 2*n; ++k) mat[i][k] /= factor;
for (int row = 0; row < n; ++row) {
if (row != i) {
double f = mat[row][i];
for (int k = 0; k < 2*n; ++k)
mat[row][k] -= f * mat[i][k];
}
}
}
// Kết quả nghịch đảo nằm từ col [n] đến [2n-1]
}
Ma Trận Tích Hợp (Compound Matrix)
Là ma trận chứa các phần tử là ma trận con. Dùng để tối ưu các bài toán đệ quy phức tạp. Cần đảm bảo khởi tạo đúng kích thước con để tránh lỗi nhân ma trận.
Định Thức và Định Lý Cây Ma Trận Kirchhoff
Khi tính định thức modulo, thường dùng thuật toán giống Euclid để khử. Mục đích cuối cùng là đưa về ma trận tam giác trên.
Ứng dụng: Tính số cây khung của đồ thị.
Công thức: $|L|$ với $L$ là ma trận Laplacian (Ma trận bậc - Ma trận kề).
Đối với đồ thị có hướng, phân biệt cây hướng đi ra (Out-tree) và cây hướng đi vào (In-tree). Ma trận bậc sẽ tương ứng với vào hoặc ra.
// Mô hình thêm cạnh vô hướng
void addEdge(int u, int v) {
adj[u][u]++; adj[v][v]++; // Cập nhật bậc
adj[u][v]--; adj[v][u]--; // Cập nhật kề
}
// Hàm tính định thức bằng cách khử dần (Euclidean style)
ll calculateDeterminant(int n) {
ll ans = 1;
for (int i = 0; i < n; ++i) {
// Đảm bảo phần tử trên chéo không 0
if (adj[i][i] == 0) {
// Tìm hàng khác có phần tử khác 0 tại cột i để đổi chỗ
bool found = false;
for (int j = i + 1; j < n; ++j) {
if (adj[j][i]) {
std::swap(adj[i], adj[j]);
found = true;
break;
}
}
if (!found) return 0; // Hàng toàn 0 => Det = 0
}
// Khử dòng dưới dòng i
for (int j = i + 1; j < n; ++j) {
while (adj[j][i]) {
ll q = adj[i][i] / adj[j][i];
for (int k = i; k < n; ++k) {
adj[i][k] = (adj[i][k] - q * adj[j][k]) % MOD;
if (adj[i][k] < 0) adj[i][k] += MOD;
}
std::swap(adj[i], adj[j]);
ans = -ans; // Đổi dấu khi đổi dòng
}
}
ans = (ans * adj[i][i]) % MOD;
}
return (ans + MOD) % MOD;
}
Linear Basis (Cơ Sở Tuyến Tính)
Dùng để tìm hạng của tập hợp vectơ nhị phân hoặc thực. Nó giúp xác định số lượng tối thiểu các vectơ cần thiết để sinh ra không gian.
Cách tiếp cận thực tế: Sắp xếp các vectơ theo chiều giảm dần, thử đặt vào cấu trúc lưu trữ. Nếu vectơ mới độc lập với tập hiện tại, thêm vào. Nếu phụ thuộc, dùng basis để triệt tiêu nó.
// Cấu trúc dữ liệu Vector
struct RealVector {
double val[MAXN];
};
RealVector basis[MAXN];
bool hasBasis[MAXN];
int cnt = 0;
// Thêm vectơ v vào Linear Basis
void insert(const RealVector& v) {
for (int i = 0; i < MAXN; ++i) {
if (fabs(v.val[i]) < EPS) continue;
// Kiểm tra xem đã có cơ sở ở bit i chưa
if (!hasBasis[i]) {
hasBasis[i] = true;
basis[i] = v;
cnt++;
return;
} else {
// Loại bỏ thành phần tương ứng với cơ sở cũ
double ratio = v.val[i] / basis[i].val[i];
for (int k = i; k < MAXN; ++k) {
v.val[k] -= ratio * basis[i].val[k];
}
}
}
}
Mã Gốc Ma Trận Nhân Nhanh (Power Of Matrix)
struct Matrix {
int size;
long long data[MAX_N][MAX_N];
// Constructor khởi tạo kích thước và điền 0
Matrix(int s) : size(s) { memset(data, 0, sizeof(data)); }
Matrix operator+(const Matrix& other) const {
Matrix res(size);
for(int i=0; i 0) {
if(exp & 1) res = res * base;
base = base * base;
exp >>= 1;
}
return res;
}