Ask Your Question
0

how one can obtain eigenvalue and eigenvectors from a list of matrices at a single step

asked 2017-08-10 10:21:29 -0600

A gravatar image

how one can obtain eigenvalue and eigenvectors from a list of matrices at a single step?I have tried the following code which results in three matrices and I need only the eigenvector in all three cases that corresponds to the second smallest eigenvalue.

for G in graphs.trees(18): if G.diameter()==5: L=G.laplacian_matrix().eigenvalues() L.sort() if L[1]*L[17]==1: print L G.show() show(G.laplacian_matrix())

edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted
0

answered 2017-08-13 05:14:11 -0600

dan_fulea gravatar image

updated 2017-08-18 12:51:49 -0600

kcrisman gravatar image

This answer uses also networkx, else there is an overlap with the answer of fidbc .

First of all let us restate the question in a mathematical setting, fixing thus the key words for programming in sage.

Let $T$ be a tree with $n$ verices. Let $L=L(T)$ be the laplacian matrix of $T$. The laplace spectrum of $T$ is the spectrum of $L$, $$\mu_1\ge \mu_2\ge \dots\ge \mu_{n-1}\ge\mu_n=0\ .$$ (Here, $0$ is always an eigenvalue with eigenvector $(1,1,\dots,1)$, since $T$ is connected. Its multiplicity is one.)

The second smallest value $\mu_{n-1}=a(T)$ is the

algebraic connectivity

of $T$. The biggest eigenvalue $\mu_1$ is the laplace spectral radius of $T$. Aka the norm of $L$.

The posted questions wants among all trees $T$ with $n=18$ vertices and diameter $d=5$ those $T$ with $$\mu_1\mu_{n-1} = 1\ .$$ Then for each such tree $T$ also the Fiedler vector (see loc. cit.), i.e. the $L$--eigenvector corresponding to the algebraic connectivity $a(T)=\mu_{n-1}$.

There are $2015$ relevant trees with $n=18$ vertices and diameter $5$ .

sage: T18_5 = [ T for T in graphs.trees(18) if T.diameter() == 5 ]
sage: len( T18_5 )
2015

We select the needed subset:

T_LIST = []
# count = 0
for T in T18_5:
    spec = T.laplacian_matrix().eigenvalues()
    spec . sort()
    # count += 1
    # if count%100 == 0:    print count 
    if spec[1] * spec[-1] == 1:
        T_LIST.append( T )

Using networkx we can now ask for...

from networkx import algebraic_connectivity as a
from networkx import fiedler_vector         as fiedler

for T in T_LIST:
    Tx = T.networkx_graph()
    print "a(T) = %s\nFiedler vector:\n%s\n" % ( a(Tx), fiedler(Tx) )

and get:

a(T) = 0.127016653793
Fiedler vector:
[-0.12469138  0.12469138  0.28566726  0.32723106  0.32723105  0.32723106
  0.14283363  0.14283363  0.14283363  0.14283363 -0.28566726 -0.32723107
 -0.32723105 -0.32723104 -0.14283363 -0.14283362 -0.14283364 -0.14283364]

a(T) = 0.14589803375
Fiedler vector:
[-0.15316861  0.15316861  0.22416617  0.26245832  0.22416619  0.26245836
  0.22416616  0.26245831  0.22416616  0.26245831 -0.22416618 -0.26245834
 -0.22416617 -0.26245833 -0.22416615 -0.26245829 -0.22416618 -0.26245834]

a(T) = 0.133108958618
Fiedler vector:
[-0.06494166  0.19176279  0.2688225   0.31009952  0.2688225   0.31009952
  0.2688225   0.31009952 -0.25699018 -0.29645038 -0.29645038 -0.29645038
 -0.29645038 -0.09103845 -0.1050172  -0.07491327 -0.07491327 -0.07491327]

This is all.

Note: Outside networkx we can also get valuable information, for instance ask for the minimal polynomial of the algebraic_connectivity:

E = matrix.identity(18)
for T in T_LIST:
    L =  T.laplacian_matrix()
    spec = L.eigenvalues()
    spec . sort()

    print "  a(T)   = %s with minpoly = %s" % ( spec[ 1], spec[ 1].minpoly() )
    print "| L(T) | = %s with minpoly = %s" % ( spec[-1], spec[-1].minpoly() )
    print "Fiedler vector:\n%s\n\n" % column_matrix(( L - spec[1]*E ).kernel().basis()[0])
    # printed version of ( L - spec[1]*E ).kernel()

This gives:

  a(T)   = 0.1270166537925831? with minpoly = x^2 - 8*x + 1
| L(T) | = 7.872983346207417? with minpoly = x^2 - 8*x + 1
Fiedler vector:
[                  1]
[                 -1]
[-2.290994448735806?]
[-2.624327782069139?]
[-2.624327782069139?]
[-2.624327782069139?]
[-1.145497224367903?]
[-1.145497224367903?]
[-1.145497224367903?]
[-1.145497224367903?]
[ 2.290994448735806?]
[ 2.624327782069139?]
[ 2.624327782069139?]
[ 2.624327782069139?]
[ 1.145497224367903?]
[ 1.145497224367903?]
[ 1.145497224367903?]
[ 1.145497224367903?]


  a(T)   = 0.1458980337503155? with minpoly = x^2 - 7*x + 1
| L(T) | = 6.854101966249684? with minpoly = x^2 - 7*x + 1
Fiedler vector:
[                  1]
[                 -1]
[-1.463525491562421?]
[-1.713525491562421?]
[-1.463525491562421?]
[-1.713525491562421?]
[-1.463525491562421?]
[-1.713525491562421?]
[-1.463525491562421?]
[-1.713525491562421?]
[ 1.463525491562421?]
[ 1.713525491562421?]
[ 1.463525491562421?]
[ 1.713525491562421?]
[ 1.463525491562421?]
[ 1.713525491562421?]
[ 1.463525491562421?]
[ 1.713525491562421?]


  a(T)   = 0.1331089586175058? with minpoly = x^4 - 10*x^3 + 20*x^2 - 10*x + 1
| L(T) | = 7.512642352447085? with minpoly = x^4 - 10*x^3 + 20*x^2 - 10*x + 1
Fiedler vector:
[                  1]
[-2.952846325924191?]
[-4.139445001431823?]
[-4.775046463544424?]
[-4.139445001431823?]
[-4.775046463544424?]
[-4.139445001431823?]
[-4.775046463544424?]
[ 3.957245732488123?]
[ 4.564870950998888?]
[ 4.564870950998888?]
[ 4.564870950998888?]
[ 4.564870950998888?]
[ 1.401849112529162?]
[ 1.617099549550692?]
[ 1.153547507429801?]
[ 1.153547507429801?]
[ 1.153547507429801?]

In particular, we can identify the algebraic connectivity values as the algebraic numbers: $$ 4-\sqrt{15}\ ,\qquad \frac 12(7-3\sqrt{5})\ ,\qquad \frac 12\left( 5+\sqrt7-\sqrt{28+10\sqrt7} \right)\ .$$ The laplacian spectral radius (also nom) is obtained by replacing the minus with a plus each time.

edit flag offensive delete link more
0

answered 2017-08-10 11:27:24 -0600

fidbc gravatar image

updated 2017-08-10 11:28:52 -0600

Not entirely sure what you are asking. Specially:

  • "at a single step", you want to do this with a single command?
  • "eigenvalue and eigenvectors", later you say you only need the eigenvector.

Would you please clarify what you mean?

Here is something that might help.

Given a matrix M you may obtain eigenvalues and eigenvectors through M.eigenvectors_right(), see documentation for output specification.

Here is a modified version of your code which prints relevant eigenvectors.

for G in graphs.trees(18):
    if G.diameter()==5:
        L = G.laplacian_matrix()
        spec=L.eigenvalues()
        spec.sort()
        if spec[1]*spec[-1]==1:
            evs = sorted(L.eigenvectors_right())
            if evs[0][2]>1:
                print evs[0][1][0]
            else:
                print evs[1][1][0]

Which should output:

(1, -1, -2.290994448735806?, -2.624327782069139?, -2.624327782069139?, -2.624327782069139?, -1.145497224367903?, -1.145497224367903?, -1.145497224367903?, -1.145497224367903?, 2.290994448735806?, 2.624327782069139?, 2.624327782069139?, 2.624327782069139?, 1.145497224367903?, 1.145497224367903?, 1.145497224367903?, 1.145497224367903?)
(1, -1, -1.463525491562421?, -1.713525491562421?, -1.463525491562421?, -1.713525491562421?, -1.463525491562421?, -1.713525491562421?, -1.463525491562421?, -1.713525491562421?, 1.463525491562421?, 1.713525491562421?, 1.463525491562421?, 1.713525491562421?, 1.463525491562421?, 1.713525491562421?, 1.463525491562421?, 1.713525491562421?)
(1, -2.952846325924191?, -4.139445001431823?, -4.775046463544424?, -4.139445001431823?, -4.775046463544424?, -4.139445001431823?, -4.775046463544424?, 3.957245732488123?, 4.564870950998888?, 4.564870950998888?, 4.564870950998888?, 4.564870950998888?, 1.401849112529162?, 1.617099549550692?, 1.153547507429801?, 1.153547507429801?, 1.153547507429801?)
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-08-10 10:21:29 -0600

Seen: 95 times

Last updated: Aug 18