is_indefinite returns nothing or error: 'simplify' flag is unsupported in roots()

[JS]

Hello,

I have run into a problem with various matrices. I have read Gotchas and Pitfalls and tried to search around, but I was unable to find anything relevant.

For some matrices M, the  M.is_indefinite simply returns no output. I have noticed that M.eigenvals() works for on these matrices, however,  M.diagonalize() runs for more than a minute before it gives an output.

Matrices that have caused this problem for me:

M1 = Matrix(([4, 2, sqrt(3)], [2, 2, 0], [sqrt(3), 0, 1] ))
M1.is_indefinite

M2 = Matrix(([4, 2, 1], [2, 2, 0], [1, 0, 1] ))
M2.is_indefinite

M3 = Matrix(([14, -9, 0], [-9, 32, 30], [0, 30, 1]))
M3.is_indefinite
 

M4 = Matrix(([1, -4, -6], [-4, 2, 3], [-6, 3, 8] ))
M4.is_indefinite

Link to SymPy Live output.

Some bigger matrices B returns error

# Since 'simplify' flag is unsupported in roots() MatrixError: Could not compute eigenvalues for Matrix

when using B.is_indefinite, when I use B.is_indefinite. I get same kind of error for B.eigenvals() and B.diagonalize().

Matrices that have caused this problem for me:

B1 = Matrix(([3, -1, 1, 1, 0, 0], [-1, 2, 0, 1, 0, 0], [1, 0, 1, 0, 0, 0], [1, 1, 0, 1, 1, 0], [0, 0, 0, 1, 4, 1], [0, 0, 0, 1, 1, 2] ))
B1.is_indefinite
B1.eigenvals()
B1.diagonalize()

B2 = Matrix([[12, -4, 4, 3, 1, 0], [-4, 6, -1, 2, 1, 0], [4, -1, 2, 1, 0, 0], [3, 2, 1, 5, 6, 3], [1, 1, 0, 6, 18, 6], [0, 0, 0, 3, 6, 5]])  # this is in fact L2 = L1.T*L1
B2.is_indefinite
B2.eigenvals()
B2.diagonalize()

B3 = Matrix(([1, -1, 1, 0, 0, 1], [-1, 2, 1, 0, 2, 0], [1, 1, 6, 2, 3, 0], [0, 0, 2, 1, 4, 0], [0, 2, 3, 4, 5, 1], [1, 0, 0, 0, 1, 2] ))  
B3.is_indefinite
B3.eigenvals()
B3.diagonalize()

Link to SymPy Live output.

I have this problem on my Linux machine (SymPy 1.5.1, Python 3.8.2-64-bit) as well as on the SymPy Live (SymPy 1.5.1, Python 2.7.12).

Please, could you tell me if I’m just doing something wrong (hopefully it’s just that),

or if SymPy is really unable to perform these operations?

Thanks. : - )

[Oscar Benjamin]

There have been some recent improvements to the code handling this
which you could try out by installing the pre-release of 1.6 with pip:

pip install -U --pre sympy

--
Oscar

> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/3963eddf-e9fd-487d-949a-3ce151f3988f%40googlegroups.com.

[JS]

Thank you for the answer. I have tried again with SymPy 1.6rc1, Python 3.8.2-64-bit, unfortunately with the same result.

The errors that I got were:

B1 = Matrix(([3, -1, 1, 1, 0, 0], [-1, 2, 0, 1, 0, 0], [1, 0, 1, 0, 0, 0], [1, 1, 0, 1, 1, 0], [0, 0, 0, 1, 4, 1], [0, 0, 0, 1, 1, 2] ))



B1.is_indefinite                                                        

---------------------------------------------------------------------------
MatrixError                               Traceback (most recent call last)
<ipython-input-4-e4a304898903> in <module>
----> 1 B1.is_indefinite


~/.local/lib/python3.8/site-packages/sympy/matrices/matrices.py in is_indefinite(self)
    402     @property
    403     def is_indefinite(self):
--> 404         return _is_indefinite(self)
    405
    406     def jordan_form(self, calc_transform=True, **kwargs):


~/.local/lib/python3.8/site-packages/sympy/matrices/eigen.py in _is_indefinite(M)
    679
    680     elif M.is_square:
--> 681         return (M + M.H).is_indefinite
    682
    683     return False


~/.local/lib/python3.8/site-packages/sympy/matrices/matrices.py in is_indefinite(self)
    402     @property
    403     def is_indefinite(self):
--> 404         return _is_indefinite(self)
    405
    406     def jordan_form(self, calc_transform=True, **kwargs):


~/.local/lib/python3.8/site-packages/sympy/matrices/eigen.py in _is_indefinite(M)
    670 def _is_indefinite(M):
    671     if M.is_hermitian:
--> 672         eigen = M.eigenvals()
    673         args1        = [x.is_positive for x in eigen.keys()]
    674         any_positive = fuzzy_or(args1)


~/.local/lib/python3.8/site-packages/sympy/matrices/matrices.py in eigenvals(self, error_when_incomplete, **flags)
    365
    366     def eigenvals(self, error_when_incomplete=True, **flags):
--> 367         return _eigenvals(self, error_when_incomplete=error_when_incomplete, **flags)
    368
    369     def eigenvects(self, error_when_incomplete=True, iszerofunc=_iszero, **flags):


~/.local/lib/python3.8/site-packages/sympy/matrices/eigen.py in _eigenvals(M, error_when_incomplete, **flags)
    178         if not multiple and sum(eigs.values()) != M.rows or \
    179             multiple and len(eigs) != M.cols:
--> 180             raise MatrixError(
    181                 "Could not compute eigenvalues for {}".format(M))
    182


MatrixError: Could not compute eigenvalues for Matrix([[6, -2, 2, 2, 0, 0], [-2, 4, 0, 2, 0, 0], [2, 0, 2, 0, 0, 0], [2, 2, 0, 2, 2, 1], [0, 0, 0, 2, 8, 2], [0, 0, 0, 1, 2, 4]])


B1.eigenvals()                                                          
---------------------------------------------------------------------------
MatrixError                               Traceback (most recent call last)
<ipython-input-5-c349f98060e3> in <module>
----> 1 B1.eigenvals()


~/.local/lib/python3.8/site-packages/sympy/matrices/matrices.py in eigenvals(self, error_when_incomplete, **flags)
    365
    366     def eigenvals(self, error_when_incomplete=True, **flags):
--> 367         return _eigenvals(self, error_when_incomplete=error_when_incomplete, **flags)
    368
    369     def eigenvects(self, error_when_incomplete=True, iszerofunc=_iszero, **flags):


~/.local/lib/python3.8/site-packages/sympy/matrices/eigen.py in _eigenvals(M, error_when_incomplete, **flags)
    178         if not multiple and sum(eigs.values()) != M.rows or \
    179             multiple and len(eigs) != M.cols:
--> 180             raise MatrixError(
    181                 "Could not compute eigenvalues for {}".format(M))
    182


MatrixError: Could not compute eigenvalues for Matrix([[3, -1, 1, 1, 0, 0], [-1, 2, 0, 1, 0, 0], [1, 0, 1, 0, 0, 0], [1, 1, 0, 1, 1, 0], [0, 0, 0, 1, 4, 1], [0, 0, 0, 1, 1, 2]])


B1.diagonalize()                                                        
---------------------------------------------------------------------------
MatrixError                               Traceback (most recent call last)
<ipython-input-6-e1b11adc4556> in <module>
----> 1 B1.diagonalize()


~/.local/lib/python3.8/site-packages/sympy/matrices/matrices.py in diagonalize(self, reals_only, sort, normalize)
    375
    376     def diagonalize(self, reals_only=False, sort=False, normalize=False):
--> 377         return _diagonalize(self, reals_only=reals_only, sort=sort,
    378                 normalize=normalize)
    379


~/.local/lib/python3.8/site-packages/sympy/matrices/eigen.py in _diagonalize(M, reals_only, sort, normalize)
    599         raise NonSquareMatrixError()
    600
--> 601     is_diagonalizable, eigenvecs = _is_diagonalizable_with_eigen(M,
    602                 reals_only=reals_only)
    603


~/.local/lib/python3.8/site-packages/sympy/matrices/eigen.py in _is_diagonalizable_with_eigen(M, reals_only)
    336         return False, []
    337
--> 338     eigenvecs = M.eigenvects(simplify=True)
    339
    340     for val, mult, basis in eigenvecs:


~/.local/lib/python3.8/site-packages/sympy/matrices/matrices.py in eigenvects(self, error_when_incomplete, iszerofunc, **flags)
    368
    369     def eigenvects(self, error_when_incomplete=True, iszerofunc=_iszero, **flags):
--> 370         return _eigenvects(self, error_when_incomplete=error_when_incomplete,
    371                 iszerofunc=iszerofunc, **flags)
    372


~/.local/lib/python3.8/site-packages/sympy/matrices/eigen.py in _eigenvects(M, error_when_incomplete, iszerofunc, **flags)
    301         M = M.applyfunc(lambda x: nsimplify(x, rational=True))
    302
--> 303     eigenvals = M.eigenvals(
    304         rational=False, error_when_incomplete=error_when_incomplete,
    305         **flags)


~/.local/lib/python3.8/site-packages/sympy/matrices/matrices.py in eigenvals(self, error_when_incomplete, **flags)
    365
    366     def eigenvals(self, error_when_incomplete=True, **flags):
--> 367         return _eigenvals(self, error_when_incomplete=error_when_incomplete, **flags)
    368
    369     def eigenvects(self, error_when_incomplete=True, iszerofunc=_iszero, **flags):


~/.local/lib/python3.8/site-packages/sympy/matrices/eigen.py in _eigenvals(M, error_when_incomplete, **flags)
    178         if not multiple and sum(eigs.values()) != M.rows or \
    179             multiple and len(eigs) != M.cols:
--> 180             raise MatrixError(
    181                 "Could not compute eigenvalues for {}".format(M))
    182


MatrixError: Could not compute eigenvalues for Matrix([[3, -1, 1, 1, 0, 0], [-1, 2, 0, 1, 0, 0], [1, 0, 1, 0, 0, 0], [1, 1, 0, 1, 1, 0], [0, 0, 0, 1, 4, 1], [0, 0, 0, 1, 1, 2]])

It seems, at least from my experience, that 2 by 2 matrices work.
3 by 3 matrices do not return anything, neither output, nor error, bur occasionally they work.
So far, I have found only a single 3 by 3 matrix that works (it works on Sympy Live, on my Linux with SymPy 1.5.1 as well as SymPy 1.6rc1)
W = Matrix(([1, 2, 2], [2, 5, 10], [2, 10, 26] ))

W.is_indefinite
All 6 by 6 matrices I have tried so far have returned an error.

I have also tried matrices of other sizes by deleting rows and columns form matrix B1. (on SymPy 1.6rc1it as well as Sympy Live )

4 by 4 matrix does not return anything, neither output, nor error.
5 by 5 matrix returns error raise MatrixError( "Could not compute eigenvalues for {}".format(M)) MatrixError: Could not compute eigenvalues for Matrix

B1_44 = Matrix(([3, -1, 1, 1], [-1, 2, 0, 1], [1, 0, 1, 0], [1, 1, 0, 1]))
B1_44.is_indefinite

B1_55 = Matrix(([3, -1, 1, 1, 0], [-1, 2, 0, 1, 0], [1, 0, 1, 0, 0], [1, 1, 0, 1, 1], [0, 0, 0, 1, 4]))
B1_55.is_indefinite

By an accident I have created non-square 6 by 5 matrix.

On SymPy live (SymPy 1.5.1, Python 2.7.12) it does not return anything, on my Linux computer (SymPy 1.6rc1, Python 3.8.2-64-bit)

for B1.is_indefinite it has returned False.

I find this rather strange as I thought that Definiteness of a matrix is only for the square matrices.

B1_65 = Matrix(([3, -1, 1, 1, 0], [-1, 2, 0, 1, 0], [1, 0, 1, 0, 0], [1, 1, 0, 1, 1], [0, 0, 0, 1, 4], [0, 0, 0, 1, 1] ))
B1_65.is_indefinite

 

On Thursday, May 14, 2020 at 11:57:15 AM UTC+2, Oscar wrote:

There have been some recent improvements to the code handling this
which you could try out by installing the pre-release of 1.6 with pip:

    pip install -U --pre sympy

--
Oscar

> To unsubscribe from this group and stop receiving emails from it, send an email to sy...@googlegroups.com.

[Oscar Benjamin]

Looking at it seems that the improvements were for `is_positive_definite`, `is_positive_semidefinite` etc rather than `is_indefinite`.

These cases compute fine:

In [11]: B1.is_positive_semidefinite                                               Out[11]: False

In [12]: B1.is_negative_semidefinite                                               Out[12]: False

I think that should be enough to conclude that the matrix is indefinite. The improvements are that the algorithms for those cases no longer attempt to compute the eigenvalues. Computing the eigenvalues symbolically is not usually possible for bigger than a 4x4 matrix due to Abel-Ruffini:

https://en.wikipedia.org/wiki/Abel%E2%80%93Ruffini_theorem

As a workaround you can convert to a matrix of floats since then the eigenvalues can be computed approximately by mpmath:

In [13]: B1.n().eigenvals()                                                        Out[13]: {-0.423518261117994: 1, 0.830838432644968: 1, 1.57353243409785: 1, 2.309362853398: 1, 3.91273545644822: 1, 4.79704908452897: 1}

In [14]: B1.n().is_indefinite                                                      Out[14]: True

--

Oscar

[JS]

Thank you.

This has worked for all matrices that I have tried. : - )

Even M.is_positive_definite and M.is_negative_definite works. 

[JS]

Should I report it as a bug on the github? There is currently none for is_indefinite.

Writing something like

"is_indefinite returns error when it attempts to compute the eigenvalues.

Try to import the improvments `is_positive_definite`, `is_positive_semidefinite` etc rather than `is_indefinite`, no longer attempt to compute the eigenvalues. Computing the eigenvalues symbolically is not usually possible for bigger than a 4x4 matrix due to Abel-Ruffini.

Converting to a matrix M to matrix of floats M.n() works as a workaround since then the eigenvalues can be computed approximately by mpmath."?

and giving a link to this conversation?

[Oscar Benjamin]

On Thu, 14 May 2020 at 14:05, JS <jakub....@gmail.com> wrote:
>
> Should I report it as a bug on the github? There is currently none for is_indefinite.
> Writing something like
> "is_indefinite returns error when it attempts to compute the eigenvalues.
> Try to import the improvments `is_positive_definite`, `is_positive_semidefinite` etc rather than `is_indefinite`, no longer attempt to compute the eigenvalues. Computing the eigenvalues symbolically is not usually possible for bigger than a 4x4 matrix due to Abel-Ruffini.
> Converting to a matrix M to matrix of floats M.n() works as a workaround since then the eigenvalues can be computed approximately by mpmath."?
> and giving a link to this conversation?

Yes, that would be great. It's probably also worth noting that if we
are just trying to determine the definiteness of the matrix then
computing the eigenvalues as Floats (when possible) with mpmath would
be much faster.

--
Oscar

[S.Y. Lee]

I've opened an issue at https://github.com/sympy/sympy/issues/19365