q1ss.binalg.affine

Affine subspaces.

AffineSubspace

final class AffineSubspace(generators, basepoint=None, *, copy=False)[source]

Bases: object

A linear or affine subspace of a binary vector space, represened by:

a matrix whose rows span the (underlying) linear subspace
a basepoint vector

The subspace representation can be canonicalized: see is_canonical and canonicalize for details.

Warning

For efficiency reasons, the internal representation of the affine subspace is not canonicalised at construction time. Many properties and methods automatically canonicalize the subspace as part of their inner workings, but the following properties and methods don’t do so:

ambient_dim
num_generators
generators
basepoint
linspace
__rmatmul__
__add__
__radd__
draw

The values returned by num_generators, generators and basepoint change when the space is canonicalized.

__add__(vec)[source]

Translates the affine subspace by the given vector.

Parameters:: vec (binvec)
Return type:: AffineSubspace

__contains__(vec)[source]

Whether the given vector is contained in this affine subspace.

Parameters:: vec (binvec)
Return type:: bool

__eq__(other)[source]

Checks whether this affine subspace is equal to another affine subspace.

Parameters:: other (Any)
Return type:: bool

__radd__(vec)[source]

Translates the affine subspace by the given vector.

Parameters:: vec (binvec)
Return type:: AffineSubspace

__rmatmul__(mat)[source]

Transforms the affine subspace by the given matrix.

Parameters:: mat (binmat)
Return type:: AffineSubspace

__sub__(vec)[source]

Same as __add__.

Parameters:: vec (binvec)
Return type:: AffineSubspace

property ambient_dim

The dimension of the ambient space.

Return type:: int

property basepoint

The value returned by this property is only guaranteed to be constant if the subspace is_canonical, in which case:

it is guaranteed to be zero at the pivot cols for the basis matrix (which is in RREF when the subspace is canonical);
it is the zero vector if and only if the subspace is linear

Return type:: binvec

property basis

A RREF matrix whose rows form a basis for the linear subspace.

The subspace is automatically canonicalised.

Return type:: binmat

canonicalize()[source]

Canonicalises the affine subspace’s internal data:

the generators are brought to RCEF, zero columns are dropped and the subspace dimension is obtained as the number of non-zero columns.
the basepoint vector is reduced according to the new generators, and the subspace is linear when the reduced basepoint is zero.

Return type:: None

copy(*, canonical=False)[source]

Returns a copy of this affine subspace. If canonical=True, the copy is canonicalised.

Parameters:: canonical (bool; default = False)
Return type:: AffineSubspace

property dim

The dimension of the subspace.

The subspace is automatically canonicalised.

Return type:: int

draw(axes, *, color=None, label=None, **draw_networkx_kwargs)[source]

Draws this affine subspace using draw_networkx.

Parameters:

axes (HypercubeAxes)
color (str | None)
label (BinvecLabelFun | None)
draw_networkx_kwargs (Any; variadic keyword)

Return type:

None

static draw_many(axes, subspaces, *, colors=None, label=None, subsp_kwargs=None, **draw_networkx_kwargs)[source]

Draws the given affine subspaces using draw_networkx.

Parameters:

axes (HypercubeAxes)
subspaces (Sequence[AffineSubspace])
colors (Sequence[str] | None)
label (BinvecLabelFun | None)
subsp_kwargs (Sequence[Mapping[str, Any]] | None)
draw_networkx_kwargs (Any; variadic keyword)

Return type:

None

property generators

A matrix whose rows span the (underlying) linear subspace.

The value returned by this property is only guaranteed to be constant if the subspace is_canonical, in which case it is the same as the subspace basis.

Return type:: binmat

property is_canonical

Whether the subspace is in canonical form:

the basis matrix is in RREF
the basepoint vector has been reduced to canonical form

A subspace can be put in canonical form by calling canonicalize, and it henceforth remains in canonical form. The subspace is automatically canonicalized the first time that an operation is executed which requires canonical data.

Return type:: bool

is_disjoint(other)[source]

Whether this affine subspace is disjoint from the other given subspace.

Parameters:: other (AffineSubspace)
Return type:: bool

property is_linear

Whether the subspace is linear.

The subspace is automatically canonicalised.

Return type:: bool

is_ortho(vec)[source]

Whether the given vector is orthogonal to the subspace.

Parameters:: vec (binvec)
Return type:: bool

property iter_basis

Iterates over the basis vectors for the linear subspace.

The subspace is automatically canonicalised.

Return type:: Iterator[binvec]

property iter_points

Iterates over all the points in the affine subspace.

Return type:: Iterator[binvec]

property linspace

The linear subspace corresponding to this affine subspace.

Return type:: AffineSubspace

property num_generators

Returns the number of generators for the (underlying) linear subspace.

Return type:: int

property points

Returns a matrix whose columns are all points of this affine subspace.

Return type:: binmat

static random(subsp_dim, ambient_dim, *, linear=False, rng=None)[source]

Samples a random affine subspace with given subspace dimension, within a vector space with given ambient dimension. If linear is True, only linear subspaces are sampled.

Warning

This method relies on random_rref to sample the underlying linear subspace: currently, it does not result in a uniform sampling across all subspaces. This will change in future releases.

Parameters:

subsp_dim (int)
ambient_dim (int)
linear (bool; default = False)
rng (np.random.Generator | int | None)

Return type:

AffineSubspace

random_points(num_samples, *, rng=None)[source]

Returns a matrix with the given number of random subspace points as its rows.

Parameters:

num_samples (int)
rng (np.random.Generator | int | None)

Return type:

binmat

residual(vec)[source]

Returns the canonical translation that must be applied to this affine subspace to obtain a coset which contains the given vector.

Parameters:: vec (binvec)
Return type:: binvec

select(coeffs)[source]

Returns a matrix whose columns are the affine subspace points obtained by linear combination of the basis vectors, using the columns of the input matrix as coefficient vectors.

Parameters:: coeffs (binmat)
Return type:: binmat

static std(subsp_dim, ambient_dim, basepoint=None)[source]

Returns the standard affine subspace of given dimension, using the first \(n\) standard basis vectors of the ambient space where \(n\) is the subspace dimension.

Parameters:

subsp_dim (int)
ambient_dim (int)
basepoint (binvec | None)

Return type:

AffineSubspace

transform(matrices, *, partial=False)[source]

Transforms the subspace by the given matrices, applied in order left-to-right. If partial=True, matrices are allowed to have dimension/side k smaller than the ambient dimension of the subspace, in which case they are applied to the subspace spanned by the first k standard ambient vectors.

Parameters:

matrices (binmat | Sequence[binmat])
partial (bool; default = False)

Return type:

AffineSubspace

BinvecLabelFun

class BinvecLabelFun(*args, **kwargs)[source]

Bases: Protocol

Structural type for a labelling function which can be passed to the label argument of various drawing methods for affine subspaces.

HypercubeAxes

HypercubeAxes = numpy.ndarray[tuple[typing.Any, ...], numpy.dtype[numpy.number[typing.Any]]] | collections.abc.Sequence[collections.abc.Sequence[int | float]]: Type alias for hypercube axes that can be passed to AffineSubspace.draw, and AffineSubspace.draw_many.

draw_hypercube

draw_hypercube(axes, *, label=None, **draw_networkx_kwargs)[source]

Draws a hypercube using draw_networkx, plotting the generating directions along the given 2D axes.

Parameters:

axes (HypercubeAxes)
label (BinvecLabelFun | None)
draw_networkx_kwargs (Any; variadic keyword)

Return type:

None