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 <BitMat.h>

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

Public Member Functions
Constructors
constexpr	BitMat ()
	The default constructor creates an empty bit-matrix with no rows or columns.
constexpr	BitMat (usize n)
	Constructs the n x n square bit-matrix with all the elements set to 0.
constexpr	BitMat (usize m, usize n)
	Constructs the m x n bit-matrix with all the elements set to 0.
constexpr	BitMat (const std::vector< row_type > &rows)
	Construct a bit-matrix by copying a given set of rows which can be any BitStore subclass.
constexpr	BitMat (std::vector< BitVec< Word > > &&rows)
	Construct a bit-matrix by moving the given rows.
Simple 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?
Special Shape Queries
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 BitVec< 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 BitMat.
Appending Rows and Columns
constexpr BitMat &	append_row (const BitVec< Word > &row)
	Appends a single row onto the end of the bit-matrix by copying it.
constexpr BitMat &	append_row (BitVec< Word > &&row)
	Appends a single row onto the end of the bit-matrix by moving it.
constexpr BitMat &	append_rows (const BitMat< Word > &src)
	Appends all the rows from the src bit-matrix onto the end of this bit-matrix by copying them.
constexpr BitMat &	append_rows (BitMat< Word > &&src)
	Appends all the rows from the src bit-matrix onto the end of this bit-matrix by moving them.
template<typename Store> requires store_word_is<Store, Word>
constexpr BitMat &	append_col (const BitStore< Store > &col)
	Appends a single column col onto the right of the bit-matrix so M -> M\|col.
constexpr BitMat &	append_cols (const BitMat< Word > &src)
	Appends all the columns from the src bit-matrix onto the right of this bit-matrix so M -> M\|src.
Removing Rows and Columns
constexpr std::optional< BitVec< 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< BitMat< 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< BitVec< 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 BitMat	sub (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 (usize top, usize left, const BitMat< Word > &src)
	Replaces the sub-matrix starting at row top and column left with a copy of the sub-matrix src.
Triangular Sub-Matrices
constexpr BitMat	lower () const
	Returns an independent clone of the lower triangular part of the bit-matrix.
constexpr BitMat	upper () const
	Returns an independent clone of the upper triangular part of the bit-matrix.
constexpr BitMat	strictly_lower () const
	Returns an independent clone of the strictly lower triangular part of the bit-matrix.
constexpr BitMat	strictly_upper () const
	Returns an independent clone of the strictly upper triangular part of the bit-matrix.
constexpr BitMat	unit_lower () const
	Returns an independent clone of the unit lower triangular part of the bit-matrix.
constexpr BitMat	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 BitMat	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 BitMat	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
BitVec< Word >	to_echelon_form ()
	Transforms an arbitrary shaped, non-empty, bit-matrix to row-echelon form (in-place).
BitVec< 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 Linear Equations
template<typename Store> requires store_word_is<Store, Word>
auto	solver_for (const BitStore< Store > &b) const
	Returns the Gaussian elimination solver for this bit-matrix and the passed r.h.s. vector b.
template<typename Store> requires store_word_is<Store, Word>
auto	x_for (const BitStore< Store > &b) const
	Returns a solution to the system of linear equations A.x_ = b or std::nullopt if there are none. inconsistent.
Bitwise Operations
constexpr void	operator^= (const BitMat< Word > &rhs)
	In-place XOR with a bit-matrix rhs.
constexpr void	operator&= (const BitMat< Word > &rhs)
	In-place AND with a bit-matrix rhs.
constexpr void	operator\|= (const BitMat< Word > &rhs)
	In-place OR with a bit-matrix rhs.
constexpr auto	operator^ (const BitMat< Word > &rhs) const
	TheXOR of this with a bit-matrix rhs returning a new bit-matrix.
constexpr auto	operator& (const BitMat< Word > &rhs) const
	TheAND of this with a bit-matrix rhs returning a new bit-matrix.
constexpr auto	operator\| (const BitMat< Word > &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+= (const BitMat< Word > &rhs)
	In-place addition with a bit-matrix rhs – in GF(2) addition is the same as XOR.
constexpr void	operator-= (const BitMat< Word > &rhs)
	In-place difference with a bit-matrix rhs – in GF(2) subtraction is the same as XOR.
constexpr auto	operator+ (const BitMat< Word > &rhs) const
	Returns a new bit-matrix that is this + rhs which is this ^ rhs in GF(2).
constexpr auto	operator- (const BitMat< Word > &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 BitMat	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 BitMat	zeros (usize m)
	Factory method to create the m x m square bit-matrix with all the elements set to 0.
static constexpr BitMat	ones (usize m, usize n)
	Factory method to create the m x n bit-matrix with all the elements set to 1.
static constexpr BitMat	ones (usize m)
	Factory method to create the m x m square bit-matrix with all the elements set to 1.
static constexpr BitMat	alternating (usize m, usize n)
	Factory method to create the m x n bit-matrix with alternating elements.
static constexpr BitMat	alternating (usize m)
	Factory method to create the m x m square bit-matrix with alternating elements.
static constexpr BitMat	outer_product (const BitVec< Word > &u, const BitVec< Word > &v)
	Factory method to create the m x n bit-matrix from the outer product of the given bit-vectors.
static constexpr BitMat	outer_sum (const BitVec< Word > &u, const BitVec< Word > &v)
	Factory method to create the m x n bit-matrix from the outer sum of the given bit-vectors.
static constexpr BitMat	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 BitMat	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 BitMat	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 BitMat	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 BitMat	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 BitMat	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.
Special BitMat Constructors
static constexpr BitMat	zero (usize m)
	Factory method to create the m x m square "zero" bit-matrix.
static constexpr BitMat	identity (usize m)
	Factory method to create the m x m identity bit-matrix.
template<typename Rhs>
static constexpr BitMat	companion (const BitStore< Rhs > &top_row)
	Constructs a square companion BitMat with a copy of the given top row and a sub-diagonal of 1s.
static constexpr BitMat	left_shift (usize n, usize p)
	Constructs the n x n shift-left by p places BitMat.
static BitMat	right_shift (usize n, usize p)
	Constructs the n x n shift-right by p places BitMat.
static BitMat	left_rotation (usize n, usize p)
	Constructs the n x n rotate-left by p places matrix.
static BitMat	right_rotation (usize n, usize p)
	Constructs the n x n rotate-right by p places matrix.
Reshaping Constructors
static std::optional< BitMat >	from_vector_of_rows (const BitVec< Word > &v, usize r)
	Factory method to reshape a bit-vector v that is assumed to a sequence of r rows into a bit-matrix.
static std::optional< BitMat >	from_vector_of_cols (const BitVec< Word > &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< BitMat >	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< BitMat >	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
BitPoly< Word >	characteristic_polynomial () const
	Returns the characteristic polynomial of any square bit-matrix as a gf2::BitPoly.
std::vector< BitVec< Word > >	frobenius_form () const
	Returns the Frobenius form of this bit-matrix in compact top-row only form.
static BitPoly< Word >	frobenius_matrix_characteristic_polynomial (const std::vector< BitVec< Word > > &top_rows)
	Class method that returns the characteristic polynomial of a Frobenius matrix as a gf2::BitPoly.
static BitPoly< Word >	companion_matrix_characteristic_polynomial (const BitVec< Word > &top_row)
	Class method to return the characteristic polynomial of a companion matrix as a gf2::BitPoly.

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

Detailed Description

template<unsigned_word Word = usize>
class gf2::BitMat< 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: These 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

◆ BitMat() [1/5]

template<unsigned_word Word = usize>

gf2::BitMat< Word >::BitMat ( )

inlineconstexpr

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

Example

BitMat m;

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

gf2::BitMat::to_compact_binary_string

std::string to_compact_binary_string() const

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

Definition BitMat.h:2281

gf2::BitMat::BitMat

constexpr BitMat()

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

Definition BitMat.h:54

◆ BitMat() [2/5]

template<unsigned_word Word = usize>

gf2::BitMat< Word >::BitMat ( 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

BitMat m{3};

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

◆ BitMat() [3/5]

template<unsigned_word Word = usize>

gf2::BitMat< Word >::BitMat	(	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

BitMat m{3, 4};

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

◆ BitMat() [4/5]

template<unsigned_word Word = usize>

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

inlineconstexpr

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

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

Example

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

◆ BitMat() [5/5]

template<unsigned_word Word = usize>

gf2::BitMat< Word >::BitMat ( std::vector< BitVec< 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.

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

Example

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

Member Function Documentation

◆ add_identity()

template<unsigned_word Word = usize>

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

inlineconstexpr

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

Note: In debug mode, this panics if the bit-matrix is not square.

Example

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

◆ all()

template<unsigned_word Word = usize>

bool gf2::BitMat< 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 = BitMat<>::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 Word = usize>

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

inlinestaticconstexpr

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

Example

auto m = BitMat<>::alternating(3);

assert_eq(m.to_compact_binary_string(), "101 010 101");

gf2::BitMat::alternating

static constexpr BitMat alternating(usize m, usize n)

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

Definition BitMat.h:163

◆ alternating() [2/2]

template<unsigned_word Word = usize>

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

inlinestaticconstexpr

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

Example

auto m = BitMat<>::alternating(3, 4);

assert_eq(m.to_compact_binary_string(), "1010 0101 1010");

◆ any()

template<unsigned_word Word = usize>

bool gf2::BitMat< 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 = BitMat<>::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 Word = usize>

template<typename Store>
requires store_word_is<Store, Word>

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

inlineconstexpr

Appends a single column col onto the right of the bit-matrix so M -> M|col.

Returns a reference to the current object for chaining.

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

Example

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

◆ append_cols()

template<unsigned_word Word = usize>

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

inlineconstexpr

Appends all the columns from the src bit-matrix onto the right of this bit-matrix so M -> M|src.

Returns a reference to the current object for chaining.

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

Example

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

◆ append_row() [1/2]

template<unsigned_word Word = usize>

BitMat & gf2::BitMat< Word >::append_row ( BitVec< Word > && row )

inlineconstexpr

Appends a single row onto the end of the bit-matrix by moving it.

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.

Returns a reference to the current object for chaining.

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

Example

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

◆ append_row() [2/2]

template<unsigned_word Word = usize>

BitMat & gf2::BitMat< Word >::append_row ( const BitVec< Word > & row )

inlineconstexpr

Appends a single row onto the end of the bit-matrix by copying it.

Returns a reference to the current object for chaining.

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

Example

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

◆ append_rows() [1/2]

template<unsigned_word Word = usize>

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

inlineconstexpr

Appends all the rows from the src bit-matrix onto the end of this bit-matrix by moving them.

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.

Returns a reference to the current object for chaining.

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

Example

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

◆ append_rows() [2/2]

template<unsigned_word Word = usize>

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

inlineconstexpr

Appends all the rows from the src bit-matrix onto the end of this bit-matrix by copying them.

Returns a reference to the current object for chaining.

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

Example

auto m = BitMat<>::zero(3);
auto src = BitMat<>::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 Word = usize>

BitMat gf2::BitMat< 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 = BitMat<>::biased_random(10, 0.3);

assert_eq(u.size(), 100);

gf2::BitMat::biased_random

static BitMat 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 co...

Definition BitMat.h:341

◆ biased_random() [2/2]

template<unsigned_word Word = usize>

BitMat gf2::BitMat< 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 = BitMat<>::biased_random(10, 7, 0.3);
auto v = BitMat<>::biased_random(10, 7, 0.3);
assert_eq(u.size(), v.size());

◆ characteristic_polynomial()

template<unsigned_word Word = usize>

BitPoly< Word > gf2::BitMat< Word >::characteristic_polynomial ( ) const

inline

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

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.

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

Example

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

◆ clear()

template<unsigned_word Word = usize>

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

inlineconstexpr

Removes all the elements from the bit-matrix.

Example

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

◆ col()

template<unsigned_word Word = usize>

BitVec< Word > gf2::BitMat< 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 BitMat columns!

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

Example

auto m = BitMat<>::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 Word = usize>

template<typename Rhs>

constexpr BitMat gf2::BitMat< Word >::companion ( const BitStore< Rhs > & top_row )

inlinestaticconstexpr

Constructs a square companion BitMat 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 BitMat. The rest of the BitMat is initialized to zero and the sub-diagonal is set to 1s.

Example

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

◆ companion_matrix_characteristic_polynomial()

template<unsigned_word Word = usize>

BitPoly< Word > gf2::BitMat< Word >::companion_matrix_characteristic_polynomial ( const BitVec< Word > & top_row )

inlinestatic

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

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 = BitVec<>::from_binary_string("101").value();

assert_eq(BitMat<>::companion_matrix_characteristic_polynomial(top_row).to_string(), "1 + x^2 + x^3");

gf2::BitMat::to_string

std::string to_string() const

Returns the default string representation for this bit-matrix.

Definition BitMat.h:2292

gf2::BitMat::companion_matrix_characteristic_polynomial

static BitPoly< Word > companion_matrix_characteristic_polynomial(const BitVec< Word > &top_row)

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

Definition BitMat.h:1992

gf2::BitVec::from_binary_string

static std::optional< BitVec > from_binary_string(std::string_view sv, bool no_punctuation=false)

Factory method to construct a bit-vector from a binary string, returning std::nullopt on failure.

Definition BitVec.h:439

◆ count_ones()

template<unsigned_word Word = usize>

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

inlineconstexpr

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

Example

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

◆ count_ones_on_diagonal()

template<unsigned_word Word = usize>

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

inlineconstexpr

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

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

Example

auto m = BitMat<>::identity(3);

assert_eq(m.count_ones_on_diagonal(), 3);

◆ count_zeros()

template<unsigned_word Word = usize>

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

inlineconstexpr

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

Example

auto m = BitMat<>::identity(3);

assert_eq(m.count_zeros(), 6);

◆ flip()

template<unsigned_word Word = usize>

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

inlineconstexpr

Flips the bit at row r and column c.

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

Example

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

◆ flip_all()

template<unsigned_word Word = usize>

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

inlineconstexpr

Flips all the elements of the bit-matrix.

Example

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

◆ flip_diagonal()

template<unsigned_word Word = usize>

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

inlineconstexpr

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

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

Example

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

◆ flip_sub_diagonal()

template<unsigned_word Word = usize>

void gf2::BitMat< 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.

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

Example

auto m = BitMat<>::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 Word = usize>

void gf2::BitMat< 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.

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

Example

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

◆ frobenius_form()

template<unsigned_word Word = usize>

std::vector< BitVec< Word > > gf2::BitMat< 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.

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

◆ frobenius_matrix_characteristic_polynomial()

template<unsigned_word Word = usize>

BitPoly< Word > gf2::BitMat< Word >::frobenius_matrix_characteristic_polynomial ( const std::vector< BitVec< Word > > & top_rows )

inlinestatic

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

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 Word = usize>

constexpr BitMat gf2::BitMat< 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 = BitMat<>::from(3, 2, [](usize i, usize) { return i % 2 == 0; });

assert_eq(m.to_compact_binary_string(), "11 00 11");

gf2::BitMat::from

static constexpr BitMat from(usize m, usize n, std::invocable< usize, usize > auto f)

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

Definition BitMat.h:222

gf2::usize

std::size_t usize

Word type alias for the platform's "native"-sized unsigned integer.

Definition unsigned_word.h:41

◆ from_string()

template<unsigned_word Word = usize>

std::optional< BitMat > gf2::BitMat< 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 = BitMat<>::from_string("111   111\n111").value();
assert_eq(m1.to_compact_binary_string(), "111 111 111");
auto m2 = BitMat<>::from_string("0XAA; 0b1111_0000").value();
assert_eq(m2.to_compact_binary_string(), "10101010 11110000");
auto m3 = BitMat<>::from_string("0x7.8 000").value();
assert_eq(m3.to_compact_binary_string(), "111 000");

◆ from_vector_of_cols()

template<unsigned_word Word = usize>

std::optional< BitMat > gf2::BitMat< Word >::from_vector_of_cols	(	const BitVec< Word > &	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 = BitVec<>::ones(15);
auto m1 = BitMat<>::from_vector_of_cols(v, 3).value();
assert_eq(m1.to_compact_binary_string(), "111 111 111 111 111");
auto m2 = BitMat<>::from_vector_of_cols(v, 5).value();
assert_eq(m2.to_compact_binary_string(), "11111 11111 11111");
auto m3 = BitMat<>::from_vector_of_cols(v, 15).value();
assert_eq(m3.to_compact_binary_string(), "111111111111111");

◆ from_vector_of_rows()

template<unsigned_word Word = usize>

std::optional< BitMat > gf2::BitMat< Word >::from_vector_of_rows	(	const BitVec< Word > &	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 = BitVec<>::ones(15);
auto m1 = BitMat<>::from_vector_of_rows(v, 3).value();
assert_eq(m1.to_compact_binary_string(), "11111 11111 11111");
auto m2 = BitMat<>::from_vector_of_rows(v, 5).value();
assert_eq(m2.to_compact_binary_string(), "111 111 111 111 111");
auto m3 = BitMat<>::from_vector_of_rows(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");

◆ get()

template<unsigned_word Word = usize>

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

inlineconstexpr

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

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

Example

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

◆ identity()

template<unsigned_word Word = usize>

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

inlinestaticconstexpr

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

Example

auto m = BitMat<>::identity(3);

assert_eq(m.to_compact_binary_string(), "100 010 001");

◆ inverse()

template<unsigned_word Word = usize>

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

inline

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

Example

auto m = BitMat<>::identity(3);

assert_eq(m.inverse().value().to_compact_binary_string(), "100 010 001");

◆ is_identity()

template<unsigned_word Word = usize>

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

inlineconstexpr

Returns true if this is the identity bit-matrix.

Example

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

◆ is_square()

template<unsigned_word Word = usize>

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

inlineconstexpr

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

Example

BitMat 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 Word = usize>

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

inlineconstexpr

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

Example

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

◆ is_zero()

template<unsigned_word Word = usize>

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

inlineconstexpr

Returns true if this a square zero bit-matrix?

Example

BitMat 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 Word = usize>

BitMat gf2::BitMat< 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 = BitMat<>::left_rotation(5, 2);
auto v = BitVec<>::from_binary_string("11100").value();
assert_eq(dot(m, v).to_string(), "00111");

◆ left_shift()

template<unsigned_word Word = usize>

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

inlinestaticconstexpr

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

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

Example

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

◆ lower()

template<unsigned_word Word = usize>

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

inlineconstexpr

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

Example

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

◆ LU()

template<unsigned_word Word = usize>

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

inline

Returns the LU decomposition of the bit-matrix.

Example

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

◆ make_square()

template<unsigned_word Word = usize>

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

inlineconstexpr

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

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

Example

auto m = BitMat<>::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 Word = usize>

bool gf2::BitMat< 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 = BitMat<>::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 Word = usize>

constexpr BitMat gf2::BitMat< 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 = BitMat<>::ones(3);

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

◆ ones() [2/2]

template<unsigned_word Word = usize>

constexpr BitMat gf2::BitMat< 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 = BitMat<>::ones(3, 4);

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

◆ operator&()

template<unsigned_word Word = usize>

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

inlineconstexpr

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

Note: This methods panics if the dimensions do not match.

Example

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

◆ operator&=()

template<unsigned_word Word = usize>

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

inlineconstexpr

In-place AND with a bit-matrix rhs.

Note: This methods panics if the dimensions do not match.

Example

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

◆ operator()() [1/2]

template<unsigned_word Word = usize>

BitRef< row_type > gf2::BitMat< 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.

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

Example

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

◆ operator()() [2/2]

template<unsigned_word Word = usize>

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

inlineconstexpr

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

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

Example

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

◆ operator+()

template<unsigned_word Word = usize>

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

inlineconstexpr

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

Note: This methods panics if the dimensions do not match.

Example

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

◆ operator+=()

template<unsigned_word Word = usize>

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

inlineconstexpr

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

Note: This methods panics if the dimensions of do not match.

Example

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

◆ operator-()

template<unsigned_word Word = usize>

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

inlineconstexpr

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

Note: This methods panics if the dimensions so not match.

Example

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

◆ operator-=()

template<unsigned_word Word = usize>

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

inlineconstexpr

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

Note: This methods panics if the dimensions do not match.

Example

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

◆ operator[]() [1/2]

template<unsigned_word Word = usize>

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

inlineconstexpr

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

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

Example

auto m = BitMat<>::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 Word = usize>

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

inlineconstexpr

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

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

Example

auto m = BitMat<>::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 Word = usize>

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

inlineconstexpr

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

Note: This methods panics if the dimensions do not match.

Example

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

◆ operator^=()

template<unsigned_word Word = usize>

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

inlineconstexpr

In-place XOR with a bit-matrix rhs.

Note: This methods panics if the dimensions do not match.

Example

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

◆ operator|()

template<unsigned_word Word = usize>

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

inlineconstexpr

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

Note: This methods panics if the dimensions do not match.

Example

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

◆ operator|=()

template<unsigned_word Word = usize>

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

inlineconstexpr

In-place OR with a bit-matrix rhs.

Note: This methods panics if the dimensions do not match.

Example

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

◆ operator~()

template<unsigned_word Word = usize>

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

inlineconstexpr

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

Example

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

◆ outer_product()

template<unsigned_word Word = usize>

constexpr BitMat gf2::BitMat< Word >::outer_product	(	const BitVec< Word > &	u,
		const BitVec< Word > &	v )

inlinestaticconstexpr

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

Example

auto u = BitVec<>::from_string("101").value();
auto v = BitVec<>::from_string("110").value();
auto m = BitMat<>::outer_product(u, v);
assert_eq(m.to_compact_binary_string(), "110 000 110");

◆ outer_sum()

template<unsigned_word Word = usize>

constexpr BitMat gf2::BitMat< Word >::outer_sum	(	const BitVec< Word > &	u,
		const BitVec< Word > &	v )

inlinestaticconstexpr

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

Example

auto u = BitVec<>::from_string("101").value();
auto v = BitVec<>::from_string("110").value();
auto m = BitMat<>::outer_sum(u, v);
assert_eq(m.to_compact_binary_string(), "001 110 001");

◆ probability_invertible()

template<unsigned_word Word = usize>

constexpr double gf2::BitMat< 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.

Note: 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 = BitMat<>::probability_invertible(10);

assert(abs(p - 0.289) < 1e-3);

gf2::BitMat::probability_invertible

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 elemen...

Definition BitMat.h:1845

◆ probability_singular()

template<unsigned_word Word = usize>

constexpr double gf2::BitMat< 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.

Note: 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 = BitMat<>::probability_singular(10);

assert(abs(p - 0.711) < 1e-3);

gf2::BitMat::probability_singular

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 ...

Definition BitMat.h:1875

◆ random()

template<unsigned_word Word = usize>

BitMat gf2::BitMat< 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 BitMat<>::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).

Note: 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 = BitMat<>::random(3, 2, 0.5, seed);
auto v = BitMat<>::random(3, 2, 0.5, seed);
assert(u == v);

◆ remove_col()

template<unsigned_word Word = usize>

std::optional< BitVec< Word > > gf2::BitMat< 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 = BitMat<>::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 Word = usize>

std::optional< BitVec< Word > > gf2::BitMat< 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 = BitMat<>::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 Word = usize>

std::optional< BitMat< Word > > gf2::BitMat< 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 = BitMat<>::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()

template<unsigned_word Word = usize>

void gf2::BitMat< Word >::replace	(	usize	top,
		usize	left,
		const BitMat< Word > &	src )

inlineconstexpr

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

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

Example

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

◆ resize()

template<unsigned_word Word = usize>

void gf2::BitMat< 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

BitMat 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 Word = usize>

BitMat gf2::BitMat< 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 = BitMat<>::right_rotation(5, 2);
auto v = BitVec<>::from_binary_string("11100").value();
assert_eq(dot(m, v).to_string(), "10011");

◆ right_shift()

template<unsigned_word Word = usize>

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

inlinestatic

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

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

Example

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

◆ row() [1/2]

template<unsigned_word Word = usize>

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

inlineconstexpr

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

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

Example

auto m = BitMat<>::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 Word = usize>

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

inlineconstexpr

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

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

Example

auto m = BitMat<>::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 Word = usize>

BitMat gf2::BitMat< 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).

Note: 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 = BitMat<>::seeded_random(3, seed);
auto v = BitMat<>::seeded_random(3, seed);
assert(u == v);

◆ seeded_random() [2/2]

template<unsigned_word Word = usize>

BitMat gf2::BitMat< 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).

Note: 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 = BitMat<>::seeded_random(3, 2, seed);
auto v = BitMat<>::seeded_random(3, 2, seed);
assert(u == v);

◆ set()

template<unsigned_word Word = usize>

void gf2::BitMat< 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.

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

Example

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

◆ set_all()

template<unsigned_word Word = usize>

void gf2::BitMat< 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 = BitMat<>::zero(3);
m.set_all();
assert_eq(m.to_compact_binary_string(), "111 111 111");

◆ set_diagonal()

template<unsigned_word Word = usize>

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

inlineconstexpr

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

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

Example

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

◆ set_sub_diagonal()

template<unsigned_word Word = usize>

void gf2::BitMat< 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.

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

Example

auto m = BitMat<>::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 Word = usize>

void gf2::BitMat< 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.

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

Example

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

◆ solver_for()

template<unsigned_word Word = usize>

template<typename Store>
requires store_word_is<Store, Word>

auto gf2::BitMat< Word >::solver_for ( const BitStore< Store > & b ) const

inline

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

Example

auto A = BitMat<>::ones(3, 3);
auto b = BitVec<>::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 Word = usize>

BitMat gf2::BitMat< 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 = BitMat<>::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 Word = usize>

BitMat gf2::BitMat< 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 = BitMat<>::ones(3, 3);
auto sub_m = m.strictly_upper();
assert_eq(sub_m.to_compact_binary_string(), "011 001 000");

◆ sub()

template<unsigned_word Word = usize>

BitMat gf2::BitMat< Word >::sub	(	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.

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

Example

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

◆ swap_cols()

template<unsigned_word Word = usize>

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

inlineconstexpr

Swaps columns i and j of the bit-matrix.

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

Example

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

◆ swap_rows()

template<unsigned_word Word = usize>

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

inlineconstexpr

Swaps rows i and j of the bit-matrix.

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

Example

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

◆ to_binary_string()

template<unsigned_word Word = usize>

std::string gf2::BitMat< 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 = BitMat<>::identity(4);

assert_eq(I.to_binary_string(), "1000\n0100\n0010\n0001");

◆ to_compact_binary_string()

template<unsigned_word Word = usize>

std::string gf2::BitMat< 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 = BitMat<>::identity(4);

assert_eq(I.to_compact_binary_string(), "1000 0100 0010 0001");

◆ to_compact_hex_string()

template<unsigned_word Word = usize>

std::string gf2::BitMat< 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

BitMat m0;
assert_eq(m0.to_compact_hex_string(), "");
auto m1 = BitMat<>::zero(4);
m1.set_all();
assert_eq(m1.to_compact_hex_string(), "F F F F");
auto m2 = BitMat<>::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 Word = usize>

BitVec< Word > gf2::BitMat< 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.

Note: This method panics if the bit-matrix is empty.

Example

auto m = BitMat<>::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 Word = usize>

std::string gf2::BitMat< 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

BitMat m0;
assert_eq(m0.to_hex_string(), "");
auto m1 = BitMat<>::zero(4);
m1.set_all();
assert_eq(m1.to_hex_string(), "F\nF\nF\nF");
auto m2 = BitMat<>::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 Word = usize>

std::string gf2::BitMat< 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 = BitMat<>::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 Word = usize>

BitVec< Word > gf2::BitMat< 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.

Note: This method panics if the bit-matrix is empty.

Example

auto m = BitMat<>::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 Word = usize>

std::string gf2::BitMat< 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 = BitMat<>::identity(4);

assert_eq(I.to_string(), "1000\n0100\n0010\n0001");

◆ to_the()

template<unsigned_word Word = usize>

BitMat gf2::BitMat< 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.

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

Example

auto m = BitMat<>::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 Word = usize>

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

inlineconstexpr

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

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

Example

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

◆ transpose()

template<unsigned_word Word = usize>

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

inlineconstexpr

Transposes a square bit-matrix in place.

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

Example

auto m = BitMat<>::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 Word = usize>

BitMat gf2::BitMat< 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 = BitMat<>::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 Word = usize>

BitMat gf2::BitMat< 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 = BitMat<>::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 Word = usize>

BitMat gf2::BitMat< 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 = BitMat<>::zeros(3, 3);
auto sub_m = m.unit_upper();
assert_eq(sub_m.to_compact_binary_string(), "100 010 001");

◆ upper()

template<unsigned_word Word = usize>

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

inlineconstexpr

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

Example

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

◆ x_for()

template<unsigned_word Word = usize>

template<typename Store>
requires store_word_is<Store, Word>

auto gf2::BitMat< Word >::x_for ( const BitStore< Store > & b ) const

inline

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

Example

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

◆ zero()

template<unsigned_word Word = usize>

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

inlinestaticconstexpr

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

Example

auto m = BitMat<>::zero(3);

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

◆ zeros() [1/2]

template<unsigned_word Word = usize>

constexpr BitMat gf2::BitMat< 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 = BitMat<>::zeros(3);

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

◆ zeros() [2/2]

template<unsigned_word Word = usize>

constexpr BitMat gf2::BitMat< 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 = BitMat<>::zeros(3, 4);

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

◆ operator==

template<unsigned_word Word = usize>

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

friend

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

Example

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

Public Types

Public Member Functions

Static Public Member Functions

Inversion

Characteristic Polynomial

Comparison Operator

Detailed Description

Constructor & Destructor Documentation

◆ BitMat() [1/5]

Example

◆ BitMat() [2/5]

Example

◆ BitMat() [3/5]

Example

◆ BitMat() [4/5]

Example

◆ BitMat() [5/5]

Example

Member Function Documentation

◆ add_identity()

Example

◆ all()

Example

◆ alternating() [1/2]

Example

◆ alternating() [2/2]

Example

◆ any()

Example

◆ append_col()

Example

◆ append_cols()

Example

◆ append_row() [1/2]

Example

◆ append_row() [2/2]

Example

◆ append_rows() [1/2]

Example

◆ append_rows() [2/2]

Example

◆ biased_random() [1/2]

Example

◆ biased_random() [2/2]

Example

◆ characteristic_polynomial()

Example

◆ clear()

Example

◆ col()

Example

◆ companion()

Example

◆ companion_matrix_characteristic_polynomial()

Example

◆ count_ones()

Example

◆ count_ones_on_diagonal()

Example

◆ count_zeros()

Example

◆ flip()

Example

◆ flip_all()

Example

◆ flip_diagonal()

Example

◆ flip_sub_diagonal()

Example

◆ flip_super_diagonal()

Example

◆ frobenius_form()

◆ frobenius_matrix_characteristic_polynomial()

◆ from()

Example

◆ from_string()

Example

◆ from_vector_of_cols()

Example

◆ from_vector_of_rows()