模2下Gauss reduction求解B*X=C的非零解问题（C语言）

Alright, let's break down why your current code only returns the trivial (all-zero) solution and how to fix it to find non-zero solutions like x0=1, x1=1 for your example.

Core Issues with Your Current Code #

Your Gaussian elimination implementation is designed for real/integer fields, but we need to work in the binary field GF(2) (all operations modulo 2). Additionally, you're not handling free variables—which are the key to finding non-trivial solutions for underdetermined or rank-deficient homogeneous systems.

Key Fixes for GF(2) Gaussian Elimination #

Here's what you need to adjust:

• All operations must be modulo 2: In GF(2), addition/subtraction is equivalent to XOR (or (a + b) % 2), and multiplication is equivalent to AND ((a * b) % 2).
• Track pivot positions: Identify which columns are pivot columns (leading 1s) and which are free variables (columns without pivots).
• Assign values to free variables: For homogeneous systems, set free variables to 1 (or any non-zero value) and back-substitute to solve for pivot variables—this generates non-trivial solutions.

Modified C Code for GF(2) Gaussian Elimination #

Let's rewrite your Gaussian elimination function and adjust related code to work in GF(2):

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Allocate a matrix (nb_lines x nb_columns)
int **newMatrice(unsigned long long int nb_lines, unsigned long long int nb_columns) {
    int **mat = malloc(nb_lines * sizeof(int*));
    for (unsigned long long int i = 0; i < nb_lines; i++) {
        mat[i] = calloc(nb_columns, sizeof(int)); // Initialize to 0
    }
    return mat;
}

// Print the system (mod 2)
void afficheSysteme(int **m, unsigned long long int nb_lines, unsigned long long int nb_columns) {
    printf(" /\n");
    for (unsigned long long int i = 0; i < nb_lines; i++) {
        printf("| ");
        for (unsigned long long int j = 0; j < nb_columns; j++) {
            int val = m[i][j] % 2; // Ensure mod 2
            if (j != nb_columns - 1) {
                if (val != 0) {
                    if (j != 0) printf(" + ");
                    printf("X%llu", j);
                }
            } else {
                printf(" = %d (L%llu)", val % 2, i);
            }
        }
        printf("\n");
    }
    printf(" \\ \n");
}

// Find pivot row for given column (first row with 1 in column >= current row)
unsigned long long int getPivot(int **m, unsigned long long int col, unsigned long long int nb_lines) {
    for (unsigned long long int i = col; i < nb_lines; i++) {
        if (m[i][col] % 2 == 1) {
            return i;
        }
    }
    return col; // No pivot found in this column
}

// GF(2) Gaussian elimination to find row-echelon form, track pivot positions
void gaussGF2(int **m, unsigned long long int nb_lines, unsigned long long int nb_columns, bool *is_pivot_col) {
    // Initialize pivot column tracker
    for (unsigned long long int j = 0; j < nb_columns - 1; j++) {
        is_pivot_col[j] = false;
    }

    unsigned long long int current_row = 0;
    for (unsigned long long int col = 0; col < nb_columns - 1 && current_row < nb_lines; col++) {
        // Find pivot row
        unsigned long long int pivot_row = getPivot(m, col, nb_lines);
        if (m[pivot_row][col] % 2 == 0) {
            continue; // No pivot in this column, move to next
        }

        // Swap current row with pivot row
        if (pivot_row != current_row) {
            int *tmp = m[current_row];
            m[current_row] = m[pivot_row];
            m[pivot_row] = tmp;
        }

        // Mark this column as pivot
        is_pivot_col[col] = true;

        // Eliminate this column in all other rows
        for (unsigned long long int i = 0; i < nb_lines; i++) {
            if (i != current_row && m[i][col] % 2 == 1) {
                // Add pivot row to this row (mod 2)
                for (unsigned long long int j = col; j < nb_columns; j++) {
                    m[i][j] = (m[i][j] + m[current_row][j]) % 2;
                    // Ensure non-negative (though mod 2 should handle it)
                    if (m[i][j] < 0) m[i][j] += 2;
                }
            }
        }

        current_row++;
    }
}

// Find a non-trivial solution for homogeneous system B*X=0 (mod 2)
void findNonTrivialSolution(int **m, unsigned long long int nb_lines, unsigned long long int nb_columns, int *sol) {
    bool *is_pivot_col = malloc((nb_columns - 1) * sizeof(bool));
    gaussGF2(m, nb_lines, nb_columns, is_pivot_col);

    // Initialize solution to 0
    for (unsigned long long int i = 0; i < nb_columns - 1; i++) {
        sol[i] = 0;
    }

    // Assign 1 to first free variable, then solve for pivot variables
    bool found_free = false;
    for (unsigned long long int j = 0; j < nb_columns - 1; j++) {
        if (!is_pivot_col[j]) {
            sol[j] = 1;
            found_free = true;
            break;
        }
    }

    if (!found_free) {
        // Only trivial solution exists
        return;
    }

    // Back-substitute to find pivot variables
    for (unsigned long long int i = 0; i < nb_lines; i++) {
        unsigned long long int pivot_col = nb_columns;
        // Find pivot column in this row
        for (unsigned long long int j = 0; j < nb_columns - 1; j++) {
            if (m[i][j] % 2 == 1) {
                pivot_col = j;
                break;
            }
        }
        if (pivot_col == nb_columns) continue; // Row is all zeros

        int sum = 0;
        for (unsigned long long int j = pivot_col + 1; j < nb_columns - 1; j++) {
            sum = (sum + m[i][j] * sol[j]) % 2;
        }
        // m[i][pivot_col] * sol[pivot_col] = (-sum) mod 2 → which is sum mod 2 (since -1 ≡1 mod2)
        sol[pivot_col] = sum % 2;
        if (sol[pivot_col] < 0) sol[pivot_col] += 2;
    }

    free(is_pivot_col);
}

int main() {
    // Example: Solve B*X=0 mod2 where B = [[0,0],[1,1]]
    unsigned long long int nb_lines = 2;
    unsigned long long int nb_columns = 3; // B + C (C is 0 vector)
    int **matrix = newMatrice(nb_lines, nb_columns);

    // Initialize matrix B (mod2)
    matrix[0][0] = 0 % 2;
    matrix[0][1] = 0 % 2;
    matrix[1][0] = 1 % 2;
    matrix[1][1] = 1 % 2;

    // Initialize vector C (0 vector mod2)
    matrix[0][2] = 0 % 2;
    matrix[1][2] = 0 % 2;

    printf("Original system (mod 2):\n");
    afficheSysteme(matrix, nb_lines, nb_columns);

    int *sol = malloc((nb_columns - 1) * sizeof(int));
    findNonTrivialSolution(matrix, nb_lines, nb_columns, sol);

    printf("\n>>> Non-trivial Solution <<<\n");
    for (unsigned long long int i = 0; i < nb_columns - 1; i++) {
        printf("\tx%llu = %d\n", i, sol[i]);
    }

    // Cleanup
    for (unsigned long long int i = 0; i < nb_lines; i++) {
        free(matrix[i]);
    }
    free(matrix);
    free(sol);

    return 0;
}

Expected Output #

Original system (mod 2):
 /
|  = 0 (L0)
| X0 + X1 = 0 (L1)
 \ 

>>> Non-trivial Solution <<<
	x0 = 1
	x1 = 1

Explanation #

1. GF(2) Operations: All arithmetic is done modulo 2, which aligns with your requirement of reducing matrices/vectors mod2.
2. Pivot Tracking: We track which columns are pivot columns to identify free variables. Setting a free variable to 1 ensures we get a non-trivial solution.
3. Back-Substitution: After setting the free variable, we solve for the pivot variables using the row-echelon form of the matrix.

This approach will work for larger matrices too—you just need to ensure all operations stay within GF(2) and handle multiple free variables if needed (you can generate multiple non-trivial solutions by setting different free variables to 1).

内容的提问来源于stack exchange，提问作者Paul