หา Determinant ของเมทริกซ์ใน C++

บทนำ

Determinant (อาจารยธรรม) ของเมทริกซ์สี่เหลี่ยมจัตุรัส คำนวณได้โดยการขยายโคแฟกเตอร์ (Cofactor Expansion) แบบ Recursive

ขั้นตอนการแก้ปัญหา

1. ถ้าเมทริกซ์ 1×1 → คืนค่าเดี่ยว
2. ถ้าเมทริกซ์ 2×2 → ad - bc
3. เมทริกซ์ใหญ่กว่า: ขยายตามแถวแรก
4. สร้าง Submatrix โดยตัดแถวและคอลัมน์ขององค์ประกอบปัจจุบัน
5. Determinant = Σ (-1)^(i+j) × a[0][j] × det(submatrix)

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

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

#define N 3

void subMatrix(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 determinantOfMatrix(int matrix[N][N], int n) {
    int determinant = 0;
    if (n == 1) {
        return matrix[0][0];
    }
    if (n == 2) {
        return (matrix[0][0] * matrix[1][1]) - (matrix[0][1] * matrix[1][0]);
    }
    int temp[N][N], sign = 1;
    for (int i = 0; i < n; i++) {
        subMatrix(matrix, temp, 0, i, n);
        determinant += sign * matrix[0][i] * determinantOfMatrix(temp, n - 1);
        sign = -sign;
    }
    return determinant;
}

int main() {
    int mat[N][N] = {{2, 1, 3}, {6, 5, 7}, {4, 9, 8}};
    cout << "Determinant: " << determinantOfMatrix(mat, N) << endl;
    return 0;
}

ผลลัพธ์

Determinant: 36

ตรวจสอบ

| 2 1 3 | | 6 5 7 | | 4 9 8 | = 2(5×8 - 7×9) - 1(6×8 - 7×4) + 3(6×9 - 5×4) = 2(40-63) - 1(48-28) + 3(54-20) = 2(-23) - 20 + 3(34) = -46 - 20 + 102 = 36 ✓

หมายเหตุประสิทธิภาพ

อัลกอริทึมนี้ O(n!) เหมาะเฉพาะเมทริกซ์เล็ก (n ≤ 10) สำหรับเมทริกซ์ใหญ่ ใช้ LU Decomposition หรือ Gaussian Elimination O(n³)

สรุป

Cofactor Expansion เป็นวิธีคลาสสิกสอนในLinear Algebra ใช้ได้จริงกับเมทริกซ์ขนาดเล็ก