在C语言中如何确定线性方程组自由变量的整数值以获得整数解？

问题背景 #

用C语言求解线性方程组时，遇到了存在自由变量的情况：消元后出现零行，方程组有无穷多解。需要找到一组整数解，但不想硬编码自由变量的取值；同时现有代码在回代阶段因零行出现NaN，需要修复。此外希望方案能通用到多变量（如5变量）的同类问题。

第一个方程组的消元与推导 #

方程组及消元过程：

4a = c          4  0 -1 0             1  0 -0.25 0
10a + b = 4c -> 10 1 -4 0 R1 -> R1/4  10 1 -4    0
2b = 3c         0  2 -3 0             0  2 -3    0         
------------------------------------------------------>
               1 0 -0.25 0                 1 0 -0.25 0
R2-> R2 - 10R  0 1 -1.5  0 R3 -> R3 – 2R2  0 1  1.5  0
               0 2 -3    0                 0 0  0    0

推导得：a = 0.25c、b = 1.5c。手动测试c=4时，a=1、b=6均为整数，但不想硬编码这个值，需要程序自动找到合适的正整数c。

现有C语言代码及运行问题 #

完整代码：

#include <stdio.h>
#include <math.h>

#define N 3  // Number of equations

void print_matrix(double matrix[N][N+1]) {
    printf("Matriz:\n");
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= N; j++) {
            printf("%.2f\t", matrix[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void gauss_elimination(double matrix[N][N+1], double solution[N]) {
    int i, j, k;
    
    // Elimination phase
    for (i = 0; i < N - 1; i++) {
        //Partial pivoting
        for (k = i + 1; k < N; k++) {
            if (fabs(matrix[i][i]) < 1e-10) {
                for (j = 0; j <= N; j++) {
                    double temp = matrix[i][j];
                    matrix[i][j] = matrix[k][j];
                    matrix[k][j] = temp;
                }
            }
        }
        
        // Gaussian elimination
        for (k = i + 1; k < N; k++) {
            double factor = matrix[k][i] / matrix[i][i];
            for (j = i; j <= N; j++) {
                matrix[k][j] -= factor * matrix[i][j];
            }
        }
    }
    print_matrix(matrix);
    
    // Back replacement phase
    for (i = N - 1; i >= 0; i--) {
        solution[i] = matrix[i][N];
        for (j = i + 1; j < N; j++) {
            solution[i] -= matrix[i][j] * solution[j];
        }
        solution[i] /= matrix[i][i];
    }
}

int main() {
    double matrix[N][N+1] = {
        {4.00, 0.00, -1.00, 0.00},
        {10.00, 1.00, -4.00, 0.00},
        {0.00, 2.00, -3.00, 0.00}
    };

    double solution[N];

    // Solve the system
    gauss_elimination(matrix, solution);
    
    printf("Solutions:\n");
    for(int i = 0; i < N; i++){
        printf("%c = %.2f\n",'a' + i, solution[i]);
    }
    return 0;
}

运行结果：

Matriz:
4.00    0.00    -1.00   0.00    
0.00    1.00    -1.50   0.00    
0.00    0.00    0.00    0.00    

Solutions:
a = -nan
b = -nan
c = -nan
=== Code Execution Successful ===
  a     b        c      d
a 4.00  0.00    -1.00   0.00 //=    1/4 = 0,25
b 0.00  1.00    -1.50   0.00 //=    1,50/1 = 1,50
c 0.00  2.00    -3.00   0.00 //= NULL

问题：回代阶段因零行导致除数为0，出现NaN；无法自动找到使所有变量为整数的自由变量取值。

已添加的零行判断逻辑 #

尝试添加零行判断，但仍存在硬编码问题：

int null_row = -1; //  Indicator for null line not found
for (int i = 0; i < N; i++) {
    int is_null = 1;
    for (int j = 0; j < N; j++) {
        if (fabs(matrix[i][j]) > 1e-10) {
            is_null = 0; // The line is not null
            break;
        }
    }
    if (is_null) {
        null_row = i;
        break;
    }
}

if (null_row != -1) {
    // Determine the variable corresponding to the null 
    char null_variable = 'a' + null_row;
    printf("Line Null line variable: %c\n", null_variable);
    // Back substitution phase
    for (i = N - 1; i >= 0; i--) {
        if (fabs(matrix[i][i]) < 1e-10) {
            // Handle special case where matrix[i][i] is zero
            solution[i] = 0.0; 
            // -Set the variable to zero
        } else {
            solution[i] = matrix[i][N];
            for (j = i + 1; j < N; j++) {
                solution[i] -= matrix[i][j] * 4.0;
                //Here I multiplied by 4 is where the problem is. 
               //How to make a loop go through positive integers until the result of 
             //solution[i] /= matrix[i][i]; are integers? Or, I don’t know, some 
           //other way to get the value 4?
            }
            solution[i] /= matrix[i][i];
        }
    }
} else {
    printf("There is no null line.\n");
}

注释中明确问题：当前硬编码了自由变量值4，需要替换为自动遍历正整数的逻辑，找到使所有变量为整数的取值。

5变量方程组测试案例 #

测试的5变量方程组矩阵：

//n = 5
{1.00, 0.00, 0.00, 0.00, -2.00, 0.00},
{1.00, 0.00, -1.00, 0.00, 0.00, 0.00},
{3.00, 3.00, -3.00, -2.00, -1.00, 0.00},
{0.00, 2.00, -1.00, 0.00, 0.00, 0.00},
{0.00, 1.00, 0.00, -1.00, 0.00, 0.00}

行最简形及推导：

matrix reduced to row reduced echelon form as
a = 2e                    1 0 0 0 -2 0
a = c                     0 1 0 0 -1 0
3a + 3b = 3c + 2d + e     0 0 1 0 -2 0
2b = c                    0 0 0 1 -1 0
b = d                     0 0 0 0  0 0 

Here rank(A) = 4 = rank ([A, B]) < n = 5, Thus the system (5) has
infinitely many solutions. Let one variable 𝑥5 is independent variable, it 
takes any real number. Let 𝒙𝟓 = 𝟏, Equations from the matrix (6) are as:  
From first row of matrix (6): 𝑥1 − 2𝑥5 = 0 i.e. 𝒙𝟏 = 𝟐𝒙𝟓 = 𝟐  
From second row of matrix (6): 𝑥2 − 𝑥5 = 0 i.e. 𝒙𝟐 = 𝒙𝟓 = 𝟏  
From third row of matrix (6): 𝑥3 − 2𝑥5 = 0 i.e. 𝒙𝟑 = 𝟐(𝒙𝟓) = 𝟐(𝟏) = 𝟐  
From fourth row of matrix (6): 𝑥4 − 𝑥5 = 0 i.e. 𝒙𝟒 = 𝒙𝟓 = 𝟏  

同样需要处理自由变量，找到整数解的通用方案。

需求总结 #

1. 修复回代阶段因零行导致的NaN问题
2. 实现自动遍历正整数，找到使所有变量为整数的自由变量取值，避免硬编码
3. 提供适用于含任意数量自由变量的线性方程组的通用解决方案

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