How to obtain a linear space from the direct sum of two spaces?

asked 2024-09-19 10:59:51 +0200

Ycs
51 ●3 ●8

Dear all,

Given a linear space $V$ of dimension $m$ over a finite field. $W_1$ is $t_1$-dimensional space of $V$. $W_2$ is $t_2$-dimensional space of $V$ . $W_1$ and $W_2$ are in direct sum. If $W=W_1 + W_2$ and $W_1$ are known, then how to solve $W_2$ by Sage?

def random_small_space_gen(t,m):
    B = matrix(GF(q),t,m,0)
    while B.rank() != t:
        B = random_matrix(GF(q),t,m)
    return B.row_space()

(q,m,t1,t2) = (2,30,3,4)
Fqm = GF(q)

V = random_small_space_gen(m,m)
W1 = random_small_space_gen(t1,m)
W2 = random_small_space_gen(t2,m)
W = W1 + W2
print("W :", W)
print()
print("W1 :", W1)

Thanks all very much!

edit retag flag offensive close merge delete

add a comment

answered 2024-09-19 15:39:53 +0200

Max Alekseyev

6355 ●8 ●45 ●150

updated 2024-09-20 02:20:26 +0200

A possible solution:

W.intersection(W1.complement())

UPDATE. As explained in the comments, this does not quite work over finite fields. Here is a somewhat slower alternative:

# computes the complement of U in A
def mycomplement(U,A):
    R = A.subspace([])
    while U.dimension() < A.dimension():
        while True:
            if (v := A.random_element()) not in U:
                break
        U += span([v])
        R += span([v])
    return R

W2_ = mycomplement(W1,W)
assert W == W1 + W2_ and W1.intersection(W2_).dimension()==0

edit flag offensive delete link

Comments

Thanks! But I seem not to get a successful test!

 def random_small_space_gen(t,m):
    B = matrix(GF(q),t,m,0)
    while B.rank() != t:
        B = random_matrix(GF(q),t,m)
    return B.row_space()

(q, m, t1, t2) = (2,30,3,4)

V = random_small_space_gen(m,m)

while W2.intersection(W1) == 0:
    W1 = random_small_space_gen(t1, m)
    W2 = random_small_space_gen(t2, m)


print("Is intersection of W1 and W2 zero space?", W2.intersection(W1))
W = W1 + W2

print()
print("W2 :\n", W2.basis_matrix())
print()
W2_test = W.intersection(W1.complement())
print("W2_test :\n", W2_test.basis_matrix())
print()
print(W2_test == W2)

Ycs ( 2024-09-19 16:48:26 +0200 )edit

Something fishy is going on. However, the condition while W2.intersection(W1) == 0: looks wrong anyway. Perhaps, you meant while W2.intersection(W1).dimension() != 0: here.

Max Alekseyev ( 2024-09-19 17:08:10 +0200 )edit

Thank you very much! Even using the condition while W2.intersection(W1).dimension() != 0:, I also do not get a successful test! Does the code W2_test = W.intersection(W1.complement()) need to be improved by other sage functions?

Ycs ( 2024-09-19 18:21:05 +0200 )edit

The explanation for this behavior is given in the docs:

All these complements are only done with respect to the inner product in the usual basis. Over finite fields, this means we can get complements which are only isomorphic to a vector space decomposition complement.

How to obtain a linear space from the direct sum of two spaces?

1 Answer

Comments

Your Answer

Question Tools

Stats

How to obtain a linear space from the direct sum of two spaces? edit

1 Answer

Comments

Your Answer

Question Tools

Stats

How to obtain a linear space from the direct sum of two spaces?