Định thức ma trận trong C++

Giới thiệu

Tính định thức (determinant) của ma trận vuông n×n bằng phương pháp khai triển Laplace (cofactor expansion) đệ quy.

Định thức ma trận 2×2 và 3×3

|a b|     |a b c|
|c d|  = ad - bc

|a b c|     a(ei-fh) - b(di-fg) + c(dh-eg)
|d e f|  =
|g h i|

Mã nguồn hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

void getSubMatrix(vector<vector<int>> mat, vector<vector<int>> &temp, int p, int q, int n) {
    int i = 0, j = 0;
    for (int row = 0; row < n; row++) {
        for (int col = 0; col < n; col++) {
            if (row != p && col != q) {
                temp[i][j++] = mat[row][col];
                if (j == n - 1) {
                    j = 0;
                    i++;
                }
            }
        }
    }
}

int determinantOfMatrix(vector<vector<int>> matrix, int n) {
    int det = 0;
    
    if (n == 1) return matrix[0][0];
    if (n == 2) {
        return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
    }
    
    vector<vector<int>> temp(n, vector<int>(n));
    int sign = 1;
    
    for (int i = 0; i < n; i++) {
        getSubMatrix(matrix, temp, 0, i, n);
        det += sign * matrix[0][i] * determinantOfMatrix(temp, n - 1);
        sign = -sign;
    }
    return det;
}

int main() {
    vector<vector<int>> mat = {
        {2, 1, 3},
        {6, 5, 7},
        {4, 9, 8}
    };
    
    cout << "Dinh thuc: " << determinantOfMatrix(mat, 3) << endl;
    return 0;
}

Kết quả chạy chương trình

Dinh thuc: 36

Kiểm tra thủ công

|2 1 3|
|6 5 7| = 2(5×8 - 7×9) - 1(6×8 - 7×4) + 3(6×9 - 5×4)
|4 9 8|

= 2(40 - 63) - 1(48 - 28) + 3(54 - 20)
= 2(-23) - 1(20) + 3(34)
= -46 - 20 + 102 = 36 ✓

Phân tích độ phức tạp

• Thời gian: O(n!) - rất chậm cho n > 10
• Không gian: O(n²) - ma trận con ở mỗi cấp đệ quy

Tối ưu hóa: Khử Gauss (O(n³))

double determinantGaussian(vector<vector<double>> a) {
    int n = a.size();
    double det = 1;
    
    for (int i = 0; i < n; i++) {
        // Tìm pivot
        int pivot = i;
        for (int j = i + 1; j < n; j++) {
            if (abs(a[j][i]) > abs(a[pivot][i])) pivot = j;
        }
        
        if (abs(a[pivot][i]) < 1e-9) return 0; // Ma trận suy biến
        
        if (pivot != i) {
            swap(a[pivot], a[i]);
            det = -det; // Đổi hàng đổi dấu định thức
        }
        
        det *= a[i][i];
        
        // Khử Gauss
        for (int j = i + 1; j < n; j++) {
            double factor = a[j][i] / a[i][i];
            for (int k = i; k < n; k++) {
                a[j][k] -= factor * a[i][k];
            }
        }
    }
    return det;
}

Kết luận

Đệ quy Laplace dễ hiểu nhưng chỉ phù hợp n ≤ 10. Với ma trận lớn, cần dùng khử Gauss O(n³) hoặc phân tích LU.