Coset graph of linear codes

[gh-Ivo-Maffei]

Added method to the AbstractLinearCode class to compute the coset graph of a linear code.

[dimpase]

hamming -> Hamming

Also: we have abstract linear codes, to which you can attach different metrics. E.g. there are rank codes (on matrices, with distance being the rank of the difference), already implemented in Sage. So it would be good to have this implemented there too.

Provide a definition of the coset graph.

One day we should have additive codes (to have cosets of C, it suffices to have C an additive subgroup), so that we can also implement coset graphs for them, see e.g. ​https://arxiv.org/abs/1806.07069

[dimpase]

What kind of graph does this correspond to in terms of the dual to C code?

[gh-Ivo-Maffei]

First of all, I'm not sure the algorithm used is the best one. I could simply compute the cosets of C and work with their representatives, but I have a feeling it will be slower. That said, I think the algorithm relies on C being a set of vectors. In Sagemath MatrixSpace is not a subtype of VectorSpace so I think this function will have issues if the vectors are actually matrices.

A definition for the coset graph is provided in the docstring: "the vertices are the cosets and 2 cosets are adjacent if they have representatives that differ in one coordinate".
I haven't found any LinearRankMetricCode in Sagemath that doesn't use vectors, so I could just move the cosetGraph method to AbstractLinearCodeNoMetric. However, if you wish to use a different definition of coset graph that uses a more general metric, then we need a substantially different implementation (still doable).

As far as the dual code is concerned, if I get it right the dual code of C is the orthogonal complement of C which is not a direct sum complement of C if we use a non positive-definite bilinear form. So I don't see many connections when the base field is finite. For instance:

sage: C = codes.GolayCode(GF(3))
sage: U = C.dual_code()
sage: U == C
True

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​eeaeb02

fixed typos

[dimpase]

Replying to gh-Ivo-Maffei:

First of all, I'm not sure the algorithm used is the best one. I could simply compute the cosets of C and work with their representatives, but I have a feeling it will be slower.

I think working in a complement space, as you did, is good.

That said, I think the algorithm relies on C being a set of vectors. In Sagemath MatrixSpace is not a subtype of VectorSpace so I think this function will have issues if the vectors are actually matrices.

A definition for the coset graph is provided in the docstring: "the vertices are the cosets and 2 cosets are adjacent if they have representatives that differ in one coordinate".

maybe something like "the vertices are the cosets of C, considered as a subgroup of the additive group of the ambient vector space, and two cosets are adjacent if they have representatives that differ in exactly one coordinate".

I haven't found any LinearRankMetricCode in Sagemath that doesn't use vectors, so I could just move the cosetGraph method to AbstractLinearCodeNoMetric.

hmm, no, as there is no metric at all, whereas you do use the Hamming metric.

However, if you wish to use a different definition of coset graph that uses a more general metric, then we need a substantially different implementation (still doable).

As far as the dual code is concerned, if I get it right the dual code of C is the orthogonal complement of C which is not a direct sum complement of C if we use a non positive-definite bilinear form. So I don't see many connections when the base field is finite.

you're right, sorry for noise at this point.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​d89d8a5

improved def of coset graph

[dimpase]

the (direct sum) complement -> a (direct sum) complement (it's certainly not unique)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​87c56f5

minor docstring change

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​e8d16c8

fixed issue with basis computation; fixed bug with zero projections

[dimpase]

looks good to me