# How to construct the set of all symmetric invertible $\{0,1\}$ matrices of order 5 in sagemath

Anonymous

How to construct the set of all symmetric invertible {0,1} matrices (that is, entries of the matrices are either 0 or 1) of order 5 in sage math.

edit retag close merge delete

Sort by » oldest newest most voted

One way is to define a generator that goes through symmetric zero-one matrices and yields those that are invertible.

There could be several variations, depending whether we want to consider the matrices as defined (and invertible) over $\mathbb{Z}$, $\mathbb{Q}$, or $\mathbb{Z}/2\mathbb{Z}$, and whether the inverses should also be zero-one matrices.

Here is a version which gives all symmetric zero-one invertible matrices over $\mathbb{Q}$, of size d by d.

def symmetric_invertible_zero_one_matrices(d, mutable=True):
r"""
Return a generator of symmetric invertible zero-one d by d matrices.

EXAMPLES::

sage: list(symmetric_invertible_zero_one_matrices(0))
[[]]
sage: list(symmetric_invertible_zero_one_matrices(1))
[[1]]
sage: list(symmetric_invertible_zero_one_matrices(2))
[
[0 1]  [1 1]  [1 0]  [0 1]
[1 0], [1 0], [0 1], [1 1]
]
sage: {d: sum(1 for m in symmetric_invertible_zero_one_matrices(d))
....:  for d in range(6)}
{0: 1, 1: 1, 2: 4, 3: 32, 4: 528, 5: 18596}
"""
M = MatrixSpace(QQ, d)
n = d * (d + 1) // 2
z = [0] * n
for a in srange(2^n):
c = z[:]
b = a.bits()
c[:len(b)] = b
f = lambda i, j: (c[d*i - i*(i+1) // 2 + j])
g = lambda i, j: f(i, j) if i <= j else f(j, i)
m = M(g)
if m.is_invertible():
if not mutable:
m.set_immutable()
yield m


To make a set of them, use mutable=False.

sage: S = set(symmetric_invertible_zero_one_matrices(5, mutable=False))
sage: len(S)
18596

more

Nice answer. Thank you. Now from this collection, we we find those invertible matrices whose inverses have entries in {0,1,-1}?

( 2021-07-04 20:44:35 +0200 )edit

To only get those, change two things in the function:

• change M = MatrixSpace(QQ, d) to M = MatrixSpace(ZZ, d)
• change if m.is_invertible(): to if m.is_unit() and all(e in (-1, 0, 1) for e in m.inverse_of_unit().list()):

To extract them after the fact:

sage: T = {m for m in S if all(e in (-1, 0, 1) for e in m.inverse().list())}
sage: len(T)
7906

( 2021-07-04 21:07:05 +0200 )edit

I tried to compile. for that I copied the text, but the outcome is not coming

( 2021-07-04 21:24:33 +0200 )edit

Not sure what you mean by "compile". Maybe you can say more on how you are using Sage.

( 2021-07-05 01:38:41 +0200 )edit