mqt.qecc.mod2

Utilities for binary linear algebra (mod 2) to replace dependency on ldpc.mod2.

Functions

row_echelon(...)	Convert a binary matrix to row echelon form over GF(2).
rank(→ int)	Compute the rank of a binary matrix over GF(2).
nullspace(→ numpy.typing.NDArray[numpy.integer])	Compute a basis for the nullspace of a binary matrix over GF(2).
row_basis(→ numpy.typing.NDArray[numpy.integer])	Compute a basis for the row space of a binary matrix over GF(2).

Module Contents

row_echelon(matrix: numpy.typing.NDArray[integer], *, full: bool = False) → tuple[numpy.typing.NDArray[integer], int, numpy.typing.NDArray[integer], list[int]]

Convert a binary matrix to row echelon form over GF(2).

The input is assumed to be a dense binary integer matrix (entries 0 or 1). It is copied internally so the caller’s array is never modified.

Parameters:

• matrix – Binary matrix to reduce.

• full – If True, eliminate entries above and below each pivot (reduced row echelon form). Otherwise only eliminate below.

Returns:

A tuple containing

• the row echelon form,

• the matrix rank,

• the transformation matrix T such that (T @ matrix) % 2 equals the row echelon form,

• the pivot column indices.

rank(matrix: numpy.typing.NDArray[integer]) → int

Compute the rank of a binary matrix over GF(2).

Parameters:

matrix – Binary matrix.

Returns:

The rank of the matrix.

nullspace(matrix: numpy.typing.NDArray[integer]) → numpy.typing.NDArray[integer]

Compute a basis for the nullspace of a binary matrix over GF(2).

Parameters:

matrix – Binary matrix.

Returns:

A matrix whose rows form a basis of the nullspace, i.e. every row v satisfies matrix @ v % 2 == 0.

row_basis(matrix: numpy.typing.NDArray[integer]) → numpy.typing.NDArray[integer]

Compute a basis for the row space of a binary matrix over GF(2).

Parameters:

matrix – Binary matrix.

Returns:

A matrix whose rows are a linearly independent subset of the rows of matrix that spans the same row space.