Sage: Ticket #10153: Canonical generator matrices for linear codes and their automorphism groups
https://trac.sagemath.org/ticket/10153
<p>
Let R be a finite ring (up to now: a finite field or Z<sub>4</sub>). A submodule of R<sup>n</sup> is called a linear code of length n. Two linear codes C, C' over R of length n are equivalent, if there is
</p>
<ul><li>a permutation pi in S<sub>n</sub>
</li><li>a multiplication vector phi in R*<sup>n</sup> (R* the set of invertible elements)
</li><li>an automorphism alpha of R
</li></ul><p>
with C' = (phi, pi, alpha) C and the action is defined via
</p>
<p>
(phi, pi, alpha) (c<sub>0</sub>, ..., c<sub>n-1</sub>) = ( phi<sub>0</sub> alpha( c<sub>pi<sup>-1</sup>(0)</sub>) , ... , phi<sub>n-1</sub> alpha( c<sub>pi<sup>-1</sup>(n-1)</sub>) )
</p>
<p>
This patch adds an algorithm for calculating a unique representative within the equivalence class of a given linear code (returning some unique generator matrix). The algorithm calculates the automorphism group of the code as a byproduct.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/10153
Trac 1.1.6wdjSat, 23 Oct 2010 20:25:34 GMT
https://trac.sagemath.org/ticket/10153#comment:1
https://trac.sagemath.org/ticket/10153#comment:1
<p>
Thanks for creating this!
</p>
<p>
Haven't had time to look at this closely but I did test it out to see if it
would apply okay. On a 10.6.4 mac, I got this failure:
</p>
<pre class="wiki">hera:sage-4.6.rc0 davidjoyner$ ./sage -t -force_lib "devel/sage/sage/coding/code_can.pyx"
sage -t -force_lib "devel/sage/sage/coding/code_can.pyx"
**********************************************************************
File "/Volumes/Bay2/sagefiles2/sage-4.6.rc0/devel/sage/sage/coding/code_can.pyx", line 486:
sage: canonizer.get_autom_order()
Expected:
1627234304
Got:
5922201600
**********************************************************************
1 items had failures:
1 of 16 in __main__.example_14
***Test Failed*** 1 failures.
For whitespace errors, see the file /Users/davidjoyner/.sage//tmp/.doctest_code_can.py
[12.6 s]
----------------------------------------------------------------------
The following tests failed:
sage -t -force_lib "devel/sage/sage/coding/code_can.pyx"
Total time for all tests: 12.6 seconds
</pre>
TickettfeulnerFri, 29 Oct 2010 10:12:14 GMT
https://trac.sagemath.org/ticket/10153#comment:2
https://trac.sagemath.org/ticket/10153#comment:2
<p>
I think this is fixed with the new patch. I am now using GMP, it was a 32-bit error and
</p>
<pre class="wiki"> 5922201600
</pre><p>
is the correct order.
</p>
TicketrlmThu, 25 Nov 2010 16:38:14 GMTcc set
https://trac.sagemath.org/ticket/10153#comment:3
https://trac.sagemath.org/ticket/10153#comment:3
<ul>
<li><strong>cc</strong>
<em>rlm</em> added
</li>
</ul>
TicketwdjSun, 12 Dec 2010 01:55:05 GMTstatus changed
https://trac.sagemath.org/ticket/10153#comment:4
https://trac.sagemath.org/ticket/10153#comment:4
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_work</em>
</li>
</ul>
<p>
This applied fine to sage 4.6.1.a2 on a 10.6.5 mac, however there were some compiler warnings of the form
"warning: command line option "-Wstrict-prototypes" is valid for C/ObjC but not for C++".
I don't know if these are important. The patch passes sage -testall.
</p>
<p>
The patch is huge. I have the following questions:
</p>
<p>
1) Do you have any tests which compare your output to the output of Robert Miller's
automorphism groups in the case of binary linear codes? For example, does your
program yield the same result that
sage: C = <a class="missing wiki">HammingCode?</a>(3, GF(2))
sage: C.automorphism_group_binary_code()
does?
</p>
<p>
2) Do you have any tests which compare your output to the output of the permutation
automorphism groups in the case of non-binary linear codes? For example, does your program yield the same result that
sage: C = <a class="missing wiki">HammingCode?</a>(2, GF(3))
sage: C.permutation_automorphism_group()
Permutation Group with generators [(1,2,3)]
does?
</p>
<p>
It seems not. If that is true, it would be great to add them to the
tests.
</p>
<p>
Also, it is great that you linked your documentation into the manual.
However, most of it is too vague - for example
</p>
<pre class="wiki">get_transporter()
Returns the transporter element.
...
</pre><p>
Could this be improved?
</p>
<p>
I'm going to mark this as "needs work".
</p>
TickettfeulnerMon, 21 Mar 2011 13:34:03 GMTcc changed
https://trac.sagemath.org/ticket/10153#comment:5
https://trac.sagemath.org/ticket/10153#comment:5
<ul>
<li><strong>cc</strong>
<em>burcin</em> added
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10153#comment:4" title="Comment 4">wdj</a>:
</p>
<blockquote class="citation">
<p>
This applied fine to sage 4.6.1.a2 on a 10.6.5 mac, however there were some compiler warnings of the form "warning: command line option "-Wstrict-prototypes" is valid for C/ObjC but not for C++". I don't know if these are important. The patch passes sage -testall.
</p>
</blockquote>
<p>
This was discussed in <a class="closed ticket" href="https://trac.sagemath.org/ticket/425" title="enhancement: Squash warning cause by using "-Wstrict-prototypes" in cython (closed: invalid)">ticket:425</a>. They decided to accept this <em>minor annoyance</em>.
</p>
<blockquote class="citation">
<p>
The patch is huge. I have the following questions: 1) Do you have any tests which compare your output to the output of Robert Miller's automorphism groups in the case of binary linear codes? For example, does your program yield the same result that sage: C = <a class="missing wiki">HammingCode?</a>(3, GF(2)) sage: C.automorphism_group_binary_code() does?
</p>
</blockquote>
<p>
Now, there is a test which compares the result of both algorithms showing that the groups are equal.
</p>
<blockquote class="citation">
<p>
2) Do you have any tests which compare your output to the output of the permutation automorphism groups in the case of non-binary linear codes? For example, does your program yield the same result that sage: C = <a class="missing wiki">HammingCode?</a>(2, GF(3)) sage: C.permutation_automorphism_group() Permutation Group with generators [(1,2,3)] does? It seems not. If that is true, it would be great to add them to the tests.
</p>
</blockquote>
<p>
The new examples also try to show the differences in this case. Furthermore, I had some problems in constructing the automorphism group in the case of a finite field of order p<sup>r</sup> as a semidirect product. Maybe someone can give me a hint for improving the following example.
</p>
<pre class="wiki">sage: GammaGF4 = HammingCode(3, GF(4, 'a') ).check_mat()
sage: canonizer.start_matrix(GammaGF4)
sage: gens = canonizer.get_automorphism_generators()
sage: V = VectorSpace(GF(4, 'a'), GammaGF4.nrows() ) # long time
sage: elts = V.list() # long time
sage: A_correct = PermutationGroup([ PermutationGroupElement( [elts.index( x.apply_map(g[2])*g[0].transpose())+1 for x in elts]) for g in gens ]) # long time
sage: A_correct.order() == canonizer.get_autom_order() # long time
True
</pre><blockquote class="citation">
<p>
Also, it is great that you linked your documentation into the manual. However, most of it is too vague - for example <code> get_transporter() Returns the transporter element. ... </code> Could this be improved? I'm going to mark this as "needs work".
</p>
</blockquote>
<p>
Is this more precise? Maybe we can also discuss the <em>natural</em> way of returning the group elements. Mathematically correct via B<sup>-1</sup> or user-friendly without inversion. I have implemented the second way, but I am not sure if the warning sections are sufficient.
</p>
TicketwdjTue, 22 Mar 2011 10:41:20 GMT
https://trac.sagemath.org/ticket/10153#comment:6
https://trac.sagemath.org/ticket/10153#comment:6
<p>
Installed fine on a 10.6.6 mac running 4.7.a1. However, there was the following doctest failure:
</p>
<pre class="wiki">sage -t -force_lib "devel/sage/sage/coding/code_can.pyx"
**********************************************************************
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/devel/sage/sage/coding/code_can.pyx", line 495:
sage: canonizer._latex_()
Expected:
'\\textnormal{Canonization object for linear codes over finite fields or } `\\ZZ_4`\\textnormal{. The actual code is generated by}\\\\\\left(\\begin{array}{rrrrrrr}\n1 & 0 & 0 & 1 & 0 & 1 & 0 \\\\\n0 & 1 & 0 & 1 & 0 & 1 & 1 \\\\\n0 & 0 & 1 & 1 & 0 & 0 & 1 \\\\\n0 & 0 & 0 & 0 & 1 & 1 & 1\n\\end{array}\\right)'
Got:
'\\textnormal{Canonization object for linear codes over finite fields or } `\\ZZ_4`\\textnormal{. The actual code is generated by}\\\\\\left(\\begin{array}{rrrrrrr}\n1 & 0 & 0 & 0 & 0 & 1 & 1 \\\\\n0 & 1 & 0 & 0 & 1 & 0 & 1 \\\\\n0 & 0 & 1 & 0 & 1 & 1 & 0 \\\\\n0 & 0 & 0 & 1 & 1 & 1 & 1\n\\end{array}\\right)'
**********************************************************************
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/devel/sage/sage/coding/code_can.pyx", line 358:
sage: [a[0] * Gamma.apply_morphism(a[2]) * a[1] == Gamma for a in gens]
Expected:
[True, True, True, True, True, True, True, True, True, True, True, True, True, True, True]
Got:
[True, True, True, True, True, True, True, True, True, True, True, True, True, True]
**********************************************************************
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/devel/sage/sage/coding/code_can.pyx", line 476:
sage: repr(canonizer)
Expected:
'Canonization object for linear codes over finite fields or `\\ZZ_4`. The actual code is generated by\n[1 0 0 1 0 1 0]\n[0 1 0 1 0 1 1]\n[0 0 1 1 0 0 1]\n[0 0 0 0 1 1 1]'
Got:
'Canonization object for linear codes over finite fields or `\\ZZ_4`. The actual code is generated by\n[1 0 0 0 0 1 1]\n[0 1 0 0 1 0 1]\n[0 0 1 0 1 1 0]\n[0 0 0 1 1 1 1]'
**********************************************************************
3 items had failures:
1 of 7 in __main__.example_10
1 of 44 in __main__.example_6
1 of 7 in __main__.example_9
***Test Failed*** 3 failures.
For whitespace errors, see the file /Users/davidjoyner/.sage//tmp/.doctest_code_can.py
[43.1 s]
----------------------------------------------------------------------
The following tests failed:
sage -t -force_lib "devel/sage/sage/coding/code_can.pyx"
Total time for all tests: 43.2 seconds
</pre><p>
Honestly, I'm not sure the best way of returning the component of the automorphism group which corresponds to field automorohisms. Sage does not seem to have the Galois action on a vector space such as GF(4,"a")<sup>3 implemented. You can try to return an element of this component as a tuple of integers which give the exponents of a Frobenius action. You might also just return it as a separate abelian group. There are probably other ideas out there too. How does Magma do it?
</sup></p>
TicketwdjTue, 22 Mar 2011 17:20:22 GMT
https://trac.sagemath.org/ticket/10153#comment:7
https://trac.sagemath.org/ticket/10153#comment:7
<p>
Just a few minor comments on the documentation, which is much better.
</p>
<p>
"Canonization of linear codes over finite rings (we are only supporting finite fields and \ZZ_4)" The first sentence becomes the title. It would be nicer to simply have "Canonization of linear codes over finite rings" and add the parenthetical remark later.
</p>
<p>
"elments [A, B] and [A', B'] are multiplied componentwisely." --> "elements [A, B] and [A', B'] are multiplied componentwise."
</p>
<p>
You say "Warning: The program ..." a few times. What program? <code>get_automorphism_generators</code>?
</p>
<p>
You say "See sage.coding.code_can for the interpretation of the group elements." a few times. What does this mean exactly? I am looking at the documentation of that module. Do you mean read the source code?
</p>
TickettfeulnerFri, 25 Mar 2011 13:38:06 GMTattachment set
https://trac.sagemath.org/ticket/10153
https://trac.sagemath.org/ticket/10153
<ul>
<li><strong>attachment</strong>
set to <em>trac_10153_canonical_generator_matrices.patch</em>
</li>
</ul>
<p>
better documentation, now using templates for wrapping the C++ code
</p>
TickettfeulnerFri, 25 Mar 2011 13:51:09 GMTstatus changed
https://trac.sagemath.org/ticket/10153#comment:8
https://trac.sagemath.org/ticket/10153#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
The new patch fixes the doctest failures. They were forced by different generator matrices of the Hamming Code on different platforms.
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10153#comment:7" title="Comment 7">wdj</a>:
</p>
<blockquote class="citation">
<p>
Just a few minor comments on the documentation, which is much better. "Canonization of linear codes over finite rings (we are only supporting finite fields and \ZZ_4)" The first sentence becomes the title. It would be nicer to simply have "Canonization of linear codes over finite rings" and add the parenthetical remark later.
</p>
</blockquote>
<blockquote class="citation">
<p>
"elments [A, B] and [A', B'] are multiplied componentwisely." --> "elements [A, B] and [A', B'] are multiplied componentwise."
</p>
</blockquote>
<p>
Changed.
</p>
<blockquote class="citation">
<p>
You say "Warning: The program ..." a few times. What program? <code>get_automorphism_generators</code>?
</p>
</blockquote>
<p>
Changed. Now, the warning is linking to the corresponding functions.
</p>
<blockquote class="citation">
<p>
You say "See sage.coding.code_can for the interpretation of the group elements." a few times. What does this mean exactly? I am looking at the documentation of that module. Do you mean read the source code?
</p>
</blockquote>
<p>
I tried to link the documentation of this method to the documentation of the module via :mod:!`sage.coding.code_can<code>. But this didn</code>t work. I have removed this sentences in the warnings since the OUTPUT sections of the methods will explain the group elements, too.
</p>
TicketwdjSat, 26 Mar 2011 20:19:41 GMT
https://trac.sagemath.org/ticket/10153#comment:9
https://trac.sagemath.org/ticket/10153#comment:9
<p>
I now get the following test failure (on a 10.6.6 mac running sage-4.7.a1):
</p>
<pre class="wiki">she:sage-4.7.alpha1 davidjoyner$ ./sage -t -force_lib "devel/sage/sage/coding/linear_code.py"
sage -t -force_lib "devel/sage/sage/coding/linear_code.py"
**********************************************************************
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/devel/sage/sage/coding/linear_code.py", line 1860:
sage: G = C.permutation_automorphism_group() # this should take < 5 seconds
Exception raised:
Traceback (most recent call last):
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/bin/ncadoctest.py", line 1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/bin/sagedoctest.py", line 38, in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/bin/ncadoctest.py", line 1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_42[11]>", line 1, in <module>
G = C.permutation_automorphism_group() # this should take < 5 seconds###line 1860:
sage: G = C.permutation_automorphism_group() # this should take < 5 seconds
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/lib/python/site-packages/sage/misc/decorators.py", line 573, in wrapper
return func(*args, **kwds)
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/lib/python/site-packages/sage/coding/linear_code.py", line 1949, in permutation_automorphism_group
MS = MatrixSpace(F,len(Cwt),n)
NameError: global name 'Cwt' is not defined
**********************************************************************
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/devel/sage/sage/coding/linear_code.py", line 1861:
sage: G.is_isomorphic(M11) # this should take < 5 seconds
Expected:
True
Got:
False
**********************************************************************
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/devel/sage/sage/coding/linear_code.py", line 1875:
sage: C.permutation_automorphism_group(algorithm="partition")
Exception raised:
Traceback (most recent call last):
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/bin/ncadoctest.py", line 1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/bin/sagedoctest.py", line 38, in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/bin/ncadoctest.py", line 1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_42[17]>", line 1, in <module>
C.permutation_automorphism_group(algorithm="partition")###line 1875:
sage: C.permutation_automorphism_group(algorithm="partition")
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/lib/python/site-packages/sage/misc/decorators.py", line 573, in wrapper
return func(*args, **kwds)
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/lib/python/site-packages/sage/coding/linear_code.py", line 1949, in permutation_automorphism_group
MS = MatrixSpace(F,len(Cwt),n)
NameError: global name 'Cwt' is not defined
**********************************************************************
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/devel/sage/sage/coding/linear_code.py", line 1879:
sage: C.permutation_automorphism_group(algorithm="partition")
Exception raised:
Traceback (most recent call last):
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/bin/ncadoctest.py", line 1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/bin/sagedoctest.py", line 38, in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/bin/ncadoctest.py", line 1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_42[19]>", line 1, in <module>
C.permutation_automorphism_group(algorithm="partition")###line 1879:
sage: C.permutation_automorphism_group(algorithm="partition")
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/lib/python/site-packages/sage/misc/decorators.py", line 573, in wrapper
return func(*args, **kwds)
File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/lib/python/site-packages/sage/coding/linear_code.py", line 1949, in permutation_automorphism_group
MS = MatrixSpace(F,len(Cwt),n)
NameError: global name 'Cwt' is not defined
**********************************************************************
1 items had failures:
4 of 22 in __main__.example_42
***Test Failed*** 4 failures.
For whitespace errors, see the file /Users/davidjoyner/.sage//tmp/.doctest_linear_code.py
[17.4 s]
----------------------------------------------------------------------
The following tests failed:
sage -t -force_lib "devel/sage/sage/coding/linear_code.py"
Total time for all tests: 17.4 seconds
</pre>
TickettfeulnerMon, 28 Mar 2011 07:02:39 GMT
https://trac.sagemath.org/ticket/10153#comment:10
https://trac.sagemath.org/ticket/10153#comment:10
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10153#comment:9" title="Comment 9">wdj</a>:
</p>
<blockquote class="citation">
<p>
I now get the following test failure (on a 10.6.6 mac running sage-4.7.a1)
</p>
</blockquote>
<p>
Sorry, the patch changed a single line linear_code.py, which was not my intention.<br />
</p>
TickettfeulnerMon, 28 Mar 2011 07:03:12 GMTattachment set
https://trac.sagemath.org/ticket/10153
https://trac.sagemath.org/ticket/10153
<ul>
<li><strong>attachment</strong>
set to <em>trac_10153_canonical_generator_matrices.2.patch</em>
</li>
</ul>
TicketdimpaseSat, 07 May 2011 05:15:02 GMT
https://trac.sagemath.org/ticket/10153#comment:11
https://trac.sagemath.org/ticket/10153#comment:11
<p>
IMHO, it would be good to represent the resulting group generators as sparse matrices.
(Or, perhaps, a new Sage type "<a class="missing wiki">MonomialMatrix?</a>" ?)
</p>
<p>
Did you check that parts of Boost you are using are not in Sage? (It would be more consistent to add them there, if needed, rather than to keep them here).
</p>
<p>
Would it be possible to factor out the code by Ralf Gugisch into a separate package/patch?
(well, that's certainly a lot of work, I know, so just wondering... I noticed he had some stuff on oriented matroids
implemented, is this a part of it?)
</p>
<p>
I also noticed that the patch mixes up <a class="missing wiki">Unix/Windows?</a> encoded files. Can this be streamlined?
</p>
TickettfeulnerTue, 04 Sep 2012 07:07:22 GMTstatus, milestone changed
https://trac.sagemath.org/ticket/10153#comment:12
https://trac.sagemath.org/ticket/10153#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-5.3</em> to <em>sage-duplicate/invalid/wontfix</em>
</li>
</ul>
<p>
The approach of adding a large C++ library is wrong. I started a new attempt written in cython, which uses Robert Millers partition refinement code. This will hopefully become an optional package soon.
</p>
TicketjdemeyerTue, 11 Sep 2012 15:10:40 GMTstatus changed; reviewer, resolution set; author deleted
https://trac.sagemath.org/ticket/10153#comment:13
https://trac.sagemath.org/ticket/10153#comment:13
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>reviewer</strong>
set to <em>Thomas Feulner</em>
</li>
<li><strong>resolution</strong>
set to <em>invalid</em>
</li>
<li><strong>author</strong>
<em>Thomas Feulner</em> deleted
</li>
</ul>
Ticket