Ask Your Question
1

Generating specific matrix group in Sagemath

asked 2024-01-13 05:31:54 +0200

anonymous user

Anonymous

updated 2024-01-14 02:53:58 +0200

Hi, this is my first time here, and I am trying to use Sagemath to generate some matrix group.

The group I want to generate is the BLTA(Block Lower Triangular Group). For some background, the BLTA group has a parameter, called the profile, written as $\mathbf{s} = (s_1, s_2, \cdots s_l)$. The $\mathsf{BLTA}(\mathbf{s})$ group is a binary matrix group of size n by n where $n=s_1+s_2+\cdots+s_l$. We can consider this matrix as a block matrix with blocks divided by $s_1\times s_1, s_2\times s_2, \cdots s_l\times s_l$, and the lower trianglar part can be either 0 or 1, and the upper triangular part(excluding the main block diagonal) must be all zero. This forms a matrix group under ordinary matrix multiplication over the binary field $\mathbb{F}_2$. But I don't think I can find the generators of this group. How can I make this group in Sagemath?

Edit I realized that my description may be hard to understand due to my poor English skills. So essentially what I'm finding is a subgroup of the general linear group over the binary field $\mathbf{F}_2$ that has specific entries to be set to 0. But I am not aware of the generators of this new group. How can I implement it? I hope this makes more sense.

edit retag flag offensive close merge delete

Comments

Can you provide an example of what you look for profile $(2,3)$, say? Also, what do you mean by saying "I don't think I can find the generators of this group"? Didn't you just describe the generators?

Max Alekseyev gravatar imageMax Alekseyev ( 2024-01-14 14:11:20 +0200 )edit

@Max Alekseyev So, for a profile with $\mathbf{s}=(2, 3)$, we are looking for a subset of 5 by 5 size matrices, and a generic element of this group would be $$ \begin{bmatrix} * & * & 0 & 0 & 0 \\ * & * & 0 & 0 & 0 \\ * & * & * & * & * \\ * & * & * & * & * \\ * & * & * & * & * \end{bmatrix} $$ where the star entries can be either 0 or 1, while ensuring that the matrix is invertible so that it is a subgroup of the general linear group.

woojoshua78 gravatar imagewoojoshua78 ( 2024-01-15 02:23:11 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted
0

answered 2024-01-15 21:06:13 +0200

Max Alekseyev gravatar image

updated 2024-01-16 03:17:30 +0200

This a rather dumb approach but it seems to work for small arguments. The idea is to use a growing number of random elements of the target group as generators until the target group size is matched:

def mygroup(s):
    n = sum(s)
    k = len(s)

    # matrix spaces for the blocks of target matrices
    spaces = [GL(s[i],GF(2)) if i==j else MatrixSpace(GF(2),s[i],s[j]) if i>j else Set([Matrix(GF(2),s[i],s[j],immutable=True)]) for i in range(k) for j in range(k)]

    # target group cardinality
    mycard = prod( T.cardinality() for T in spaces )

    # trying random generators
    for t in range(mycard):
        # print(f'Tring {t+1} random generators')
        S = GL(n,GF(2)).subgroup( block_matrix([[Matrix(GF(2),spaces[i*k+j].random_element()) for j in range(k)] for i in range(k)]) for _ in range(t+1) ) 
        if S.cardinality() == mycard:
            return S

For example, mygroup([3,2]) gives:

Subgroup with 4 generators (
[0 1 1 0 0]  [0 1 0 0 0]  [1 0 1 0 0]  [0 1 1 0 0]
[1 0 1 0 0]  [0 1 1 0 0]  [0 1 0 0 0]  [1 1 0 0 0]
[1 0 0 0 0]  [1 1 1 0 0]  [1 0 0 0 0]  [1 1 1 0 0]
[0 0 1 0 1]  [1 1 1 1 1]  [0 0 1 1 0]  [0 1 1 1 0]
[1 1 1 1 0], [0 0 1 0 1], [0 1 0 0 1], [1 1 0 1 1]
) of General Linear Group of degree 5 over Finite Field of size 2
edit flag offensive delete link more

Comments

Thank you sir, for your kind answer.

woojoshua78 gravatar imagewoojoshua78 ( 2024-01-16 02:36: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: 2024-01-13 05:31:54 +0200

Seen: 244 times

Last updated: Jan 16