GF2::Matrix Frobenius & Companion Matrices
static constexpr Matrix companion(const vector_type &top_row) (1)| 1 | Class method to create a companion matrix i.e. a square bit-matrix with the given top-row and ones on the sub-diagonal. |
template<std::unsigned_integral Block, typename Allocator>
Vector<Block, Allocator>
companion_matrix_characteristic_polynomial(const Vector<Block, Allocator> &top_row) (1)| 1 | Non-member function which takes a companion matrix in compact, top-row only form as input and returns the coefficients for its characteristic polynomial as bit-vector p where the polynomial is |
template<std::unsigned_integral Block, typename Allocator>
std::vector<Vector<Block, Allocator>>
compact_frobenius_form(const Matrix<Block, Allocator> &A) (1)| 1 | Non-member function which returns the Frobenius form of the input square bit-matrix. Each element in the return vector is a companion matrix stored in compact top-row only form. |
Companion Matrices
Our version of a companion matrix is upper Hessenberg with an arbitrary top-row, ones on the sub-diagonal, and zeros everywhere else. These can be compactly stored in top-row only form.
The first class method above turns that compact form into a regular looking bit-matrix.
Companion matrices are important because one can readily read off the coefficients in their characteristic polynomials. The second non-member function above does exactly that.
Frobenius Matrices
A square matrix is in Frobenius form if it is block-diagonal and each of those square blocks is a companion matrix. One can readily compute the characteristic polynomial of a Frobenius matrix by multiplying together the characteristic polynomials of all the companion matrices.
Any square matrix can be transformed by a similarity transformation to Frobenius form. You can see how we actually achieve this in the documentation for Danilevsky’s algorithm.
This is the key to our implementation of the non-member function characteristic_polynomial which takes an arbitrary square bit-matrix as input and returns its characteristic polynomial.
#include <GF2/GF2.h>
int main()
{
}