Wiki › Thuật toán › Toán học › Khử Gauss (Gaussian Elimination)

Khử Gauss (Gaussian Elimination)

Giải hệ phương trình tuyến tính, tính hạng và định thức bằng biến đổi hàng. Trình bày cho số thực (chọn trụ lớn nhất), modulo số nguyên tố và GF(2) với cơ sở XOR.

huunguyen huunguyen Updated Tháng 11. 16, 2026 Đọc 18 phút 6 lượt xem

Khử Gauss (Gaussian elimination) là thuật toán giải hệ n phương trình tuyến tính m ẩn Ax=b bằng cách biến đổi sơ cấp trên hàng (đổi chỗ hai hàng, nhân một hàng với hằng số khác 0, cộng bội của hàng này vào hàng khác) cho tới khi ma trận có dạng bậc thang. Cùng một khung thuật toán cho ta: nghiệm của hệ (hoặc biết hệ vô nghiệm, vô số nghiệm), hạng của ma trận, định thức, ma trận nghịch đảo. Độ phức tạp O(n·m·min(n,m)), thực tế dùng được với n,m tới khoảng 500 (số thực, modulo) và lớn hơn nhiều trên GF(2) nhờ bitset.

Trong competitive programming, khử Gauss xuất hiện trên ba "trường số": số thực (kỳ vọng, xác suất của bước đi ngẫu nhiên, mạch điện), modulo số nguyên tố (đếm theo modulo, định thức để đếm cây khung) và GF(2) (bài bật tắt đèn, cơ sở XOR, XOR lớn nhất của tập con).

Ý tưởng / Trực giác

Vì sao biến đổi hàng không làm đổi tập nghiệm? Mỗi biến đổi sơ cấp đều khả nghịch: đổi chỗ thì đổi lại, nhân với c≠0 thì nhân với 1/c, cộng c lần hàng j vào hàng i thì trừ lại. Một nghiệm của hệ cũ thỏa mọi phương trình, nên thỏa cả các tổ hợp tuyến tính của chúng; điều ngược lại đúng nhờ tính khả nghịch. Vậy hệ mới và hệ cũ tương đương.

Thuật toán (bản Gauss-Jordan). Duyệt từng cột col. Tìm trong các hàng chưa dùng một hàng có ai,col≠0 (gọi là trụ), đưa nó lên vị trí row, rồi trừ bội thích hợp của hàng trụ khỏi mọi hàng khác để cột col chỉ còn một số khác 0. Nếu cột không có trụ, ẩn tương ứng là ẩn tự do. Kết thúc, mỗi ẩn có trụ được đọc trực tiếp: xcol=arow,m/arow,col.

Phân loại nghiệm. Gọi r là số trụ (hạng của A).

  • Có hàng mà vế trái toàn 0 nhưng vế phải khác 0 (dạng 0=c): vô nghiệm.
  • Ngược lại, nếu r=m: nghiệm duy nhất.
  • Ngược lại (r<m): vô số nghiệm, có m−r ẩn tự do. Trên trường hữu hạn p phần tử, số nghiệm chính xác là pm−r.

Định thức. Đưa ma trận vuông về tam giác trên; định thức bằng tích các phần tử trên đường chéo, đổi dấu mỗi lần đổi chỗ hai hàng (cộng bội một hàng vào hàng khác không đổi định thức). Định thức bằng 0 khi và chỉ khi có cột không có trụ.

Ba trường số, ba cách chọn trụ.

  • Số thực: phép chia cho số rất nhỏ khuếch đại sai số. Luôn chọn trụ có giá trị tuyệt đối lớn nhất trong cột (partial pivoting) và coi |v|<ε là 0. Nếu ma trận đối xứng xác định dương (ví dụ hệ kỳ vọng của bước đi ngẫu nhiên trên đồ thị vô hướng), khử không chọn trụ cũng ổn định.
  • Modulo số nguyên tố p: mọi số khác 0 có nghịch đảo (Fermat nhỏ: a−1=ap−2), nên toàn bộ lý thuyết giữ nguyên; trụ chỉ cần khác 0, không có sai số.
  • GF(2): cộng và trừ đều là XOR, nhân là AND, trụ chỉ cần là bit 1. Một hàng là một số nguyên (hoặc bitset), khử cả hàng bằng một phép XOR. Trường hợp đặc biệt quan trọng là cơ sở XOR: chèn từng số vào một bảng basis[b] (vector có bit cao nhất là b), mỗi lần chèn là một bước khử. Tập các XOR của mọi tập con chính là không gian sinh bởi cơ sở, có đúng 2r phần tử.

Vì sao tham lam trên cơ sở XOR cho giá trị lớn nhất? Trong cơ sở, các vector có bit cao nhất đôi một khác nhau. Duyệt bit từ cao xuống: quyết định lấy basis[b] chỉ ảnh hưởng bit b và các bit thấp hơn, và các vector đứng sau không thể chạm bit b. Vậy để bit b bằng 1 khi có thể là tối ưu, và điều kiện (r ^ basis[b]) > r kiểm tra đúng việc đó.

Ví dụ chạy tay

Giải hệ trên số thực:

{2x+y−z=8−3x−y+2z=−11−2x+y+2z=−3

Ma trận mở rộng và ba lượt khử (chọn trụ có |giá trị| lớn nhất, đánh dấu [ ]):

 ban đầu:                         sau cột 0 (trụ -3, hàng 2 lên đầu):
 [  2    1   -1  |    8  ]        [ [-3]  -1     2   |  -11  ]
 [ -3   -1    2  |  -11  ]        [   0   1/3   1/3  |  2/3  ]
 [ -2    1    2  |   -3  ]        [   0   5/3   2/3  |  13/3 ]

 sau cột 1 (trụ 5/3, đổi 2 hàng): sau cột 2 (trụ 1/5):
 [ -3    0   12/5 | -42/5 ]       [ -3    0     0   |  -6   ]
 [  0  [5/3]  2/3 |  13/3 ]       [  0   5/3    0   |   5   ]
 [  0    0    1/5 |  -1/5 ]       [  0    0   [1/5] | -1/5  ]

Ở cột 0, |−3| lớn nhất nên hàng 2 được đưa lên đầu; ở cột 1, giữa 1/3 và 5/3 ta chọn 5/3 và đổi chỗ hai hàng dưới. Đọc nghiệm:

Ẩn Hàng trụ Phép tính Giá trị
x [−3,0,0∣−6] −6/−3 2
y [0,5/3,0∣5] 5/(5/3) 3
z [0,0,1/5∣−1/5] (−1/5)/(1/5) −1

Thử lại: 2·2+3−(−1)=8, −6−3−2=−11, −4+3−2=−3.

Cơ sở XOR với dãy 1,6,12,6 (4 bit):

Chèn Nhị phân Quá trình basis[3..0]
1 0001 bit 0 trống, đặt basis[0] = 1 0, 0, 0, 1
6 0110 bit 2 trống, đặt basis[2] = 6 0, 6, 0, 1
12 1100 bit 3 trống, đặt basis[3] = 12 12, 6, 0, 1
6 0110 bit 2: XOR với 6 còn 0, phụ thuộc không đổi

Hạng r=3, nên có 23=8 giá trị XOR khác nhau. Tham lam: r=0→12 (bit 3), thử 12⊕6=10<12 nên bỏ, bit 1 trống, 12⊕1=13>12 nên lấy. XOR lớn nhất là 13=1⊕12.

Cài đặt

Số thực (Gauss-Jordan, chọn trụ lớn nhất)
C++
const double EPS = 1e-9;

// Giải hệ a * x = b, a là ma trận n x (m+1) (cột cuối là vế phải).
// Trả về 0 nếu vô nghiệm, 1 nếu nghiệm duy nhất, 2 nếu vô số nghiệm; ans nhận một nghiệm.
int gauss(vector<vector<double>> a, vector<double>& ans) {
    int n = a.size(), m = a[0].size() - 1;
    vector<int> where(m, -1);  // where[c] = hàng chứa trụ của cột c
    for (int col = 0, row = 0; col < m && row < n; col++) {
        int sel = row;  // chọn trụ có |giá trị| lớn nhất (partial pivoting)
        for (int i = row; i < n; i++)
            if (fabs(a[i][col]) > fabs(a[sel][col])) sel = i;
        if (fabs(a[sel][col]) < EPS) continue;  // cột này không có trụ: ẩn tự do
        swap(a[sel], a[row]);
        where[col] = row;
        for (int i = 0; i < n; i++)  // khử cột col ở mọi hàng khác (Gauss-Jordan)
            if (i != row) {
                double c = a[i][col] / a[row][col];
                for (int j = col; j <= m; j++) a[i][j] -= a[row][j] * c;
            }
        row++;
    }
    ans.assign(m, 0);  // ẩn tự do gán 0
    for (int c = 0; c < m; c++)
        if (where[c] != -1) ans[c] = a[where[c]][m] / a[where[c]][c];
    for (int i = 0; i < n; i++) {  // kiểm tra lại: phát hiện hàng 0 = khác 0
        double s = 0;
        for (int j = 0; j < m; j++) s += ans[j] * a[i][j];
        if (fabs(s - a[i][m]) > 1e-6) return 0;
    }
    for (int c = 0; c < m; c++)
        if (where[c] == -1) return 2;
    return 1;
}
Python
EPS = 1e-9


# Giải hệ a * x = b, a là ma trận n x (m+1) (cột cuối là vế phải).
# Trả về (0 vô nghiệm | 1 nghiệm duy nhất | 2 vô số nghiệm, một nghiệm)
def gauss(a):
    a = [row[:] for row in a]
    n, m = len(a), len(a[0]) - 1
    where = [-1] * m  # where[c] = hàng chứa trụ của cột c
    row = 0
    for col in range(m):
        if row == n:
            break
        sel = max(range(row, n), key=lambda i: abs(a[i][col]))  # trụ lớn nhất
        if abs(a[sel][col]) < EPS:
            continue  # ẩn tự do
        a[sel], a[row] = a[row], a[sel]
        where[col] = row
        for i in range(n):  # khử cột col ở mọi hàng khác (Gauss-Jordan)
            if i != row:
                c = a[i][col] / a[row][col]
                for j in range(col, m + 1):
                    a[i][j] -= a[row][j] * c
        row += 1
    ans = [0.0] * m  # ẩn tự do gán 0
    for c in range(m):
        if where[c] != -1:
            ans[c] = a[where[c]][m] / a[where[c]][c]
    for i in range(n):  # kiểm tra lại: phát hiện hàng 0 = khác 0
        s = sum(ans[j] * a[i][j] for j in range(m))
        if abs(s - a[i][m]) > 1e-6:
            return 0, ans
    return (2 if -1 in where else 1), ans
Modulo số nguyên tố: giải hệ và tính định thức
C++
const long long MOD = 1000000007;

long long power(long long a, long long b) {
    long long res = 1;
    a %= MOD;
    for (; b > 0; b >>= 1) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
    }
    return res;
}

// Giải hệ theo modulo số nguyên tố MOD; a là n x (m+1), mọi phần tử trong [0, MOD).
// Trả về số ẩn tự do (>= 0), hoặc -1 nếu vô nghiệm; ans nhận một nghiệm (ẩn tự do = 0).
int gauss_mod(vector<vector<long long>> a, vector<long long>& ans) {
    int n = a.size(), m = a[0].size() - 1, row = 0;
    vector<int> where(m, -1);
    for (int col = 0; col < m && row < n; col++) {
        int sel = -1;  // modulo p chỉ cần trụ khác 0, không cần lớn nhất
        for (int i = row; i < n; i++)
            if (a[i][col] != 0) { sel = i; break; }
        if (sel == -1) continue;
        swap(a[sel], a[row]);
        where[col] = row;
        long long inv = power(a[row][col], MOD - 2);  // chia = nhân nghịch đảo
        for (int j = col; j <= m; j++) a[row][j] = a[row][j] * inv % MOD;
        for (int i = 0; i < n; i++)
            if (i != row && a[i][col] != 0) {
                long long c = a[i][col];
                for (int j = col; j <= m; j++) a[i][j] = (a[i][j] - c * a[row][j] % MOD + MOD) % MOD;
            }
        row++;
    }
    for (int i = row; i < n; i++)  // hàng toàn 0 bên trái nhưng vế phải khác 0
        if (a[i][m] != 0) return -1;
    ans.assign(m, 0);
    for (int c = 0; c < m; c++)
        if (where[c] != -1) ans[c] = a[where[c]][m];
    return m - row;
}

// Định thức ma trận vuông theo modulo MOD: đưa về tam giác trên, đổi hàng thì đổi dấu.
long long det_mod(vector<vector<long long>> a) {
    int n = a.size();
    long long det = 1;
    for (int col = 0; col < n; col++) {
        int sel = -1;
        for (int i = col; i < n; i++)
            if (a[i][col] != 0) { sel = i; break; }
        if (sel == -1) return 0;
        if (sel != col) { swap(a[sel], a[col]); det = (MOD - det) % MOD; }
        det = det * a[col][col] % MOD;
        long long inv = power(a[col][col], MOD - 2);
        for (int i = col + 1; i < n; i++) {
            long long c = a[i][col] * inv % MOD;
            for (int j = col; j < n; j++) a[i][j] = (a[i][j] - c * a[col][j] % MOD + MOD) % MOD;
        }
    }
    return det;
}
Python
MOD = 1000000007


# Giải hệ theo modulo số nguyên tố MOD; a là n x (m+1), phần tử trong [0, MOD).
# Trả về (số ẩn tự do hoặc -1 nếu vô nghiệm, một nghiệm với ẩn tự do = 0)
def gauss_mod(a):
    a = [row[:] for row in a]
    n, m = len(a), len(a[0]) - 1
    where = [-1] * m
    row = 0
    for col in range(m):
        if row == n:
            break
        sel = next((i for i in range(row, n) if a[i][col]), -1)  # trụ khác 0
        if sel == -1:
            continue
        a[sel], a[row] = a[row], a[sel]
        where[col] = row
        inv = pow(a[row][col], MOD - 2, MOD)  # chia = nhân nghịch đảo
        a[row] = [v * inv % MOD for v in a[row]]
        for i in range(n):
            if i != row and a[i][col]:
                c = a[i][col]
                a[i] = [(x - c * y) % MOD for x, y in zip(a[i], a[row])]
        row += 1
    if any(a[i][m] for i in range(row, n)):  # hàng 0 = khác 0
        return -1, None
    ans = [0] * m
    for c in range(m):
        if where[c] != -1:
            ans[c] = a[where[c]][m]
    return m - row, ans


# Định thức ma trận vuông theo modulo MOD: đưa về tam giác trên, đổi hàng thì đổi dấu.
def det_mod(a):
    a = [row[:] for row in a]
    n = len(a)
    det = 1
    for col in range(n):
        sel = next((i for i in range(col, n) if a[i][col]), -1)
        if sel == -1:
            return 0
        if sel != col:
            a[sel], a[col] = a[col], a[sel]
            det = -det % MOD
        det = det * a[col][col] % MOD
        inv = pow(a[col][col], MOD - 2, MOD)
        for i in range(col + 1, n):
            c = a[i][col] * inv % MOD
            if c:
                a[i] = [(x - c * y) % MOD for x, y in zip(a[i], a[col])]
    return det
GF(2): cơ sở XOR

Với hệ phương trình tổng quát trên GF(2), dùng đúng khung gauss_mod nhưng mỗi hàng là một bitset<N>, phép khử là a[i] ^= a[row]. Bản dưới là trường hợp hay gặp nhất: cơ sở của các số nguyên dưới 260.

C++
// Cơ sở XOR (khử Gauss trên GF(2)): basis[b] là vector có bit cao nhất là b, hoặc 0.
struct XorBasis {
    long long basis[60] = {};
    int rank = 0;
    // Thêm x; trả về false nếu x đã biểu diễn được bằng các vector cũ
    bool insert(long long x) {
        for (int b = 59; b >= 0; b--) {
            if (!(x >> b & 1)) continue;
            if (!basis[b]) { basis[b] = x; rank++; return true; }
            x ^= basis[b];  // khử bit b, giống trừ hàng trụ
        }
        return false;
    }
    // XOR lớn nhất của một tập con: tham lam từ bit cao xuống
    long long max_xor() {
        long long r = 0;
        for (int b = 59; b >= 0; b--)
            if ((r ^ basis[b]) > r) r ^= basis[b];
        return r;
    }
    // Số giá trị XOR khác nhau của các tập con là 2^rank
};
Python
# Cơ sở XOR (khử Gauss trên GF(2)): basis[b] là vector có bit cao nhất là b, hoặc 0.
class XorBasis:
    def __init__(self, bits=60):
        self.basis = [0] * bits
        self.rank = 0

    # Thêm x; trả về False nếu x đã biểu diễn được bằng các vector cũ
    def insert(self, x):
        for b in range(len(self.basis) - 1, -1, -1):
            if not (x >> b & 1):
                continue
            if not self.basis[b]:
                self.basis[b] = x
                self.rank += 1
                return True
            x ^= self.basis[b]  # khử bit b, giống trừ hàng trụ
        return False

    # XOR lớn nhất của một tập con: tham lam từ bit cao xuống
    def max_xor(self):
        r = 0
        for v in reversed(self.basis):
            if r ^ v > r:
                r ^= v
        return r

Độ phức tạp

Bài toán Thời gian Bộ nhớ
Giải hệ n×m (số thực hoặc modulo p) O(n·m·min(n,m)) O(nm)
Định thức / nghịch đảo ma trận n×n O(n3) O(n2)
Hệ trên GF(2) với bitset O(n·m·min(n,m)/64) O(nm/64)
Chèn một số vào cơ sở XOR B bit O(B) O(B)

Mỗi cột có trụ gây ra một lượt khử trên n hàng, mỗi hàng O(m) phép tính, và có tối đa min(n,m) trụ. Bản modulo thêm một lần lũy thừa O(logp) mỗi trụ, không đáng kể. Với n=500, khoảng 1,25·108 phép nhân: C++ chạy dưới một giây, Python thuần thì quá chậm (nên dùng phép toán trên cả hàng như zip ở trên, hoặc chỉ dùng cho n cỡ 100 đến 200).

⚠️ Lỗi thường gặp

  • Không chọn trụ lớn nhất trên số thực: chia cho trụ cỡ 10−12 làm nổ sai số; luôn chọn |ai,col| lớn nhất và so với ε thay vì so với 0.
  • Quên kiểm tra vô nghiệm: sau khi khử, các hàng không có trụ phải có vế phải bằng 0; bỏ qua bước này sẽ in "nghiệm" cho hệ vô nghiệm.
  • Dùng sai row và col: khi một cột không có trụ, chỉ tăng col, không tăng row. Viết for (i = 0; i < n; i++) dùng i cho cả hàng lẫn cột chỉ đúng khi ma trận khả nghịch.
  • Modulo âm trong C++: (a - c * b) % MOD có thể âm; cộng MOD trước khi lấy dư. Và c * b phải là long long.
  • Quên đổi dấu định thức mỗi lần đổi chỗ hai hàng, hoặc chia cho trụ mà quên nhân trụ vào định thức.
  • Cơ sở XOR với số 64 bit: dịch 1 << b với b >= 31 là tràn int; dùng 1LL << b hoặc x >> b & 1 như trên. Bảng basis phải đủ số bit của dữ liệu.

Biến thể / Mở rộng

  • Ma trận nghịch đảo: khử Gauss-Jordan trên ma trận ghép [A∣I]; khi bên trái thành I thì bên phải là A−1.
  • Định lý Kirchhoff (ma trận cây): số cây khung của đồ thị bằng định thức của ma trận Laplace bỏ một hàng một cột, tính bằng det_mod.
  • Xích Markov hấp thụ: kỳ vọng số bước và xác suất kết thúc là nghiệm của hệ tuyến tính; xem Chuỗi Markov và kỳ vọng qua hệ phương trình và DP xác suất & kỳ vọng.
  • Khử trạng thái (GTH): khi hệ xác suất kém điều kiện, khử từng trạng thái chỉ bằng cộng, nhân, chia số không âm để giữ sai số tương đối nhỏ.
  • Định thức của ma trận đa thức: tính giá trị tại các căn đơn vị (NTT), khử Gauss tại từng điểm, rồi nội suy ngược; xem FFT.
  • Cơ sở XOR nâng cao: phần tử nhỏ thứ k (đưa cơ sở về dạng rút gọn), cơ sở trên tiền tố có lưu chỉ số để trả lời truy vấn đoạn, cơ sở chu trình của đồ thị (XOR đường đi). Liên hệ Bitset Optimization.

Bài tập luyện

  • XOR Tập Con Lớn Nhất (xorsubset): (Hard) Tìm XOR lớn nhất của một tập con 2·105 số; dựng cơ sở XOR rồi tham lam từ bit cao.
  • XOR cực đại tập con (xorbasis): (Very Hard) XOR lớn nhất của một tập con với giá trị tới 260; cơ sở tuyến tính trên GF(2) rồi tham lam từ bit cao.
  • Hệ phương trình tuyến tính (linearsys): (Very Hard) Giải hệ n×m theo modulo 109+7, báo vô nghiệm hoặc in một nghiệm bất kỳ; đúng bài gauss_mod.
  • Đồ thị (icpc25mbe): (Very Hard) Đánh số cạnh để tối thiểu kỳ vọng tổng điểm của bước đi ngẫu nhiên; số lần qua mỗi đỉnh là nghiệm của hệ n−1 ẩn trên số thực.
  • Xác suất dễ (icpc19nate): (Very Hard) Xác suất thắng trong trò tung đồng xu với hai xâu đích; hệ xích Markov trên automaton kém điều kiện, giải bằng khử trạng thái kiểu GTH.
  • Ống dẫn quỹ đạo kín (icpc26mbg): (Master) Đếm có trọng số các nhật ký vận hành trên vòng; đáp án là hệ số của định thức một ma trận đa thức, tính bằng NTT và khử Gauss modulo tại từng căn đơn vị.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0