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: |
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
- Branch set to u/vdelecroix/17452
- Commit set to 173f3ece741427bbc40f3f91305e0a14391ea7fb
- Status changed from new to needs_review
comment:2 Changed 7 years ago by
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
- Reviewers set to Nathann Cohen
- Status changed from needs_review to positive_review
comment:4 Changed 7 years ago by
Wonderful. Thanks!
Vincent
comment:5 Changed 7 years ago by
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
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
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
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
- Branch changed from u/vdelecroix/17452 to 173f3ece741427bbc40f3f91305e0a14391ea7fb
- Resolution set to fixed
- Status changed from positive_review to closed
New commits:
trac #17452: clean min_wt_vec_gap
trac #17452: add a check for rank (+ doc)