Sage: Ticket #19462: LinearCode.is_projective
https://trac.sagemath.org/ticket/19462
<p>
As the title says, this branch adds a very short function to <a class="missing wiki">LinearCode?</a>.
</p>
<p>
Nathann
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/19462
Trac 1.1.6ncohenFri, 23 Oct 2015 12:22:00 GMTstatus changed; commit, branch set
https://trac.sagemath.org/ticket/19462#comment:1
https://trac.sagemath.org/ticket/19462#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>7272942710a80866935ba073fe0e8697d7a3f137</em>
</li>
<li><strong>branch</strong>
set to <em>public/19462</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=7272942710a80866935ba073fe0e8697d7a3f137"><span class="icon"></span>7272942</a></td><td><code>trac #19462: LinearCode.is_projective</code>
</td></tr></table>
TicketwasFri, 23 Oct 2015 18:28:43 GMT
https://trac.sagemath.org/ticket/19462#comment:2
https://trac.sagemath.org/ticket/19462#comment:2
<p>
Typo in this line: "[BS11] E, Byrne and A. Sneyd,". It should be "[BS11] E. Byrne and A. Sneyd"
</p>
TicketgitFri, 23 Oct 2015 18:35:19 GMTcommit changed
https://trac.sagemath.org/ticket/19462#comment:3
https://trac.sagemath.org/ticket/19462#comment:3
<ul>
<li><strong>commit</strong>
changed from <em>7272942710a80866935ba073fe0e8697d7a3f137</em> to <em>4a8d9701a24ab0437ff4e8fbf517bb47443ef425</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=4a8d9701a24ab0437ff4e8fbf517bb47443ef425"><span class="icon"></span>4a8d970</a></td><td><code>trac #19462: Typo</code>
</td></tr></table>
TicketvdelecroixFri, 23 Oct 2015 19:45:30 GMT
https://trac.sagemath.org/ticket/19462#comment:4
https://trac.sagemath.org/ticket/19462#comment:4
<p>
One simplification: Since your matrix has coefficient in a field, you can always normalize the rows. For each of them, choose the first coefficient which is nonzero, let say <code>a</code> and multiply your row by <code>1/a</code>. It gives a canonical representative of the row. Then, you just have to check that your normalized columns are distinct.
</p>
<p>
There might be already some code to do that somewhere... let me check.
</p>
TicketncohenFri, 23 Oct 2015 19:46:29 GMT
https://trac.sagemath.org/ticket/19462#comment:5
https://trac.sagemath.org/ticket/19462#comment:5
<blockquote class="citation">
<p>
One simplification: Since your matrix has coefficient in a field
</p>
</blockquote>
<p>
Why could I assume that the base ring is a field?
</p>
<p>
Nathann
</p>
TicketvdelecroixFri, 23 Oct 2015 19:49:41 GMT
https://trac.sagemath.org/ticket/19462#comment:6
https://trac.sagemath.org/ticket/19462#comment:6
<p>
Until you review <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/6452" title="enhancement: Submodules of (ZZ/nZZ)^r (needs_work)">#6452</a>, they will be...
</p>
TicketncohenFri, 23 Oct 2015 19:57:58 GMT
https://trac.sagemath.org/ticket/19462#comment:7
https://trac.sagemath.org/ticket/19462#comment:7
<p>
I do not understand, could you say explicitly why we may be allowed to assume that the base ring is a field?
</p>
TicketvdelecroixFri, 23 Oct 2015 20:01:46 GMT
https://trac.sagemath.org/ticket/19462#comment:8
https://trac.sagemath.org/ticket/19462#comment:8
<p>
Currently in Sage you can only build linear codes over finite fields. The only tentative to generalize it (though only to the rings <code>ZZ/nZZ</code>) is <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/6452" title="enhancement: Submodules of (ZZ/nZZ)^r (needs_work)">#6452</a>. Note that this ticket not add directly a new linear code function but rather focuses on having a nice class for submodules of <code>(ZZ/nZZ)^r</code> which is exactly what linear codes are about.
</p>
<p>
And <a class="ext-link" href="https://en.wikipedia.org/wiki/Linear_code"><span class="icon"></span>wikipedia</a> says that linear code are over finite fields.
</p>
<p>
EDIT: until the last paragraph where it is mentioned that some authors used linear code for code over rings.
</p>
TicketvdelecroixFri, 23 Oct 2015 20:05:14 GMT
https://trac.sagemath.org/ticket/19462#comment:9
https://trac.sagemath.org/ticket/19462#comment:9
<p>
Anyway, you can do
</p>
<pre class="wiki">if not self.base_ring() in Fields():
raise NotImplementedError
</pre><p>
And if your field is <code>GF(2)</code> it should even be faster.
</p>
<p>
Could you also add an example of <strong>non</strong> projective code?
</p>
TicketncohenFri, 23 Oct 2015 20:05:46 GMT
https://trac.sagemath.org/ticket/19462#comment:10
https://trac.sagemath.org/ticket/19462#comment:10
<p>
The reason why I want to managed general rings is because the paper from which I took the definition (a link appears in the branch) explicitly mention rings. Thus I saw no reason to assume more.
</p>
<p>
Also, if we do assume that we have fields won't your patch -- that enables general rings for codes -- make this code invalid?
</p>
<p>
Nathann
</p>
TicketncohenFri, 23 Oct 2015 20:07:07 GMT
https://trac.sagemath.org/ticket/19462#comment:11
https://trac.sagemath.org/ticket/19462#comment:11
<blockquote class="citation">
<p>
Anyway, you can do
</p>
<pre class="wiki">if not self.base_ring() in Fields():
raise NotImplementedError
</pre><p>
And if your field is <code>GF(2)</code> it should even be faster.
</p>
</blockquote>
<p>
Why on earth would you ask me to degrade my code to manage fields only, when it is meant to handle general rings and *you* tell me that rings will be supported by <a class="missing wiki">LinearCode?</a> eventually?
</p>
<blockquote class="citation">
<p>
Could you also add an example of <strong>non</strong> projective code?
</p>
</blockquote>
<p>
If you want.. I have to find one though...
</p>
<p>
Nathann
</p>
TicketvdelecroixFri, 23 Oct 2015 20:10:24 GMT
https://trac.sagemath.org/ticket/19462#comment:12
https://trac.sagemath.org/ticket/19462#comment:12
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19462#comment:11" title="Comment 11">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Anyway, you can do
</p>
<pre class="wiki">if not self.base_ring() in Fields():
raise NotImplementedError
</pre><p>
And if your field is <code>GF(2)</code> it should even be faster.
</p>
</blockquote>
<p>
Why on earth would you ask me to degrade my code to manage fields only, when it is meant to handle general rings and *you* tell me that rings will be supported by <a class="missing wiki">LinearCode?</a> eventually?
</p>
</blockquote>
<p>
Because checking duplicates in a list of size <code>|size of the field| x nrows</code> is longer than in a list of size <code>nrows</code>.
</p>
<p>
I have no idea whether linear code over rings will be one day supported... ticket <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/6452" title="enhancement: Submodules of (ZZ/nZZ)^r (needs_work)">#6452</a> is just a first step. And I was just mentioning it to make some advertisement. But nobody cares.
</p>
TicketncohenFri, 23 Oct 2015 20:14:24 GMT
https://trac.sagemath.org/ticket/19462#comment:13
https://trac.sagemath.org/ticket/19462#comment:13
<blockquote class="citation">
<p>
Because checking duplicates in a list of size <code>|size of the field| x nrows</code> is longer than in a list of size <code>nrows</code>.
</p>
</blockquote>
<p>
This is a good justification for a field-specific version of this 5-lines algorithm. Not a justification for not supporting rings at all.
</p>
<blockquote class="citation">
<p>
I have no idea whether linear code over rings will be one day supported... ticket <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/6452" title="enhancement: Submodules of (ZZ/nZZ)^r (needs_work)">#6452</a> is just a first step. And I was just mentioning it to make some advertisement. But nobody cares.
</p>
</blockquote>
<p>
I have no idea either, but unless it is written somewhere that we can assume fields only, you won't see me adding a code that assumes more than it should.
</p>
<p>
Nathann
</p>
TicketncohenFri, 23 Oct 2015 20:28:28 GMT
https://trac.sagemath.org/ticket/19462#comment:14
https://trac.sagemath.org/ticket/19462#comment:14
<blockquote class="citation">
<p>
And I was just mentioning it to make some advertisement. But nobody cares.
</p>
</blockquote>
<p>
Try to advertise it to people who you think should care. I review patches in less than three years, but on the other hand my field is graph theory. I forgot all I ever knew about rings.
</p>
<p>
About this ticket: it seems that some part of the code 'assumes' that the ring is a field indeed:
</p>
<pre class="wiki">sage: LinearCode(matrix.ones(IntegerModRing(6),5))
...
NotImplementedError: Echelon form not implemented over 'Ring of integers modulo 6'.
</pre><p>
Though that is apparently because the 'rank' function is only implemented on fields. This notion exists on rings too, doesn't it? Though I expect that the definition would be pretty nasty <code>:-/</code>
</p>
<p>
'on the paper', however:
</p>
<pre class="wiki">sage: LinearCode(matrix.ones(IntegerModRing(3),5))
Linear code of length 5, dimension 1 over Ring of integers modulo 3
</pre><p>
That's cheating, however, for
</p>
<pre class="wiki">sage: IntegerModRing(3).is_field()
True
</pre><p>
Nathann
</p>
TicketncohenFri, 23 Oct 2015 20:30:26 GMT
https://trac.sagemath.org/ticket/19462#comment:15
https://trac.sagemath.org/ticket/19462#comment:15
<p>
All of a sudden, however, I wonder about something... Given that the generator matrix is automatically replaced by a generator matrix with full rank, can this function return anything but 'True'?
</p>
<p>
Nathann
</p>
TicketvdelecroixFri, 23 Oct 2015 21:05:44 GMT
https://trac.sagemath.org/ticket/19462#comment:16
https://trac.sagemath.org/ticket/19462#comment:16
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19462#comment:15" title="Comment 15">ncohen</a>:
</p>
<blockquote class="citation">
<p>
All of a sudden, however, I wonder about something... Given that the generator matrix is automatically replaced by a generator matrix with full rank, can this function return anything but 'True'?
</p>
</blockquote>
<p>
Anyway, you should return
</p>
<pre class="wiki">return len(set(RM)) == M.nrows()
</pre><p>
to fit with the definition in the paper.
</p>
TicketvdelecroixFri, 23 Oct 2015 21:07:40 GMT
https://trac.sagemath.org/ticket/19462#comment:17
https://trac.sagemath.org/ticket/19462#comment:17
<p>
And then
</p>
<pre class="wiki">sage: sage: C = codes.LinearCode(matrix(GF(2),[[1,0,1],[1,1,1]]))
sage: sage: C.is_projective()
False
</pre>
TicketncohenFri, 23 Oct 2015 21:10:29 GMT
https://trac.sagemath.org/ticket/19462#comment:18
https://trac.sagemath.org/ticket/19462#comment:18
<p>
True. That got lost in the successive workaround of this mutable/immutable mess <code>>_<</code>
</p>
<p>
Nathann
</p>
TicketgitFri, 23 Oct 2015 21:13:22 GMTcommit changed
https://trac.sagemath.org/ticket/19462#comment:19
https://trac.sagemath.org/ticket/19462#comment:19
<ul>
<li><strong>commit</strong>
changed from <em>4a8d9701a24ab0437ff4e8fbf517bb47443ef425</em> to <em>017089a65dc9ef2087762007590d43cde1832240</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=017089a65dc9ef2087762007590d43cde1832240"><span class="icon"></span>017089a</a></td><td><code>trac #19462: Bugfix+doctest</code>
</td></tr></table>
TicketvdelecroixFri, 23 Oct 2015 21:40:37 GMT
https://trac.sagemath.org/ticket/19462#comment:20
https://trac.sagemath.org/ticket/19462#comment:20
<p>
dedicated version for fields at <code>public/19462-bis</code>.
</p>
TicketjsrnFri, 23 Oct 2015 21:41:12 GMT
https://trac.sagemath.org/ticket/19462#comment:21
https://trac.sagemath.org/ticket/19462#comment:21
<p>
<code>LinearCode</code> is beyond broken for rings. That the object cannot even be constructed is only the tip of the iceberg. The <code>ZZ/pZZ</code>-modules that Vincent implemented can form a base of a type of code over ring later on, but that will not inherit from <code>LinearCode</code> or <code>AbstractLinearCode</code> since there field assumption is everywhere. I don't know how much code sharing will be possible, but I doubt too much non-trivial code.
</p>
<p>
Also, I don't think it's high on anyone's list of priorities...
</p>
<p>
I've also been discussing with David to change <code>LinearCode</code> so it doesn't
mention rings anymore. It's stupid since they're clearly not supported.
</p>
<p>
So I agree with Vincent that it's nicer to have code run in linear time rather than quadratic.
</p>
<p>
Moreover, I don't even think your code is correct over rings. Consider the
following generator matrix over ZZ mod 6:
</p>
<blockquote>
<p>
[ 1 2 0 ]
[ 1 2 1 ]
</p>
</blockquote>
<p>
This is clearly not projective since 2*c1 = c2.
But your code would compare
</p>
<blockquote>
<p>
set([ c1 * (ZZ mod 6) ]) = { (0,0), (1, 1), (2,2), ..., (5,5) }
set([ c2 * (ZZ mod 6) ]) = { (0,0), (2,2), (4,4) }
</p>
</blockquote>
<p>
Thus the check at the end would succeed, and you return <code>True</code>.
</p>
TicketvdelecroixFri, 23 Oct 2015 21:49:07 GMT
https://trac.sagemath.org/ticket/19462#comment:22
https://trac.sagemath.org/ticket/19462#comment:22
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19462#comment:21" title="Comment 21">jsrn</a>:
</p>
<blockquote class="citation">
<p>
This is clearly not projective since 2*c1 = c2.
</p>
</blockquote>
<p>
In the definition given in reference by Nathann, the condition is that <code>R c1 != R c2</code>... but of course, the definition is non-ambiguous over a field.
</p>
<p>
Vincent
</p>
TicketjsrnFri, 23 Oct 2015 22:09:34 GMT
https://trac.sagemath.org/ticket/19462#comment:23
https://trac.sagemath.org/ticket/19462#comment:23
<p>
Ah, I see. Ok, so the code seems correct then :-)
</p>
<p>
But that's not what's usually understood by "linearly independent", I believe. If you, Nathann, insist on retaining the ring stuff, I suggest the definition be written out in full in the docstring (noone is going to look up a definition he believes he knows from high school).
</p>
<p>
Best,
Johan
</p>
TicketdimpaseFri, 23 Oct 2015 22:51:36 GMT
https://trac.sagemath.org/ticket/19462#comment:24
https://trac.sagemath.org/ticket/19462#comment:24
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19462#comment:23" title="Comment 23">jsrn</a>:
</p>
<blockquote class="citation">
<p>
Ah, I see. Ok, so the code seems correct then :-)
</p>
<p>
But that's not what's usually understood by "linearly independent", I believe. If you, Nathann, insist on retaining the ring stuff, I suggest the definition be written out in full in the docsring (noone is going to look up a definition he believes he knows from high school).
</p>
</blockquote>
<p>
yeah, I agree - even if one's high school linear algebra virginity has been lost to irresistible charms of commutative algebra, it's still quite unusual definition.
</p>
TicketgitSat, 24 Oct 2015 05:32:05 GMTcommit changed
https://trac.sagemath.org/ticket/19462#comment:25
https://trac.sagemath.org/ticket/19462#comment:25
<ul>
<li><strong>commit</strong>
changed from <em>017089a65dc9ef2087762007590d43cde1832240</em> to <em>03f759a5326645822fc56e0156487bcf4238fde0</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=47d566defc92bb3ac9e7f7c8f4ac3e03965416dd"><span class="icon"></span>47d566d</a></td><td><code>Trac 19461: optimized code for fields</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=03f759a5326645822fc56e0156487bcf4238fde0"><span class="icon"></span>03f759a</a></td><td><code>trac #19462: Enforce the unwritten assumption</code>
</td></tr></table>
TicketvdelecroixSat, 24 Oct 2015 12:26:08 GMT
https://trac.sagemath.org/ticket/19462#comment:26
https://trac.sagemath.org/ticket/19462#comment:26
<p>
And actually in the reference Nathann gave, they consider codes over non-commutative finite rings! Which is indeed infinitely more general.
</p>
<p>
Nathann, for this version of the code, since you switched to a field implementation, could you adapt the documentation?
</p>
TicketgitSun, 25 Oct 2015 07:37:33 GMTcommit changed
https://trac.sagemath.org/ticket/19462#comment:27
https://trac.sagemath.org/ticket/19462#comment:27
<ul>
<li><strong>commit</strong>
changed from <em>03f759a5326645822fc56e0156487bcf4238fde0</em> to <em>11e0f8295faa3497ad753728e2402932c2e4f362</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=11e0f8295faa3497ad753728e2402932c2e4f362"><span class="icon"></span>11e0f82</a></td><td><code>trac #19462: ring->field</code>
</td></tr></table>
TicketgitSun, 25 Oct 2015 07:38:37 GMTcommit changed
https://trac.sagemath.org/ticket/19462#comment:28
https://trac.sagemath.org/ticket/19462#comment:28
<ul>
<li><strong>commit</strong>
changed from <em>11e0f8295faa3497ad753728e2402932c2e4f362</em> to <em>fc7e50975777e4f50e0c345cfdb0cf42f12740c5</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=fc7e50975777e4f50e0c345cfdb0cf42f12740c5"><span class="icon"></span>fc7e509</a></td><td><code>trac #19462: ring->field</code>
</td></tr></table>
TicketvdelecroixThu, 29 Oct 2015 12:24:54 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/19462#comment:29
https://trac.sagemath.org/ticket/19462#comment:29
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Johan Sebastian Rosenkilde Nielsen, Vincent Delecroix</em>
</li>
</ul>
<p>
Good to go!
</p>
TicketncohenThu, 29 Oct 2015 12:26:50 GMT
https://trac.sagemath.org/ticket/19462#comment:30
https://trac.sagemath.org/ticket/19462#comment:30
<p>
Thanks,
</p>
<p>
Nathann
</p>
TicketvbraunThu, 29 Oct 2015 16:34:57 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/19462#comment:31
https://trac.sagemath.org/ticket/19462#comment:31
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/19462</em> to <em>fc7e50975777e4f50e0c345cfdb0cf42f12740c5</em>
</li>
</ul>
Ticket