bit::gauss — Construction

1gauss(const bit::matrix &A, const bit::vector &b);

gauss
2gauss_for(const bit::matrix &A, const bit::vector &b);
1
Instance constructor.
2
Non-member factory constructor.

These construct a gauss object for the system \(A \cdot x = b\) where \(A\) is a square bit-matrix, and \(b\) is a bit-vector of the same size as there are rows in \(A\).

On construction, a gauss computes the reduced row echelon form of \(A\) by using elementary row operations. It performs the same operations to a copy of the input bit-vector \(b\). Once done, it can readily compute the rank of \(A\), check the system for consistency, calculate the number of free variables, etc.

If \(A\) is \(n \times n\), then construction is an \(\mathcal{O}(n^3)\) operation (though due to the nature of \(\mathbb{F}_2\), things are done in blocks at a time). There are potentially sub-cubic ways of doing this work using various block-iterative methods that have not yet been implemented.

Example

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

    auto A = bit::matrix<>::random(m);
    auto b = bit::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
    auto solver = bit::gauss(A, b);

    // Print some general information
    std::cout << "Number of equations in the 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';

    // Also have a look at the echelon form of A and the equivalently transformed b
    std::cout << "The echelon forms of A & b are:\n";
    print(solver.lhs(), solver.rhs());
}

Output (depends on the values of the random inputs)

Solving the system A.x = b for the following A & b:
011100100101    0
000111011100    1
111101000011    1
010000111110    1
110011110000    1
101100100100    1
011010110010    0
010010000111    1
101110110001    0
001100101110    1
100000011010    1
111111010100    1
Number of equations in the system: 12
Rank of the matrix A:              11
Number of free variables:          1
Number of solutions to A.x = b:    2
The echelon forms of A & b are:
100000000000    1
010000000000    0
001000000000    1
000100000000    0
000010000100    0
000001000000    0
000000100100    1
000000010000    1
000000001000    0
000000000010    1
000000000001    0
000000000000    0
Back to top