Ma trận chéo trội (Diagonally Dominant Matrix) trong C++

Giới thiệu

Ma trận vuông n×n gọi là chéo trội nếu tại mỗi hàng, giá trị tuyệt đối của phần tử trên đường chéo chính lớn hơn hoặc bằng tổng giá trị tuyệt đối của các phần tử còn lại trên hàng đó.

Định nghĩa toán học

Ma trận A = [aᵢⱼ] n×n là chéo trội nếu:

|aᵢᵢ| ≥ Σⱼ₌₁,ⱼ≠ᵢⁿ |aᵢⱼ| với mọi i = 1..n

Ví dụ

Ma trận:
4  2  1
3  5  2
2  4  7

Kiểm tra:
Hàng 1: |4| = 4 ≥ |2|+|1| = 3     ✓
Hàng 2: |5| = 5 ≥ |3|+|2| = 5     ✓
Hàng 3: |7| = 7 ≥ |2|+|4| = 6     ✓
→ Là ma trận chéo trội

Mã nguồn hoàn chỉnh

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

bool isDiagonallyDominantMatrix(vector<vector<int>> matrix) {
    int n = matrix.size();
    
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = 0; j < n; j++) {
            if (i != j) {
                sum += abs(matrix[i][j]);
            }
        }
        if (abs(matrix[i][i]) < sum) {
            return false;
        }
    }
    return true;
}

int main() {
    vector<vector<int>> matrix = {
        {4, 2, 1},
        {3, 5, 2},
        {2, 4, 7}
    };
    
    if (isDiagonallyDominantMatrix(matrix)) {
        cout << "Yes - La ma tran cheo troi" << endl;
    } else {
        cout << "No - Khong phai ma tran cheo troi" << endl;
    }
    return 0;
}

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

Yes - La ma tran cheo troi

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

• Thời gian: O(n²) - duyệt toàn bộ ma trận
• Không gian: O(1) - không dùng bộ nhớ phụ

Loại ma trận chéo trội

Ứng dụng quan trọng

• Phương pháp lặp Jacobi/Gauss-Seidel: Hội tụ nếu ma trận chéo trội mạnh
• Giải hệ phương trình tuyến tính: Đảm bảo ổn định số
• Phân tích giá trị riêng: Định lý Gershgorin

Kết luận

Ma trận chéo trội là khái niệm quan trọng trong đại số tuyến tính số, đảm bảo hội tụ của nhiều phương pháp lặp giải hệ phương trình.