BMat8 helpers

This page contains the documentation for various helper functions for manipulating BMat8 objects. All these functions are contained in the submodule libsemigroups_pybind11.bmat8.

Contents

`col_space_basis`(…)	Find a basis for the column space of a `BMat8`.
`col_space_size`(…)	Returns the size of the column space of a `BMat8`.
`minimum_dim`(…)	Returns the minimum dimension of a `BMat8`.
`number_of_cols`(…)	Returns the number of non-zero columns in a `BMat8`.
`number_of_rows`(…)	Returns the number of non-zero rows in a `BMat8`.
`one`(…)	Returns the identity `BMat8` of a given dimension.
`random`(…)	Construct a random `BMat8` of dimension at most dim.
`row_space_basis`(…)	Find a basis for the row space of a `BMat8`.
`row_space_size`(…)	Returns the size of the row space of a `BMat8`.
`rows`(…)	Returns a list of the rows of a `BMat8`.
`transpose`(…)	Returns the transpose of a `BMat8`.

Full API

This module contains the helper functions from libsemigroups_pybind11.bmat8.

bmat8.col_space_basis(x: BMat8) → BMat8

Find a basis for the column space of a BMat8.

This function returns a BMat8 whose non-zero columns form a basis for the column space of x.

Parameters:: x (BMat8) – the matrix.
Returns:: A BMat8.
Return type:: BMat8
Complexity:: Constant.

>>> from libsemigroups_pybind11 import BMat8, bmat8
>>> x = BMat8([[1, 0, 1], [0, 1, 0], [0, 0, 0]])
>>> bmat8.col_space_basis(x)
BMat8([[1, 0],
       [0, 1]])

bmat8.col_space_size(x: BMat8) → int

Returns the size of the column space of a BMat8.

Parameters:: x (BMat8) – the matrix.
Returns:: The size of the column space of x.
Return type:: int
Complexity:: \(O(n)\) where \(n\) is the return value of this function.

See also

row_space_size.

>>> from libsemigroups_pybind11 import BMat8, bmat8
>>> x = BMat8([[0, 1], [1, 0]])
>>> bmat8.col_space_size(x)
4

bmat8.is_regular_element(x: BMat8) → bool

Check whether x is a regular element of the full boolean matrix monoid of appropriate dimension.

Parameters:: x (BMat8) – the matrix.
Returns:: True if there exists a boolean matrix y such that x * y * x = x where x, and False otherwise.
Return type:: bool
Complexity:: Constant.

>>> from libsemigroups_pybind11 import BMat8, bmat8
>>> x = BMat8([[0, 1], [1, 0]])
>>> bmat8.is_regular_element(x)
True
>>> sum(1 for x in range(100000) if bmat8.is_regular_element(BMat8(x)))
97996

bmat8.minimum_dim(x: BMat8) → int

Returns the minimum dimension of a BMat8.

This function returns the maximal n such that row n or column n in the boolean matrix x contains a 1. Equivalent to the maximum of number_of_rows and number_of_cols.

Parameters:: x (BMat8) – the matrix.
Returns:: The minimum dimension of x.
Return type:: int
Complexity:: Constant.

>>> from libsemigroups_pybind11 import BMat8, bmat8
>>> x = BMat8([[0, 1], [1, 0]])
>>> bmat8.minimum_dim(x)
2

bmat8.number_of_cols(x: BMat8) → int

Returns the number of non-zero columns in a BMat8.

BMat8 objects do not know their “dimension” - in effect they are all of dimension 8. However, this function can be used to obtain the number of non-zero rows of a BMat8.

Parameters:: x (BMat8) – the matrix.
Returns:: The number of non-zero columns.
Return type:: int
Complexity:: Constant.

See also

number_of_rows and minimum_dim.

>>> from libsemigroups_pybind11 import BMat8, bmat8
>>> x = BMat8([[1, 0, 1], [0, 1, 0], [0, 0, 0]])
>>> bmat8.number_of_cols(x)
3

bmat8.number_of_rows(x: BMat8) → int

Returns the number of non-zero rows in a BMat8.

BMat8 objects do not know their “dimension” - in effect they are all of dimension 8. However, this function can be used to obtain the number of non-zero rows of a BMat8.

Parameters:: x (BMat8) – the matrix.
Returns:: The number of non-zero rows.
Return type:: int
Complexity:: Constant.

See also

number_of_cols and minimum_dim.

>>> from libsemigroups_pybind11 import BMat8, bmat8
>>> x = BMat8([[1, 0, 1], [0, 1, 0], [0, 0, 0]])
>>> bmat8.number_of_rows(x)
2

bmat8.one(dim: int) → BMat8

Returns the identity BMat8 of a given dimension.

This function returns the BMat8 with the first dim entries in the main diagonal equal to 1 and every other value equal to 0.

Parameters:: dim (int) – the dimension of the identity (default: 8)
Returns:: A BMat8.
Return type:: BMat8
Complexity:: Constant.

>>> from libsemigroups_pybind11 import bmat8
>>> bmat8.one(4)
BMat8([[1, 0, 0, 0],
       [0, 1, 0, 0],
       [0, 0, 1, 0],
       [0, 0, 0, 1]])

bmat8.random(dim: int) → BMat8

Construct a random BMat8 of dimension at most dim.

This function returns a BMat8 chosen at random, where only the top-left dim by dim entries can be non-zero.

Parameters:: dim (int) – the dimension.
Returns:: A BMat8.
Return type:: BMat8

bmat8.row_space_basis(x: BMat8) → BMat8

Find a basis for the row space of a BMat8.

This function returns a BMat8 whose non-zero rows form a basis for the row space of x.

Parameters:: x (BMat8) – the matrix.
Returns:: A BMat8.
Return type:: BMat8
Complexity:: Constant.

>>> from libsemigroups_pybind11 import BMat8, bmat8
>>> x = BMat8([[1, 0, 1], [0, 1, 0], [0, 0, 0]])
>>> bmat8.row_space_basis(x)
BMat8([[1, 0, 1],
       [0, 1, 0],
       [0, 0, 0]])

bmat8.row_space_size(x: BMat8) → int

Returns the size of the row space of a BMat8.

Parameters:: x (BMat8) – the matrix.
Returns:: The size of the row space of x.
Return type:: int
Complexity:: \(O(n)\) where \(n\) is the return value of this function.

See also

col_space_size.

>>> from libsemigroups_pybind11 import BMat8, bmat8
>>> x = BMat8([[1, 0, 0], [0, 1, 1], [0, 1, 0]])
>>> bmat8.row_space_size(x)
6

bmat8.rows(x: BMat8) → list[list[bool]]

Returns a list of the rows of a BMat8.

This function returns the rows of x. The returned list always has length 8, even if x was constructed with fewer rows.

Parameters:: x (BMat8) – the matrix.
Returns:: The list of rows of the boolean matrix x.
Return type:: list[list[bool]]
Complexity:: Constant.

>>> from libsemigroups_pybind11 import BMat8, bmat8
>>> x = BMat8([[0, 1], [1, 0]])
>>> bmat8.rows(x)
[[False, True, False, False, False, False, False, False],
 [True, False, False, False, False, False, False, False],
 [False, False, False, False, False, False, False, False],
 [False, False, False, False, False, False, False, False],
 [False, False, False, False, False, False, False, False],
 [False, False, False, False, False, False, False, False],
 [False, False, False, False, False, False, False, False],
 [False, False, False, False, False, False, False, False]]

bmat8.transpose(x: BMat8) → BMat8

Returns the transpose of a BMat8.

This function returns the transpose of its argument x, which is computed using the technique found in [Knu09].

Parameters:: x (BMat8) – the matrix to transpose.
Returns:: A BMat8.
Return type:: BMat8
Complexity:: Constant.

>>> from libsemigroups_pybind11 import BMat8, bmat8
>>> x = BMat8([[1, 0, 1], [0, 1, 0], [0, 0, 0]])
>>> bmat8.transpose(x)
BMat8([[1, 0, 0],
       [0, 1, 0],
       [1, 0, 0]])