Opened 7 years ago

Closed 7 years ago

#17452 closed defect (fixed)

LinearCode should check the rank

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.5
Component: coding theory Keywords:
Cc: wdj Merged in:
Authors: Vincent Delecroix Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: 173f3ec (Commits, GitHub, GitLab) Commit: 173f3ece741427bbc40f3f91305e0a14391ea7fb
Dependencies: Stopgaps:

Status badges

Description

Hi,

In a question on ask.sagemath.org was presented the following problem

sage: K = GF(4,"a")
sage: a = K.gen()
sage: G = Matrix([[a, a + 1, 1, a + 1, 1, 0, 0],
....:             [0, a, a + 1, 1, a + 1, 1, 0],
....:             [0, 0, a, a + 1, 1, a + 1, 1],
....:             [a + 1, 0, 1, 0, a + 1, 1, a + 1],
....:             [a, a + 1, a + 1, 0, 0, a + 1, 1],
....:             [a + 1, a, a, 1, 0, 0, a + 1],
....:             [a, a + 1, 1, a + 1, 1, 0, 0]])
sage: C = LinearCode(G)
sage: C.minimum_distance()
5

whereas the code has distance 3. The problem is that the input matrix does not has full rank... but this is never tested!

Change History (9)

comment:1 Changed 7 years ago by vdelecroix

  • Branch set to u/vdelecroix/17452
  • Commit set to 173f3ece741427bbc40f3f91305e0a14391ea7fb
  • Status changed from new to needs_review

New commits:

8013ac0trac #17452: clean min_wt_vec_gap
173f3ectrac #17452: add a check for rank (+ doc)

comment:2 Changed 7 years ago by ncohen

Wow. Thank you for fixing that and cleaning the code a bit, it was really ugly. It took me a long time only to understand what it did, and I had your commit to help me O_o

I do not get why that code would return a d equal to zero, however... What is the meaning of that ?

It is not really a problem for the review, that's what the code deals with already... But I would be glad to understand.

I would also be glad to understand why the GAP function is so complicated and takes this 'i' as a parameter, but well O_o

Nathann

comment:3 Changed 7 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

comment:4 Changed 7 years ago by vdelecroix

Wonderful. Thanks!

Vincent

comment:5 Changed 7 years ago by vdelecroix

To answer your question, I guess that the GAP function AClosestVectorCombinationsMatFFEVecFFECoords is really stupid: it just runs through all possible linear combinations with no zero coefficient (though, I did not look at the source code). Anyway, it is fast enough on reasonable input. From this function, if you obtain a 0 it means that your input vectors were not linearly independent (and its perfectly fine from the specification above). It perhaps would be safer to through an error there instead of silently ignore it.

Vincent

comment:6 Changed 7 years ago by ncohen

HMmmmm... Okay... If it is that stupid perhaps we should rewrite it ourselves someday.... O_o

Weird.

Nathann

comment:7 follow-up: Changed 7 years ago by vdelecroix

I just looked at gap source code. My rough idea was right but there is a bunch of optimizations to minimize arithmetic operations. Why would you like to duplicate something like that?

Vincent

comment:8 in reply to: ↑ 7 Changed 7 years ago by ncohen

I just looked at gap source code. My rough idea was right but there is a bunch of optimizations to minimize arithmetic operations. Why would you like to duplicate something like that?

Don't know... Perhaps only to not have to give the matrix to gap, then get vectors back... Things like that. I would not object if the interface was cleaner perhaps, but those matrices encoded as strings are too much for me :-P

Nathann

comment:9 Changed 7 years ago by vbraun

  • Branch changed from u/vdelecroix/17452 to 173f3ece741427bbc40f3f91305e0a14391ea7fb
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.