ตรวจสอบว่า Matrix Invertible (มี Matrix ยกกลับ) ใน C++

Matrix M Invertible (มี M⁻¹) ก็ต่อเมื่อ Determinant ≠ 0

M⁻¹ = adj(M) / det(M)

การคำนวณ Determinant (Recursive)

1. Base case: 1×1 → det = element
2. หา Cofactor Matrix (ตัดแถว p, คอลัมน์ q)
3. det = Σ (-1)^(i+j) × a[0][j] × det(Cofactor)

ตัวอย่างโค้ด

#include <iostream>
#define N 4
using namespace std;

void getCofactor(int mat[N][N], int temp[N][N], 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 determinant(int mat[N][N], int n) {
    if (n == 1) return mat[0][0];

    int temp[N][N];
    int det = 0;
    int sign = 1;

    for (int f = 0; f < n; f++) {
        getCofactor(mat, temp, 0, f, n);
        det += sign * mat[0][f] * determinant(temp, n - 1);
        sign = -sign;
    }
    return det;
}

bool isInvertible(int mat[N][N], int n) {
    return determinant(mat, n) != 0;
}

int main() {
    int matrix[N][N] = {
        {1, 0, 2, -1},
        {3, 0, 0, 5},
        {2, 1, 4, -3},
        {1, 0, 5, 0}
    };

    if (isInvertible(matrix, N))
        cout << "The matrix is invertible";
    else
        cout << "The matrix is not invertible";

    return 0;
}

ผลลัพธ์

The matrix is invertible

ความซับซ้อน

เวลา: O(n!) - ใช้ได้กับ Matrix เล็ก (n ≤ 10)

Matrix ใหญ่ ควรใช้ Gaussian Elimination (O(n³)) หรือ LU Decomposition

Gaussian Elimination แบบ Determinant

double detGaussian(vector> a) {
    int n = a.size();
    double det = 1;
    for (int i = 0; i < n; i++) {
        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-12) return 0;
        if (pivot != i) { swap(a[i], a[pivot]); det = -det; }
        det *= a[i][i];
        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;
}