Opened 7 years ago

Closed 7 years ago

# LinearCode should check the rank

Reported by: Owned by: vdelecroix major sage-6.5 coding theory wdj Vincent Delecroix Nathann Cohen N/A 173f3ec 173f3ece741427bbc40f3f91305e0a14391ea7fb

### 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!

### 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:

 ​8013ac0 `trac #17452: clean min_wt_vec_gap` ​173f3ec `trac #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: ↓ 8 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.