# Can sage extend bases?

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

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

( 2016-02-21 05:38:10 -0600 )edit

@tmonteil I just updated the question with an example.

( 2016-02-21 19:53:20 -0600 )edit

Sort by » oldest newest most voted

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

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

( 2016-02-22 20:01:58 -0600 )edit