GF2::Matrix

Overview

A GF2::Matrix represents a matrix over GF(2) (a.k.a. \(\mathbb{F}_2\)) the simplest Galois field that has just two elements usually denoted 0 & 1, or as booleans—true & false, or as bits—set & unset. Arithmetic in GF(2) is defined mod 2 which has the effect that addition/subtraction becomes the XOR operation while multiplication/division becomes AND.

We often refer to an object of the type GF2::Matrix as a bit-matrix. It is a matrix where all the elements are either 0 or 1 and where arithmetic is expected to be done mod 2.

A GF2::Matrix is stored in row-major mode where each row is a single GF2::Vector. This means it is typically much more efficient to arrange computations to work row by row as opposed to column by column. Most of the time you will be using higher level methods already defined in the class or as free functions where that is already taken into account.

The main aim here is to facilitate efficient linear algebra over GF(2) where the bit-vector class is GF2::Vector. This bit-matrix class is implemented as a std::vector of rows where each row is a single bit-vector. If instead, the primary aim was to minimize storage, one would simply 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 on an element by element basis which is much, much slower than doing things block by block as we do here.

Like bit-vectors, bit-matrices are sized dynamically at runtime and the row elements are packed into blocks that can be any unsigned integral type. That template parameter defaults to 64-bit words (it might be reasonable to use a smaller type for lots of small matrices).

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

Many of the methods defined for GF2::Vector are also implemented for GF2::Matrix. We also define free functions dot(lhs, rhs) to handle 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 GF2::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 special nature of arithmetic over GF(2).

See below for the full list.

Declaration

The GF2::Matrix class is defined in the header <GF2/Matrix.h> as follows:

namespace GF2 {
    template<
        std::unsigned_integral Block = uint64_t,
        Allocator = std::allocator<Block>
    > class Matrix;
}

The two template parameters add some visual clutter but they both have reasonable defaults so the clutter completely disappears in most uses.

For example your code might have a line like:

    ...
    GF2::Matrix M(3,5);
    ...

This creates a 3 x 5 matrix with 15 elements which by default are all set to 0.

Template Parameters

std::unsigned_integral
Block = uint64_t

The individual matrix elements/bits are stored by row and the rows in turn are packed into blocks. The default Block is an unsigned 64-bit word.

Allocator =
std::allocator

The default std::allocator should be just fine for most purposes, but you can use your own custom type to handle all memory allocations/de-allocations for blocks.

As mentioned, the default std::unsigned_integral used for a Block is 64-bits which is the native size for many modern CPU’s. Of course if you are using lots of smaller bit-matrices and have concerns about space being conserved you might use a different Block. Perhaps if the bit-matrices all fit in 32 bits you might have code along the lines

    using Matrix = GF2::Matrix<uint32_t>;
    Matrix mat = ...

You should use just one Block type throughout your code. In theory, there is no reason that one couldn’t intermingle operations between say a GF2::Matrix<uint32_t> and a GF2::Vector<uint64_t> but doing so efficiently greatly increases code complexity and the library doesn’t support this.

Class Types

Type	Definition
`std::vector_type`	Alias for `GF2::Vector` — the type used for matrix rows (and columns).

Type

Definition

std::vector_type

Alias for GF2::Vector — the type used for matrix rows (and columns).

Methods

Construction
`constructors`	Create a bit-matrix in various ways.
`random`	Class methods to construct a bit-matrix with a random fill.
`ones` `zeros` `checker_board` `identity` `shift` `rotate`	Class methods to construct various “special” bit-matrices.
`companion`	Class method so construct a companion matrix from its top-row only.
Queries
`is_zero` `is_ones` `is_identity` `is_symmetric`	Query to see if this matrix is special in some way.
Element Access
`operator()` `row` `col` `operator[]` `test`	Access a bit-matrix element, or a whole row, or whole column.
`all` `any` `none`	Checks if all, any, or none of the bit-matrix elements are set.
`count` `count_diagonal` `trace`	The number of set elements overall or just on a diagonal.
`sub`	Extracts a bit-matrix as a distinct copy of some of the elements of this one. Note that views into a bit-matrix are not supported.
`lower` `strictly_lower` `upper` `strictly_upper`	Extracts the lower or upper triangular elements of this bit-matrix. These return distinct copies of some of the elements of this bit-matrix. Note that views into a bit-matrix are not supported.
Capacity
`rows` `cols` `is_square` `size` `empty`	The number of rows, columns, and elements in the bit-matrix etc.
`row_capacity` `col_capacity`	Information about the capacity of the bit-matrix—how many rows/columns can be added without needing a memory allocation.
`shrink_to_fit`	Tries to reduce memory usage by freeing unused memory
Modifiers
`clear`	Clears all the elements from the bit-matrix so `rows()`, cols(), and `size() all become 0.
`resize`	Resizes the bit-matrix, padding out any added values with zeros.
`add_row` `add_col` `pop_row` `pop_col`	Adds a single row or a column to the end of the bit-matrix or remove the final row or column.
`append`	Augments a bit-matrix in-place by appending columns from a vector or another bit-matrix on the right.
`swap_rows` `swap_cols`	Swaps two rows or two columns in a bit-matrix.
`to_transpose`	Transpose a square bit-matrix in-place.
`replace`	Methods to replace some of the contents of the bit-matrix with other values.
`set` `set_diagonal` `reset` `reset_diagonal` `flip`	Sets, resets, or flips various elements in the bit-matrix.
`set_if` `flip_if`	Sets or flips the values in a bit-matrix based on the return value from a function of each element index-pair.
`operator&=` `operator^=` `operator\|=` `operator+=` `operator-=` `operator*=` `operator~`	Element-by-element logical operations between this bit-matrix and another of equal dimensions. Note that in GF(2) addition and subtraction are the same as XOR, while multiplication is the same as AND.
`operator<<=` `operator>>=` `operator<<` `operator>>`	Left and right shifts of the bit-matrix rows.
`to_echelon_form` `to_reduced_echelon_form`	Changes this bit-matrix in place to a row-echelon form.
Conversions
`to_string` `to_bit_order` `to_hex`	Returns various string representations of the bit-matrix.
`to_vector`	Packs the bit-matrix into a bit-vector.
Other methods
`probability_invertible` `probability_singular`	Returns the probability that a “fair” square bit-matrix is either invertible or singular.
Debugging
`description`	A method to write some descriptive data about the bit-matrix to a stream.
`GF2_DEBUG` `GF2_NDEBUG` `gf2_debug_assert` `gf2_assert` `gf2_always_assert`	The first two are optional compile time flags that control the degree of safety checking that is performed in the library. In particular, builds that set the `GF2_DEBUG` flag at compile time will get all indices bounds checked at runtime as well as other checks on sizes etc.

Construction

constructors

Create a bit-matrix in various ways.

random

Class methods to construct a bit-matrix with a random fill.

ones
zeros
checker_board
identity
shift
rotate

Class methods to construct various “special” bit-matrices.

companion

Class method so construct a companion matrix from its top-row only.

Queries

is_zero
is_ones
is_identity
is_symmetric

Query to see if this matrix is special in some way.

Element Access

operator()
row
col
operator[]
test

Access a bit-matrix element, or a whole row, or whole column.

all
any
none

Checks if all, any, or none of the bit-matrix elements are set.

count
count_diagonal
trace

The number of set elements overall or just on a diagonal.

sub

Extracts a bit-matrix as a distinct copy of some of the elements of this one.
Note that views into a bit-matrix are not supported.

lower
strictly_lower
upper
strictly_upper

Extracts the lower or upper triangular elements of this bit-matrix. These return distinct copies of some of the elements of this bit-matrix.
Note that views into a bit-matrix are not supported.

Capacity

rows
cols
is_square
size
empty

The number of rows, columns, and elements in the bit-matrix etc.

row_capacity
col_capacity

Information about the capacity of the bit-matrix—how many rows/columns can be added without needing a memory allocation.

shrink_to_fit

Tries to reduce memory usage by freeing unused memory

Modifiers

clear

Clears all the elements from the bit-matrix so rows(), cols(), and `size() all become 0.

resize

Resizes the bit-matrix, padding out any added values with zeros.

add_row
add_col
pop_row
pop_col

Adds a single row or a column to the end of the bit-matrix or remove the final row or column.

append

Augments a bit-matrix in-place by appending columns from a vector or another bit-matrix on the right.

swap_rows
swap_cols

Swaps two rows or two columns in a bit-matrix.

to_transpose

Transpose a square bit-matrix in-place.

replace

Methods to replace some of the contents of the bit-matrix with other values.

set
set_diagonal
reset
reset_diagonal
flip

Sets, resets, or flips various elements in the bit-matrix.

set_if
flip_if

Sets or flips the values in a bit-matrix based on the return value from a function of each element index-pair.

operator&=
operator^=
operator|=
operator+=
operator-=
operator*=
operator~

Element-by-element logical operations between this bit-matrix and another of equal dimensions. Note that in GF(2) addition and subtraction are the same as XOR, while multiplication is the same as AND.

operator<<=
operator>>=
operator<<
operator>>

Left and right shifts of the bit-matrix rows.

to_echelon_form
to_reduced_echelon_form

Changes this bit-matrix in place to a row-echelon form.

Conversions

to_string
to_bit_order
to_hex

Returns various string representations of the bit-matrix.

to_vector

Packs the bit-matrix into a bit-vector.

Other methods

probability_invertible
probability_singular

Returns the probability that a “fair” square bit-matrix is either invertible or singular.

Debugging

description

A method to write some descriptive data about the bit-matrix to a stream.

GF2_DEBUG
GF2_NDEBUG
gf2_debug_assert gf2_assert gf2_always_assert

The first two are optional compile time flags that control the degree of safety checking that is performed in the library.

In particular, builds that set the GF2_DEBUG flag at compile time will get all indices bounds checked at runtime as well as other checks on sizes etc.

Non-member Functions

operator&
operator|
operator^
operator+
operator-
operator*

Element-by-element logical operations between two bit-matrices of equal dimensions. Note that in GF(2) addition and subtraction are the same as XOR, while multiplication is the same as AND.

dot

Returns the dot product of a bit-matrix with a bit-vector or another bit-matrix.

join

Returns an augmented bit-matrix by copying one input and then appending columns from a bit-vector or another bit-matrix on the right of that.

transpose

Returns the transpose of an arbitrary rectangular bit-matrix as a new bit-matrix.

pow
pow2

Raises a square bit-matrix to a power \(n\) or \(2^n\) respectively.

polynomial_sum

Evaluates a polynomial over GF(2) using a square bit-matrix as the argument.

invert

Attempts to return the inverse of a square bit-matrix.

solve

Attempts to solve a system of linear equations \(A \cdot x = b\) where \(A\) is a square bit-matrix.

gauss_solver

Returns a GaussSolver object that can iterate through solutions of \(A \cdot x = b\) where \(A\) is a square bit-matrix.

lu_decompose

Returns a LUDecompose object that can performs the LU decomposition of a square bit-matrix \(A\).

echelon_form
reduced_echelon_form

Returns the row-echelon forms of an arbitrary bit-matrix.

characteristic_polynomial

Returns the coefficients of the characteristic polynomial of a square bit-matrix.

compact_frobenius_form

Returns the companion matrices that are the diagonal blocks in the Frobenius form of a square bit-matrix.

operator<<
operator>>

Performs stream input and output for bit-matrices.

print

Prints multiple bit-matrices or a bit-matrix with potentially multiple bit-vectors side by side to a stream.