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.Wed, 29 Jun 2016 06:19:21 -0500Linear Algebra in Finite Fields (Goppa Codes)http://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/Context:
I am trying to calculate a generator matrix for Goppa codes.
We are working in GF(16), e is a generator of GF(16), and we are given the polynomial
g = (x+e)*(x+e^14)
F.<e> = GF(16)
p = e.minpoly()
p
R.<x> = PolynomialRing(F)
g=(x+e)*(x+e^14)
i calculate the parity check matrix with coefficients in GF(16) as follows
H = matrix(F,2,12)
for i in range (2,14):
f=-((g(x)-g(e^i))/(x-e^i))*(1/g(e^i))
print("i=%s %s"%(i,f))
ff=R(f) # coerce to polynomial with canonical injection
H[0,i-2]=ff.list()[0]
H[1,i-2]=ff.list()[1]
i=2 (e^3 + e^2 + e + 1)*x + e^3 + e
i=3 (e^3 + e^2)*x + e^2 + e + 1
i=4 (e^3 + e^2)*x + e^3 + e
i=5 e*x + e^3 + 1
i=6 (e^3 + e^2 + e)*x + e^3 + e^2
i=7 x
i=8 (e^3 + 1)*x + e^2 + e + 1
i=9 (e^2 + 1)*x + e^2 + 1
i=10 (e^3 + e^2 + e)*x + e^2
i=11 (e^3 + 1)*x + e^3 + e + 1
i=12 (e^3 + e^2 + e + 1)*x + e^3 + 1
i=13 e*x + e^3 + e^2
H is a 2x12 matrix in GF(16)
now I am are interested in getting a 8x12 matrix corresponding to 8 equations. We get 4 equations for each row of H.
i am considering a vector of size 12 of unknowns c=(c1,c2,...,12) [with possible values 0 or 1], and for each row, we will look at the equation row_i * c=0 and we group terms corresponding to 1,e,e^2,e^3 and because this is a basis of GF(16) we know that the coefficients of 1,e,e^2,e^3 are 0. I want to extract those equations.
var('c1','c2','c3','c4','c5','c6','c7','c8','c9','c10','c11','c12')
C=matrix([[c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12]])
H*C.T
[ (e^3 + e)*c1 + (e^3 + e + 1)*c10 + (e^3 + 1)*c11 + (e^3
+ e^2)*c12 + (e^2 + e + 1)*c2 + (e^3 + e)*c3 + (e^3 + 1)*c4 + (e^3 +
e^2)*c5 + (e^2 + e + 1)*c7 + (e^2 + 1)*c8 + e^2*c9]
[(e^3 + e^2 + e + 1)*c1 + (e^3 + 1)*c10 + (e^3 + e^2 + e + 1)*c11 +
e*c12 + (e^3 + e^2)*c2 + (e^3 + e^2)*c3 + e*c4 + (e^3 + e^2 + e)*c5 + c6
+ (e^3 + 1)*c7 + (e^2 + 1)*c8 + (e^3 + e^2 + e)*c9]
for example for the first row the equation corresponding to e should be
(c1+c10+c2+c3+c7 =0)
could u please tell me how to recover the equation
AND to get the answer in matrix form
the next step of course is to find a basis for the kernel. How do we do that in SAGE ?
[of course it can be done by hand, but i want to be able to write the program]
PS. i am rather new to SAGE and to cryptography, i am following the MOOC from INRIA on fun-mooc
thank youSat, 25 Jun 2016 06:18:09 -0500http://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/Comment by kcrisman for <div class="snippet"><p>Context:</p>
<p>I am trying to calculate a generator matrix for Goppa codes.</p>
<p>We are working in GF(16), e is a generator of GF(16), and we are given the polynomial
g = (x+e)*(x+e^14)</p>
<pre><code>F.<e> = GF(16)
p = e.minpoly()
p
R.<x> = PolynomialRing(F)
g=(x+e)*(x+e^14)
</code></pre>
<p>i calculate the parity check matrix with coefficients in GF(16) as follows</p>
<pre><code>H = matrix(F,2,12)
for i in range (2,14):
f=-((g(x)-g(e^i))/(x-e^i))*(1/g(e^i))
print("i=%s %s"%(i,f))
ff=R(f) # coerce to polynomial with canonical injection
H[0,i-2]=ff.list()[0]
H[1,i-2]=ff.list()[1]
</code></pre>
<p>i=2 (e^3 + e^2 + e + 1)*x + e^3 + e</p>
<p>i=3 (e^3 + e^2)*x + e^2 + e + 1</p>
<p>i=4 (e^3 + e^2)*x + e^3 + e</p>
<p>i=5 e*x + e^3 + 1</p>
<p>i=6 (e^3 + e^2 + e)*x + e^3 + e^2</p>
<p>i=7 x</p>
<p>i=8 (e^3 + 1)*x + e^2 + e + 1</p>
<p>i=9 (e^2 + 1)*x + e^2 + 1</p>
<p>i=10 (e^3 + e^2 + e)*x + e^2</p>
<p>i=11 (e^3 + 1)*x + e^3 + e + 1</p>
<p>i=12 (e^3 + e^2 + e + 1)*x + e^3 + 1</p>
<p>i=13 e*x + e^3 + e^2</p>
<p>H is a 2x12 matrix in GF(16)
now I am are interested in getting a 8x12 matrix corresponding to 8 equations. We get 4 equations for each row of H.
i am considering a vector of size 12 of unknowns c=(c1,c2,...,12) [with possible values 0 or 1], and for each row, we will look at the equation row_i * c=0 and we group terms corresponding to 1,e,e^2,e^3 and because this is a basis of GF(16) we know that the coefficients of 1,e,e^2,e^3 are 0. I want to extract those equations.</p>
<pre><code>var('c1','c2','c3','c4','c5','c6','c7','c8','c9','c10','c11','c12')
C=matrix([[c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12]])
H*C.T
</code></pre>
<p>[ (e^3 + e)<em>c1 + (e^3 + e + 1)</em>c10 + (e^3 + 1)<em>c11 + (e^3
+ e^2)</em>c12 + (e^2 + e + 1)<em>c2 + (e^3 + e)</em>c3 + (e^3 + 1)<em>c4 + (e^3 +
e^2)</em>c5 + (e^2 + e + 1)<em>c7 + (e^2 + 1)</em>c8 + e^2<em>c9]
[(e^3 + e^2 + e + 1)</em>c1 + (e^3 + 1)<em>c10 + (e^3 + e^2 + e + 1)</em>c11 +
e<em>c12 + (e^3 + e^2)</em>c2 + (e^3 + e^2)<em>c3 + e</em>c4 + (e^3 + e^2 + e)<em>c5 + c6
+ (e^3 + 1)</em>c7 + (e^2 + 1)<em>c8 + (e^3 + e^2 + e)</em>c9]</p>
<p>for example for the first row the equation corresponding to e should be
(c1+c10+c2+c3+c7 =0)</p>
<p>could u please tell me how to recover the equation
AND to get ...<span class="expander"> <a>(more)</a></span></p></div>http://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/?comment=33917#post-id-33917See also [on Stackoverflow](http://stackoverflow.com/questions/38029680/sage-linear-algebra-in-finite-fields-goppa-codes).Sat, 25 Jun 2016 13:16:44 -0500http://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/?comment=33917#post-id-33917Answer by tmonteil for <div class="snippet"><p>Context:</p>
<p>I am trying to calculate a generator matrix for Goppa codes.</p>
<p>We are working in GF(16), e is a generator of GF(16), and we are given the polynomial
g = (x+e)*(x+e^14)</p>
<pre><code>F.<e> = GF(16)
p = e.minpoly()
p
R.<x> = PolynomialRing(F)
g=(x+e)*(x+e^14)
</code></pre>
<p>i calculate the parity check matrix with coefficients in GF(16) as follows</p>
<pre><code>H = matrix(F,2,12)
for i in range (2,14):
f=-((g(x)-g(e^i))/(x-e^i))*(1/g(e^i))
print("i=%s %s"%(i,f))
ff=R(f) # coerce to polynomial with canonical injection
H[0,i-2]=ff.list()[0]
H[1,i-2]=ff.list()[1]
</code></pre>
<p>i=2 (e^3 + e^2 + e + 1)*x + e^3 + e</p>
<p>i=3 (e^3 + e^2)*x + e^2 + e + 1</p>
<p>i=4 (e^3 + e^2)*x + e^3 + e</p>
<p>i=5 e*x + e^3 + 1</p>
<p>i=6 (e^3 + e^2 + e)*x + e^3 + e^2</p>
<p>i=7 x</p>
<p>i=8 (e^3 + 1)*x + e^2 + e + 1</p>
<p>i=9 (e^2 + 1)*x + e^2 + 1</p>
<p>i=10 (e^3 + e^2 + e)*x + e^2</p>
<p>i=11 (e^3 + 1)*x + e^3 + e + 1</p>
<p>i=12 (e^3 + e^2 + e + 1)*x + e^3 + 1</p>
<p>i=13 e*x + e^3 + e^2</p>
<p>H is a 2x12 matrix in GF(16)
now I am are interested in getting a 8x12 matrix corresponding to 8 equations. We get 4 equations for each row of H.
i am considering a vector of size 12 of unknowns c=(c1,c2,...,12) [with possible values 0 or 1], and for each row, we will look at the equation row_i * c=0 and we group terms corresponding to 1,e,e^2,e^3 and because this is a basis of GF(16) we know that the coefficients of 1,e,e^2,e^3 are 0. I want to extract those equations.</p>
<pre><code>var('c1','c2','c3','c4','c5','c6','c7','c8','c9','c10','c11','c12')
C=matrix([[c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12]])
H*C.T
</code></pre>
<p>[ (e^3 + e)<em>c1 + (e^3 + e + 1)</em>c10 + (e^3 + 1)<em>c11 + (e^3
+ e^2)</em>c12 + (e^2 + e + 1)<em>c2 + (e^3 + e)</em>c3 + (e^3 + 1)<em>c4 + (e^3 +
e^2)</em>c5 + (e^2 + e + 1)<em>c7 + (e^2 + 1)</em>c8 + e^2<em>c9]
[(e^3 + e^2 + e + 1)</em>c1 + (e^3 + 1)<em>c10 + (e^3 + e^2 + e + 1)</em>c11 +
e<em>c12 + (e^3 + e^2)</em>c2 + (e^3 + e^2)<em>c3 + e</em>c4 + (e^3 + e^2 + e)<em>c5 + c6
+ (e^3 + 1)</em>c7 + (e^2 + 1)<em>c8 + (e^3 + e^2 + e)</em>c9]</p>
<p>for example for the first row the equation corresponding to e should be
(c1+c10+c2+c3+c7 =0)</p>
<p>could u please tell me how to recover the equation
AND to get ...<span class="expander"> <a>(more)</a></span></p></div> http://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/?answer=33918#post-id-33918Given an element of the finite field `F`, you can see it as a vector over its prime subfield as follows:
sage: x = 1+e+e^3
sage: x
e^3 + e + 1
sage: vector(x)
(1, 1, 0, 1)
sage: vector(x).parent()
Vector space of dimension 4 over Finite Field of size 2
So you can "unfold" you matrix as follows;
sage: K = GF(2)
sage: M = Matrix(K,8,12)
sage: for i in range(2):
....: for j in range(4):
....: for k in range(12):
....: M[4*i+j,k] = vector(H[i,k])[j]
sage: M
[0 1 0 1 0 0 1 1 0 1 1 0]
[1 1 1 0 0 0 1 0 0 1 0 0]
[0 1 0 0 1 0 1 1 1 0 0 1]
[1 0 1 1 1 0 0 0 0 1 1 1]
[1 0 0 0 0 1 1 1 0 1 1 0]
[1 0 0 1 1 0 0 0 1 0 1 1]
[1 1 1 0 1 0 0 1 1 0 1 0]
[1 1 1 0 1 0 1 0 1 1 1 0]
You can check that the second row corresponds to your equation `c1+c10+c2+c3+c7 =0` (note however that it is usually more practical and more Python-friendly, to have indices starting at 0, not 1).
Then you can get the right kernel of `M` as follows:
sage: M.right_kernel()
Vector space of degree 12 and dimension 4 over Finite Field of size 2
Basis matrix:
[1 0 0 0 1 1 0 1 1 1 0 1]
[0 1 0 0 1 1 1 1 0 0 1 0]
[0 0 1 0 1 0 1 1 1 0 0 0]
[0 0 0 1 1 1 0 0 0 0 1 1]
**EDIT**
You can get the kernel as the rows of a matrix as follows:
sage: B = M.right_kernel().basis_matrix()
sage: B
[1 0 0 0 1 1 0 1 1 1 0 1]
[0 1 0 0 1 1 1 1 0 0 1 0]
[0 0 1 0 1 0 1 1 1 0 0 0]
[0 0 0 1 1 1 0 0 0 0 1 1]
Note that the vectors of the basis are rows of the matrix, so, if you want to combine them with `M`, since we took the right kernel, you have to take the transpose of it:
sage: B.T
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
[1 1 1 1]
[1 1 0 1]
[0 1 1 0]
[1 1 1 0]
[1 0 1 0]
[1 0 0 0]
[0 1 0 1]
[1 0 0 1]
sage: M*B.T
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
sage: B*M.T
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
Sat, 25 Jun 2016 17:29:31 -0500http://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/?answer=33918#post-id-33918Comment by tmonteil for <div class="snippet"><p>Given an element of the finite field <code>F</code>, you can see it as a vector over its prime subfield as follows:</p>
<pre><code>sage: x = 1+e+e^3
sage: x
e^3 + e + 1
sage: vector(x)
(1, 1, 0, 1)
sage: vector(x).parent()
Vector space of dimension 4 over Finite Field of size 2
</code></pre>
<p>So you can "unfold" you matrix as follows;</p>
<pre><code>sage: K = GF(2)
sage: M = Matrix(K,8,12)
sage: for i in range(2):
....: for j in range(4):
....: for k in range(12):
....: M[4*i+j,k] = vector(H[i,k])[j]
sage: M
[0 1 0 1 0 0 1 1 0 1 1 0]
[1 1 1 0 0 0 1 0 0 1 0 0]
[0 1 0 0 1 0 1 1 1 0 0 1]
[1 0 1 1 1 0 0 0 0 1 1 1]
[1 0 0 0 0 1 1 1 0 1 1 0]
[1 0 0 1 1 0 0 0 1 0 1 1]
[1 1 1 0 1 0 0 1 1 0 1 0]
[1 1 1 0 1 0 1 0 1 1 1 0]
</code></pre>
<p>You can check that the second row corresponds to your equation <code>c1+c10+c2+c3+c7 =0</code> (note however that it is usually more practical and more Python-friendly, to have indices starting at 0, not 1).</p>
<p>Then you can get the right kernel of <code>M</code> as follows:</p>
<pre><code>sage: M.right_kernel()
Vector space of degree 12 and dimension 4 over Finite Field of size 2
Basis matrix:
[1 0 0 0 1 1 0 1 1 1 0 1]
[0 1 0 0 1 1 1 1 0 0 1 0]
[0 0 1 0 1 0 1 1 1 0 0 0]
[0 0 0 1 1 1 0 0 0 0 1 1]
</code></pre>
<p><strong>EDIT</strong></p>
<p>You can get the kernel as the rows of a matrix as follows:</p>
<pre><code>sage: B = M.right_kernel().basis_matrix()
sage: B
[1 0 0 0 1 1 0 1 1 1 0 1]
[0 1 0 0 1 1 1 1 0 0 1 0]
[0 0 1 0 1 0 1 1 1 0 0 0]
[0 0 0 1 1 1 0 0 0 0 1 1]
</code></pre>
<p>Note that the vectors of the basis are rows of the matrix, so, if you want to combine them with <code>M</code>, since we took the right kernel, you have to take the transpose of it:</p>
<pre><code>sage: B.T
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
[1 1 1 1]
[1 1 0 1]
[0 1 1 0]
[1 1 1 0]
[1 0 1 0]
[1 0 0 0]
[0 1 0 1]
[1 0 0 1]
sage: M*B.T
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 ...</code></pre><span class="expander"> <a>(more)</a></span></div>http://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/?comment=33959#post-id-33959By the way, note that there will be some Sage days about coding theory, including Goppa codes, in august in France, see https://wiki.sagemath.org/days75Wed, 29 Jun 2016 06:19:21 -0500http://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/?comment=33959#post-id-33959Comment by fagui for <div class="snippet"><p>Given an element of the finite field <code>F</code>, you can see it as a vector over its prime subfield as follows:</p>
<pre><code>sage: x = 1+e+e^3
sage: x
e^3 + e + 1
sage: vector(x)
(1, 1, 0, 1)
sage: vector(x).parent()
Vector space of dimension 4 over Finite Field of size 2
</code></pre>
<p>So you can "unfold" you matrix as follows;</p>
<pre><code>sage: K = GF(2)
sage: M = Matrix(K,8,12)
sage: for i in range(2):
....: for j in range(4):
....: for k in range(12):
....: M[4*i+j,k] = vector(H[i,k])[j]
sage: M
[0 1 0 1 0 0 1 1 0 1 1 0]
[1 1 1 0 0 0 1 0 0 1 0 0]
[0 1 0 0 1 0 1 1 1 0 0 1]
[1 0 1 1 1 0 0 0 0 1 1 1]
[1 0 0 0 0 1 1 1 0 1 1 0]
[1 0 0 1 1 0 0 0 1 0 1 1]
[1 1 1 0 1 0 0 1 1 0 1 0]
[1 1 1 0 1 0 1 0 1 1 1 0]
</code></pre>
<p>You can check that the second row corresponds to your equation <code>c1+c10+c2+c3+c7 =0</code> (note however that it is usually more practical and more Python-friendly, to have indices starting at 0, not 1).</p>
<p>Then you can get the right kernel of <code>M</code> as follows:</p>
<pre><code>sage: M.right_kernel()
Vector space of degree 12 and dimension 4 over Finite Field of size 2
Basis matrix:
[1 0 0 0 1 1 0 1 1 1 0 1]
[0 1 0 0 1 1 1 1 0 0 1 0]
[0 0 1 0 1 0 1 1 1 0 0 0]
[0 0 0 1 1 1 0 0 0 0 1 1]
</code></pre>
<p><strong>EDIT</strong></p>
<p>You can get the kernel as the rows of a matrix as follows:</p>
<pre><code>sage: B = M.right_kernel().basis_matrix()
sage: B
[1 0 0 0 1 1 0 1 1 1 0 1]
[0 1 0 0 1 1 1 1 0 0 1 0]
[0 0 1 0 1 0 1 1 1 0 0 0]
[0 0 0 1 1 1 0 0 0 0 1 1]
</code></pre>
<p>Note that the vectors of the basis are rows of the matrix, so, if you want to combine them with <code>M</code>, since we took the right kernel, you have to take the transpose of it:</p>
<pre><code>sage: B.T
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
[1 1 1 1]
[1 1 0 1]
[0 1 1 0]
[1 1 1 0]
[1 0 1 0]
[1 0 0 0]
[0 1 0 1]
[1 0 0 1]
sage: M*B.T
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 ...</code></pre><span class="expander"> <a>(more)</a></span></div>http://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/?comment=33926#post-id-33926thank you very much for this refresher...it was very very helpful !!!Sun, 26 Jun 2016 06:12:05 -0500http://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/?comment=33926#post-id-33926Comment by tmonteil for <div class="snippet"><p>Given an element of the finite field <code>F</code>, you can see it as a vector over its prime subfield as follows:</p>
<pre><code>sage: x = 1+e+e^3
sage: x
e^3 + e + 1
sage: vector(x)
(1, 1, 0, 1)
sage: vector(x).parent()
Vector space of dimension 4 over Finite Field of size 2
</code></pre>
<p>So you can "unfold" you matrix as follows;</p>
<pre><code>sage: K = GF(2)
sage: M = Matrix(K,8,12)
sage: for i in range(2):
....: for j in range(4):
....: for k in range(12):
....: M[4*i+j,k] = vector(H[i,k])[j]
sage: M
[0 1 0 1 0 0 1 1 0 1 1 0]
[1 1 1 0 0 0 1 0 0 1 0 0]
[0 1 0 0 1 0 1 1 1 0 0 1]
[1 0 1 1 1 0 0 0 0 1 1 1]
[1 0 0 0 0 1 1 1 0 1 1 0]
[1 0 0 1 1 0 0 0 1 0 1 1]
[1 1 1 0 1 0 0 1 1 0 1 0]
[1 1 1 0 1 0 1 0 1 1 1 0]
</code></pre>
<p>You can check that the second row corresponds to your equation <code>c1+c10+c2+c3+c7 =0</code> (note however that it is usually more practical and more Python-friendly, to have indices starting at 0, not 1).</p>
<p>Then you can get the right kernel of <code>M</code> as follows:</p>
<pre><code>sage: M.right_kernel()
Vector space of degree 12 and dimension 4 over Finite Field of size 2
Basis matrix:
[1 0 0 0 1 1 0 1 1 1 0 1]
[0 1 0 0 1 1 1 1 0 0 1 0]
[0 0 1 0 1 0 1 1 1 0 0 0]
[0 0 0 1 1 1 0 0 0 0 1 1]
</code></pre>
<p><strong>EDIT</strong></p>
<p>You can get the kernel as the rows of a matrix as follows:</p>
<pre><code>sage: B = M.right_kernel().basis_matrix()
sage: B
[1 0 0 0 1 1 0 1 1 1 0 1]
[0 1 0 0 1 1 1 1 0 0 1 0]
[0 0 1 0 1 0 1 1 1 0 0 0]
[0 0 0 1 1 1 0 0 0 0 1 1]
</code></pre>
<p>Note that the vectors of the basis are rows of the matrix, so, if you want to combine them with <code>M</code>, since we took the right kernel, you have to take the transpose of it:</p>
<pre><code>sage: B.T
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
[1 1 1 1]
[1 1 0 1]
[0 1 1 0]
[1 1 1 0]
[1 0 1 0]
[1 0 0 0]
[0 1 0 1]
[1 0 0 1]
sage: M*B.T
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 ...</code></pre><span class="expander"> <a>(more)</a></span></div>http://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/?comment=33924#post-id-33924- NO there are less bases than that:
- for the first vector of the basis, you can chose any nonzero vector : `2^4-1 = 2^4 - 2^0` choices
- for the second vector, you can chose any vector not colinear to the first : `2^4 - 2 = 2^4 - 2^1` choices
- for the third vector, you can chose any vector not in the plane generated by the first two vectors : `2^4 - 2^2` choices
- for the fourth vector, you can chose any vector not in the 3D-space generated by the first three vectors : `2^4 - 2^3`
So, the total number of ordered bases is `(2^4 - 2^3)*(2^4 - 2^2)*(2^4 - 2^2)*(2^4 - 1) = 17280`, so the total number of bases is `(2^4 - 2^3)*(2^4 - 2^2)*(2^4 - 2^2)*(2^4 - 1)/4! = 720`.Sun, 26 Jun 2016 04:24:43 -0500http://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/?comment=33924#post-id-33924Comment by tmonteil for <div class="snippet"><p>Given an element of the finite field <code>F</code>, you can see it as a vector over its prime subfield as follows:</p>
<pre><code>sage: x = 1+e+e^3
sage: x
e^3 + e + 1
sage: vector(x)
(1, 1, 0, 1)
sage: vector(x).parent()
Vector space of dimension 4 over Finite Field of size 2
</code></pre>
<p>So you can "unfold" you matrix as follows;</p>
<pre><code>sage: K = GF(2)
sage: M = Matrix(K,8,12)
sage: for i in range(2):
....: for j in range(4):
....: for k in range(12):
....: M[4*i+j,k] = vector(H[i,k])[j]
sage: M
[0 1 0 1 0 0 1 1 0 1 1 0]
[1 1 1 0 0 0 1 0 0 1 0 0]
[0 1 0 0 1 0 1 1 1 0 0 1]
[1 0 1 1 1 0 0 0 0 1 1 1]
[1 0 0 0 0 1 1 1 0 1 1 0]
[1 0 0 1 1 0 0 0 1 0 1 1]
[1 1 1 0 1 0 0 1 1 0 1 0]
[1 1 1 0 1 0 1 0 1 1 1 0]
</code></pre>
<p>You can check that the second row corresponds to your equation <code>c1+c10+c2+c3+c7 =0</code> (note however that it is usually more practical and more Python-friendly, to have indices starting at 0, not 1).</p>
<p>Then you can get the right kernel of <code>M</code> as follows:</p>
<pre><code>sage: M.right_kernel()
Vector space of degree 12 and dimension 4 over Finite Field of size 2
Basis matrix:
[1 0 0 0 1 1 0 1 1 1 0 1]
[0 1 0 0 1 1 1 1 0 0 1 0]
[0 0 1 0 1 0 1 1 1 0 0 0]
[0 0 0 1 1 1 0 0 0 0 1 1]
</code></pre>
<p><strong>EDIT</strong></p>
<p>You can get the kernel as the rows of a matrix as follows:</p>
<pre><code>sage: B = M.right_kernel().basis_matrix()
sage: B
[1 0 0 0 1 1 0 1 1 1 0 1]
[0 1 0 0 1 1 1 1 0 0 1 0]
[0 0 1 0 1 0 1 1 1 0 0 0]
[0 0 0 1 1 1 0 0 0 0 1 1]
</code></pre>
<p>Note that the vectors of the basis are rows of the matrix, so, if you want to combine them with <code>M</code>, since we took the right kernel, you have to take the transpose of it:</p>
<pre><code>sage: B.T
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
[1 1 1 1]
[1 1 0 1]
[0 1 1 0]
[1 1 1 0]
[1 0 1 0]
[1 0 0 0]
[0 1 0 1]
[1 0 0 1]
sage: M*B.T
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 ...</code></pre><span class="expander"> <a>(more)</a></span></div>http://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/?comment=33923#post-id-33923Reagrding your last question, i updated my answer. Regarding the other questions:
- YES a vector space usually have more than one basis
- YES there are 2^4 vectors in the subspace
- NO there are not all linearly independent, for example, the first row, the second row, and the sum of the two are not linearly independent
- by lack of space i answer the question about below the number of bases below.Sun, 26 Jun 2016 04:22:13 -0500http://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/?comment=33923#post-id-33923Comment by fagui for <div class="snippet"><p>Given an element of the finite field <code>F</code>, you can see it as a vector over its prime subfield as follows:</p>
<pre><code>sage: x = 1+e+e^3
sage: x
e^3 + e + 1
sage: vector(x)
(1, 1, 0, 1)
sage: vector(x).parent()
Vector space of dimension 4 over Finite Field of size 2
</code></pre>
<p>So you can "unfold" you matrix as follows;</p>
<pre><code>sage: K = GF(2)
sage: M = Matrix(K,8,12)
sage: for i in range(2):
....: for j in range(4):
....: for k in range(12):
....: M[4*i+j,k] = vector(H[i,k])[j]
sage: M
[0 1 0 1 0 0 1 1 0 1 1 0]
[1 1 1 0 0 0 1 0 0 1 0 0]
[0 1 0 0 1 0 1 1 1 0 0 1]
[1 0 1 1 1 0 0 0 0 1 1 1]
[1 0 0 0 0 1 1 1 0 1 1 0]
[1 0 0 1 1 0 0 0 1 0 1 1]
[1 1 1 0 1 0 0 1 1 0 1 0]
[1 1 1 0 1 0 1 0 1 1 1 0]
</code></pre>
<p>You can check that the second row corresponds to your equation <code>c1+c10+c2+c3+c7 =0</code> (note however that it is usually more practical and more Python-friendly, to have indices starting at 0, not 1).</p>
<p>Then you can get the right kernel of <code>M</code> as follows:</p>
<pre><code>sage: M.right_kernel()
Vector space of degree 12 and dimension 4 over Finite Field of size 2
Basis matrix:
[1 0 0 0 1 1 0 1 1 1 0 1]
[0 1 0 0 1 1 1 1 0 0 1 0]
[0 0 1 0 1 0 1 1 1 0 0 0]
[0 0 0 1 1 1 0 0 0 0 1 1]
</code></pre>
<p><strong>EDIT</strong></p>
<p>You can get the kernel as the rows of a matrix as follows:</p>
<pre><code>sage: B = M.right_kernel().basis_matrix()
sage: B
[1 0 0 0 1 1 0 1 1 1 0 1]
[0 1 0 0 1 1 1 1 0 0 1 0]
[0 0 1 0 1 0 1 1 1 0 0 0]
[0 0 0 1 1 1 0 0 0 0 1 1]
</code></pre>
<p>Note that the vectors of the basis are rows of the matrix, so, if you want to combine them with <code>M</code>, since we took the right kernel, you have to take the transpose of it:</p>
<pre><code>sage: B.T
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
[1 1 1 1]
[1 1 0 1]
[0 1 1 0]
[1 1 1 0]
[1 0 1 0]
[1 0 0 0]
[0 1 0 1]
[1 0 0 1]
sage: M*B.T
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 ...</code></pre><span class="expander"> <a>(more)</a></span></div>http://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/?comment=33920#post-id-33920last question:
the last object is
<class
'sage.modules.free_module.FreeModule_submodule_field_with_category'>
how do i get in a matrix object the basis matrix that is given in output ?
if i define `v=M.right_kernel()`
and do
sage: v*M.T
i get an error `TypeError: each element of basis must be in the ambient vector space`Sat, 25 Jun 2016 20:56:22 -0500http://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/?comment=33920#post-id-33920Comment by fagui for <div class="snippet"><p>Given an element of the finite field <code>F</code>, you can see it as a vector over its prime subfield as follows:</p>
<pre><code>sage: x = 1+e+e^3
sage: x
e^3 + e + 1
sage: vector(x)
(1, 1, 0, 1)
sage: vector(x).parent()
Vector space of dimension 4 over Finite Field of size 2
</code></pre>
<p>So you can "unfold" you matrix as follows;</p>
<pre><code>sage: K = GF(2)
sage: M = Matrix(K,8,12)
sage: for i in range(2):
....: for j in range(4):
....: for k in range(12):
....: M[4*i+j,k] = vector(H[i,k])[j]
sage: M
[0 1 0 1 0 0 1 1 0 1 1 0]
[1 1 1 0 0 0 1 0 0 1 0 0]
[0 1 0 0 1 0 1 1 1 0 0 1]
[1 0 1 1 1 0 0 0 0 1 1 1]
[1 0 0 0 0 1 1 1 0 1 1 0]
[1 0 0 1 1 0 0 0 1 0 1 1]
[1 1 1 0 1 0 0 1 1 0 1 0]
[1 1 1 0 1 0 1 0 1 1 1 0]
</code></pre>
<p>You can check that the second row corresponds to your equation <code>c1+c10+c2+c3+c7 =0</code> (note however that it is usually more practical and more Python-friendly, to have indices starting at 0, not 1).</p>
<p>Then you can get the right kernel of <code>M</code> as follows:</p>
<pre><code>sage: M.right_kernel()
Vector space of degree 12 and dimension 4 over Finite Field of size 2
Basis matrix:
[1 0 0 0 1 1 0 1 1 1 0 1]
[0 1 0 0 1 1 1 1 0 0 1 0]
[0 0 1 0 1 0 1 1 1 0 0 0]
[0 0 0 1 1 1 0 0 0 0 1 1]
</code></pre>
<p><strong>EDIT</strong></p>
<p>You can get the kernel as the rows of a matrix as follows:</p>
<pre><code>sage: B = M.right_kernel().basis_matrix()
sage: B
[1 0 0 0 1 1 0 1 1 1 0 1]
[0 1 0 0 1 1 1 1 0 0 1 0]
[0 0 1 0 1 0 1 1 1 0 0 0]
[0 0 0 1 1 1 0 0 0 0 1 1]
</code></pre>
<p>Note that the vectors of the basis are rows of the matrix, so, if you want to combine them with <code>M</code>, since we took the right kernel, you have to take the transpose of it:</p>
<pre><code>sage: B.T
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
[1 1 1 1]
[1 1 0 1]
[0 1 1 0]
[1 1 1 0]
[1 0 1 0]
[1 0 0 0]
[0 1 0 1]
[1 0 0 1]
sage: M*B.T
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 ...</code></pre><span class="expander"> <a>(more)</a></span></div>http://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/?comment=33919#post-id-33919thank you so much !!!!
as my linear algebra is a little bit rusty:
there is not ONE basis matrix right ? the function returns ONE basis among a (finite) number of them
for example, change the 2nd row by the addition of the 1st and 2 rows...
more exactly there are 2^4 vectors in that subspace, including the null vector, which all linearly independent (save for the null vector), and there are thus choose(15,4) possible basis.
correct ?Sat, 25 Jun 2016 20:21:56 -0500http://ask.sagemath.org/question/33915/linear-algebra-in-finite-fields-goppa-codes/?comment=33919#post-id-33919