GF2::GaussSolver — Solutions Access

Methods that find solutions for the system \(A \cdot x = b\).

GF2::Vector operator()() const;                 (1)
GF2::Vector operator()(std::size_t n) const;    (2)
1 Returns a random solution amongst all the possible solutions for the system \(A \cdot x = b\).
2 Returns a specific solution (solution number n if you like) for the system \(A \cdot x = b\).
Both these methods throw an exception if the system has no solutions. You can avoid that by first calling the solution_count() method.

If the system is consistent (so has at least one solution) with \(m\) independent equations for \(n\) unknowns and \(n > m\) then it has \(f = n-m\) free variables.

A GaussSolver object transforms (a copy of) \(A\) into reduced row echelon form which allows it to quickly check whether or not the system is consistent and to also compute just how many independent equations there really are in the system and hence compute \(f\).

Over \(\mathbb{F}_2\) a free variable can take on one of the two values 0 and 1. Hence if the system is consistent and has \(f\) free variables it will have \(2^f\) possible solutions. So if there are no free variables then a consistent system will have one unique solution.

If \(f\) is large then the number of possible solutions is clearly explosively large! The first call above will always get you one of those solutions picked completely at random. Successive calls may return different solutions.

The second call above allows you to address (a large number of) the possible solutions in an indexed manner. The solution_count() method gives you the number of solutions we can access this way and it will return 0 for an inconsistent system, 1 for a full rank system, and \(\min(2^f, 2^{63})\) for the general case where there are some free variables (the \(2^{63}\) number assumes that std::size_t is a 64 bit integer).

If solver is our GaussSolver object then the call solver(n) will return solution “number” n where n is one of those addressable solutions.

The n must be less than solution_count() or an exception will be thrown.
Example
#include <GF2/GF2.h>
int
main()
{
    std::size_t m = 12;

    auto A = GF2::Matrix<>::random(m);
    auto b = GF2::Vector<>::random(m);
    std::cout << "Solving the system A.x = b for the following A & b:\n";
    print(A, b);

    // Create a solver object for the system
    GF2::GaussSolver<> solver(A, b);

    // Print some general information
    std::size_t num_solutions = solver.solution_count();
    std::cout << "Number of equations in system:   " << solver.equation_count() << '\n';
    std::cout << "Rank of the matrix A:            " << solver.rank()           << '\n';
    std::cout << "Number of free variables:        " << solver.free_count()     << '\n';
    std::cout << "Number of solutions to A.x = b:  " << num_solutions           << '\n';

    // Iterate through all the solutions we can address & check each one is an actual solution
    for (std::size_t ns = 0; ns < num_solutions; ++ns) {
        auto x = solver(ns);
        auto Ax = GF2::dot(A, x);
        std::cout << "Solution: " << x << " has A.x = " <<  Ax << " ";
        std::cout << (b == Ax ? "which matches our rhs b." : "which DOES NOT match our rhs b!!!") << "\n";
    }

    // Maybe there were no solutions?
    if (num_solutions == 0) std::cout << "This system is inconsistent and has NO solutions!\n";
}
Output for a consistent system (details depends on the values of the random inputs)
Solving the system A.x = b for the following A & b:
100001001000    0
001110011010    0
010101011000    1
100011010101    0
110001011111    0
001100100010    0
111101101010    1
010001110001    1
100111010010    0
010100001011    0
111000100001    0
011011011101    1
Number of equations in system:   12
Rank of the matrix A:            11
Number of free variables:        1
Number of solutions to A.x = b:  2
Solution: 110110001010 has A.x = 001000110001 which matches our rhs b.
Solution: 110100101001 has A.x = 001000110001 which matches our rhs b.
Output for an inconsistent system (details depends on the values of the random inputs)
Solving the system A.x = b for the following A & b:
111011010010    1
001110000011    1
011110000001    1
001001011111    1
110001101011    1
100111110011    0
001101100010    1
010000010101    1
110011001100    1
110011100100    1
001011111111    0
010010111001    1
Number of equations in system:   12
Rank of the matrix A:            10
Number of free variables:        2
Number of solutions to A.x = b:  0
This system is inconsistent and has NO solutions!
See Also

solve