LinearCode should check the rank

[videlec]

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!

CC: @wdjoyner

Component: coding theory

Author: Vincent Delecroix

Branch/Commit: 173f3ec

Reviewer: Nathann Cohen

Issue created by migration from https://trac.sagemath.org/ticket/17452

[videlec]

Branch: u/vdelecroix/17452

[videlec]

Commit: 173f3ec

[videlec]

New commits:

8013ac0	trac #17452: clean min_wt_vec_gap
173f3ec	trac #17452: add a check for rank (+ doc)

[nathanncohen]

comment:2

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

[nathanncohen]

Reviewer: Nathann Cohen

[videlec]

comment:4

Wonderful. Thanks!

Vincent

[videlec]

comment:5

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

[nathanncohen]

comment:6

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

Weird.

Nathann

[videlec]

comment:7

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

[nathanncohen]

comment:8

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

[vbraun]

Changed branch from u/vdelecroix/17452 to 173f3ec