Тест линейной независимости Гаусса для двоичных векторов

Question

Я запрограммировал версию исключения Гаусса, чтобы проверить линейную независимость набора двоичных векторов. Он вводит матрицу (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;
}