ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 22 Feb 2016 20:01:58 -0600Can sage extend bases?http://ask.sagemath.org/question/32607/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?
Sat, 20 Feb 2016 11:44:43 -0600http://ask.sagemath.org/question/32607/can-sage-extend-bases/Comment by done_with_fish for <p>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?</p>
<p>For example, I have two matrices</p>
<pre><code>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()
</code></pre>
<p>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</p>
<pre><code>sage: d2.column_space().basis()
</code></pre>
<p>How could we extend this basis to a basis of the null space of d1?</p>
http://ask.sagemath.org/question/32607/can-sage-extend-bases/?comment=32619#post-id-32619@tmonteil I just updated the question with an example.Sun, 21 Feb 2016 19:53:20 -0600http://ask.sagemath.org/question/32607/can-sage-extend-bases/?comment=32619#post-id-32619Comment by tmonteil for <p>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?</p>
<p>For example, I have two matrices</p>
<pre><code>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()
</code></pre>
<p>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</p>
<pre><code>sage: d2.column_space().basis()
</code></pre>
<p>How could we extend this basis to a basis of the null space of d1?</p>
http://ask.sagemath.org/question/32607/can-sage-extend-bases/?comment=32611#post-id-32611It is doable, how are the subspaces given ? Could you provide a concrete example ?Sun, 21 Feb 2016 05:38:10 -0600http://ask.sagemath.org/question/32607/can-sage-extend-bases/?comment=32611#post-id-32611Answer by tmonteil for <p>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?</p>
<p>For example, I have two matrices</p>
<pre><code>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()
</code></pre>
<p>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</p>
<pre><code>sage: d2.column_space().basis()
</code></pre>
<p>How could we extend this basis to a basis of the null space of d1?</p>
http://ask.sagemath.org/question/32607/can-sage-extend-bases/?answer=32623#post-id-32623You 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 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]
Also:
sage: type(B1)
<class 'sage.structure.sequence.Sequence_generic'>
sage: type(B)
<type 'list'>
This is not necessarily important for further computations, but to be cleaner (with respect to the current design), you should create a mutable sequence, transform the elements of `B2` as elements of `B1`:
sage: B = Sequence(B2, universe = d1.right_kernel(), immutable=False, cr=True)
sage: B
[
(1, 1, 0, 1, 1, 0, 0, 0, 0, 0),
(0, 0, 1, 1, 1, 0, 0, 0, 0, 0)
]
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)
]
In particular, you have the expected properties:
sage: span(B) == span(B1)
True
sage: len(B) == len(B1)
True
sage: B[0:2] == B2
True
Also, you can check that now `B` is of the same type as `B1`
sage: type(B)
<class 'sage.structure.sequence.Sequence_generic'>
sage: B.universe() == B1.universe()
True
Mon, 22 Feb 2016 03:44:17 -0600http://ask.sagemath.org/question/32607/can-sage-extend-bases/?answer=32623#post-id-32623Comment by kcrisman for <div class="snippet"><p>You should know that the bases of <code>Y</code> is a matroid, that is, for any base <code>B2</code> of <code>Y</code> and any independent set <code>B1</code> of <code>Y</code>, you can pick some elements of <code>B2</code> and add them to <code>B1</code> to form a new basis, and this can be done greedily.</p>
<p>Here is how i will do such a case:</p>
<p>First define the two bases <code>B1</code> and <code>B2</code>:</p>
<pre><code>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)
]
</code></pre>
<p>Note that <code>B1</code> and <code>B2</code> are not lists, but immutable <code>Sequences</code> (in particular you can not append new vectors to <code>B2</code>). The quick way is the following:</p>
<pre><code>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)]
</code></pre>
<p>Which looks correct, but it is not completely satisfactory since the vectors do not belong to the same space:</p>
<pre><code>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 ...</code></pre><span class="expander"> <a>(more)</a></span></div>http://ask.sagemath.org/question/32607/can-sage-extend-bases/?comment=32637#post-id-32637This should practically be in a linear algebra tutorial somewhere...Mon, 22 Feb 2016 20:01:58 -0600http://ask.sagemath.org/question/32607/can-sage-extend-bases/?comment=32637#post-id-32637