# Ticket #10153(closed enhancement: invalid)

Opened 3 years ago

## Canonical generator matrices for linear codes and their automorphism groups

Reported by: Owned by: tfeulner wdj major sage-duplicate/invalid/wontfix coding theory Automorpism group, canonical representative rlm, burcin N/A Thomas Feulner

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

## Change History

### comment:1 Changed 3 years ago by wdj

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 3 years ago by tfeulner 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 3 years ago by rlm • Cc rlm added ### comment:4 follow-up: ↓ 5 Changed 3 years ago by wdj • Status changed from new to 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 2 years ago by tfeulner • Cc burcin 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 2 years ago by wdj 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 2 years ago by 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." 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 2 years ago by tfeulner better documentation, now using templates for wrapping the C++ code ### comment:8 in reply to: ↑ 7 Changed 2 years ago by tfeulner • Status changed from needs_work to 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 2 years ago by wdj 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 2 years ago by tfeulner

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 2 years ago by dimpase

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 months ago by tfeulner

• Status changed from needs_review to positive_review
• Milestone changed from sage-5.3 to sage-duplicate/invalid/wontfix

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 9 months ago by jdemeyer

• Status changed from positive_review to closed
• Reviewers set to Thomas Feulner
• Resolution set to invalid
• Authors Thomas Feulner deleted
Note: See TracTickets for help on using tickets.