Sage: Ticket #10793: Matrices can be "constructed" from matrices of wrong dimensions
https://trac.sagemath.org/ticket/10793
<p>
Let's make a matrix and use it to define a morphism:
</p>
<pre class="wiki">sage: projection = matrix(ZZ,[[1,0,0],[0,1,0]])
sage: projection
[1 0 0]
[0 1 0]
sage: H = Hom(ZZ^3, ZZ^2)
sage: H(projection)
Free module morphism defined by the matrix
[1 0]
[0 0]
[1 0]
Domain: Ambient free module of rank 3 over the principal ideal domain ...
Codomain: Ambient free module of rank 2 over the principal ideal domain ...
</pre><p>
As we see, the matrix of the morphism is very unlikely to be what it should be. Here is the source of the problem:
</p>
<pre class="wiki">sage: projection.parent()
Full MatrixSpace of 2 by 3 dense matrices over Integer Ring
sage: M = MatrixSpace(ZZ, 3 , 2)
sage: M
Full MatrixSpace of 3 by 2 dense matrices over Integer Ring
sage: M(projection)
[1 0]
[0 0]
[1 0]
</pre><p>
So the matrix space converts the input to the matrix no matter what (same with <code>matrix</code> command, but inside morphisms matrix spaces are used). I suppose this will work any time the number of entries in the original and in the destination is matching. I think that if one really wants to do it, then this one is very welcome to insert an explicit conversion of a matrix to a list and then back to a matrix, but the above should raise exceptions.
</p>
<p>
Apply trac_10793_bug_in_matrix_construction.patch, trac_10793_fixing_existing_bugs.patch
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/10793
Trac 1.2Andrey NovoseltsevThu, 17 Feb 2011 15:43:08 GMTdescription, component, summary, priority, owner, type changed
https://trac.sagemath.org/ticket/10793#comment:1
https://trac.sagemath.org/ticket/10793#comment:1
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/10793?action=diff&version=1">diff</a>)
</li>
<li><strong>component</strong>
changed from <em>algebraic geometry</em> to <em>linear algebra</em>
</li>
<li><strong>summary</strong>
changed from <em>FanMorphism defined by matrices are dangerous</em> to <em>Matrices can be "constructed" from matrices of wrong dimensions</em>
</li>
<li><strong>priority</strong>
changed from <em>major</em> to <em>critical</em>
</li>
<li><strong>owner</strong>
changed from <em>Alex Ghitza</em> to <em>jason, was</em>
</li>
<li><strong>type</strong>
changed from <em>PLEASE CHANGE</em> to <em>defect</em>
</li>
</ul>
<p>
I have completely replaced the original Volker's description since the problem is unrelated to fan morphisms themselves.
</p>
<p>
Also I think that this is an extremely dangerous bug and will take the liberty to elevate its priority...
</p>
TicketJason GroutThu, 17 Feb 2011 16:00:43 GMT
https://trac.sagemath.org/ticket/10793#comment:2
https://trac.sagemath.org/ticket/10793#comment:2
<p>
So it seems that the problem here is that in converting to an element of the matrix space, it views the entries of the matrix (or indeed, the entries of a nested list as well) as a flattened list:
</p>
<pre class="wiki">sage: M
Full MatrixSpace of 3 by 2 dense matrices over Integer Ring
sage: M([[1,2,3],[4,5,6]])
[1 2]
[3 4]
[5 6]
</pre><p>
So I guess you're saying that <a class="missing wiki">MatrixSpace?</a> shouldn't flatten the list, but instead should throw an error?
</p>
TicketJason GroutThu, 17 Feb 2011 16:05:04 GMT
https://trac.sagemath.org/ticket/10793#comment:3
https://trac.sagemath.org/ticket/10793#comment:3
<p>
Around line 361 in <code>matrix/matrix_space.py</code>, we see:
</p>
<pre class="wiki"> if isinstance(entries, (list, tuple)) and len(entries) > 0 and \
sage.modules.free_module_element.is_FreeModuleElement(entries[0]):
#Try to determine whether or not the entries should
#be rows or columns
if rows is None:
#If the matrix is square, default to rows
if self.__ncols == self.__nrows:
rows = True
elif len(entries[0]) == self.__ncols:
rows = True
elif len(entries[0]) == self.__nrows:
rows = False
else:
raise ValueError, "incorrect dimensions"
if self.__is_sparse:
e = {}
zero = self.base_ring()(0)
for i in xrange(len(entries)):
for j, x in entries[i].iteritems():
if x != zero:
if rows:
e[(i,j)] = x
else:
e[(j,i)] = x
entries = e
else:
entries = sum([v.list() for v in entries],[])
</pre><p>
So:
</p>
<ol><li>I think it tries to be too intelligent about guessing whether you have rows or columns. That leads to inconsistent behavior when you have code dealing with different matrix spaces with different dimensions.
</li></ol><ol start="2"><li>It indeed does flatten the list if all else fails (that's the sum([v.list()... line). I agree that that looks dangerous as well.
</li></ol>
TicketAndrey NovoseltsevThu, 17 Feb 2011 16:08:20 GMT
https://trac.sagemath.org/ticket/10793#comment:4
https://trac.sagemath.org/ticket/10793#comment:4
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10793#comment:2" title="Comment 2">jason</a>:
</p>
<blockquote class="citation">
<p>
So it seems that the problem here is that in converting to an element of the matrix space, it views the entries of the matrix (or indeed, the entries of a nested list as well) as a flattened list:
</p>
<pre class="wiki">sage: M
Full MatrixSpace of 3 by 2 dense matrices over Integer Ring
sage: M([[1,2,3],[4,5,6]])
[1 2]
[3 4]
[5 6]
</pre><p>
So I guess you're saying that <a class="missing wiki">MatrixSpace?</a> shouldn't flatten the list, but instead should throw an error?
</p>
</blockquote>
<p>
Absolutely! I see no reason why such flattening can make sense, so even if there some - I think they should do it explicitly.
</p>
<p>
I find it a bit confusing that Sage uses right matrix action, so in the description I tend to think that <code>projection</code> itself is the matrix of the morphism, not its transpose. I suspect I am not the only one who can fall into this trap: it is accepted as an input, but some other not-very-related matrix is then used in the morphism.
</p>
TicketAndrey NovoseltsevTue, 14 Jun 2011 16:52:32 GMTcc changed
https://trac.sagemath.org/ticket/10793#comment:5
https://trac.sagemath.org/ticket/10793#comment:5
<ul>
<li><strong>cc</strong>
<em>Rob Beezer</em> added; <em>Andrey Novoseltsev</em> removed
</li>
</ul>
<p>
Hi Rob, this is the ticket I was talking about!
</p>
TicketAndrey NovoseltsevThu, 16 Jun 2011 22:54:49 GMTattachment set
https://trac.sagemath.org/ticket/10793
https://trac.sagemath.org/ticket/10793
<ul>
<li><strong>attachment</strong>
set to <em>trac_10793_bug_in_matrix_construction.patch</em>
</li>
</ul>
TicketAndrey NovoseltsevThu, 16 Jun 2011 22:55:57 GMTstatus changed; author set
https://trac.sagemath.org/ticket/10793#comment:6
https://trac.sagemath.org/ticket/10793#comment:6
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
set to <em>Andrey Novoseltsev</em>
</li>
</ul>
TicketAndrey NovoseltsevThu, 16 Jun 2011 22:56:13 GMTkeywords set
https://trac.sagemath.org/ticket/10793#comment:7
https://trac.sagemath.org/ticket/10793#comment:7
<ul>
<li><strong>keywords</strong>
<em>sd31</em> added
</li>
</ul>
TicketAndrey NovoseltsevThu, 16 Jun 2011 23:04:53 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/10793#comment:8
https://trac.sagemath.org/ticket/10793#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>doctest failures</em>
</li>
</ul>
<p>
There are doctest failures that have to be addressed. I suspect that all places that are affected were just kind of wrong. For Nx1 and 1xN matrices nothing too horrible is going on, hopefully there are no other cases.
</p>
TicketAndrey NovoseltsevFri, 17 Jun 2011 00:02:59 GMT
https://trac.sagemath.org/ticket/10793#comment:9
https://trac.sagemath.org/ticket/10793#comment:9
<p>
Here is the list of offenders:
</p>
<pre class="wiki"> sage -t -long devel/sage-main/sage/crypto/mq/sr.py # 15 doctests failed
sage -t -long devel/sage-main/sage/interfaces/sage0.py # 2 doctests failed
sage -t -long devel/sage-main/sage/crypto/mq/mpolynomialsystem.py # 50 doctests failed
sage -t -long devel/sage-main/sage/geometry/fan_morphism.py # 4 doctests failed
sage -t -long devel/sage-main/sage/rings/polynomial/multi_polynomial_sequence.py # 33 doctests failed
sage -t -long devel/sage-main/sage/categories/map.pyx # 16 doctests failed
sage -t -long devel/sage-main/sage/interfaces/magma.py # 2 doctests failed
sage -t -long devel/sage-main/sage/modules/matrix_morphism.py # 9 doctests failed
</pre><p>
IMHO, all these files are full of bugs!
</p>
TicketAndrey NovoseltsevFri, 17 Jun 2011 00:34:48 GMTstatus changed; work_issues deleted
https://trac.sagemath.org/ticket/10793#comment:10
https://trac.sagemath.org/ticket/10793#comment:10
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>work_issues</strong>
<em>doctest failures</em> deleted
</li>
</ul>
<p>
OK, it turned out to be not as scary as it seemed to me originally. Most of the errors were due to forgetting that matrices act from the right. In crypto I have added explicit conversion of matrices to lists since it seems that they wanted it. I don't understand that code to make sure that this is indeed correct, but at the very least I didn't introduce a new bug ;-)
</p>
TicketAndrey NovoseltsevWed, 06 Jul 2011 00:15:15 GMTdependencies set
https://trac.sagemath.org/ticket/10793#comment:11
https://trac.sagemath.org/ticket/10793#comment:11
<ul>
<li><strong>dependencies</strong>
set to <em>#11200</em>
</li>
</ul>
<p>
Patches should apply fine on top of sage-4.7.1.alpha4, as <a class="closed ticket" href="https://trac.sagemath.org/ticket/11200" title="#11200: enhancement: Add fibration check to FanMorphism (closed: fixed)">#11200</a> (and other patches modifying fan morphisms) was merged.
</p>
TicketKarl-Dieter CrismanMon, 01 Aug 2011 16:47:42 GMTcc changed
https://trac.sagemath.org/ticket/10793#comment:12
https://trac.sagemath.org/ticket/10793#comment:12
<ul>
<li><strong>cc</strong>
<em>Karl-Dieter Crisman</em> added
</li>
</ul>
TicketVolker BraunSun, 14 Aug 2011 02:58:55 GMTstatus, description, milestone changed; reviewer set
https://trac.sagemath.org/ticket/10793#comment:13
https://trac.sagemath.org/ticket/10793#comment:13
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Volker Braun</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/10793?action=diff&version=13">diff</a>)
</li>
<li><strong>milestone</strong>
changed from <em>sage-4.7.1</em> to <em>sage-4.7.2</em>
</li>
</ul>
<p>
I totally forgot that we haven't merged this ticket yet. Applies fine on Sage-4.7.1.rc2. Positive review.
</p>
TicketJeroen DemeyerWed, 17 Aug 2011 20:34:25 GMTstatus changed
https://trac.sagemath.org/ticket/10793#comment:14
https://trac.sagemath.org/ticket/10793#comment:14
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
This patch conflicts with <a class="closed ticket" href="https://trac.sagemath.org/ticket/11552" title="#11552: defect: Fix surjectivity testing for free module morphisms (closed: fixed)">#11552</a>. Since the latter is older, I propose that this patch is rebased to <a class="closed ticket" href="https://trac.sagemath.org/ticket/11552" title="#11552: defect: Fix surjectivity testing for free module morphisms (closed: fixed)">#11552</a>.
</p>
TicketAndrey NovoseltsevWed, 17 Aug 2011 21:39:45 GMTattachment set
https://trac.sagemath.org/ticket/10793
https://trac.sagemath.org/ticket/10793
<ul>
<li><strong>attachment</strong>
set to <em>trac_10793_fixing_existing_bugs.patch</em>
</li>
</ul>
TicketAndrey NovoseltsevWed, 17 Aug 2011 21:41:13 GMTstatus, dependencies changed
https://trac.sagemath.org/ticket/10793#comment:15
https://trac.sagemath.org/ticket/10793#comment:15
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>dependencies</strong>
changed from <em>#11200</em> to <em>#11200, #11552</em>
</li>
</ul>
<p>
Rebased on top of <a class="closed ticket" href="https://trac.sagemath.org/ticket/11552" title="#11552: defect: Fix surjectivity testing for free module morphisms (closed: fixed)">#11552</a>, needs review.
</p>
TicketRob BeezerWed, 17 Aug 2011 23:46:06 GMT
https://trac.sagemath.org/ticket/10793#comment:16
https://trac.sagemath.org/ticket/10793#comment:16
<p>
I think that if a rebase is straightforward (ie there is no real change to code), then it does not need to be reviewed. I can't tell here, since the rebased patch replaced the old patch.
</p>
<p>
No matter - I've applied it and done minimal tests. All looks good. I'm running all tests right now and then will flip to positive review.
</p>
<p>
I'm glad this got fixed. While doing work on free module morphisms I ran into this frequently, where domains and codomains got confused, and so on. I'm surprised it survived this long. Thanks Volker and Andrey for the fix!
</p>
<p>
Rob
</p>
TicketAndrey NovoseltsevThu, 18 Aug 2011 00:01:43 GMT
https://trac.sagemath.org/ticket/10793#comment:17
https://trac.sagemath.org/ticket/10793#comment:17
<p>
It was straightforward, your patch added spaces after commas in two lines that I have altered...
</p>
TicketRob BeezerThu, 18 Aug 2011 00:05:41 GMTstatus changed
https://trac.sagemath.org/ticket/10793#comment:18
https://trac.sagemath.org/ticket/10793#comment:18
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Sorry. ;-) Thanks for the rebase. Passes all tests.
</p>
<p>
Rob
</p>
TicketJeroen DemeyerThu, 18 Aug 2011 22:02:18 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/10793#comment:19
https://trac.sagemath.org/ticket/10793#comment:19
<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>merged</strong>
set to <em>sage-4.7.2.alpha2</em>
</li>
</ul>
Ticket