The BitMatrix Class

Introduction

A gf2::BitMatrix is a dynamically sized matrix of bit elements.

In mathematical terms, a bit-matrix is a matrix over GF2, the simplest Galois-Field with just two elements, usually denoted 0 & 1, as the booleans true & false, or as the bits set & unset. Arithmetic over GF(2) is mod 2, so addition/subtraction becomes the XOR operation while multiplication/division becomes AND.

Note

Operations on and between bit-matrices and other objects in the gf2 library are implemented using bitwise operations on whole underlying words at a time. These operations are highly optimised in modern CPUs, allowing for fast computation even on large bit-vectors. It also means we never have to worry about overflows or carries as we would with normal integer arithmetic.

A bit-matrix is stored in row-major mode where each row is a single gf2::BitVector. This means that arranging computations to work row by row instead of column by column is typically much more efficient. The methods and functions in the library take this into consideration.

This bit-matrix class is a std::vector of rows where each row is a single bit-vector. If the primary aim was to minimize storage, we would store the bit-matrix as a single long bit-vector with appropriate index operations. However, in that case, matrix operations would often need to be done across word boundaries, which is much slower than doing things word-by-word.

Note

Arbitrary \(m \times n\) bit-matrices are supported, but some functions only make sense for square matrices where \(n = m\).

The gf2::BitMatrix class has many of the same methods defined for gf2::BitVector, such as bitwise operations and stringification. We also have methods for matrix-vector, vector-matrix, and matrix-matrix multiplication.

There are methods to solve linear systems of equations \(A \cdot x = b\).

Danilevsky's method to compute characteristic polynomials (and the determinant) for a bit-matrix is available and works for quite large matrices (ones with millions of entries) that would choke a naive implementation that didn't take into account the nature of arithmetic over \(\mathbb{F}_2\).

Declaration

The declaration looks like this:

template <Unsigned Word = usize>
class BitMatrix {
 // ...
};

The Word template parameter specifies the underlying unsigned integer type used by the row bit-vectors to store the bits elements, and the default is usually the most efficient type for the target platform. On most modern platforms, that [usize] will be a 64-bit unsigned integer.

If your application calls for a vast number of small bit-matrices, you might consider using std::uint8_t as the Word type to save memory.

Note

You might notice that many of the doctests in the library use 8-bit underlying words. The reason is we want to exercise the various functions across word boundaries for modest, easily readable bit-stores.

Constructors

You can create a bit-matrix with the following constructors:

Method Name	Description
gf2::BitMatrix::BitMatrix	Creates a matrix with a given size.
gf2::BitMatrix::BitMatrix(const std::vector<row_type>&)	Creates a matrix by copying a vector of rows.
gf2::BitMatrix::BitMatrix(std::vector<BitVector<Word>>&&)	Creates a matrix by moving a vector of rows.

If you create a matrix with a given size, all the bits are initialised to zero. The number of rows and columns are specified as parameters, the default constructor creates an empty matrix with zero rows and zero columns.

If you create a matrix from a vector of rows, we check that all the rows have the same length and throw an exception if they do not. That check can be disabled by setting the NDEBUG preprocessor symbol.

If you move a vector of rows into the matrix, they are no longer valid after the move.

Factory Constructors

The BitMatrix class provides a rich set of methods for constructing bit-matrices:

Common Matrices

Method Name	Description
gf2::BitMatrix::zeros	Creates the zero with all elements set to 0.
gf2::BitMatrix::ones	Creates the matrix with all elements set to 1.
gf2::BitMatrix::alternating	Creates the matrix with elements in a checker-board pattern.
gf2::BitMatrix::from_outer_product	Creates a matrix as the outer product of two bit-vectors.
gf2::BitMatrix::from_outer_sum	Creates a matrix as the outer sum of two bit-vectors.
gf2::BitMatrix::from	Creates a matrix by repeatedly invoking a function \(f(i,j)\).
gf2::BitMatrix::random	Creates a matrix with a random fill.
gf2::BitMatrix::seeded_random	Creates a matrix with a repeatable random fill.
gf2::BitMatrix::biased_random	Creates a matrix with a biased random fill.

Some of these methods come in two versions – one that takes the number of rows and columns as parameters, and another that creates square matrices of a given size.

Special Matrices

We have methods to create some special matrices:

Method Name	Description
gf2::BitMatrix::zero	The square zero matrix.
gf2::BitMatrix::identity	The square identity matrix.
gf2::BitMatrix::left_shift	The n x n shift-left by p places matrix.
gf2::BitMatrix::right_shift	The n x n shift-right by p places matrix.
gf2::BitMatrix::left_rotation	The n x n rotate-left by p places matrix.
gf2::BitMatrix::right_rotation	The n x n rotate-right by p places matrix.
gf2::BitMatrix::companion	A square matrix with a top-row and a sub-diagonal that is all ones.

Reshaping from Vectors

We have methods to reshape a bit-vector into a matrix, either by rows or by columns:

Method Name	Description
gf2::BitMatrix::from_vector_of_rows	Reshapes a bit-vector of rows into a matrix.
gf2::BitMatrix::from_vector_of_cols	Reshapes a bit-vector of columns into a matrix.

These can fail so we return a BitMatrix wrapped in a std::optional and std::nullopt if the size of the vector is not compatible with the requested matrix shape.

From Strings

Finally, we have a method to construct a bit-matrix from one of its string representations:

Method Name	Description
gf2::BitMatrix::from_string	Tries to create a matrix from a string.

This can fail so return a a BitMatrix wrapped in a std::optional and std::nullopt if we fail to parse the string.

The rows in the matrix string can be separated by newlines, white space, commas, single quotes, or semicolons. Each row should be a binary or hex string representation of a bit-vector. See constructing bit-vectors from strings for details of the accepted formats for each row.

Resizing and Reshaping

We have methods to resize the matrix where current elements are preserved as much as possible and any added elements are initialised to zero.

Method Name	Description
gf2::BitMatrix::resize	Resizes the matrix to the passed dimensions.
gf2::BitMatrix::clear	This is equivalent to resize(0,0).
gf2::BitMatrix::make_square	This is equivalent to resize(m,m).

Appending and Removing Rows/Columns

We have methods to append and remove rows and columns from the matrix:

Method Name	Description
gf2::BitMatrix::append_row	Appends a row to the end of the matrix either by copying or moving a bit-vector.
gf2::BitMatrix::append_rows	Appends rows to the end of the matrix either by copying or moving a standard vector of bit-vectors.
gf2::BitMatrix::append_col	Appends a column to the right of the matrix by copying a bit-vector.
gf2::BitMatrix::append_cols	Appends columns to the right of the matrix by copying standard vector of bit-vectors.
gf2::BitMatrix::remove_row	Removes a row from the end of the matrix and returns it as a bit-vector.
gf2::BitMatrix::remove_rows	Removes multiple rows from the end of the matrix and returns them as a bit-matrix.
gf2::BitMatrix::remove_col	Removes a column from the right of the matrix and returns it as a bit-vector.

The remove methods return an std::optional wrapped result as the request can fail.

Size and Type Queries

We have methods to query the matrix dimensions and check if it is "special" in some way:

Method Name	Description
gf2::BitMatrix::rows	Returns the number of rows in the matrix.
gf2::BitMatrix::cols	Returns the number of columns in the matrix.
gf2::BitMatrix::size	Returns the number of elements in the matrix.
gf2::BitMatrix::is_empty	Returns true if the matrix has no elements.
gf2::BitMatrix::is_square	Returns true if the number of rows equals the number of columns.
gf2::BitMatrix::is_zero	Returns true if this is a square zero matrix.
gf2::BitMatrix::is_identity	Returns true if this is a square identity matrix.
gf2::BitMatrix::is_symmetric	Returns true if this is a square symmetric matrix \(M(i,j) = M(j,i)\).

Bit Counts

We have methods to count the number of set and unset elements in the matrix, as well as on the main diagonal.

Method Name	Description
gf2::BitMatrix::count_ones	Returns the overall number of set elements in the matrix.
gf2::BitMatrix::count_zeros	Returns the overall number of unset elements in the matrix.
gf2::BitMatrix::count_ones_on_diagonal	Returns the overall number of set elements on the main diagonal.
gf2::BitMatrix::trace	Returns the "sum" of the main diagonal elements.
gf2::BitMatrix::any	Returns true if the matrix has any set elements.
gf2::BitMatrix::all	Returns true if the matrix is all ones.
gf2::BitMatrix::none	Returns true if the matrix is all zeros.

General Access

There are methods to access individual elements, rows and columns, and the entire matrix.

Method Name	Description
gf2::BitMatrix::get	Access an individual matrix element either as a bool or a gf2::BitRef
gf2::BitMatrix::operator()()	Access an individual matrix element either as a bool or a gf2::BitRef
gf2::BitMatrix::set	Set an individual matrix element to a value that defaults to true
gf2::BitMatrix::flip	Flips the value of an individual matrix element.
gf2::BitMatrix::row	Returns a reference to a matrix row as a gf2::BitVector.
gf2::BitMatrix::operator[]()	Returns a reference to a matrix row as a gf2::BitVector.
gf2::BitMatrix::col	Returns a copy of a matrix column as a gf2::BitVector.
gf2::BitMatrix::set_all	Sets all matrix elements to a value that defaults to true
gf2::BitMatrix::flip_all	Flips the values of all matrix elements.

Diagonal Access

We have methods to access and modify the main diagonal, super-diagonals, and sub-diagonals of a square matrix:

Method Name	Description
gf2::BitMatrix::set_diagonal	Sets all the main diagonal elements to a value that defaults to true
gf2::BitMatrix::flip_diagonal	Flips the values of all the main diagonal elements.
gf2::BitMatrix::set_super_diagonal	Sets all elements of a super-diagonal elements to a value that defaults to true
gf2::BitMatrix::flip_super_diagonal	Flips the values of all elements on a super-diagonal.
gf2::BitMatrix::set_sub_diagonal	Sets all elements of a sub-diagonal elements to a value that defaults to true
gf2::BitMatrix::flip_sub_diagonal	Flips the values of all elements on a sub-diagonal.

Sub-Matrices

There are methods to extract and replace sub-matrices:

Method Name	Description
gf2::BitMatrix::sub_matrix	Extracts a sub-matrix as a new bit-matrix.
gf2::BitMatrix::replace_sub_matrix	Replaces a sub-matrix.

These methods panic if the requested sub-matrix is out of bounds.

Triangular Sub-Matrices

We have methods to extract triangular sub-matrices:

Method Name	Description
gf2::BitMatrix::lower	Returns the lower triangular sub-matrix including the main diagonal.
gf2::BitMatrix::upper	Returns the upper triangular sub-matrix including the main diagonal.
gf2::BitMatrix::strictly_lower	Returns the lower triangular sub-matrix excluding the main diagonal.
gf2::BitMatrix::strictly_upper	Returns the upper triangular sub-matrix excluding the main diagonal.
gf2::BitMatrix::unit_lower	Returns the lower triangular sub-matrix with ones on the main diagonal.
gf2::BitMatrix::unit_upper	Returns the upper triangular sub-matrix with ones on the main diagonal.

The triangular extraction methods do not need the matrix to be square. The returned sub-matrix will have the same number of rows and columns as the original matrix, with the appropriate elements zeroed out.

Elementary Operations

We have methods to perform elementary row and column operations as well as adding the identity matrix in-place:

Method Name	Description
gf2::BitMatrix::swap_rows	Swaps two rows in a matrix.
gf2::BitMatrix::swap_cols	Swap two columns in a matrix.
gf2::BitMatrix::add_identity	Adds the identity matrix to a square matrix in-place.

These operations are fundamental to many matrix algorithms.

Transposition

We have methods to transpose a matrix either in-place (for square matrices) or to return a new transposed matrix:

Method Name	Description
gf2::BitMatrix::transpose	Transposes a square matrix in place.
gf2::BitMatrix::transposed	Returns a new matrix that is the transpose of this arbitrarily shaped one.

The gf2::BitMatrix::transposed method works for non-square matrices by creating a new matrix with the appropriate dimensions and filling it in.

Exponentiation

Method Name	Description
gf2::BitMatrix::to_the	Returns a new matrix that is this one raised to a power.

We efficiently compute \(M^e\) by using a square and multiply algorithm, where \(e = n\) or \(2^n\) for some \(n\).

Matrix Inversion

We have methods to reduce a matrix to echelon form, reduced echelon form, and to compute the inverse of a square matrix:

Method Name	Description
gf2::BitMatrix::to_echelon_form	Reduces a matrix to echelon form in-place.
gf2::BitMatrix::to_reduced_echelon_form	Reduces a matrix to reduced echelon form in-place.
gf2::BitMatrix::inverse	Returns the inverse of a matrix or std::nullopt on failure.
gf2::BitMatrix::probability_invertible	Returns the probability of a fair random \(n \times n\) matrix being invertible.
gf2::BitMatrix::probability_singular	Returns the probability of a fair random \(n \times n\) matrix not being invertible.

The inversion method can fail so we return an std::optional wrapped result.

Bitwise & Arithmetic Operations

Method Name	Description
gf2::BitMatrix::operator^=(const BitMatrix<Word>&)	In-place XOR with another matrix.
gf2::BitMatrix::operator&=(const BitMatrix<Word>&)	In-place AND with another matrix.
gf2::BitMatrix::operator\|=(const BitMatrix<Word>&)	In-place OR with another matrix.
gf2::BitMatrix::operator^(const BitMatrix<Word>&)	Returns a new matrix that is the XOR of two others.
gf2::BitMatrix::operator&(const BitMatrix<Word>&)	Returns a new matrix that is the AND of two others.
gf2::BitMatrix::operator\|(const BitMatrix<Word>&)	Returns a new matrix that is the OR of two others.
gf2::BitMatrix::operator~	Returns a new matrix that is the NOT of this one.
gf2::BitMatrix::operator+=(const BitMatrix<Word>&)	In-place addition with another matrix.
gf2::BitMatrix::operator-=(const BitMatrix<Word>&)	In-place subtraction with another matrix.
gf2::BitMatrix::operator+(const BitMatrix<Word>&)	Returns a new matrix that is the sum of two others.
gf2::BitMatrix::operator-(const BitMatrix<Word>&)	Returns a new matrix that is the difference of two others.

These operations act element-by-element and panic if the matrices are not the same size.

In GF(2) addition and subtraction are both equivalent to XOR.

Method Name	Description
gf2::dot	Overloaded to handle vector-matrix, matrix-vector, and matrix-matrix multiplication.
gf2::operator*	Another way to call gf2::dot.

Linear System Solvers

Method Name	Description
gf2::BitMatrix::LU	Returns a gf2::BitLU object for the matrix.
gf2::BitMatrix::solver_for(const BitVector<Word>&)	Returns a gf2::BitGauss object for the matrix and given right hand side.
gf2::BitMatrix::x_for(const BitVector<Word>&)	Tries to fund a solution to the system of linear equations.

Characteristic Polynomials

Method Name	Description
gf2::BitMatrix::characteristic_polynomial	Returns the characteristic polynomial of a square matrix.
gf2::BitMatrix::frobenius_form	Returns the Frobenius normal form of a square matrix.

The characteristic polynomial is computed using Danilevsky's method, which is not well known but is efficient for bit-matrices. It words by reducing the matrix to Frobenius normal form using a series of similarity transformations implemented using row and column operations. See the [Danilevsky's Algorithm](Danilevsky) page for more details.

Stringification

The following methods return a string representation for a bit-matrix. The string can be in the obvious binary format or a more compact hex format.

Method	Description
gf2::BitMatrix::to_binary_string	Returns a configurable binary string representation for a bit-matrix.
gf2::BitMatrix::to_compact_binary_string	Returns a one-line minimal binary string representation for a bit-matrix.
gf2::BitMatrix::to_string	Returns a default (binary) string representation for a bit-matrix.
gf2::BitMatrix::to_pretty_string	Returns a "pretty" string representation for a bit-matrix.
gf2::BitMatrix::to_hex_string	Returns a hex string representation for a bit-matrix.
gf2::BitMatrix::to_compact_hex_string	Returns a one-line minimal hex string representation for a bit-matrix.
gf2::BitMatrix::operator<<(std::ostream&)	The usual output stream output stream operator for bit-matrices.
struct std::formatter<gf2::BitMatrix>	Specialisation of [std::formatter] for bit-matrices.

See the stringification section in the gf2::BitStore documentation for details on the various options available for formatting the rows of the matrix.

Example

#include <gf2/namespace.h>
int
main() {
    auto M = BitMatrix<>::random(5, 15);
    std::println("M.to_string():\n{}\n", M.to_string());
    std::println("M.to_binary_string():\n{}\n", M.to_binary_string());
    std::println("M.to_compact_binary_string():\n{}\n", M.to_compact_binary_string());
    std::println("M.to_hex_string():\n{}\n", M.to_hex_string());
    std::println("M.to_compact_hex_string():\n{}\n", M.to_compact_hex_string());
    std::println("M.to_pretty_string():\n{}", M.to_pretty_string());
}

That might produce output like this:

M.to_string():
101100101010001
100110111100010
000000010100010
001111011110001
001110010010110
 
M.to_binary_string():
101100101010001
100110111100010
000000010100010
001111011110001
001110010010110
 
M.to_compact_binary_string():
101100101010001 100110111100010 000000010100010 001111011110001 001110010010110
 
M.to_hex_string():
B2A1.8
9BC2.8
0142.8
3DE1.8
3926.8
 
M.to_compact_hex_string():
B2A1.8 9BC2.8 0142.8 3DE1.8 3926.8
 
M.to_pretty_string():
│1 0 1 1 0 0 1 0 1 0 1 0 0 0 1│
│1 0 0 1 1 0 1 1 1 1 0 0 0 1 0│
│0 0 0 0 0 0 0 1 0 1 0 0 0 1 0│
│0 0 1 1 1 1 0 1 1 1 1 0 0 0 1│
│0 0 1 1 1 0 0 1 0 0 1 0 1 1 0│

Utility String Functions

We have a set of utility functions to get string representations for matrices & vectors side-by-side:

Method	Description
gf2::string_for(const BitMatrix&, BitStore&)	A string for a matrix and vector side-by-side.
gf2::string_for(const BitMatrix&, BitStore&, BitStore&)	A string for a matrix and two vectors side-by-side.
gf2::string_for(const BitMatrix&, BitStore&, BitStore&, BitStore&)	A string for a matrix and three vectors side-by-side.
gf2::string_for(const BitMatrix&, BitMatrix&)	A string for two matrices side-by-side.
gf2::string_for(const BitMatrix&, BitMatrix&, BitMatrix&)	A string for two matrices side-by-side.

Here is an example that shows a matrix alongside its lower and upper triangular parts:

#include <gf2/namespace.h>
int
main() {
    auto M = BitMatrix<>::ones(7, 7);
    std::println("    M      L       U");
    std::println("{}", string_for(M, M.lower(), M.strictly_upper()));
}

Output:

    M      L       U
1111111 1000000 0111111
1111111 1100000 0011111
1111111 1110000 0001111
1111111 1111000 0000111
1111111 1111100 0000011
1111111 1111110 0000001
1111111 1111111 0000000

See Also

• gf2::BitMatrix for detailed documentation of all class methods.
• BitStore for the concept API shared by all bit-stores.
• BitArray for fixed-size vectors of bits.
• BitVector for dynamically-sized vectors of bits.
• BitSpan for non-owning views into any bit-store.
• BitPolynomial for polynomials over GF(2).
• Danilevsky's method for computing characteristic polynomials.