GF2::Matrix — Probability that a Bit-Matrix is Invertible

Class methods that calculates the probability that a square bit-matrix is invertible or singular.

double GF2::Matrix<>::probability_invertible(std::size_t n);   (1)
double GF2::Matrix<>::probability_singular(std::size_t n);     (2)
1 Returns the probability that an \(n \times n\) bit-matrix filled by flipping fair coins is invertible.
2 Returns the probability that an \(n \times n\) bit-matrix filled by flipping fair coins is singular (i.e. non-invertible).

The simplest possible case is a \(1 \times 1\) matrix \(A = [a_{11}]\). Now \(a_{11}\) can only be 0 or 1 so this matrix is invertible 50% of the time and singular the other 50% of the time.

More generally, 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 roughly a 71% chance the matrix is singular if the elements were set by flipping fair coins. This contrasts to matrices over \(\mathbb{R}\) where, mathematically at least, matrices are almost surely invertible (of course the numerics of the situation over \(\mathbb{R}\) may not be so certain).

Example: Create lots of \(N \times N\) matrices and see how many are singular
#include <GF2/GF2.h>
int
main()
{
    std::size_t N = 100;                                        (1)
    std::size_t trials = 1000;                                  (2)
    std::size_t fails = 0;
    for (std::size_t trial = 0; trial < trials; ++trial) {
        auto A = GF2::Matrix<>::random(N, N);                   (3)
        auto B = GF2::invert(A);                                (4)
        if (!B) ++fails;                                        (5)
    }
    auto p = GF2::Matrix<>::probability_singular(N);
    std::cout << "Matrix size: " << N << " x " << N << "\n"     (6)
              << "P[singular]: " << 100 * p << "%\n"
              << "Trials:      " << trials << "\n"
              << "No inverse:  " << fails << " times\n"
              << "Expected:    " << int(p * double(trials)) << " times\n";

    return 0;
}
1 In each trial we will create an \(N \times N\) matrix.
2 Run this number of trials.
3 Each matrix is filled at random by flipping fair coins.
4 Then we attempt to invert the matrix.
5 We count the number of times the inversion fails—​i.e. how often the matrix is singular.
6 Print the outcome of the trials and compare those to the expectation.
Output (actual numbers varies from run to run)
Matrix size: 100 x 100
P[singular]: 71.1212%
Trials:      1000
No inverse:  703 times
Expected:    711 times
See Also

invert