GF2::GaussSolver — System Queries

Information that a GaussSolver can provide for the system \(A \cdot x = b\).

constexpr std::size_t equation_count() const;     (1)
constexpr bool        is_consistent()  const;     (2)
constexpr std::size_t free_count()     const;     (3)
constexpr std::size_t solution_count() const;     (4)
constexpr std::size_t rank()           const;     (5)

1	Returns the number of equations in the system (the number of rows in \(A\)).
2	Returns `true` if the system of equations is consistent. If the system is not consistent then it has no solutions.
3	Returns the number of free variables in the system.
4	Returns the number of solutions to the system we can directly address.
5	Returns the rank of the bit-matrix \(A\).

Generally speaking if the system is consistent (so has at least one solution) with \(m\) independent equations for \(n\) unknowns and \(n>m\) then it has 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\).

The rank of \(A\) is \(n - f\).

Over \(\mathbb{R}\) a free variable can take on any value hence there are an infinite number of possible solutions to the system. Over \(\mathbb{F}_2\) the situation is different because a free variable can only 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! We supply a method operator() to address quite a lot of those in an indexed manner. The solution_count() method gives you the number of solutions we can access that 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).

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::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:  " << solver.solution_count() << '\n';
}

Output (depends on the values of the random inputs)

Solving the system A.x = b for the following A & b:
101100101100    1
111100010101    0
100101011000    0
111100101000    0
011011111000    0
110001110100    1
110011011001    1
110100010011    1
000110101001    1
110001011000    0
110111010010    0
100000010011    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:  4