Sympy Could Not Compute The Eigenvalues Of This Matrix

I want to compute the second eigenvalue of a Laplacian matrix to check if the corresponding graph is connected or not, but when I try to use SymPy's eigenvals, a lot of times it ha

Solution 1:

Since the Laplacian is an integer matrix, let us use integers:

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

Computing the eigenvalues:

>>>L.eigenvals()
{0:3, 1:1, 2:1}

This is very strange, as the matrix is 10-by-10, not 5-by-5.

I tried to compute the Jordan normal form, but could not do it, as function jordan_form produced the error message IndexError: list index out of range.

Computing the characteristic polynomial:

>>>s = Symbol('s')>>>p = (s * eye(10) - L).det()>>>p
s**10 - 14*s**9 + 77*s**8 - 214*s**7 + 321*s**6 - 256*s**5 + 99*s**4 - 14*s**3

Note that the monomial of lowest degree is cubic. This allows us to conclude that the multiplicity of eigenvalue 0 is 3 and, thus, the graph is not connected.

Let us try to find the roots of the characteristic polynomial:

>>> solve(p,s)
[0, 0, 0, 1, 2, CRootOf(s**5 - 11*s**4 + 42*s**3 - 66*s**2 + 39*s - 7, 0), CRootOf(s**5 - 11*s**4 + 42*s**3 - 66*s**2 + 39*s - 7, 1), CRootOf(s**5 - 11*s**4 + 42*s**3 - 66*s**2 + 39*s - 7, 2), CRootOf(s**5 - 11*s**4 + 42*s**3 - 66*s**2 + 39*s - 7, 3), CRootOf(s**5 - 11*s**4 + 42*s**3 - 66*s**2 + 39*s - 7, 4)]

Note that only 5 roots were actually found (eigenvals produced only 5 eigenvalues, too). The 5 missing roots are the roots of the quintic s**5 - 11*s**4 + 42*s**3 - 66*s**2 + 39*s - 7.

It has been known since the 19th century that not all polynomials of degree 5 (or higher) have roots that can be expressed using arithmetic operations and radicals. Hence, we may be asking SymPy to do the impossible. Better use NumPy to compute approximate values of the 10 eigenvalues.

Solution 2:

You can get numerical approximations of all 10 roots of the characteristic polynomial using nroots after bumping up the maxsteps parameter for it:

>>>p = s**10 - 14*s**9 + 77*s**8 - 214*s**7 + 321*s**6 - 256*s**5 + 99*s**4 - 14*s**3>>>[i.n(2) for i in nroots(eq,maxsteps=100)]
[0, 0, 0, 0.32, 0.68, 1.0, 2.0, 2.1, 3.2, 4.6]

The CRootOf instances from solve(p, s) are actually solutions, too, that can be numerically evaluated:

>>> CRootOf(s**5 - 11*s**4 + 42*s**3 - 66*s**2 + 39*s - 7, 0).n(2)
0.32