1

我编写了一个版本的高斯消除来验证一组二进制向量的线性独立性。它输入一个矩阵 (mxn) 来评估并返回：

  • True（线性无关）：未找到零行。
  • False（线性相关）：如果最后一行为零。

它似乎总是运行良好，或者至少几乎运行良好。我发现当矩阵在最后一行有两个重复向量时它不起作用：

std::vector<std::vector<int>> A = {
    {1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1 },
    {0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0 },
    {0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0 },
    {0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0},   // <---- duplicated
    {0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0},}; // <---- duplicated
gaussianElimination_binary(A);

该函数说矩阵是“线性独立的”，因为没有找到零行，而且结果中确实有任何零行。但是调试我发现在某些时候一行变成了零，但是在一些行操作之后它又恢复了“正常”。

我仔细检查了代码，使其工作的唯一方法是在流程结束之前找到“零行”时也返回“false” ，更准确地说，在行操作期间：

// perform XOR in "k-th" row against "row-th" row
    for (int k = 0; k <= max_row; ++k) //k=col_pivot?
    {
        if ( (k != row)   )
        {
            int check_zero_row = 0; // <---- APPLIED PATCH
            for (std::size_t j = 0; j <= max_col; j++) {
                B[k][j] = B[k][j] ^ B[row][j];
                check_zero_row = check_zero_row | B[k][j];
            }
            if (check_zero_row == 0 ) // <---- APPLIED PATCH
            {
                return false;
            }
        }
    }

我想知道这是否正确，或者我只是在“修补”错误的代码。

谢谢！

下面是完整的代码：

#include vector
bool gaussianElimination_binary(std::vector<std::vector<int>> &A) {
std::vector<std::vector<int>> B = A;
std::size_t max_col = B[0].size() - 1;      //cols
std::size_t max_row = B.size() -1 ;     //rows
std::size_t col_pivot = 0;

//perform "gaussian" elimination
for (std::size_t row = 0; row <= max_row; ++row) //for every column
{
    if (col_pivot > max_col)
        break;

    // Search for first row having "1" in column "lead"
    std::size_t i = row; //Start searching from row "i"=row
    while (B[i][col_pivot] == 0)
    {
        ++i;
        if (i > max_row) // no "1" was found across rows
        {
            i = row;        // set "i" back to "row"
            ++col_pivot;    // move to next column
            if (col_pivot > max_col) //if no more columns
                break;
        }
    }

    // swap "i" and "row" rows
    if ((0 <= i) && (i <= max_row) && (0 <= row) && (row <= max_row)) {
        for (std::size_t col = 0; col <= max_col; ++col) {
            std::swap(B[i][col], B[row][col]);
        }
    }

    // perform XOR in "k-th" row against "row-th" row
    for (int k = 0; k <= max_row; ++k) //k=col_pivot?
    {
        if ( (k != row)   )
        {
            int check_zero_row = 0;
            for (std::size_t j = 0; j <= max_col; j++) {
                B[k][j] = B[k][j] ^ B[row][j];
                check_zero_row = check_zero_row | B[k][j];
            }
            if (check_zero_row == 0 )
            {
                return false;
            }
        }
    }
}

return true;
}
4

0 回答 0