MATH
Login Or Sign up

Eigenvalues of a $20 \times 20$ symmetric matrix

270 Views Asked by At

$$\left[\begin{smallmatrix} 19&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1\\ 1&19&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1\\ 1&1&17&1&1&0&1&1&1&1&1&1&1&1&1&0&1&1&1&1\\ 1&1&1&19&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1\\ 1&1&1&1&16&0&1&1&1&1&0&1&1&1&1&0&1&1&1&1\\ 1&1&0&1&0&11&0&1&0&1&1&1&0&1&0&1&0&1&0&1\\ 1&1&1&1&1&0&17&1&1&1&1&1&1&1&1&0&1&1&1&1\\ 1&1&1&1&1&1&1&19&1&1&1&1&1&1&1&1&1&1&1&1\\ 1&1&1&1&1&0&1&1&16&1&0&1&1&1&1&0&1&1&1&1\\ 1&1&1&1&1&1&1&1&1&19&1&1&1&1&1&1&1&1&1&1\\ 1&1&1&1&0&1&1&1&0&1&15&1&0&1&1&1&0&1&1&1\\ 1&1&1&1&1&1&1&1&1&1&1&19&1&1&1&1&1&1&1&1\\ 1&1&1&1&1&0&1&1&1&1&0&1&16&1&1&0&1&1&1&1\\ 1&1&1&1&1&1&1&1&1&1&1&1&1&19&1&1&1&1&1&1\\ 1&1&1&1&1&0&1&1&1&1&1&1&1&1&17&0&1&1&1&1\\ 1&1&0&1&0&1&0&1&0&1&1&1&0&1&0&11&0&1&0&1\\ 1&1&1&1&1&0&1&1&1&1&0&1&1&1&1&0&16&1&1&1\\ 1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&19&1&1\\ 1&1&1&1&1&0&1&1&1&1&1&1&1&1&1&0&1&1&17&1\\ 1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&19 \end{smallmatrix}\right] $$

Using a software, I found that $18$ is an eigenvalue of this matrix, with multiplicity $9$. I need to prove it mathematically. Since the matrix is real and symmetric, I thought of finding the nullity of $A-18I$ but that's tough to compute. Is there any other way to prove it ?

linear-algebra matrices eigenvalues-eigenvectors symmetric-matrices
Original Q&A
4

There are 4 best solutions below

1
On

If you look at $A - 18I$ you will see you have $9$ rows of only ones (each corresponding to a row of $A$ with $19$ on the diagonal).

Those rows are obviously linearly depended. $8$ of them are the copies of the first one in fact.

You can now simplify the problem:

  1. write down the matrix $A - 18I$ but remove $8$ of the rows with ones only (since they are linearly dependent anyways so they won't change the dimensions!)
  2. Look for columns that have the same entries. Those will not change the linear dependency at all! So you can remove them as well.
  3. You should be now left with way smaller matrix.

In worst case (there are no columns to remove in step 2) you will have an $10 \times 18$ matrix. You should try to put it in echelon form (if 18 is indeed an eigenvalue with multiplicity 8 then this should be possible without getting any zero rows.)

Hope this helps!

5
On

Let $e$ be the all-one vector and $K=(6,16,11,5,9,13,17,3,7,15,19,1,2,4,8,10,12,14,18,20)$. Then $$ A(K,K) = 18\,I + ee^T - ((D+F)\oplus 0_{9\times9}), $$ where $D=\operatorname{diag}(8,8,4,3,3,3,3,2,2,2,2)$ and $$ F=\pmatrix{ 0&0&0&1&1&1&1&1&1&1&1\\ 0&0&0&1&1&1&1&1&1&1&1\\ 0&0&0&1&1&1&1&0&0&0&0\\ 1&1&1&0&0&0&0&0&0&0&0\\ 1&1&1&0&0&0&0&0&0&0&0\\ 1&1&1&0&0&0&0&0&0&0&0\\ 1&1&1&0&0&0&0&0&0&0&0\\ 1&1&0&0&0&0&0&0&0&0&0\\ 1&1&0&0&0&0&0&0&0&0&0\\ 1&1&0&0&0&0&0&0&0&0&0\\ 1&1&0&0&0&0&0&0&0&0&0}. $$ Note that $(1,1,1,-1,-1,-1,-1,-1,-1,-1,-1)^\top\in\ker(D+F)$. Therefore,

  • the nullity of $D+F$ is at least $1$,
  • the nullity of $(D+F)\oplus 0_{9\times9}$ is at least $10$,
  • the nullity of $ee^T - ((D+F)\oplus 0_{9\times9})$ is at least $9$, and
  • $A(K,K)=18\,I + ee^T - ((D+F)\oplus 0_{9\times9})$ has an eigenvalue $18$ of multiplicity $\ge9$.

Now the conclusion follows because $A$ and $A(K,K)$ have the same spectrum.

1
On

Using SymPy:

from sympy import *

A = Matrix([[19,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1],
            [ 1, 19,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1],
            [ 1,  1, 17,  1,  1,  0,  1,  1,  1,  1,  1,  1,  1,  1,  1,  0,  1,  1,  1,  1],
            [ 1,  1,  1, 19,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1],
            [ 1,  1,  1,  1, 16,  0,  1,  1,  1,  1,  0,  1,  1,  1,  1,  0,  1,  1,  1,  1],
            [ 1,  1,  0,  1,  0, 11,  0,  1,  0,  1,  1,  1,  0,  1,  0,  1,  0,  1,  0,  1],
            [ 1,  1,  1,  1,  1,  0, 17,  1,  1,  1,  1,  1,  1,  1,  1,  0,  1,  1,  1,  1],
            [ 1,  1,  1,  1,  1,  1,  1, 19,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1],
            [ 1,  1,  1,  1,  1,  0,  1,  1, 16,  1,  0,  1,  1,  1,  1,  0,  1,  1,  1,  1],
            [ 1,  1,  1,  1,  1,  1,  1,  1,  1, 19,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1],
            [ 1,  1,  1,  1,  0,  1,  1,  1,  0,  1, 15,  1,  0,  1,  1,  1,  0,  1,  1,  1],
            [ 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, 19,  1,  1,  1,  1,  1,  1,  1,  1],
            [ 1,  1,  1,  1,  1,  0,  1,  1,  1,  1,  0,  1, 16,  1,  1,  0,  1,  1,  1,  1],
            [ 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, 19,  1,  1,  1,  1,  1,  1],
            [ 1,  1,  1,  1,  1,  0,  1,  1,  1,  1,  1,  1,  1,  1, 17,  0,  1,  1,  1,  1],
            [ 1,  1,  0,  1,  0,  1,  0,  1,  0,  1,  1,  1,  0,  1,  0, 11,  0,  1,  0,  1],
            [ 1,  1,  1,  1,  1,  0,  1,  1,  1,  1,  0,  1,  1,  1,  1,  0, 16,  1,  1,  1],
            [ 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, 19,  1,  1],
            [ 1,  1,  1,  1,  1,  0,  1,  1,  1,  1,  1,  1,  1,  1,  1,  0,  1,  1, 17,  1],
            [ 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, 19]])

s = Symbol('s')
p = (s * eye(20) - A).det()

The characteristic polynomial is

>>> print p
s**20 - 340*s**19 + 54682*s**18 - 5532760*s**17 + 395069941*s**16 - 21166131356*s**15 + 882953073528*s**14 - 29370793354368*s**13 + 791321447285872*s**12 - 17440025771736000*s**11 + 316151576030552832*s**10 - 4722592405018189824*s**9 + 58030753657512358656*s**8 - 583406463683957216256*s**7 + 4751863719311098607616*s**6 - 30874863028022989553664*s**5 + 156275998101853212119040*s**4 - 593868884118152929689600*s**3 + 1593920286142768447488000*s**2 - 2693994644579903078400000*s + 2156402247949143244800000

Factoring the characteristic polynomial, we obtain

>>> p.factor()
(s - 18)**9*(s - 16)**3*(s - 15)**3*(s - 10)*(s**4 - 75*s**3 + 1924*s**2 - 20588*s + 78640)

Printing in $\LaTeX$, we have

$$p (s) = \left(s - 18\right)^{9} \left(s - 16\right)^{3} \left(s - 15\right)^{3} \left(s - 10\right) \left(s^{4} - 75 s^{3} + 1924 s^{2} - 20588 s + 78640\right)$$

Note that eigenvalue $18$ has multiplicity $9$. Alternatively,

>>> (A - 18 * eye(20)).rank()
11

and, thus, the nullity of matrix $\mathrm A - 18 \,\mathrm I_{20}$ is equal to $20-11 = 9$.

Addendum

We can also find the roots of the quartic $s^{4} - 75 s^{3} + 1924 s^{2} - 20588 s + 78640$, as follows

>>> roots = solve(s**4 - 75*s**3 + 1924*s**2 - 20588*s + 78640, s)
>>> for r in roots:
        simplify(r)

    75/4 - 11**(5/6)*sqrt(4449*11**(1/3) + 78936/(4441 + 12*sqrt(1904982)*I)**(1/3) + 24*11**(2/3)*(4441 + 12*sqrt(1904982)*I)**(1/3))/132 - 11**(11/12)*sqrt(8898*11**(1/6) - 24*sqrt(11)*(4441 + 12*sqrt(1904982)*I)**(1/3) - 168822*11**(1/3)*sqrt(3)/sqrt(1483*11**(1/3) + 26312/(4441 + 12*sqrt(1904982)*I)**(1/3) + 8*11**(2/3)*(4441 + 12*sqrt(1904982)*I)**(1/3)) - 7176*11**(5/6)/(4441 + 12*sqrt(1904982)*I)**(1/3))/132
    75/4 - 11**(5/6)*sqrt(4449*11**(1/3) + 78936/(4441 + 12*sqrt(1904982)*I)**(1/3) + 24*11**(2/3)*(4441 + 12*sqrt(1904982)*I)**(1/3))/132 + 11**(11/12)*sqrt(8898*11**(1/6) - 24*sqrt(11)*(4441 + 12*sqrt(1904982)*I)**(1/3) - 168822*11**(1/3)*sqrt(3)/sqrt(1483*11**(1/3) + 26312/(4441 + 12*sqrt(1904982)*I)**(1/3) + 8*11**(2/3)*(4441 + 12*sqrt(1904982)*I)**(1/3)) - 7176*11**(5/6)/(4441 + 12*sqrt(1904982)*I)**(1/3))/132
    75/4 - 11**(11/12)*sqrt(8898*11**(1/6) - 24*sqrt(11)*(4441 + 12*sqrt(1904982)*I)**(1/3) + 168822*11**(1/3)*sqrt(3)/sqrt(1483*11**(1/3) + 26312/(4441 + 12*sqrt(1904982)*I)**(1/3) + 8*11**(2/3)*(4441 + 12*sqrt(1904982)*I)**(1/3)) - 7176*11**(5/6)/(4441 + 12*sqrt(1904982)*I)**(1/3))/132 + 11**(5/6)*sqrt(4449*11**(1/3) + 78936/(4441 + 12*sqrt(1904982)*I)**(1/3) + 24*11**(2/3)*(4441 + 12*sqrt(1904982)*I)**(1/3))/132
    75/4 + 11**(11/12)*sqrt(8898*11**(1/6) - 24*sqrt(11)*(4441 + 12*sqrt(1904982)*I)**(1/3) + 168822*11**(1/3)*sqrt(3)/sqrt(1483*11**(1/3) + 26312/(4441 + 12*sqrt(1904982)*I)**(1/3) + 8*11**(2/3)*(4441 + 12*sqrt(1904982)*I)**(1/3)) - 7176*11**(5/6)/(4441 + 12*sqrt(1904982)*I)**(1/3))/132 + 11**(5/6)*sqrt(4449*11**(1/3) + 78936/(4441 + 12*sqrt(1904982)*I)**(1/3) + 24*11**(2/3)*(4441 + 12*sqrt(1904982)*I)**(1/3))/132
0
On

here are a basis of 18 eigenvectors, written as 9 rows, which is alright as the matrix is symmetric

[-1 1 0 0 0  0 0 0 0 0  0 0 0 0 0  0 0 0 0 0]

[-1 0 0 1 0  0 0 0 0 0  0 0 0 0 0  0 0 0 0 0]

[-1 0 0 0 0  0 0 1 0 0  0 0 0 0 0  0 0 0 0 0]

[-1 0 0 0 0  0 0 0 0 1  0 0 0 0 0  0 0 0 0 0]

[-1 0 0 0 0  0 0 0 0 0  0 1 0 0 0  0 0 0 0 0]

[-1 0 0 0 0  0 0 0 0 0  0 0 0 1 0  0 0 0 0 0]

[-1 0 0 0 0  0 0 0 0 0  0 0 0 0 0  0 0 1 0 0]

[-5 0 1 0 1 -1 1 0 1 0 -1 0 1 0 1 -1 1 0 1 0]

[-1 0 0 0 0  0 0 0 0 0  0 0 0 0 0  0 0 0 0 1]

for verisimilitude, here is what happens when we multiply this 9 by 20 matrix by the symmetric 20 by 20:

[-18 18  0  0  0   0  0  0  0  0   0  0  0  0  0   0  0  0  0  0]

[-18  0  0 18  0   0  0  0  0  0   0  0  0  0  0   0  0  0  0  0]

[-18  0  0  0  0   0  0 18  0  0   0  0  0  0  0   0  0  0  0  0]

[-18  0  0  0  0   0  0  0  0 18   0  0  0  0  0   0  0  0  0  0]

[-18  0  0  0  0   0  0  0  0  0   0 18  0  0  0   0  0  0  0  0]

[-18  0  0  0  0   0  0  0  0  0   0  0  0 18  0   0  0  0  0  0]

[-18  0  0  0  0   0  0  0  0  0   0  0  0  0  0   0  0 18  0  0]

[-90  0 18  0 18 -18 18  0 18  0 -18  0 18  0 18 -18 18  0 18  0]

[-18  0  0  0  0   0  0  0  0  0   0  0  0  0  0   0  0  0  0 18]

here is the 9 by 9 Gram matrix for this basis 

[2 1 1 1 1 1 1  5 1]

[1 2 1 1 1 1 1  5 1]

[1 1 2 1 1 1 1  5 1]

[1 1 1 2 1 1 1  5 1]

[1 1 1 1 2 1 1  5 1]

[1 1 1 1 1 2 1  5 1]

[1 1 1 1 1 1 2  5 1]

[5 5 5 5 5 5 5 36 5]

[1 1 1 1 1 1 1  5 2]

characteristic polynomial of this Gram matrix is $(x-1)^7 (x^2 - 45 x + 124)$ so it is positive definite and the nine rows really are linearly independent. As it is relevant: the roots of $x^2 - 45 x + 124$ are positive and approximately $2.9487852 \; , \; \; \; 42.0512148 \; \; .$

====================================================================

the three 16

[0 0 -1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]

[0 0 -1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0]

[0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0]

here is the Gram matrix of inner products for these three

[2 1 1]

[1 2 1]

[1 1 2]

this characteristic polynomial is $(x-1)^2 (x-4)$

========================================================

for 15:

[0 0 0 0 -1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0]

[0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]

gram, same as 16

[2 1 1]

[1 2 1]

[1 1 2]

======================================================

for 10, just one row

[0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 1 0 0 0 0]

============================================

Related Questions in LINEAR-ALGEBRA

Related Questions in MATRICES

Related Questions in EIGENVALUES-EIGENVECTORS

Related Questions in SYMMETRIC-MATRICES

Trending Questions

Popular # Hahtags

second-order-logic numerical-methods puzzle logic probability number-theory winding-number real-analysis integration calculus complex-analysis sequences-and-series proof-writing set-theory functions homotopy-theory elementary-number-theory ordinary-differential-equations circles derivatives game-theory definite-integrals elementary-set-theory limits multivariable-calculus geometry algebraic-number-theory proof-verification partial-derivative algebra-precalculus

Popular Questions

Copyright © 2021 JogjaFile Inc.