Ask Your Question
0

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

asked 2021-07-03 08:05:26 +0200

anonymous user

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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
1

answered 2021-07-04 17:40:42 +0200

slelievre gravatar image

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
edit flag offensive delete link more

Comments

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

rewi gravatar imagerewi ( 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
slelievre gravatar imageslelievre ( 2021-07-04 21:07:05 +0200 )edit

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

rewi gravatar imagerewi ( 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.

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

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2021-07-03 08:05:26 +0200

Seen: 83 times

Last updated: Jul 04 '21