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

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.