1 | initial version |
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