gf2::BitMatrix< Word >

A dynamically-sized matrix over GF(2) stored as a vector of bit-vectors representing the rows of the matrix. The row elements are compactly stored in standard vectors of primitive unsigned words whose type is given by the template parameter Word. More...

#include <BitMatrix.h>

Public Types
using	word_type = Word
	The underlying unsigned word type used to store the bits.

Public Member Functions
Constructors
constexpr	BitMatrix ()
	The default constructor creates an empty bit-matrix with no rows or columns.
constexpr	BitMatrix (usize n)
	Constructs the n x n square bit-matrix with all the elements set to 0.
constexpr	BitMatrix (usize m, usize n)
	Constructs the m x n bit-matrix with all the elements set to 0.
constexpr	BitMatrix (std::vector< row_type > const &rows)
	Construct a bit-matrix by copying a given set of rows which can be any BitStore subclass.
constexpr	BitMatrix (std::vector< BitVector< Word > > &&rows)
	Construct a bit-matrix by moving the given rows.
Basic queries
constexpr usize	rows () const
	Returns the number of rows in the bit-matrix.
constexpr usize	cols () const
	Returns the number of columns in the bit-matrix.
constexpr usize	size () const
	Returns the totalnumber of elements in the bit-matrix.
constexpr bool	is_empty () const
	Is this an empty bit-matrix?
Checks for Special Bit-Matrices
constexpr bool	is_square () const
	Returns true if this a square bit-matrix? Note that empty bit-matrices are NOT considered square.
constexpr bool	is_zero () const
	Returns true if this a square zero bit-matrix?
constexpr bool	is_identity () const
	Returns true if this is the identity bit-matrix.
constexpr bool	is_symmetric () const
	Returns true if this is a symmetric square bit-matrix.
Bit Counts
constexpr usize	count_ones () const
	Returns the number of one elements in the bit-matrix.
constexpr usize	count_zeros () const
	Returns the number of zero elements in the bit-matrix.
constexpr usize	count_ones_on_diagonal () const
	Returns the number of ones on the main diagonal of the bit-matrix.
constexpr bool	trace () const
	Returns the "sum" of the main diagonal elements of the bit-matrix.
Overall State Queries
constexpr bool	any () const
	Returns true if any element of the bit-matrix is set.
constexpr bool	all () const
	Returns true if all elements of the bit-matrix are set.
constexpr bool	none () const
	Returns true if no elements of the bit-matrix are set.
Individual Element Access
constexpr bool	get (usize r, usize c) const
	Returns true if the element at row r and column c is set.
constexpr bool	operator() (usize r, usize c) const
	Returns the value of the bit at row r and column c as a bool.
constexpr void	set (usize r, usize c, bool val=true)
	Sets the bit at row r and column c to the bool value val. The default is to set the bit to true.
constexpr BitRef< row_type >	operator() (usize r, usize c)
	Returns the bit at row r and column c as a BitRef reference which can be used to set the bit.
constexpr void	flip (usize r, usize c)
	Flips the bit at row r and column c.
Row Access
constexpr const row_type &	row (usize r) const
	Returns a read-only reference to the row at index r.
constexpr row_type &	row (usize r)
	Returns a read-write reference to the row at index r.
constexpr const row_type &	operator[] (usize r) const
	Returns a read-only reference to the row at index r.
constexpr row_type &	operator[] (usize r)
	Returns a read-write reference to the row at index r.
Column Access
constexpr BitVector< Word >	col (usize c) const
	Returns a clone of the elements in column c from the bit-matrix as an independent bit-vector.
Whole Matrix Mutators
constexpr void	set_all (bool value=true)
	Sets all the elements of the bit-matrix to the specified boolean value.
constexpr void	flip_all ()
	Flips all the elements of the bit-matrix.
Diagonal Mutators
constexpr void	set_diagonal (bool val=true)
	Sets the main diagonal of a square bit-matrix to the boolean value val.
constexpr void	flip_diagonal ()
	Flips all the elements on the main diagonal of a square bit-matrix.
constexpr void	set_super_diagonal (usize d, bool val=true)
	Sets the elements on super-diagonal d of a square bit-matrix to the boolean value val.
constexpr void	flip_super_diagonal (usize d)
	Flips all the elements on the super-diagonal d of a square bit-matrix.
constexpr void	set_sub_diagonal (usize d, bool val=true)
	Sets the elements on sub-diagonal d of a square bit-matrix to the boolean value val.
constexpr void	flip_sub_diagonal (usize d)
	Flips all the elements on the sub-diagonal d of a square bit-matrix.
Resizing
constexpr void	resize (usize r, usize c)
	Resize the bit-matrix to r rows and c columns.
constexpr void	clear ()
	Removes all the elements from the bit-matrix.
constexpr void	make_square (usize n)
	Makes an arbitrary rectangular bit-matrix into a square BitMatrix.
Appending Rows and Columns
template<BitStore Store> requires std::same_as<typename Store::word_type, Word>
constexpr BitMatrix &	append_row (Store const &row)
	Appends a single row onto the end of the bit-matrix by copying it and returns a reference to the this for chaining.
template<BitStore Store> requires std::same_as<typename Store::word_type, Word>
constexpr BitMatrix &	append_row (Store &&row)
	Appends a single row onto the end of the bit-matrix by moving it and returns a reference to the this for chaining.
constexpr BitMatrix &	append_rows (BitMatrix< Word > const &src)
	Appends all the rows from the src bit-matrix onto the end of this bit-matrix by copying them and returns a reference to the this for chaining.
constexpr BitMatrix &	append_rows (BitMatrix< Word > &&src)
	Appends all the rows from the src bit-matrix onto the end of this bit-matrix by moving them and returns a reference to the this for chaining.
template<BitStore Store> requires std::same_as<typename Store::word_type, Word>
constexpr BitMatrix &	append_col (Store const &col)
	Appends a single column col onto the right of the bit-matrix so M -> M|col and returns a reference to the this for chaining.
constexpr BitMatrix &	append_cols (BitMatrix< Word > const &src)
	Appends all the columns from the src bit-matrix onto the right of this bit-matrix so M -> M|src and returns a reference to the this for chaining.
Removing Rows and Columns
constexpr std::optional< BitVector< Word > >	remove_row ()
	Removes a row off the end of the bit-matrix and returns it or std::nullopt if the bit-matrix is empty.
constexpr std::optional< BitMatrix< Word > >	remove_rows (usize k)
	Removes k rows off the end of the bit-matrix and returns them as a new bit-matrix or std::nullopt if the bit-matrix has fewer than k rows.
constexpr std::optional< BitVector< Word > >	remove_col ()
	Removes a column off the right of the bit-matrix and returns it or std::nullopt if the bit-matrix is empty.
Sub-matrices
constexpr BitMatrix	sub_matrix (usize r_start, usize r_end, usize c_start, usize c_end) const
	Returns an independent clone of the sub-matrix delimited by the given row and column ranges.
constexpr void	replace_sub_matrix (usize top, usize left, BitMatrix< Word > const &src)
	Replaces the sub-matrix starting at row top and column left with a copy of the sub-matrix src.
Triangular Sub-Matrices
constexpr BitMatrix	lower () const
	Returns an independent clone of the lower triangular part of the bit-matrix.
constexpr BitMatrix	upper () const
	Returns an independent clone of the upper triangular part of the bit-matrix.
constexpr BitMatrix	strictly_lower () const
	Returns an independent clone of the strictly lower triangular part of the bit-matrix.
constexpr BitMatrix	strictly_upper () const
	Returns an independent clone of the strictly upper triangular part of the bit-matrix.
constexpr BitMatrix	unit_lower () const
	Returns an independent clone of the unit lower triangular part of the bit-matrix.
constexpr BitMatrix	unit_upper () const
	Returns an independent clone of the unit upper triangular part of the bit-matrix.
Elementary Row and Column Operations
constexpr void	swap_rows (usize i, usize j)
	Swaps rows i and j of the bit-matrix.
constexpr void	swap_cols (usize i, usize j)
	Swaps columns i and j of the bit-matrix.
constexpr void	add_identity ()
	Adds the identity bit-matrix to the bit-matrix.
Transposing
constexpr BitMatrix	transposed () const
	Returns a new bit-matrix that is the transpose of this one.
constexpr void	transpose ()
	Transposes a square bit-matrix in place.
Exponentiation
constexpr BitMatrix	to_the (usize n, bool n_is_log2=false) const
	Returns a new bit-matrix that is this one raised to some power n or 2^n.
Row-echelon forms
BitVector< Word >	to_echelon_form ()
	Transforms an arbitrary shaped, non-empty, bit-matrix to row-echelon form (in-place).
BitVector< Word >	to_reduced_echelon_form ()
	Transforms the bit-matrix to reduced row-echelon form (in-place).
LU Decomposition
BitLU< Word >	LU () const
	Returns the LU decomposition of the bit-matrix.
Solving systems of linear equations
template<BitStore Rhs> requires std::same_as<typename Rhs::word_type, Word>
auto	solver_for (Rhs const &b) const
	Returns the Gaussian elimination solver for this bit-matrix and the passed r.h.s. vector b.
template<BitStore Rhs> requires std::same_as<typename Rhs::word_type, Word>
auto	x_for (Rhs const &b) const
	Returns a solution to the system of linear equations A.x_ = b or std::nullopt if there are none.
Bitwise Operations
constexpr void	operator^= (BitMatrix< Word > const &rhs)
	In-place XOR with a bit-matrix rhs.
constexpr void	operator&= (BitMatrix< Word > const &rhs)
	In-place AND with a bit-matrix rhs.
constexpr void	operator|= (BitMatrix< Word > const &rhs)
	In-place OR with a bit-matrix rhs.
constexpr auto	operator^ (BitMatrix< Word > const &rhs) const
	TheXOR of this with a bit-matrix rhs returning a new bit-matrix.
constexpr auto	operator& (BitMatrix< Word > const &rhs) const
	TheAND of this with a bit-matrix rhs returning a new bit-matrix.
constexpr auto	operator| (BitMatrix< Word > const &rhs) const
	TheOR of this with a bit-matrix rhs returning a new bit-matrix.
constexpr auto	operator~ ()
	Returns a copy of this bit-matrix with all the elements flipped.
Arithmetic Operations
constexpr void	operator+= (BitMatrix< Word > const &rhs)
	In-place addition with a bit-matrix rhs – in GF(2) addition is the same as XOR.
constexpr void	operator-= (BitMatrix< Word > const &rhs)
	In-place difference with a bit-matrix rhs – in GF(2) subtraction is the same as XOR.
constexpr auto	operator+ (BitMatrix< Word > const &rhs) const
	Returns a new bit-matrix that is *this + rhs which is *this ^ rhs in GF(2).
constexpr auto	operator- (BitMatrix< Word > const &rhs) const
	Returns a new bit-matrix that is *this - rhs which is *this ^ rhs in GF(2).
String Representations
std::string	to_binary_string (std::string_view row_sep="\n", std::string_view bit_sep="", std::string_view row_prefix="", std::string_view row_suffix="") const
	Returns a configurable binary string representation for this bit-matrix.
std::string	to_compact_binary_string () const
	Returns a one-line minimal binary string representation for this bit-matrix.
std::string	to_string () const
	Returns the default string representation for this bit-matrix.
std::string	to_pretty_string () const
	Returns the default pretty string representation for this bit-matrix.
std::string	to_hex_string (std::string_view row_sep="\n") const
	"Returns the "hex" string representation of the bit-matrix
std::string	to_compact_hex_string () const
	Returns a compact "hex" string representation of the bit-matrix.

Static Public Member Functions
Factory Constructors
static constexpr BitMatrix	zeros (usize m, usize n)
	Factory method to create the m x n zero bit-matrix with all the elements set to 0.
static constexpr BitMatrix	zeros (usize m)
	Factory method to create the m x m square bit-matrix with all the elements set to 0.
static constexpr BitMatrix	ones (usize m, usize n)
	Factory method to create the m x n bit-matrix with all the elements set to 1.
static constexpr BitMatrix	ones (usize m)
	Factory method to create the m x m square bit-matrix with all the elements set to 1.
static constexpr BitMatrix	alternating (usize m, usize n)
	Factory method to create the m x n bit-matrix with alternating elements.
static constexpr BitMatrix	alternating (usize m)
	Factory method to create the m x m square bit-matrix with alternating elements.
template<BitStore Lhs, BitStore Rhs> requires std::same_as<typename Lhs::word_type, Word> && std::same_as<typename Rhs::word_type, Word>
static constexpr BitMatrix	from_outer_product (Lhs const &u, Rhs const &v)
	Factory method to create the m x n bit-matrix from the outer product of the given bit-stores.
template<BitStore Lhs, BitStore Rhs> requires std::same_as<typename Lhs::word_type, Word> && std::same_as<typename Rhs::word_type, Word>
static constexpr BitMatrix	from_outer_sum (Lhs const &u, Rhs const &v)
	Factory method to create the m x n bit-matrix from the outer sum of the given bit-stores.
static constexpr BitMatrix	from (usize m, usize n, std::invocable< usize, usize > auto f)
	Factory method to construct an \(m \times n\) bit-matrix by repeatedly calling f(i, j) for each index pair.
Randomly Populated Constructors
static BitMatrix	random (usize m, usize n, double p=0.5, std::uint64_t seed=0)
	Factory method to generate a bit-matrix of size m x n where the elements are picked at random.
static BitMatrix	seeded_random (usize m, usize n, std::uint64_t seed)
	Factory method to generate a bit-matrix of size m x n where the elements are from independent fair coin flips generated from an RNG seeded with the given seed.
static BitMatrix	seeded_random (usize m, std::uint64_t seed)
	Factory method to generate a square bit-matrix of size m x m where the elements are from independent fair coin flips generated from an RNG seeded with the given seed.
static BitMatrix	biased_random (usize m, usize n, double p)
	Factory method to generate a bit-matrix of size m x n where the elements are from independent fair coin flips and where each bit is 1 with probability p.
static BitMatrix	biased_random (usize m, double p)
	Factory method to generate a square bit-matrix of size m x m where the elements are from independent fair coin flips and where each bit is 1 with probability p.
Constructors for Special Matrices
static constexpr BitMatrix	zero (usize m)
	Factory method to create the m x m square "zero" bit-matrix.
static constexpr BitMatrix	identity (usize m)
	Factory method to create the m x m identity bit-matrix.
template<BitStore Store> requires std::same_as<typename Store::word_type, Word>
static constexpr BitMatrix	companion (Store const &top_row)
	Constructs a square companion BitMatrix with a copy of the given top row and a sub-diagonal of 1s.
static constexpr BitMatrix	left_shift (usize n, usize p)
	Constructs the n x n shift-left by p places BitMatrix.
static BitMatrix	right_shift (usize n, usize p)
	Constructs the n x n shift-right by p places BitMatrix.
static BitMatrix	left_rotation (usize n, usize p)
	Constructs the n x n rotate-left by p places matrix.
static BitMatrix	right_rotation (usize n, usize p)
	Constructs the n x n rotate-right by p places matrix.
Construction by reshaping bit-stores.
template<BitStore Store> requires std::same_as<typename Store::word_type, Word>
static std::optional< BitMatrix >	from_row_store (Store const &v, usize r)
	Factory method to reshape a bit-vector v that is assumed to a sequence of r rows into a bit-matrix.
template<BitStore Store> requires std::same_as<typename Store::word_type, Word>
static std::optional< BitMatrix >	from_col_store (Store const &v, usize c)
	Factory method to reshape a bit-vector that is assumed to a sequence of c columns into a bit-matrix.
Construction from strings
static std::optional< BitMatrix >	from_string (std::string_view s)
	Factory method to construct a bit-matrix from a string that is assumed to be a sequence of rows.

Inversion
std::optional< BitMatrix >	inverse () const
	Returns the inverse of a square bit-matrix or std::nullopt if the matrix is singular.
static constexpr double	probability_invertible (usize n)
	Class method that returns the probability that a square n x n bit-matrix is invertible if each element is chosen independently and uniformly at random by flips of a fair coin.
static constexpr double	probability_singular (usize n)
	Class method that returns the probability that a square n x n bit-matrix is singular if each element is chosen independently and uniformly at random by flips of a fair coin.

Characteristic Polynomial
BitPolynomial< Word >	characteristic_polynomial () const
	Returns the characteristic polynomial of any square bit-matrix as a gf2::BitPolynomial.
std::vector< BitVector< Word > >	frobenius_form () const
	Returns the Frobenius form of this bit-matrix in compact top-row only form.
static BitPolynomial< Word >	frobenius_matrix_characteristic_polynomial (std::vector< BitVector< Word > > const &top_rows)
	Class method that returns the characteristic polynomial of a Frobenius matrix as a gf2::BitPolynomial.
static BitPolynomial< Word >	companion_matrix_characteristic_polynomial (BitVector< Word > const &top_row)
	Class method to return the characteristic polynomial of a companion matrix as a gf2::BitPolynomial.

Comparison Operator
constexpr bool	operator== (BitMatrix const &lhs, BitMatrix const &rhs)
	Equality operator checks that any pair of bit-matrices are equal in content.

Detailed Description

template<Unsigned Word = usize>
class gf2::BitMatrix< Word >

A dynamically-sized matrix over GF(2) stored as a vector of bit-vectors representing the rows of the matrix. The row elements are compactly stored in standard vectors of primitive unsigned words whose type is given by the template parameter Word.

Note

Bit-matrices are stored by row, so it is always more efficient to arrange computations to operate on rows instead of columns. The high-level methods in this library take care of this for you.

Constructor & Destructor Documentation

BitMatrix() [1/5]

template<Unsigned Word = usize>

gf2::BitMatrix< Word >::BitMatrix ( )

inlineconstexpr

The default constructor creates an empty bit-matrix with no rows or columns.

Example

BitMatrix m;
assert_eq(m.to_compact_binary_string(), "");

BitMatrix() [2/5]

template<Unsigned Word = usize>

gf2::BitMatrix< Word >::BitMatrix ( usize n )

inlineconstexpr

Constructs the n x n square bit-matrix with all the elements set to 0.

If n is zero, we create an empty bit-matrix with no rows or columns.

Example

BitMatrix m{3};
assert_eq(m.to_compact_binary_string(), "000 000 000");

BitMatrix() [3/5]

template<Unsigned Word = usize>

gf2::BitMatrix< Word >::BitMatrix ( usize m, usize n )

inlineconstexpr

Constructs the m x n bit-matrix with all the elements set to 0.

If either m or n is zero, we create an empty bit-matrix with no rows or columns.

Example

BitMatrix m{3, 4};
assert_eq(m.to_compact_binary_string(), "0000 0000 0000");

BitMatrix() [4/5]

template<Unsigned Word = usize>

gf2::BitMatrix< Word >::BitMatrix ( std::vector< row_type > const & rows )

inlineconstexpr

Construct a bit-matrix by copying a given set of rows which can be any BitStore subclass.

Panics

We check that all the rows have the same size unless NDEBUG is defined.

Example

auto rows = std::vector{BitVector<>::zeros(3), BitVector<>::ones(3)};
BitMatrix m{rows};
assert_eq(m.to_compact_binary_string(), "000 111");

BitMatrix() [5/5]

template<Unsigned Word = usize>

gf2::BitMatrix< Word >::BitMatrix ( std::vector< BitVector< Word > > && rows )

inlineconstexpr

Construct a bit-matrix by moving the given rows.

Use std::move(rows) in the constructor argument to get this version. The input rows are moved into the bit-matrix so they are no longer valid after this constructor.

Panics

We check that all the rows have the same size unless NDEBUG is defined.

Example

auto rows = std::vector{BitVector<>::zeros(3), BitVector<>::ones(3)};
BitMatrix m{std::move(rows)};
assert_eq(m.to_compact_binary_string(), "000 111");

Member Function Documentation

add_identity()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::add_identity ( )

inlineconstexpr

Adds the identity bit-matrix to the bit-matrix.

Panics

In debug mode, this method will panic if the bit-matrix is not square.

Example

auto m = BitMatrix<>::zero(3);
m.add_identity();
assert_eq(m.to_compact_binary_string(), "100 010 001");

all()

template<Unsigned Word = usize>

bool gf2::BitMatrix< Word >::all ( ) const

inlineconstexpr

Returns true if all elements of the bit-matrix are set.

Empty matrices are considered to have all bits set.

Example

auto m = BitMatrix<>::zero(3);
assert_eq(m.all(), false);
m.set_all();
assert_eq(m.all(), true);
m.clear();
assert_eq(m.all(), true);

alternating() [1/2]

template<Unsigned Word = usize>

constexpr BitMatrix gf2::BitMatrix< Word >::alternating ( usize m )

inlinestaticconstexpr

Factory method to create the m x m square bit-matrix with alternating elements.

Example

auto m = BitMatrix<>::alternating(3);
assert_eq(m.to_compact_binary_string(), "101 010 101");

alternating() [2/2]

template<Unsigned Word = usize>

constexpr BitMatrix gf2::BitMatrix< Word >::alternating ( usize m, usize n )

inlinestaticconstexpr

Factory method to create the m x n bit-matrix with alternating elements.

Example

auto m = BitMatrix<>::alternating(3, 4);
assert_eq(m.to_compact_binary_string(), "1010 0101 1010");

any()

template<Unsigned Word = usize>

bool gf2::BitMatrix< Word >::any ( ) const

inlineconstexpr

Returns true if any element of the bit-matrix is set.

Empty matrices are considered to have no set bits.

Example

auto m = BitMatrix<>::zero(3);
assert_eq(m.any(), false);
m.set(0, 0);
assert_eq(m.any(), true);
m.clear();
assert_eq(m.any(), false);

append_col()

template<Unsigned Word = usize>

template<BitStore Store>
requires std::same_as<typename Store::word_type, Word>

BitMatrix & gf2::BitMatrix< Word >::append_col ( Store const & col )

inlineconstexpr

Appends a single column col onto the right of the bit-matrix so M -> M|col and returns a reference to the this for chaining.

Panics

The column must have the same number of elements as the bit-matrix has rows.

Example

auto m = BitMatrix<>::zero(3);
auto col = BitVector<>::ones(3);
m.append_col(col);
assert_eq(m.to_compact_binary_string(), "0001 0001 0001");

append_cols()

template<Unsigned Word = usize>

BitMatrix & gf2::BitMatrix< Word >::append_cols ( BitMatrix< Word > const & src )

inlineconstexpr

Appends all the columns from the src bit-matrix onto the right of this bit-matrix so M -> M|src and returns a reference to the this for chaining.

Panics

The source bit-matrix must have the same number of rows as this bit-matrix.

Example

auto m = BitMatrix<>::zero(3);
auto src = BitMatrix<>::ones(3, 2);
m.append_cols(src);
assert_eq(m.to_compact_binary_string(), "00011 00011 00011");

append_row() [1/2]

template<Unsigned Word = usize>

template<BitStore Store>
requires std::same_as<typename Store::word_type, Word>

BitMatrix & gf2::BitMatrix< Word >::append_row ( Store && row )

inlineconstexpr

Appends a single row onto the end of the bit-matrix by moving it and returns a reference to the this for chaining.

Use std::move(row) in the method argument to guarantee this version. The input row is moved into the matrix and is no longer valid after this call.

Panics

The row must have the same number of elements as the bit-matrix has columns.

Example

auto m = BitMatrix<>::zero(3);
m.append_row(BitVector<>::ones(3));
assert_eq(m.to_compact_binary_string(), "000 000 000 111");

append_row() [2/2]

template<Unsigned Word = usize>

template<BitStore Store>
requires std::same_as<typename Store::word_type, Word>

BitMatrix & gf2::BitMatrix< Word >::append_row ( Store const & row )

inlineconstexpr

Appends a single row onto the end of the bit-matrix by copying it and returns a reference to the this for chaining.

Panics

The row must have the same number of elements as the bit-matrix has columns.

Example

auto m = BitMatrix<>::zero(3);
auto row = BitVector<>::ones(3);
m.append_row(row);
assert_eq(m.to_compact_binary_string(), "000 000 000 111");

append_rows() [1/2]

template<Unsigned Word = usize>

BitMatrix & gf2::BitMatrix< Word >::append_rows ( BitMatrix< Word > && src )

inlineconstexpr

Appends all the rows from the src bit-matrix onto the end of this bit-matrix by moving them and returns a reference to the this for chaining.

Use std::move(src) in the method argument to guarantee this version. The source bit-matrix is moved into this matrix and is no longer valid after this call.

Panics

The source bit-matrix must have the same number of columns as this bit-matrix.

Example

auto m = BitMatrix<>::zero(3);
m.append_rows(BitMatrix<>::ones(3, 3));
assert_eq(m.to_compact_binary_string(), "000 000 000 111 111 111");

append_rows() [2/2]

template<Unsigned Word = usize>

BitMatrix & gf2::BitMatrix< Word >::append_rows ( BitMatrix< Word > const & src )

inlineconstexpr

Appends all the rows from the src bit-matrix onto the end of this bit-matrix by copying them and returns a reference to the this for chaining.

Panics

The source bit-matrix must have the same number of columns as this bit-matrix.

Example

auto m = BitMatrix<>::zero(3);
auto src = BitMatrix<>::ones(3, 3);
m.append_rows(src);
assert_eq(m.to_compact_binary_string(), "000 000 000 111 111 111");

biased_random() [1/2]

template<Unsigned Word = usize>

BitMatrix gf2::BitMatrix< Word >::biased_random ( usize m, double p )

inlinestatic

Factory method to generate a square bit-matrix of size m x m where the elements are from independent fair coin flips and where each bit is 1 with probability p.

Parameters

m	The number of rows in the bit-matrix to generate.
p	The probability of the elements being 1.

Example

auto u = BitMatrix<>::biased_random(10, 0.3);
assert_eq(u.size(), 100);

biased_random() [2/2]

template<Unsigned Word = usize>

BitMatrix gf2::BitMatrix< Word >::biased_random ( usize m, usize n, double p )

inlinestatic

Factory method to generate a bit-matrix of size m x n where the elements are from independent fair coin flips and where each bit is 1 with probability p.

Parameters

m	The number of rows in the bit-matrix to generate.
n	The number of columns in the bit-matrix to generate.
p	The probability of the elements being 1.

Example

auto u = BitMatrix<>::biased_random(10, 7, 0.3);
auto v = BitMatrix<>::biased_random(10, 7, 0.3);
assert_eq(u.size(), v.size());

characteristic_polynomial()

template<Unsigned Word = usize>

BitPolynomial< Word > gf2::BitMatrix< Word >::characteristic_polynomial ( ) const

inline

Returns the characteristic polynomial of any square bit-matrix as a gf2::BitPolynomial.

The method uses similarity transformations to convert the bit-matrix to Frobenius form which has a readily computable characteristic polynomial. Similarity transformations preserve eigen-structure, and in particular they preserve the characteristic polynomial.

Panics

This method panics if the bit-matrix is not square.

Example

auto m2 = BitMatrix<>::identity(2);
assert_eq(m2.characteristic_polynomial().to_string(), "1 + x^2");
auto m3 = BitMatrix<>::identity(3);
assert_eq(m3.characteristic_polynomial().to_string(), "1 + x + x^2 + x^3");
auto m100 = BitMatrix<>::random(100, 100);
auto p = m100.characteristic_polynomial();
assert_eq(p(m100).is_zero(), true);

clear()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::clear ( )

inlineconstexpr

Removes all the elements from the bit-matrix.

Example

auto m = BitMatrix<>::zero(3);
m.clear();
assert_eq(m.rows(), 0);
assert_eq(m.cols(), 0);

col()

template<Unsigned Word = usize>

BitVector< Word > gf2::BitMatrix< Word >::col ( usize c ) const

inlineconstexpr

Returns a clone of the elements in column c from the bit-matrix as an independent bit-vector.

Matrices are stored by rows and there is no cheap reference style access to the BitMatrix columns!

Panics

In debug mode, this method will panic if c is out of bounds.

Example

auto m = BitMatrix<>::identity(3);
auto col = m.col(1);
assert_eq(col.to_string(), "010");
col.set(0);
col.set(2);
assert_eq(col.to_string(), "111");
assert_eq(m.to_compact_binary_string(), "100 010 001");

companion()

template<Unsigned Word = usize>

template<BitStore Store>
requires std::same_as<typename Store::word_type, Word>

constexpr BitMatrix gf2::BitMatrix< Word >::companion ( Store const & top_row )

inlinestaticconstexpr

Constructs a square companion BitMatrix with a copy of the given top row and a sub-diagonal of 1s.

The top row should be passed as a bit-store and is copied to the first row of the BitMatrix. The rest of the BitMatrix is initialized to zero and the sub-diagonal is set to 1s.

Example

auto top_row = BitVector<>::ones(5);
auto m = BitMatrix<>::companion(top_row);
assert_eq(m.to_compact_binary_string(), "11111 10000 01000 00100 00010");

companion_matrix_characteristic_polynomial()

template<Unsigned Word = usize>

BitPolynomial< Word > gf2::BitMatrix< Word >::companion_matrix_characteristic_polynomial ( BitVector< Word > const & top_row )

inlinestatic

Class method to return the characteristic polynomial of a companion matrix as a gf2::BitPolynomial.

The function expects to be passed the top row of the companion matrix as a bit-vector.

A companion matrix is a square matrix that is all zeros except for an arbitrary top row and a principal sub-diagonal of all ones. Companion matrices can be compactly represented by their top rows only.

The characteristic polynomial of a companion matrix can be computed from its top row.

Example

auto top_row = BitVector<>::from_binary_string("101").value();
assert_eq(BitMatrix<>::companion_matrix_characteristic_polynomial(top_row).to_string(), "1 + x^2 + x^3");

count_ones()

template<Unsigned Word = usize>

usize gf2::BitMatrix< Word >::count_ones ( ) const

inlineconstexpr

Returns the number of one elements in the bit-matrix.

Example

auto m = BitMatrix<>::zero(3);
assert_eq(m.count_ones(), 0);
m.set_all();
assert_eq(m.count_ones(), 9);

count_ones_on_diagonal()

template<Unsigned Word = usize>

usize gf2::BitMatrix< Word >::count_ones_on_diagonal ( ) const

inlineconstexpr

Returns the number of ones on the main diagonal of the bit-matrix.

Panics

In debug mode, this method will panic if the bit-matrix is not square.

Example

auto m = BitMatrix<>::identity(3);
assert_eq(m.count_ones_on_diagonal(), 3);

count_zeros()

template<Unsigned Word = usize>

usize gf2::BitMatrix< Word >::count_zeros ( ) const

inlineconstexpr

Returns the number of zero elements in the bit-matrix.

Example

auto m = BitMatrix<>::identity(3);
assert_eq(m.count_zeros(), 6);

flip()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::flip ( usize r, usize c )

inlineconstexpr

Flips the bit at row r and column c.

Panics

In debug mode, this method will panic if r or c is out of bounds.

Example

auto m = BitMatrix<>::zero(3);
m.flip(0, 0);
assert_eq(m.get(0, 0), true);

flip_all()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::flip_all ( )

inlineconstexpr

Flips all the elements of the bit-matrix.

Example

auto m = BitMatrix<>::zero(3);
m.flip_all();
assert_eq(m.to_compact_binary_string(), "111 111 111");

flip_diagonal()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::flip_diagonal ( )

inlineconstexpr

Flips all the elements on the main diagonal of a square bit-matrix.

Panics

In debug mode, this method will panic if the bit-matrix is not square.

Example

auto m = BitMatrix<>::zero(3);
m.flip_diagonal();
assert_eq(m.to_compact_binary_string(), "100 010 001");

flip_sub_diagonal()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::flip_sub_diagonal ( usize d )

inlineconstexpr

Flips all the elements on the sub-diagonal d of a square bit-matrix.

Here d = 0 is the main diagonal and d = 1 is the first sub-diagonal etc.

Panics

In debug mode, this method will panic if the bit-matrix is not square.

Example

auto m = BitMatrix<>::zero(5);
m.flip_sub_diagonal(1);
assert_eq(m.to_compact_binary_string(), "00000 10000 01000 00100 00010");

flip_super_diagonal()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::flip_super_diagonal ( usize d )

inlineconstexpr

Flips all the elements on the super-diagonal d of a square bit-matrix.

Here d = 0 is the main diagonal and d = 1 is the first super-diagonal etc.

Panics

In debug mode, this method will panic if the bit-matrix is not square.

Example

auto m = BitMatrix<>::zero(5);
m.flip_super_diagonal(1);
assert_eq(m.to_compact_binary_string(), "01000 00100 00010 00001 00000");

frobenius_form()

template<Unsigned Word = usize>

std::vector< BitVector< Word > > gf2::BitMatrix< Word >::frobenius_form ( ) const

inline

Returns the Frobenius form of this bit-matrix in compact top-row only form.

A Frobenius matrix is a square matrix that consists of one or more blocks of companion matrices along the diagonal. The companion matrices are square matrices that are all zeros except for an arbitrary top row and a principal sub-diagonal of all ones. Companion matrices can be compactly represented by their top rows only.

We can convert any bit-matrix to Frobenius form via a sequence of similarity transformations that preserve the eigen-structure of the original matrix.

We return the Frobenius companion matrices in a compact form as a Vec of their top rows as bit-vectors.

Panics

This method panics if the bit-matrix is not square.

frobenius_matrix_characteristic_polynomial()

template<Unsigned Word = usize>

BitPolynomial< Word > gf2::BitMatrix< Word >::frobenius_matrix_characteristic_polynomial ( std::vector< BitVector< Word > > const & top_rows )

inlinestatic

Class method that returns the characteristic polynomial of a Frobenius matrix as a gf2::BitPolynomial.

A Frobenius matrix is a square matrix that consists of blocks of companion matrices along the diagonal. Each companion matrix is a square matrix that is all zeros except for an arbitrary top row and a principal sub-diagonal of all ones. Companion matrices can be compactly represented by their top rows only.

This associated function expects to be passed the top rows of the companion matrices as an array of bit-vectors. The characteristic polynomial of a Frobenius matrix is the product of the characteristic polynomials of its block companion matrices which are readily computed.

from()

template<Unsigned Word = usize>

constexpr BitMatrix gf2::BitMatrix< Word >::from ( usize m, usize n, std::invocable< usize, usize > auto f )

inlinestaticconstexpr

Factory method to construct an \(m \times n\) bit-matrix by repeatedly calling f(i, j) for each index pair.

Example

auto m = BitMatrix<>::from(3, 2, [](usize i, usize) { return i % 2 == 0; });
assert_eq(m.to_compact_binary_string(), "11 00 11");

from_col_store()

template<Unsigned Word = usize>

template<BitStore Store>
requires std::same_as<typename Store::word_type, Word>

std::optional< BitMatrix > gf2::BitMatrix< Word >::from_col_store ( Store const & v, usize c )

inlinestatic

Factory method to reshape a bit-vector that is assumed to a sequence of c columns into a bit-matrix.

Parameters

v	The bit-vector to reshape.
c	The number of columns.

Example

auto v = BitVector<>::ones(15);
auto m1 = BitMatrix<>::from_col_store(v, 3).value();
assert_eq(m1.to_compact_binary_string(), "111 111 111 111 111");
auto m2 = BitMatrix<>::from_col_store(v, 5).value();
assert_eq(m2.to_compact_binary_string(), "11111 11111 11111");
auto m3 = BitMatrix<>::from_col_store(v, 15).value();
assert_eq(m3.to_compact_binary_string(), "111111111111111");

from_outer_product()

template<Unsigned Word = usize>

template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, Word> && std::same_as<typename Rhs::word_type, Word>

constexpr BitMatrix gf2::BitMatrix< Word >::from_outer_product ( Lhs const & u, Rhs const & v )

inlinestaticconstexpr

Factory method to create the m x n bit-matrix from the outer product of the given bit-stores.

Example

auto u = BitVector<>::from_string("101").value();
auto v = BitVector<>::from_string("110").value();
auto m = BitMatrix<>::from_outer_product(u, v);
assert_eq(m.to_compact_binary_string(), "110 000 110");

from_outer_sum()

template<Unsigned Word = usize>

template<BitStore Lhs, BitStore Rhs>
requires std::same_as<typename Lhs::word_type, Word> && std::same_as<typename Rhs::word_type, Word>

constexpr BitMatrix gf2::BitMatrix< Word >::from_outer_sum ( Lhs const & u, Rhs const & v )

inlinestaticconstexpr

Factory method to create the m x n bit-matrix from the outer sum of the given bit-stores.

Example

auto u = BitVector<>::from_string("101").value();
auto v = BitVector<>::from_string("110").value();
auto m = BitMatrix<>::from_outer_sum(u, v);
assert_eq(m.to_compact_binary_string(), "001 110 001");

from_row_store()

template<Unsigned Word = usize>

template<BitStore Store>
requires std::same_as<typename Store::word_type, Word>

std::optional< BitMatrix > gf2::BitMatrix< Word >::from_row_store ( Store const & v, usize r )

inlinestatic

Factory method to reshape a bit-vector v that is assumed to a sequence of r rows into a bit-matrix.

Example

auto v = BitVector<>::ones(15);
auto m1 = BitMatrix<>::from_row_store(v, 3).value();
assert_eq(m1.to_compact_binary_string(), "11111 11111 11111");
auto m2 = BitMatrix<>::from_row_store(v, 5).value();
assert_eq(m2.to_compact_binary_string(), "111 111 111 111 111");
auto m3 = BitMatrix<>::from_row_store(v, 15).value();
assert_eq(m3.to_compact_binary_string(), "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1");

from_string()

template<Unsigned Word = usize>

std::optional< BitMatrix > gf2::BitMatrix< Word >::from_string ( std::string_view s )

inlinestatic

Factory method to construct a bit-matrix from a string that is assumed to be a sequence of rows.

The rows 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. The rows can have an optional prefix of "0b", "0x" or "0X" to indicate that the string is binary or hex.

A hex string can have a suffix of ".2", ".4", or ".8" to indicate the base of the last digit/character. This allows for rows of any length as opposed to just a multiple of 4.

After parsing, the rows must all have the same length.

Example

auto m1 = BitMatrix<>::from_string("111   111\n111").value();
assert_eq(m1.to_compact_binary_string(), "111 111 111");
auto m2 = BitMatrix<>::from_string("0XAA; 0b1111_0000").value();
assert_eq(m2.to_compact_binary_string(), "10101010 11110000");
auto m3 = BitMatrix<>::from_string("0x7.8 000").value();
assert_eq(m3.to_compact_binary_string(), "111 000");

get()

template<Unsigned Word = usize>

bool gf2::BitMatrix< Word >::get ( usize r, usize c ) const

inlineconstexpr

Returns true if the element at row r and column c is set.

Panics

In debug mode, this method will panic if r or c is out of bounds.

Example

auto m = BitMatrix<>::zero(3);
assert_eq(m.get(0, 0), false);
m.set(0, 0);
assert_eq(m.get(0, 0), true);

identity()

template<Unsigned Word = usize>

constexpr BitMatrix gf2::BitMatrix< Word >::identity ( usize m )

inlinestaticconstexpr

Factory method to create the m x m identity bit-matrix.

Example

auto m = BitMatrix<>::identity(3);
assert_eq(m.to_compact_binary_string(), "100 010 001");

inverse()

template<Unsigned Word = usize>

std::optional< BitMatrix > gf2::BitMatrix< Word >::inverse ( ) const

inline

Returns the inverse of a square bit-matrix or std::nullopt if the matrix is singular.

Example

auto m = BitMatrix<>::identity(3);
assert_eq(m.inverse().value().to_compact_binary_string(), "100 010 001");

is_identity()

template<Unsigned Word = usize>

bool gf2::BitMatrix< Word >::is_identity ( ) const

inlineconstexpr

Returns true if this is the identity bit-matrix.

Example

auto m = BitMatrix<>::identity(3);
assert_eq(m.is_identity(), true);
assert_eq(m.to_compact_binary_string(), "100 010 001");

is_square()

template<Unsigned Word = usize>

bool gf2::BitMatrix< Word >::is_square ( ) const

inlineconstexpr

Returns true if this a square bit-matrix? Note that empty bit-matrices are NOT considered square.

Example

BitMatrix m;
assert_eq(m.is_square(), false);
m.resize(3, 3);
assert_eq(m.is_square(), true);
m.resize(3, 4);
assert_eq(m.is_square(), false);

is_symmetric()

template<Unsigned Word = usize>

bool gf2::BitMatrix< Word >::is_symmetric ( ) const

inlineconstexpr

Returns true if this is a symmetric square bit-matrix.

Example

auto m = BitMatrix<>::identity(3);
assert_eq(m.is_symmetric(), true);
m.row(0).set_all();
assert_eq(m.is_symmetric(), false);

is_zero()

template<Unsigned Word = usize>

bool gf2::BitMatrix< Word >::is_zero ( ) const

inlineconstexpr

Returns true if this a square zero bit-matrix?

Example

BitMatrix m;
assert_eq(m.is_zero(), false);
m.resize(3, 3);
assert_eq(m.is_zero(), true);
m.resize(3, 4);
assert_eq(m.is_zero(), false);

left_rotation()

template<Unsigned Word = usize>

BitMatrix gf2::BitMatrix< Word >::left_rotation ( usize n, usize p )

inlinestatic

Constructs the n x n rotate-left by p places matrix.

If the bit-matrix is multiplied by a bit-vector, the result is the bit-vector rotated right by p places.

Example

auto m = BitMatrix<>::left_rotation(5, 2);
auto v = BitVector<>::from_binary_string("11100").value();
assert_eq(dot(m, v).to_string(), "00111");

left_shift()

template<Unsigned Word = usize>

constexpr BitMatrix gf2::BitMatrix< Word >::left_shift ( usize n, usize p )

inlinestaticconstexpr

Constructs the n x n shift-left by p places BitMatrix.

If the bit-matrix is multiplied by a bit-vector, the result is the bit-vector shifted left by p places.

Example

auto m = BitMatrix<>::left_shift(5, 2);
auto v = BitVector<>::ones(5);
assert_eq(dot(m, v).to_string(), "11100");

lower()

template<Unsigned Word = usize>

BitMatrix gf2::BitMatrix< Word >::lower ( ) const

inlineconstexpr

Returns an independent clone of the lower triangular part of the bit-matrix.

Example

auto m = BitMatrix<>::ones(3, 3);
auto sub_m = m.lower();
assert_eq(sub_m.to_compact_binary_string(), "100 110 111");

LU()

template<Unsigned Word = usize>

BitLU< Word > gf2::BitMatrix< Word >::LU ( ) const

inline

Returns the LU decomposition of the bit-matrix.

Example

auto m = BitMatrix<>::identity(3);
auto lu = m.LU();
assert_eq(lu.LU().to_compact_binary_string(), "100 010 001");

make_square()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::make_square ( usize n )

inlineconstexpr

Makes an arbitrary rectangular bit-matrix into a square BitMatrix.

Existing elements are preserved. Any added elements are initialized to zero.

Example

auto m = BitMatrix<>::from_string("111 111 111 111").value();
m.make_square(3);
assert_eq(m.to_compact_binary_string(), "111 111 111");

none()

template<Unsigned Word = usize>

bool gf2::BitMatrix< Word >::none ( ) const

inlineconstexpr

Returns true if no elements of the bit-matrix are set.

Empty matrices are considered to have no set bits.

Example

auto m = BitMatrix<>::zero(3);
assert_eq(m.none(), true);
m.set_all();
assert_eq(m.none(), false);
m.clear();
assert_eq(m.none(), true);

ones() [1/2]

template<Unsigned Word = usize>

constexpr BitMatrix gf2::BitMatrix< Word >::ones ( usize m )

inlinestaticconstexpr

Factory method to create the m x m square bit-matrix with all the elements set to 1.

Example

auto m = BitMatrix<>::ones(3);
assert_eq(m.to_compact_binary_string(), "111 111 111");

ones() [2/2]

template<Unsigned Word = usize>

constexpr BitMatrix gf2::BitMatrix< Word >::ones ( usize m, usize n )

inlinestaticconstexpr

Factory method to create the m x n bit-matrix with all the elements set to 1.

Example

auto m = BitMatrix<>::ones(3, 4);
assert_eq(m.to_compact_binary_string(), "1111 1111 1111");

operator&()

template<Unsigned Word = usize>

auto gf2::BitMatrix< Word >::operator& ( BitMatrix< Word > const & rhs ) const

inlineconstexpr

TheAND of this with a bit-matrix rhs returning a new bit-matrix.

Panics

This method panics if the dimensions do not match.

Example

auto lhs = BitMatrix<>::identity(3);
auto rhs = BitMatrix<>::identity(3);
rhs.flip_all();
auto result = lhs & rhs;
assert_eq(result.to_compact_binary_string(), "000 000 000");

operator&=()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::operator&= ( BitMatrix< Word > const & rhs )

inlineconstexpr

In-place AND with a bit-matrix rhs.

Panics

This method panics if the dimensions do not match.

Example

auto lhs = BitMatrix<>::identity(3);
auto rhs = BitMatrix<>::identity(3);
rhs.flip_all();
lhs &= rhs;
assert_eq(lhs.to_compact_binary_string(), "000 000 000");

operator()() [1/2]

template<Unsigned Word = usize>

BitRef< row_type > gf2::BitMatrix< Word >::operator() ( usize r, usize c )

inlineconstexpr

Returns the bit at row r and column c as a BitRef reference which can be used to set the bit.

Panics

In debug mode, this method will panic if r or c is out of bounds.

Example

auto m = BitMatrix<>::zero(3);
assert_eq(m(0,0), false);
m(0,0) = true;
assert_eq(m(0,0), true);

operator()() [2/2]

template<Unsigned Word = usize>

bool gf2::BitMatrix< Word >::operator() ( usize r, usize c ) const

inlineconstexpr

Returns the value of the bit at row r and column c as a bool.

Panics

In debug mode, this method will panic if r or c is out of bounds.

Example

auto m = BitMatrix<>::zero(3);
assert_eq(m(0, 0), false);
m.set(0, 0);
assert_eq(m(0, 0), true);

operator+()

template<Unsigned Word = usize>

auto gf2::BitMatrix< Word >::operator+ ( BitMatrix< Word > const & rhs ) const

inlineconstexpr

Returns a new bit-matrix that is *this + rhs which is *this ^ rhs in GF(2).

Panics

This method panics if the dimensions do not match.

Example

auto lhs = BitMatrix<>::identity(3);
auto rhs = BitMatrix<>::identity(3);
rhs.flip_all();
auto result = lhs - rhs;
assert_eq(result.to_compact_binary_string(), "111 111 111");

operator+=()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::operator+= ( BitMatrix< Word > const & rhs )

inlineconstexpr

In-place addition with a bit-matrix rhs – in GF(2) addition is the same as XOR.

Panics

This method panics if the dimensions do not match.

Example

auto lhs = BitMatrix<>::identity(3);
auto rhs = BitMatrix<>::identity(3);
rhs.flip_all();
lhs += rhs;
assert_eq(lhs.to_compact_binary_string(), "111 111 111");

operator-()

template<Unsigned Word = usize>

auto gf2::BitMatrix< Word >::operator- ( BitMatrix< Word > const & rhs ) const

inlineconstexpr

Returns a new bit-matrix that is *this - rhs which is *this ^ rhs in GF(2).

Panics

This method panics if the dimensions do not match.

Example

auto lhs = BitMatrix<>::identity(3);
auto rhs = BitMatrix<>::identity(3);
rhs.flip_all();
auto result = lhs + rhs;
assert_eq(result.to_compact_binary_string(), "111 111 111");

operator-=()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::operator-= ( BitMatrix< Word > const & rhs )

inlineconstexpr

In-place difference with a bit-matrix rhs – in GF(2) subtraction is the same as XOR.

Panics

This method panics if the dimensions do not match.

Example

auto lhs = BitMatrix<>::identity(3);
auto rhs = BitMatrix<>::identity(3);
rhs.flip_all();
lhs -= rhs;
assert_eq(lhs.to_compact_binary_string(), "111 111 111");

operator[]() [1/2]

template<Unsigned Word = usize>

row_type & gf2::BitMatrix< Word >::operator[] ( usize r )

inlineconstexpr

Returns a read-write reference to the row at index r.

Panics

In debug mode, this method will panic if r is out of bounds.

Example

auto m = BitMatrix<>::identity(3);
m[0].set(1);
assert_eq(m[0].to_binary_string(), "110");
assert_eq(m[1].to_binary_string(), "010");
assert_eq(m[2].to_binary_string(), "001");

operator[]() [2/2]

template<Unsigned Word = usize>

const row_type & gf2::BitMatrix< Word >::operator[] ( usize r ) const

inlineconstexpr

Returns a read-only reference to the row at index r.

Panics

In debug mode, this method will panic if r is out of bounds.

Example

auto m = BitMatrix<>::identity(3);
assert_eq(m[0].to_binary_string(), "100");
assert_eq(m[1].to_binary_string(), "010");
assert_eq(m[2].to_binary_string(), "001");

operator^()

template<Unsigned Word = usize>

auto gf2::BitMatrix< Word >::operator^ ( BitMatrix< Word > const & rhs ) const

inlineconstexpr

TheXOR of this with a bit-matrix rhs returning a new bit-matrix.

Panics

This method panics if the dimensions do not match.

Example

auto lhs = BitMatrix<>::identity(3);
auto rhs = BitMatrix<>::identity(3);
rhs.flip_all();
auto result = lhs ^ rhs;
assert_eq(result.to_compact_binary_string(), "111 111 111");

operator^=()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::operator^= ( BitMatrix< Word > const & rhs )

inlineconstexpr

In-place XOR with a bit-matrix rhs.

Panics

This method panics if the dimensions do not match.

Example

auto lhs = BitMatrix<>::identity(3);
auto rhs = BitMatrix<>::identity(3);
rhs.flip_all();
lhs ^= rhs;
assert_eq(lhs.to_compact_binary_string(), "111 111 111");

operator|()

template<Unsigned Word = usize>

auto gf2::BitMatrix< Word >::operator| ( BitMatrix< Word > const & rhs ) const

inlineconstexpr

TheOR of this with a bit-matrix rhs returning a new bit-matrix.

Panics

This method panics if the dimensions do not match.

Example

auto lhs = BitMatrix<>::identity(3);
auto rhs = BitMatrix<>::identity(3);
rhs.flip_all();
auto result = lhs | rhs;
assert_eq(result.to_compact_binary_string(), "111 111 111");

operator|=()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::operator|= ( BitMatrix< Word > const & rhs )

inlineconstexpr

In-place OR with a bit-matrix rhs.

Panics

This method panics if the dimensions do not match.

Example

auto lhs = BitMatrix<>::identity(3);
auto rhs = BitMatrix<>::identity(3);
rhs.flip_all();
lhs |= rhs;
assert_eq(lhs.to_compact_binary_string(), "111 111 111");

operator~()

template<Unsigned Word = usize>

auto gf2::BitMatrix< Word >::operator~ ( )

inlineconstexpr

Returns a copy of this bit-matrix with all the elements flipped.

Example

auto m = BitMatrix<>::identity(3);
auto result = ~m;
assert_eq(result.to_compact_binary_string(), "011 101 110");

probability_invertible()

template<Unsigned Word = usize>

constexpr double gf2::BitMatrix< Word >::probability_invertible ( usize n )

inlinestaticconstexpr

Class method that returns the probability that a square n x n bit-matrix is invertible if each element is chosen independently and uniformly at random by flips of a fair coin.

For large n, the value is roughly 29% and that holds for n as low as 10.

Panics

This method panics if n is 0 – based on the assumption that querying the probability of a 0 x 0 bit-matrix being invertible is an upstream error somewhere.

Example

auto p = BitMatrix<>::probability_invertible(10);
assert(abs(p - 0.289) < 1e-3);

probability_singular()

template<Unsigned Word = usize>

constexpr double gf2::BitMatrix< Word >::probability_singular ( usize n )

inlinestaticconstexpr

Class method that returns the probability that a square n x n bit-matrix is singular if each element is chosen independently and uniformly at random by flips of a fair coin.

For large n, the value is 71% and that holds for n as low as 10.

Panics

This method panics if n is 0 – based on the assumption that querying the probability of a 0 x 0 bit-matrix being invertible is an upstream error somewhere

Example

auto p = BitMatrix<>::probability_singular(10);
assert(abs(p - 0.711) < 1e-3);

random()

template<Unsigned Word = usize>

BitMatrix gf2::BitMatrix< Word >::random ( usize m, usize n, double p = 0.5, std::uint64_t seed = 0 )

inlinestatic

Factory method to generate a bit-matrix of size m x n where the elements are picked at random.

This is the workhorse method for generating random bit-matrices that allows one to specify the probability of each bit being 1, and also a seed for the random number generator for reproducibility. If you set the seed to 0 then computer entropy is used to seed the RNG.

The default call BitMatrix<>::random(m, n) produces a random bit-matrix with each bit being 1 with probability 0.5 and where the RNG is seeded from entropy.

Parameters

m	The number of rows in the bit-matrix to generate.
n	The number of columns in the bit-matrix to generate.
p	The probability of the elements being 1 (defaults to a fair coin, i.e. 50-50).
seed	The seed to use for the random number generator (defaults to 0, which means use entropy).

If p < 0 then the bit-matrix is all zeros, if p > 1 then the bit-matrix is all ones.

Example

std::uint64_t seed = 1234567890;
auto u = BitMatrix<>::random(3, 2, 0.5, seed);
auto v = BitMatrix<>::random(3, 2, 0.5, seed);
assert(u == v);

remove_col()

template<Unsigned Word = usize>

std::optional< BitVector< Word > > gf2::BitMatrix< Word >::remove_col ( )

inlineconstexpr

Removes a column off the right of the bit-matrix and returns it or std::nullopt if the bit-matrix is empty.

Example

auto m = BitMatrix<>::ones(3, 3);
auto col = m.remove_col();
assert_eq(col->to_string(), "111");
assert_eq(m.to_compact_binary_string(), "11 11 11");

remove_row()

template<Unsigned Word = usize>

std::optional< BitVector< Word > > gf2::BitMatrix< Word >::remove_row ( )

inlineconstexpr

Removes a row off the end of the bit-matrix and returns it or std::nullopt if the bit-matrix is empty.

Example

auto m = BitMatrix<>::ones(3, 3);
auto row = m.remove_row();
assert_eq(row->to_string(), "111");
assert_eq(m.to_compact_binary_string(), "111 111");

remove_rows()

template<Unsigned Word = usize>

std::optional< BitMatrix< Word > > gf2::BitMatrix< Word >::remove_rows ( usize k )

inlineconstexpr

Removes k rows off the end of the bit-matrix and returns them as a new bit-matrix or std::nullopt if the bit-matrix has fewer than k rows.

Example

auto m = BitMatrix<>::ones(3, 3);
auto popped = m.remove_rows(2);
assert_eq(popped->to_compact_binary_string(), "111 111");
assert_eq(m.to_compact_binary_string(), "111");

replace_sub_matrix()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::replace_sub_matrix ( usize top, usize left, BitMatrix< Word > const & src )

inlineconstexpr

Replaces the sub-matrix starting at row top and column left with a copy of the sub-matrix src.

Panics

Panics if src does not fit within this bit-matrix starting at row top and column left.

Example

auto m = BitMatrix<>::identity(5);
m.replace_sub_matrix(1, 1, BitMatrix<>::ones(3, 3));
assert_eq(m.to_compact_binary_string(), "10000 01110 01110 01110 00001");

resize()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::resize ( usize r, usize c )

inlineconstexpr

Resize the bit-matrix to r rows and c columns.

Parameters

r	The new number of rows – if r < rows() then we lose the excess rows.
c	The new number of columns – if c < cols() then we lose the excess columns.

Any added elements are set to 0.

Example

BitMatrix m;
m.resize(10, 10);
assert_eq(m.rows(), 10);
assert_eq(m.cols(), 10);
m.resize(3, 7);
assert_eq(m.rows(), 3);
assert_eq(m.cols(), 7);
m.resize(0, 10);
assert_eq(m.rows(), 0);
assert_eq(m.cols(), 0);

right_rotation()

template<Unsigned Word = usize>

BitMatrix gf2::BitMatrix< Word >::right_rotation ( usize n, usize p )

inlinestatic

Constructs the n x n rotate-right by p places matrix.

If the bit-matrix is multiplied by a bit-vector, the result is the bit-vector rotated right by p places.

Example

auto m = BitMatrix<>::right_rotation(5, 2);
auto v = BitVector<>::from_binary_string("11100").value();
assert_eq(dot(m, v).to_string(), "10011");

right_shift()

template<Unsigned Word = usize>

BitMatrix gf2::BitMatrix< Word >::right_shift ( usize n, usize p )

inlinestatic

Constructs the n x n shift-right by p places BitMatrix.

If the bit-matrix is multiplied by a bit-vector, the result is the bit-vector shifted right by p places.

Example

auto m = BitMatrix<>::right_shift(5, 2);
auto v = BitVector<>::ones(5);
assert_eq(dot(m, v).to_string(), "00111");

row() [1/2]

template<Unsigned Word = usize>

row_type & gf2::BitMatrix< Word >::row ( usize r )

inlineconstexpr

Returns a read-write reference to the row at index r.

Panics

In debug mode, this method will panic if r is out of bounds.

Example

auto m = BitMatrix<>::identity(3);
m.row(0).set(1);
assert_eq(m.row(0).to_binary_string(), "110");
assert_eq(m.row(1).to_binary_string(), "010");
assert_eq(m.row(2).to_binary_string(), "001");

row() [2/2]

template<Unsigned Word = usize>

const row_type & gf2::BitMatrix< Word >::row ( usize r ) const

inlineconstexpr

Returns a read-only reference to the row at index r.

Panics

In debug mode, this method will panic if r is out of bounds.

Example

auto m = BitMatrix<>::identity(3);
assert_eq(m.row(0).to_binary_string(), "100");
assert_eq(m.row(1).to_binary_string(), "010");
assert_eq(m.row(2).to_binary_string(), "001");

seeded_random() [1/2]

template<Unsigned Word = usize>

BitMatrix gf2::BitMatrix< Word >::seeded_random ( usize m, std::uint64_t seed )

inlinestatic

Factory method to generate a square bit-matrix of size m x m where the elements are from independent fair coin flips generated from an RNG seeded with the given seed.

This allows one to have reproducible random square bit-matrices, which is useful for testing and debugging.

Parameters

m	The number of rows & columns in the bit-matrix to generate.
seed	The seed to use for the random number generator (if you set this to 0 then entropy is used).

If p < 0 then the bit-matrix is all zeros, if p > 1 then the bit-matrix is all ones.

Example

std::uint64_t seed = 1234567890;
auto u = BitMatrix<>::seeded_random(3, seed);
auto v = BitMatrix<>::seeded_random(3, seed);
assert(u == v);

seeded_random() [2/2]

template<Unsigned Word = usize>

BitMatrix gf2::BitMatrix< Word >::seeded_random ( usize m, usize n, std::uint64_t seed )

inlinestatic

Factory method to generate a bit-matrix of size m x n where the elements are from independent fair coin flips generated from an RNG seeded with the given seed.

This allows one to have reproducible random bit-vectors, which is useful for testing and debugging.

Parameters

m	The number of rows in the bit-matrix to generate.
n	The number of columns in the bit-matrix to generate.
seed	The seed to use for the random number generator (if you set this to 0 then entropy is used).

If p < 0 then the bit-matrix is all zeros, if p > 1 then the bit-matrix is all ones.

Example

std::uint64_t seed = 1234567890;
auto u = BitMatrix<>::seeded_random(3, 2, seed);
auto v = BitMatrix<>::seeded_random(3, 2, seed);
assert(u == v);

set()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::set ( usize r, usize c, bool val = true )

inlineconstexpr

Sets the bit at row r and column c to the bool value val. The default is to set the bit to true.

Panics

In debug mode, this method will panic if r or c is out of bounds.

Example

auto m = BitMatrix<>::zero(3);
m.set(0, 0);
assert_eq(m.get(0, 0), true);

set_all()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::set_all ( bool value = true )

inlineconstexpr

Sets all the elements of the bit-matrix to the specified boolean value.

By default, all bits are set to true.

Example

auto m = BitMatrix<>::zero(3);
m.set_all();
assert_eq(m.to_compact_binary_string(), "111 111 111");

set_diagonal()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::set_diagonal ( bool val = true )

inlineconstexpr

Sets the main diagonal of a square bit-matrix to the boolean value val.

Panics

In debug mode, this method will panic if the bit-matrix is not square.

Example

auto m = BitMatrix<>::zero(3);
m.set_diagonal();
assert_eq(m.to_compact_binary_string(), "100 010 001");

set_sub_diagonal()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::set_sub_diagonal ( usize d, bool val = true )

inlineconstexpr

Sets the elements on sub-diagonal d of a square bit-matrix to the boolean value val.

Here d = 0 is the main diagonal and d = 1 is the first sub-diagonal etc.

Panics

In debug mode, this method will panic if the bit-matrix is not square.

Example

auto m = BitMatrix<>::zero(5);
m.set_sub_diagonal(1);
assert_eq(m.to_compact_binary_string(), "00000 10000 01000 00100 00010");

set_super_diagonal()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::set_super_diagonal ( usize d, bool val = true )

inlineconstexpr

Sets the elements on super-diagonal d of a square bit-matrix to the boolean value val.

Here d = 0 is the main diagonal and d = 1 is the first super-diagonal etc.

Panics

In debug mode, this method will panic if the bit-matrix is not square.

Example

auto m = BitMatrix<>::zero(5);
m.set_super_diagonal(1);
assert_eq(m.to_compact_binary_string(), "01000 00100 00010 00001 00000");

solver_for()

template<Unsigned Word = usize>

template<BitStore Rhs>
requires std::same_as<typename Rhs::word_type, Word>

auto gf2::BitMatrix< Word >::solver_for ( Rhs const & b ) const

inline

Returns the Gaussian elimination solver for this bit-matrix and the passed r.h.s. vector b.

Example

auto A = BitMatrix<>::ones(3, 3);
auto b = BitVector<>::ones(3);
auto solver = A.solver_for(b);
assert_eq(solver.rank(), 1);
assert_eq(solver.free_count(), 2);
assert_eq(solver.solution_count(), 4);
assert_eq(solver.is_underdetermined(), true);
assert_eq(solver.is_consistent(), true);

strictly_lower()

template<Unsigned Word = usize>

BitMatrix gf2::BitMatrix< Word >::strictly_lower ( ) const

inlineconstexpr

Returns an independent clone of the strictly lower triangular part of the bit-matrix.

This is the same as lower() but with the diagonal reset to zero.

Example

auto m = BitMatrix<>::ones(3, 3);
auto sub_m = m.strictly_lower();
assert_eq(sub_m.to_compact_binary_string(), "000 100 110");

strictly_upper()

template<Unsigned Word = usize>

BitMatrix gf2::BitMatrix< Word >::strictly_upper ( ) const

inlineconstexpr

Returns an independent clone of the strictly upper triangular part of the bit-matrix.

This is the same as lower() but with the diagonal reset to zero.

Example

auto m = BitMatrix<>::ones(3, 3);
auto sub_m = m.strictly_upper();
assert_eq(sub_m.to_compact_binary_string(), "011 001 000");

sub_matrix()

template<Unsigned Word = usize>

BitMatrix gf2::BitMatrix< Word >::sub_matrix ( usize r_start, usize r_end, usize c_start, usize c_end ) const

inlineconstexpr

Returns an independent clone of the sub-matrix delimited by the given row and column ranges.

The ranges are half open [r_start, r_end) X [c_start, c_end) where r is for rows and c for columns.

Panics

Panics if the bit-matrix has incompatible dimensions with the requested sub-matrix.

Example

auto m = BitMatrix<>::identity(5);
auto sub1 = m.sub_matrix(1, 4, 1, 4);
assert_eq(sub1.to_compact_binary_string(), "100 010 001");
auto sub2 = m.sub_matrix(1, 1, 1, 1);
assert_eq(sub2.to_compact_binary_string(), "");

swap_cols()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::swap_cols ( usize i, usize j )

inlineconstexpr

Swaps columns i and j of the bit-matrix.

Panics

In debug mode, this method will panic if either of the indices is out of bounds.

Example

auto m = BitMatrix<>::identity(3);
m.swap_cols(0, 1);
assert_eq(m.to_compact_binary_string(), "010 100 001");

swap_rows()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::swap_rows ( usize i, usize j )

inlineconstexpr

Swaps rows i and j of the bit-matrix.

Panics

In debug mode, this method will panic if either of the indices is out of bounds.

Example

auto m = BitMatrix<>::identity(3);
m.swap_rows(0, 1);
assert_eq(m.to_compact_binary_string(), "010 100 001");

to_binary_string()

template<Unsigned Word = usize>

std::string gf2::BitMatrix< Word >::to_binary_string ( std::string_view row_sep = "\n", std::string_view bit_sep = "", std::string_view row_prefix = "", std::string_view row_suffix = "" ) const

inline

Returns a configurable binary string representation for this bit-matrix.

Parameters

row_sep	What we use to separate the rows (defaults to a "\n").
bit_sep	What we use to separate the bit elements in the rows (defaults to "").
row_prefix	Added to the left of each row (defaults to "").
row_suffix	Added to the right of each row (defaults to "").

The default prints each row as 0's and 1's without any formatting, and separates the rows with newlines.

Example

auto I = BitMatrix<>::identity(4);
assert_eq(I.to_binary_string(), "1000\n0100\n0010\n0001");

to_compact_binary_string()

template<Unsigned Word = usize>

std::string gf2::BitMatrix< Word >::to_compact_binary_string ( ) const

inline

Returns a one-line minimal binary string representation for this bit-matrix.

Each row is shown as 0's and 1's without any formatting, and separates the rows with a single space.

Example

auto I = BitMatrix<>::identity(4);
assert_eq(I.to_compact_binary_string(), "1000 0100 0010 0001");

to_compact_hex_string()

template<Unsigned Word = usize>

std::string gf2::BitMatrix< Word >::to_compact_hex_string ( ) const

inline

Returns a compact "hex" string representation of the bit-matrix.

Empty bit-matrices are represented as the empty string.

Each row in a non-empty bit-matrix is a string of hex chars without any spaces, commas, or other formatting. The rows are separated by a single space.

Each row may have a two character suffix of the form ".base" where base is one of 2, 4 or 8.
All hex characters encode 4 bits: "0X0" -> 0b0000, "0X1" -> 0b0001, ..., "0XF" -> 0b1111.
The three possible ".base" suffixes allow for bit-vectors whose length is not a multiple of 4.

• 0X1 is the hex representation of the bit-vector 0001 => length 4.
• 0X1.8 is the hex representation of the bit-vector 001 => length 3.
• 0X1.4 is the hex representation of the bit-vector 01 => length 2.
• 0X1.2 is the hex representation of the bit-vector 1 => length 1.

Example

BitMatrix m0;
assert_eq(m0.to_compact_hex_string(), "");
auto m1 = BitMatrix<>::zero(4);
m1.set_all();
assert_eq(m1.to_compact_hex_string(), "F F F F");
auto m2 = BitMatrix<>::zero(5);
m2.flip_all();
assert_eq(m2.to_compact_hex_string(), "F1.2 F1.2 F1.2 F1.2 F1.2");

to_echelon_form()

template<Unsigned Word = usize>

BitVector< Word > gf2::BitMatrix< Word >::to_echelon_form ( )

inline

Transforms an arbitrary shaped, non-empty, bit-matrix to row-echelon form (in-place).

The method returns a bit-vector that shows which columns have a "pivot" (a non-zero on or below the diagonal). The matrix rank is the number of set bits in that pivot bit-vector.

A bit-matrix is in echelon form if the first 1 in any row is to the right of the first 1 in the preceding row. It is a generalization of an upper triangular form – the result is a matrix with a "staircase" shape.

The transformation is Gaussian elimination. Any all zero rows are moved to the bottom of the matrix. The echelon form is not unique.

Panics

This method will panic if the bit-matrix is empty.

Example

auto m = BitMatrix<>::identity(3);
m.set(2, 1, false);
auto has_pivot = m.to_echelon_form();
assert_eq(has_pivot.to_string(), "111");
assert_eq(m.to_compact_binary_string(), "100 010 001");

to_hex_string()

template<Unsigned Word = usize>

std::string gf2::BitMatrix< Word >::to_hex_string ( std::string_view row_sep = "\n" ) const

inline

"Returns the "hex" string representation of the bit-matrix

Empty bit-matrices are represented as the empty string.

Each row in a non-empty bit-matrix is a string of hex chars without any spaces, commas, or other formatting. By default, the rows are separated by newlines.

Each row may have a two character suffix of the form ".base" where base is one of 2, 4 or 8.
All hex characters encode 4 bits: "0X0" -> 0b0000, "0X1" -> 0b0001, ..., "0XF" -> 0b1111.
The three possible ".base" suffixes allow for bit-vectors whose length is not a multiple of 4.

• 0X1 is the hex representation of the bit-vector 0001 => length 4.
• 0X1.8 is the hex representation of the bit-vector 001 => length 3.
• 0X1.4 is the hex representation of the bit-vector 01 => length 2.
• 0X1.2 is the hex representation of the bit-vector 1 => length 1.

Example

BitMatrix m0;
assert_eq(m0.to_hex_string(), "");
auto m1 = BitMatrix<>::zero(4);
m1.set_all();
assert_eq(m1.to_hex_string(), "F\nF\nF\nF");
auto m2 = BitMatrix<>::zero(5);
m2.flip_all();
assert_eq(m2.to_hex_string(), "F1.2\nF1.2\nF1.2\nF1.2\nF1.2");

to_pretty_string()

template<Unsigned Word = usize>

std::string gf2::BitMatrix< Word >::to_pretty_string ( ) const

inline

Returns the default pretty string representation for this bit-matrix.

Each row is shown as 0's and 1's with a space between each element. The rows are delimited by a light vertical bar on the left and right. The rows are separated by newlines.

Example

auto I = BitMatrix<>::identity(3);
auto bar = "\u2502";
auto expected = std::format("{0}1 0 0{0}\n{0}0 1 0{0}\n{0}0 0 1{0}", bar);
assert_eq(I.to_pretty_string(), expected);

to_reduced_echelon_form()

template<Unsigned Word = usize>

BitVector< Word > gf2::BitMatrix< Word >::to_reduced_echelon_form ( )

inline

Transforms the bit-matrix to reduced row-echelon form (in-place).

The method returns a bit-vector that shows which columns have a "pivot" (a non-zero on or below the diagonal). The matrix rank is the number of set bits in that bit-vector.

A bit-matrix is in reduced echelon form if it is in echelon form with at most one 1 in each column. The reduced echelon form is unique.

Panics

This method will panic if the bit-matrix is empty.

Example

auto m = BitMatrix<>::identity(3);
m.set(2, 1, false);
auto pivots = m.to_reduced_echelon_form();
assert_eq(pivots.to_string(), "111");
assert_eq(m.to_compact_binary_string(), "100 010 001");

to_string()

template<Unsigned Word = usize>

std::string gf2::BitMatrix< Word >::to_string ( ) const

inline

Returns the default string representation for this bit-matrix.

Each row is shown as 0's and 1's without any formatting, and separates the rows with a newline.

Example

auto I = BitMatrix<>::identity(4);
assert_eq(I.to_string(), "1000\n0100\n0010\n0001");

to_the()

template<Unsigned Word = usize>

BitMatrix gf2::BitMatrix< Word >::to_the ( usize n, bool n_is_log2 = false ) const

inlineconstexpr

Returns a new bit-matrix that is this one raised to some power n or 2^n.

We efficiently compute M^e by using a square and multiply algorithm where by default e = n. If the second argument n_is_log2 = true then we consider e = 2^n instead.

Panics

This method will panic if the bit-matrix is not square.

Example

auto m = BitMatrix<>::random(100, 100);
auto p1 = m.to_the(3);
auto o1 = m * m * m;
assert_eq(p1, o1);
auto p2 = m.to_the(2, true);
auto o2 = m * o1;
assert_eq(p2, o2);

trace()

template<Unsigned Word = usize>

bool gf2::BitMatrix< Word >::trace ( ) const

inlineconstexpr

Returns the "sum" of the main diagonal elements of the bit-matrix.

Returns the "sum" of the main diagonal elements of the bit-matrix.

Panics

In debug mode, this method will panic if the bit-matrix is not square.

Example

auto m1 = BitMatrix<>::identity(3);
assert_eq(m1.trace(), true);
auto m2 = BitMatrix<>::zero(4);
assert_eq(m2.trace(), false);

transpose()

template<Unsigned Word = usize>

void gf2::BitMatrix< Word >::transpose ( )

inlineconstexpr

Transposes a square bit-matrix in place.

Panics

This method will panic if the bit-matrix is not square.

Example

auto m = BitMatrix<>::zero(3);
m.row(0).set_all();
assert_eq(m.to_compact_binary_string(), "111 000 000");
m.transpose();
assert_eq(m.to_compact_binary_string(), "100 100 100");

transposed()

template<Unsigned Word = usize>

BitMatrix gf2::BitMatrix< Word >::transposed ( ) const

inlineconstexpr

Returns a new bit-matrix that is the transpose of this one.

Note: This method isn't particularly efficient as it works by iterating over all elements of the bit-matrix.

Example

auto m = BitMatrix<>::zeros(3, 2);
m.row(0).set_all();
assert_eq(m.to_compact_binary_string(), "11 00 00");
auto n = m.transposed();
assert_eq(n.to_compact_binary_string(), "100 100");

unit_lower()

template<Unsigned Word = usize>

BitMatrix gf2::BitMatrix< Word >::unit_lower ( ) const

inlineconstexpr

Returns an independent clone of the unit lower triangular part of the bit-matrix.

This is the same as lower() but with the diagonal set to one.

Example

auto m = BitMatrix<>::zeros(3, 3);
auto sub_m = m.unit_lower();
assert_eq(sub_m.to_compact_binary_string(), "100 010 001");

unit_upper()

template<Unsigned Word = usize>

BitMatrix gf2::BitMatrix< Word >::unit_upper ( ) const

inlineconstexpr

Returns an independent clone of the unit upper triangular part of the bit-matrix.

This is the same as upper() but with the diagonal set to one.

Example

auto m = BitMatrix<>::zeros(3, 3);
auto sub_m = m.unit_upper();
assert_eq(sub_m.to_compact_binary_string(), "100 010 001");

upper()

template<Unsigned Word = usize>

BitMatrix gf2::BitMatrix< Word >::upper ( ) const

inlineconstexpr

Returns an independent clone of the upper triangular part of the bit-matrix.

Example

auto m = BitMatrix<>::ones(3, 3);
auto sub_m = m.upper();
assert_eq(sub_m.to_compact_binary_string(), "111 011 001");

x_for()

template<Unsigned Word = usize>

template<BitStore Rhs>
requires std::same_as<typename Rhs::word_type, Word>

auto gf2::BitMatrix< Word >::x_for ( Rhs const & b ) const

inline

Returns a solution to the system of linear equations A.x_ = b or std::nullopt if there are none.

Example

auto A = BitMatrix<>::identity(3);
auto b = BitVector<>::ones(3);
auto x = A.x_for(b).value();
assert_eq(x.to_string(), "111");

zero()

template<Unsigned Word = usize>

constexpr BitMatrix gf2::BitMatrix< Word >::zero ( usize m )

inlinestaticconstexpr

Factory method to create the m x m square "zero" bit-matrix.

Example

auto m = BitMatrix<>::zero(3);
assert_eq(m.to_compact_binary_string(), "000 000 000");

zeros() [1/2]

template<Unsigned Word = usize>

constexpr BitMatrix gf2::BitMatrix< Word >::zeros ( usize m )

inlinestaticconstexpr

Factory method to create the m x m square bit-matrix with all the elements set to 0.

Example

auto m = BitMatrix<>::zeros(3);
assert_eq(m.to_compact_binary_string(), "000 000 000");

zeros() [2/2]

template<Unsigned Word = usize>

constexpr BitMatrix gf2::BitMatrix< Word >::zeros ( usize m, usize n )

inlinestaticconstexpr

Factory method to create the m x n zero bit-matrix with all the elements set to 0.

Example

auto m = BitMatrix<>::zeros(3, 4);
assert_eq(m.to_compact_binary_string(), "0000 0000 0000");

Friends And Related Symbol Documentation

operator==

template<Unsigned Word = usize>

bool operator== ( BitMatrix< Word > const & lhs, BitMatrix< Word > const & rhs )

friend

Equality operator checks that any pair of bit-matrices are equal in content.

Example

auto p = BitMatrix<>::identity(3);
auto q = BitMatrix<>::identity(3);
assert(p == q);