Canonical generator matrices for linear codes and their automorphism groups

[tfeulner]

Let R be a finite ring (up to now: a finite field or Z₄). A submodule of Rⁿ 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 S_n
• a multiplication vector phi in R*ⁿ (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) (c₀, ..., c_n-1) = ( phi₀ alpha( c_pi^-1(0)) , ... , phi_n-1 alpha( c_pi^-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.

[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

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

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

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

[tfeulner]

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 p^r 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.

[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?}

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

[tfeulner]

better documentation, now using templates for wrapping the C++ code

[tfeulner]

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.

[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
**********************************************************************
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

[tfeulner]

Replying to wdj:

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.

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

[tfeulner]

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.