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).
`row_span`(→ numpy.typing.NDArray[numpy.uint8])	Compute all vectors in the row space of a binary matrix over GF(2).
`is_in_row_space`(→ bool)	Check whether a binary vector lies in the binary row space of a basis.
`are_in_same_coset`(→ bool)	Check whether two binary vectors lie in the same coset of a binary row space of a basis.

Module Contents¶

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

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[source]¶

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][source]¶

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][source]¶

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.

row_span(matrix: numpy.typing.NDArray[integer]) → numpy.typing.NDArray[numpy.uint8][source]¶

Compute all vectors in the row space of a binary matrix over GF(2).

The result grows exponentially with the number of rows of the matrix: it has 2 ** matrix.shape[0] rows, so callers must bound the number of rows themselves. This is only practical for a few dozen rows at most.

Parameters:: matrix – Binary matrix.
Returns:: A matrix with one row for each binary linear combination of the rows of matrix. Row mask is the sum of the rows of matrix that are selected by the bits of mask, so vectors repeat if the rows of matrix are linearly dependent.

is_in_row_space(vector: numpy.typing.NDArray[integer], basis: numpy.typing.NDArray[integer]) → bool[source]¶

Check whether a binary vector lies in the binary row space of a basis.

Parameters:

vector – The binary vector to test.
basis – A binary matrix whose rows span the space.

Returns:

True if the vector is a binary linear combination of the basis rows.

are_in_same_coset(lhs: numpy.typing.NDArray[integer], rhs: numpy.typing.NDArray[integer], basis: numpy.typing.NDArray[integer]) → bool[source]¶

Check whether two binary vectors lie in the same coset of a binary row space of a basis.

Equivalently, can rhs be obtained from lhs by adding a linear combination of the rows of basis.

Parameters:

lhs – The first binary vector.
rhs – The second binary vector.
basis – A binary matrix whose rows span the space.

Returns:

True if the difference of the vectors is in the row space of the basis.