GF2::Matrix — Characteristic Polynomial

Finds the characteristic polynomial of a square bit-matrix.

Vector<Block, Allocator> characteristic_polynomial(const Matrix<Block, Allocator>& A);

Returns a bit-vector p where the characteristic polynomial for the bit-matrix \(A\) is given by

\[p(\lambda) = p_0 + p_1 \lambda + p_2 \lambda^2 + \cdots\]

The bit-matrix must be non-empty and square otherwise a std::invalid_argument exception is thrown.

The characteristic polynomial is computed using Danilevsky’s algorithm coded to take into account the special nature of arithmetic in GF(2). This means that the characteristic polynomial of large bit-matrices can be efficiently computed even for ones with millions of entries that would choke more naive implementations.

Example: The identiity matrices
#include <GF2/GF2.h>
int main()
{
    for(std::size_t i = 1; i < 8; ++i) {            (1)
        auto M = GF2::Matrix<>::identity(i);
        auto p = GF2::characteristic_polynomial(M);
        std::cout << "Characteristic polynomial coefficients for the "
                  << i << " x " << i << " identity matrix: " << p << '\n';
    }
}
1 We generate identity matrices from 1 x 1 to 7 x 7 and get the characteristic polynomial in each case.
Output
Characteristic polynomial coefficients for the 1 x 1 identity matrix: 11
Characteristic polynomial coefficients for the 2 x 2 identity matrix: 101
Characteristic polynomial coefficients for the 3 x 3 identity matrix: 1111
Characteristic polynomial coefficients for the 4 x 4 identity matrix: 10001
Characteristic polynomial coefficients for the 5 x 5 identity matrix: 110011
Characteristic polynomial coefficients for the 6 x 6 identity matrix: 1010101
Characteristic polynomial coefficients for the 7 x 7 identity matrix: 11111111

We can easily verify these.

For example, if we consider the 7 x 7 identity it is clear that the characteristic polynomial is given by

\[p(\lambda) = (\lambda - 1)^7 = \lambda ^7-7 \lambda ^6+21 \lambda ^5-35 \lambda ^4+35 \lambda ^3-21 \lambda ^2+7 \lambda -1\]

In GF(2), even coefficients are 0 and odd ones, whether positive or negative, are 1 so \(p(\lambda)\) becomes

\[p(\lambda) = \lambda ^7 + \lambda ^6 + \lambda ^5 + \lambda ^4 + \lambda ^3 + \lambda ^2 + \lambda + 1\]

therefore we expect to get the GF(2) coefficients as 11111111 which agrees with the output above.

Example: Bit-matrices should satisy their own characteristic polynomial
#include <GF2/GF2.h>

int main()
{
    // Probably should turn off GF2_DEBUG and enable optimization for this sized bit-matrix!
    auto M = GF2::Matrix<>::random(512);        (1)
    auto p = GF2::characteristic_polynomial(M);
    std::cout << "Characteristic polynomial coefficients:\n" << p << "\n\n";

    auto C = polynomial_sum(p, M);              (2)
    std::cout << "Does the bit-matrix satisfy its own characteristic polynomial? "
              << (C.none() ? "YES" : "NO") << '\n';
}
1 Pay attention to the comment! Can handle much larger matrices but you need to enable compiler optimizations.
2 All matrices should satisfy their own characteristic polynomial so \(p(M)\) should return the zero bit-matrix.
Output
Characteristic polynomial coefficients:
110101101110101110100111001011010101101011001011110000100010011001111101011111111010101110010101101000101000010001000010011010111001000000011110000111000110110111100010100001000010110010010000110100111110000111010010110011111111001100001000100111111110101101101110001001111101000110101111000101100111100001011111011011000101010000110010101111110001100000011111100101110101010011100110101111001001111011101100001101000101101011110110000010101011111010100110011001110110110111110100010100010100101110001000010011101

Does the bit-matrix satisfy its own characteristic polynomial? YES
See Also

polynomial_sum