Opened 12 years ago

Closed 10 years ago

# Canonical generator matrices for linear codes and their automorphism groups

Reported by: Owned by: Thomas Feulner David Joyner major sage-duplicate/invalid/wontfix coding theory Automorpism group, canonical representative Robert Miller, Burcin Erocal Thomas Feulner N/A

### Description

Let R be a finite ring (up to now: a finite field or Z4). A submodule of Rn is called a linear code of length n. Two linear codes C, C' over R of length n are equivalent, if there is

• a permutation pi in Sn
• a multiplication vector phi in R*n (R* the set of invertible elements)
• an automorphism alpha of R

with C' = (phi, pi, alpha) C and the action is defined via

(phi, pi, alpha) (c0, ..., cn-1) = ( phi0 alpha( cpi-1(0)) , ... , phin-1 alpha( cpi-1(n-1)) )

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.

### comment:1 Changed 12 years ago by David Joyner

Thanks for creating this!

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:

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  ### comment:2 Changed 12 years ago by Thomas Feulner I think this is fixed with the new patch. I am now using GMP, it was a 32-bit error and  5922201600  is the correct order. ### comment:3 Changed 12 years ago by Robert Miller Cc: Robert Miller added ### comment:4 follow-up: 5 Changed 12 years ago by David Joyner Status: new → needs_work 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. 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 = HammingCode?(3, GF(2)) sage: C.automorphism_group_binary_code() does? 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 = HammingCode?(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. Also, it is great that you linked your documentation into the manual. However, most of it is too vague - for example get_transporter() Returns the transporter element. ...  Could this be improved? I'm going to mark this as "needs work". ### comment:5 in reply to: 4 Changed 12 years ago by Thomas Feulner Cc: Burcin Erocal added Replying to wdj: 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. This was discussed in ticket:425. They decided to accept this minor annoyance. 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 = HammingCode?(3, GF(2)) sage: C.automorphism_group_binary_code() does? Now, there is a test which compares the result of both algorithms showing that the groups are equal. 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 = HammingCode?(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. 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 pr as a semidirect product. Maybe someone can give me a hint for improving the following example. 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  Also, it is great that you linked your documentation into the manual. However, most of it is too vague - for example  get_transporter() Returns the transporter element. ...  Could this be improved? I'm going to mark this as "needs work". Is this more precise? Maybe we can also discuss the natural way of returning the group elements. Mathematically correct via B-1 or user-friendly without inversion. I have implemented the second way, but I am not sure if the warning sections are sufficient. ### comment:6 Changed 12 years ago by David Joyner Installed fine on a 10.6.6 mac running 4.7.a1. However, there was the following doctest failure: 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  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")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? ### comment:7 follow-up: 8 Changed 12 years ago by David Joyner 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. "elments [A, B] and [A', B'] are multiplied componentwisely." --> "elements [A, B] and [A', B'] are multiplied componentwise." You say "Warning: The program ..." a few times. What program? get_automorphism_generators? 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? ### Changed 12 years ago by Thomas Feulner Attachment: trac_10153_canonical_generator_matrices.patch​ added better documentation, now using templates for wrapping the C++ code ### comment:8 in reply to: 7 Changed 12 years ago by Thomas Feulner Status: needs_work → needs_review The new patch fixes the doctest failures. They were forced by different generator matrices of the Hamming Code on different platforms. Replying to wdj: 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. "elments [A, B] and [A', B'] are multiplied componentwisely." --> "elements [A, B] and [A', B'] are multiplied componentwise." Changed. You say "Warning: The program ..." a few times. What program? get_automorphism_generators? Changed. Now, the warning is linking to the corresponding functions. 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? I tried to link the documentation of this method to the documentation of the module via :mod:!sage.coding.code_can. But this didnt work. I have removed this sentences in the warnings since the OUTPUT sections of the methods will explain the group elements, too. ### comment:9 follow-up: 10 Changed 12 years ago by David Joyner I now get the following test failure (on a 10.6.6 mac running sage-4.7.a1): 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
**********************************************************************
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
`

### comment:10 in reply to:  9 Changed 12 years ago by Thomas Feulner

I now get the following test failure (on a 10.6.6 mac running sage-4.7.a1)

Sorry, the patch changed a single line linear_code.py, which was not my intention.

### comment:11 Changed 12 years ago by Dima Pasechnik

IMHO, it would be good to represent the resulting group generators as sparse matrices. (Or, perhaps, a new Sage type "MonomialMatrix?" ?)

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).

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?)

I also noticed that the patch mixes up Unix/Windows? encoded files. Can this be streamlined?

### comment:12 Changed 10 years ago by Thomas Feulner

Milestone: sage-5.3 → sage-duplicate/invalid/wontfix needs_review → positive_review

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.

### comment:13 Changed 10 years ago by Jeroen Demeyer

Authors: Thomas Feulner → invalid → Thomas Feulner positive_review → closed
Note: See TracTickets for help on using tickets.