Opened 9 years ago

Closed 8 years ago

#10793 closed defect (fixed)

Matrices can be "constructed" from matrices of wrong dimensions

Reported by: vbraun Owned by: jason, was
Priority: critical Milestone: sage-4.7.2
Component: linear algebra Keywords: sd31
Cc: rbeezer, kcrisman Merged in: sage-4.7.2.alpha2
Authors: Andrey Novoseltsev Reviewers: Volker Braun
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #11200, #11552 Stopgaps:

Description (last modified by vbraun)

Let's make a matrix and use it to define a morphism:

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 ...

As we see, the matrix of the morphism is very unlikely to be what it should be. Here is the source of the problem:

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]

So the matrix space converts the input to the matrix no matter what (same with matrix 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.

Apply trac_10793_bug_in_matrix_construction.patch, trac_10793_fixing_existing_bugs.patch

Attachments (2)

trac_10793_bug_in_matrix_construction.patch (3.8 KB) - added by novoselt 8 years ago.
trac_10793_fixing_existing_bugs.patch (5.3 KB) - added by novoselt 8 years ago.

Download all attachments as: .zip

Change History (21)

comment:1 Changed 9 years ago by novoselt

  • Component changed from algebraic geometry to linear algebra
  • Description modified (diff)
  • Owner changed from AlexGhitza to jason, was
  • Priority changed from major to critical
  • Summary changed from FanMorphism defined by matrices are dangerous to Matrices can be "constructed" from matrices of wrong dimensions
  • Type changed from PLEASE CHANGE to defect

I have completely replaced the original Volker's description since the problem is unrelated to fan morphisms themselves.

Also I think that this is an extremely dangerous bug and will take the liberty to elevate its priority...

comment:2 follow-up: Changed 9 years ago by jason

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:

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]

So I guess you're saying that MatrixSpace? shouldn't flatten the list, but instead should throw an error?

comment:3 Changed 9 years ago by jason

Around line 361 in matrix/matrix_space.py, we see:

        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],[])

So:

  1. 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.
  1. 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.

comment:4 in reply to: ↑ 2 Changed 9 years ago by novoselt

Replying to jason:

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:

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]

So I guess you're saying that MatrixSpace? shouldn't flatten the list, but instead should throw an error?

Absolutely! I see no reason why such flattening can make sense, so even if there some - I think they should do it explicitly.

I find it a bit confusing that Sage uses right matrix action, so in the description I tend to think that projection 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.

comment:5 Changed 8 years ago by novoselt

  • Cc rbeezer added; novoselt removed

Hi Rob, this is the ticket I was talking about!

Changed 8 years ago by novoselt

comment:6 Changed 8 years ago by novoselt

  • Authors set to Andrey Novoseltsev
  • Status changed from new to needs_review

comment:7 Changed 8 years ago by novoselt

  • Keywords sd31 added

comment:8 Changed 8 years ago by novoselt

  • Status changed from needs_review to needs_work
  • Work issues set to doctest failures

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.

comment:9 Changed 8 years ago by novoselt

Here is the list of offenders:

	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

IMHO, all these files are full of bugs!

comment:10 Changed 8 years ago by novoselt

  • Status changed from needs_work to needs_review
  • Work issues doctest failures deleted

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 ;-)

comment:11 Changed 8 years ago by novoselt

  • Dependencies set to #11200

Patches should apply fine on top of sage-4.7.1.alpha4, as #11200 (and other patches modifying fan morphisms) was merged.

comment:12 Changed 8 years ago by kcrisman

  • Cc kcrisman added

comment:13 Changed 8 years ago by vbraun

  • Description modified (diff)
  • Milestone changed from sage-4.7.1 to sage-4.7.2
  • Reviewers set to Volker Braun
  • Status changed from needs_review to positive_review

I totally forgot that we haven't merged this ticket yet. Applies fine on Sage-4.7.1.rc2. Positive review.

comment:14 Changed 8 years ago by jdemeyer

  • Status changed from positive_review to needs_work

This patch conflicts with #11552. Since the latter is older, I propose that this patch is rebased to #11552.

Changed 8 years ago by novoselt

comment:15 Changed 8 years ago by novoselt

  • Dependencies changed from #11200 to #11200, #11552
  • Status changed from needs_work to needs_review

Rebased on top of #11552, needs review.

comment:16 Changed 8 years ago by rbeezer

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.

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.

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!

Rob

comment:17 Changed 8 years ago by novoselt

It was straightforward, your patch added spaces after commas in two lines that I have altered...

comment:18 Changed 8 years ago by rbeezer

  • Status changed from needs_review to positive_review

Sorry. ;-) Thanks for the rebase. Passes all tests.

Rob

comment:19 Changed 8 years ago by jdemeyer

  • Merged in set to sage-4.7.2.alpha2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.