Ask Your Question
1

Can sage extend bases?

asked 2016-02-20 11:44:43 -0500

done_with_fish gravatar image

updated 2016-02-21 19:57:35 -0500

Say I have subspaces $X\subset Y$ of a vector space $V$. I want to extend a basis for $X$ to a basis for $Y$. Does sage have this capability?

For example, I have two matrices

sage: d1 = matrix(GF(2), [
....: [1,0,1,0,1,0,1,0,1,0],
....: [1,1,0,0,0,0,0,0,0,1],
....: [0,1,1,1,0,0,0,0,0,0],
....: [0,0,0,1,1,1,0,0,0,0],
....: [0,0,0,0,0,1,1,1,0,0],
....: [0,0,0,0,0,0,0,1,1,1]
....: ])
sage: d2 =  matrix(GF(2), [[1,1,1,0,0,0,0,0,0,0],[0,0,1,1,1,0,0,0,0,0]]).transpose()

Since d1*d2=0 we know that the column space of d2 is a subspace of the null space of d1. We can obtain a basis for the column space of d2 with

sage: d2.column_space().basis()

How could we extend this basis to a basis of the null space of d1?

edit retag flag offensive close merge delete

Comments

It is doable, how are the subspaces given ? Could you provide a concrete example ?

tmonteil gravatar imagetmonteil ( 2016-02-21 05:38:10 -0500 )edit

@tmonteil I just updated the question with an example.

done_with_fish gravatar imagedone_with_fish ( 2016-02-21 19:53:20 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
2

answered 2016-02-22 03:44:17 -0500

tmonteil gravatar image

updated 2016-02-22 03:53:58 -0500

You should know that the bases of Y is a matroid, that is, for any base B2 of Y and any independent set B1 of Y, you can pick some elements of B2 and add them to B1 to form a new basis, and this can be done greedily.

Here is how i will do such a case:

First define the two bases B1 and B2:

sage: B1 = d1.right_kernel().basis()
sage: B1
[
(1, 0, 0, 0, 0, 0, 0, 0, 1, 1),
(0, 1, 0, 1, 0, 1, 0, 1, 0, 1),
(0, 0, 1, 1, 0, 1, 0, 1, 1, 0),
(0, 0, 0, 0, 1, 1, 0, 1, 1, 0),
(0, 0, 0, 0, 0, 0, 1, 1, 1, 0)
]
sage: B2 = d2.column_space().basis()
sage: B2
[
(1, 1, 0, 1, 1, 0, 0, 0, 0, 0),
(0, 0, 1, 1, 1, 0, 0, 0, 0, 0)
]

Note that B1 and B2 are not lists, but immutable Sequences (in particular you can not append new vectors to B2). The quick way is the following:

sage: B = list(B2)
sage: for v in B1:
....:     if v not in span(B):
....:         B.append(v)
sage: B
[(1, 1, 0, 1, 1, 0, 0, 0, 0, 0),
 (0, 0, 1, 1, 1, 0, 0, 0, 0, 0),
 (1, 0, 0, 0, 0, 0, 0, 0, 1, 1),
 (0, 1, 0, 1, 0, 1, 0, 1, 0, 1),
 (0, 0, 0, 0, 0, 0, 1, 1, 1, 0)]

Which looks correct, but it is not completely satisfactory since the vectors do not belong to the same space:

sage: for v in B: 
....:     print v.parent()
Vector space of degree 10 and dimension 2 over Finite Field of size 2
Basis matrix:
[1 1 0 1 1 0 0 0 0 0]
[0 0 1 1 1 0 0 0 0 0]
Vector space of degree 10 and dimension 2 over Finite Field of size 2
Basis matrix:
[1 1 0 1 1 0 0 0 0 0]
[0 0 1 1 1 0 0 0 0 0]
Vector space of degree 10 and dimension 5 over Finite Field of size 2
Basis matrix:
[1 0 0 0 0 0 0 0 1 1]
[0 1 0 1 0 1 0 1 0 1]
[0 0 1 1 0 1 0 1 1 0]
[0 0 0 0 1 1 0 1 1 0]
[0 0 0 0 0 0 1 1 1 0]
Vector space of degree 10 and dimension 5 over Finite Field of size 2
Basis matrix:
[1 0 0 0 0 0 0 0 1 1]
[0 1 0 1 0 1 0 1 0 1]
[0 0 1 1 0 1 0 1 1 0]
[0 0 0 0 1 1 0 1 1 0]
[0 0 0 0 0 0 1 1 1 0]
Vector space of degree 10 and dimension 5 over Finite Field of size 2
Basis matrix:
[1 0 0 0 0 0 ...
(more)
edit flag offensive delete link more

Comments

This should practically be in a linear algebra tutorial somewhere...

kcrisman gravatar imagekcrisman ( 2016-02-22 20:01:58 -0500 )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: 2016-02-20 11:44:43 -0500

Seen: 121 times

Last updated: Feb 22 '16