Opened 4 months ago
Closed 4 months ago
#30253 closed enhancement (fixed)
Coset graph of linear codes
Reported by:  ghIvoMaffei  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  graph theory  Keywords:  linear_codes coset_graph 
Cc:  dimpase, jsrn, caruso  Merged in:  
Authors:  Ivo Maffei  Reviewers:  Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  e8d16c8 (Commits)  Commit:  e8d16c8305eafa58785cc45ab1b21c33b672f466 
Dependencies:  Stopgaps: 
Description
Added method to the AbstractLinearCode
class to compute the coset graph of a linear code.
Change History (12)
comment:1 Changed 4 months ago by
 Cc dimpase added
 Status changed from new to needs_review
comment:2 Changed 4 months ago by
 Cc jsrn caruso added
comment:3 Changed 4 months ago by
What kind of graph does this correspond to in terms of the dual to C code?
comment:4 followup: ↓ 6 Changed 4 months ago by
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 positivedefinite 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
comment:5 Changed 4 months ago by
 Commit changed from e92dae9e771a0d04d1e0f4ca9d11e3299c6a990d to eeaeb0205df5c430b10bd31a908fa994c7decb56
Branch pushed to git repo; I updated commit sha1. New commits:
eeaeb02  fixed typos

comment:6 in reply to: ↑ 4 Changed 4 months ago by
Replying to ghIvoMaffei:
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 SagemathMatrixSpace
is not a subtype ofVectorSpace
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 thecosetGraph
method toAbstractLinearCodeNoMetric
.
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 ofC
which is not a direct sum complement ofC
if we use a non positivedefinite bilinear form. So I don't see many connections when the base field is finite.
you're right, sorry for noise at this point.
comment:7 Changed 4 months ago by
 Commit changed from eeaeb0205df5c430b10bd31a908fa994c7decb56 to d89d8a54b192d27acba1c9f34f7f12db005240d6
Branch pushed to git repo; I updated commit sha1. New commits:
d89d8a5  improved def of coset graph

comment:8 Changed 4 months ago by
the (direct sum) complement
> a (direct sum) complement
(it's certainly not unique)
comment:9 Changed 4 months ago by
 Commit changed from d89d8a54b192d27acba1c9f34f7f12db005240d6 to 87c56f521949fbdfee3220cef1bc17db81337062
Branch pushed to git repo; I updated commit sha1. New commits:
87c56f5  minor docstring change

comment:10 Changed 4 months ago by
 Commit changed from 87c56f521949fbdfee3220cef1bc17db81337062 to e8d16c8305eafa58785cc45ab1b21c33b672f466
Branch pushed to git repo; I updated commit sha1. New commits:
e8d16c8  fixed issue with basis computation; fixed bug with zero projections

comment:11 Changed 4 months ago by
 Reviewers set to Dima Pasechnik
 Status changed from needs_review to positive_review
looks good to me
comment:12 Changed 4 months ago by
 Branch changed from u/ghIvoMaffei/coset_graph to e8d16c8305eafa58785cc45ab1b21c33b672f466
 Resolution set to fixed
 Status changed from positive_review to closed
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