bit::solve — Solver

We supply a standalone non-member function that attempts to solve the system of linear equations \(A \cdot x = b\) over \(\mathbb{F}_2\).

std::optional<bit::vector>
1bit::solve(const bit::matrix &A, const bit::vector &b)
1
A must be square, and b must be the same size as the number of rows in A.

The std::optional return value can be safely dereferenced as a bit-vector if everything goes well. That bit-vector will be a solution \(x\) to the system \(A \cdot x = b\). The solution may or may not be unique.

If there is a problem, the return value will be a std::nullopt. This happens if the system of equations has no solution. It will also be the case if A is not square or if the size of b is not the same as the number of rows in A.

We want to get one solution for a system of equations with very little fuss.
Over \(\mathbb{F}_2\), any free variable can take on one of the values 0 and 1. Hence, if the system is consistent and has \(f\) free variables, it will have \(2^f\) possible solutions. So, a consistent system will have a unique solution only if \(A\) has full-rank. The gauss::operator(i) method iterates through potentially non-unique solutions if that is required.

Example

#include <bit/bit.h>
int main()
{
    std::size_t m = 12;

    auto A = bit::matrix<>::random(m);
    auto b = bit::vector<>::random(m);
    auto x = bit::solve(A, b);

    if (x) {
        // Check that x is indeed a solution by computing A.x and comparing that to b
        auto Ax = bit::dot(A, *x);
        std::cout << "bit::matrix A, solution vector x, product A.x, and right hand side b:\n";
        std::cout << "      A         x      A.x      b\n";
        bit::print(A, *x, Ax, b);
        std::cout << "So A.x == b? " << (Ax == b ? "YES" : "NO") << '\n';
    }
    else {
        std::cout << "System A.x = b has NO solutions for A and b as follows:\n";
        std::cout << "      A         x\n";
        bit::print(A, b);
    }
}

Output for a consistent system (varies on each run)

bit::matrix A, solution vector x, product A.x, and right hand side b:
      A         x      A.x      b
001110110111    0       0       0
100011110000    0       1       1
110010110000    0       0       0
011101011001    0       0       0
011001111001    1       0       0
011010011110    1       0       0
110110110101    0       0       0
100000010101    1       1       1
010101000101    1       1       1
110000011111    1       0       0
001010000011    0       0       0
110111110111    1       1       1
So A.x == b? YES

Output for an inconsistent system (varies on each run)

System A.x = b has NO solutions for A and b as follows:
      A         x
010100100011    1
000010010000    1
000111111011    1
000111111011    1
001101110011    1
111001110111    1
010001010111    1
101011000001    0
110101110111    0
111000010000    0
011011010100    1
011001110010    0

See Also

gauss::operator()
gauss::operator(i)

Back to top