`GF2::Matrix` — Bit-Matrix Inversion

Non-member function that attempts to invert a square bit-matrix.

template<std::unsigned_integral Block, typename Allocator>
std::optional<Matrix<Block, Allocator>>
GF2::invert(const Matrix<Block, Allocator> &M);

If this method is successful it will return \(M^{-1}\) wrapped in a std::optional. If the input matrix \(M\) is singular it will instead return std::nullopt.

Randomly filled matrices over GF(2) are quite likely to be singular. In fact one can show for matrices that are \(10 \times 10\) or larger there is a 71% chance the matrix is singular if the elements were set by flipping fair coins. This contrasts to matrices over the reals where, mathematically at least, matrices are almost surely invertible (though of course the numerics of the situation my not be so certain).

The input matrix must be square. That is checked using the gf2_assert macro. That check can be disabled by setting the GF2_NDEBUG flag at compile time.

Example

#include <GF2/GF2.h>
int main()
{
    auto A = GF2::Matrix<>::rotate(8);  (1)
    auto B = GF2::invert(A);
    if(B) {
        std::cout << "Matrix, its inverse, their product:\n";
        GF2::print(A,*B, GF2::dot(A,*B));
    }
    else {
        std::cout << "Matrix:\n" << A << "\n" << "Is singular!\n";
    }
}

1	The product of `A` and any 8-element bit-vector will rotate the elements in the vector one place to the left (see `rotate`). Obviously `A` is invertible so `B` exists and simply acts on bit-vectors by rotating their elements one place to right.

Output

Matrix, its inverse, their product:
00000001        01000000        10000000
10000000        00100000        01000000
01000000        00010000        00100000
00100000        00001000        00010000
00010000        00000100        00001000
00001000        00000010        00000100
00000100        00000001        00000010
00000010        10000000        00000001

GF2::Matrix — Bit-Matrix Inversion

`GF2::Matrix` — Bit-Matrix Inversion