Minpoly doesn't work for all matrices

[jasongrout]

Right now, not all matrices can compute minpolys. This patch exposes these matrices.

CC: @kcrisman @rbeezer @mwhansen @hedtke @tscrim

Component: linear algebra

Author: Jason Grout, Frédéric Chapoton

Branch/Commit: 329d472

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/7989

[jasongrout]

comment:2

Attachment: trac-7989-minpoly-test.patch.gz

Here are the bugs (doctests that fail) this patch exposes:

	sage -t  "4.3.1.rc0/devel/sage-main/sage/matrix/matrix1.pyx"
	sage -t  "4.3.1.rc0/devel/sage-main/sage/matrix/matrix_dense.pyx"
	sage -t  "4.3.1.rc0/devel/sage-main/sage/matrix/matrix_generic_dense.pyx"
	sage -t  "4.3.1.rc0/devel/sage-main/sage/matrix/matrix_integer_2x2.pyx"

[jasongrout]

Author: Jason Grout

[hedtke]

comment:5

Sorry, I don't understand the reason for this function. What is the idea behind it?

[williamstein]

comment:6

This is a great patch. I can't believe this has got ignored for the last 1.5 years.

Regarding what needs to be fixed, the test failure you claim for matrix_integer_2x2 is:

deep:sage wstein$ sage -t matrix/matrix_integer_2x2.pyx
sage -t  "matrix/matrix_integer_2x2.pyx"                    
**********************************************************************
File "/Users/wstein/sage/install/sage-4.7.1.rc0/devel/sage-main/sage/matrix/matrix_integer_2x2.pyx", line 101:
    sage: TestSuite(m).run()
Expected nothing
Got:
    Failure in _test_minpoly:
    Traceback (most recent call last):
      File "/Users/wstein/sage/install/current/local/lib/python/site-packages/sage/misc/sage_unittest.py", line 275, in run
        test_method(tester = tester)
      File "matrix2.pyx", line 1302, in sage.matrix.matrix2.Matrix._test_minpoly (sage/matrix/matrix2.c:8933)
      File "polynomial_element.pyx", line 358, in sage.rings.polynomial.polynomial_element.Polynomial.subs (sage/rings/polynomial/polynomial_element.c:5624)
      File "polynomial_element.pyx", line 557, in sage.rings.polynomial.polynomial_element.Polynomial.__call__ (sage/rings/polynomial/polynomial_element.c:5819)
      File "polynomial_element.pyx", line 638, in sage.rings.polynomial.polynomial_element.Polynomial.__call__ (sage/rings/polynomial/polynomial_element.c:7244)
      File "element.pyx", line 1302, in sage.structure.element.RingElement.__add__ (sage/structure/element.c:11504)
      File "coerce.pyx", line 766, in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:7337)
    TypeError: unsupported operand parent(s) for '+': 'Space of 2x2 integer matrices' and 'Integer Ring'
    ------------------------------------------------------------
    The following tests failed: _test_minpoly
**********************************************************************
1 items had failures:
   1 of   6 in __main__.example_7
***Test Failed*** 1 failures.
For whitespace errors, see the file /Users/wstein/.sage//tmp/.doctest_matrix_integer_2x2.py
	 [4.6 s]

This is because substitution isn't even implemented for that class:

sage: MS = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
sage: a = MS([1,2,3,4])
sage: a.minpoly()
x^2 - 5*x - 2
sage: a.minpoly()(a)
---------------------------------------------------------------------------
TypeError     

Also, if one adds this for minpoly, it would make sense to also add _test_charpoly.

-- William

[hedtke]

comment:7

OK. Works for me, too. Is it favored that we include a test that purposely fails?

[rbeezer]

comment:8

Replying to @hedtke:

OK. Works for me, too. Is it favored that we include a test that purposely fails?

I think the idea is to include the test-suite checking and add the fixes needed to make the tests pass.

[mezzarobba]

comment:11

sage-6.2.beta4:

sage -t src/sage/matrix/matrix_generic_dense.pyx  # 1 doctest failed
sage -t src/sage/matrix/matrix_dense.pyx  # 1 doctest failed

[jdemeyer]

Branch: u/jdemeyer/minpoly_doesn_t_work_for_all_matrices

[fchapoton]

New commits:

08701a4

test that minpoly works

[fchapoton]

Commit: 08701a4

[fchapoton]

Changed branch from u/jdemeyer/minpoly_doesn_t_work_for_all_matrices to public/ticket/7989

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ce364f7

only test minpoly for exact rings

[sagetrac-git]

Changed commit from 08701a4 to ce364f7

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

216d945

use Gap for minpoly of Gap matrices

[sagetrac-git]

Changed commit from ce364f7 to 216d945

[sagetrac-git]

Changed commit from 216d945 to 9f476b4

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

9f476b4

add doc, skip test

[sagetrac-git]

Changed commit from 9f476b4 to 329d472

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

329d472

skip another test

[fchapoton]

Changed author from Jason Grout to Jason Grout, Frédéric Chapoton

[fchapoton]

comment:21

green patchbot, so please review

[tscrim]

comment:22

LGTM.

[tscrim]

Reviewer: Travis Scrimshaw

[vbraun]

Changed branch from public/ticket/7989 to 329d472