Suppose I have a Laplacain matrix for a 3-node-path graph as follows

$L=\left[\begin{array}{ccc} 1 & -1 & 0\\ -1 & 2 & -1\\ 0 & -1 & 1 \end{array}\right]$

Now, I want to perturb the L matrix by plus rank-one matrix $M_1=\left[\begin{array}{ccc} 1\\ & 0\\ & & 0 \end{array}\right]$ and $M_2=\left[\begin{array}{ccc} 0\\ & 1\\ & & 0 \end{array}\right]$ respectively.

Denote $A_1 = L+M_1$ and $A_2=L+M_2$. Then calculate their smallest eigenvalue and corresponding eigenvector we have:

For $A_1$ the smallest eigenvalue $\lambda_1 = 0.1981$ with normalized eigenvector $v_1=\left[\begin{array}{ccc} 0.3280\\ 0.5910\\ 0.7370 \end{array}\right]$ and for $A_2$ the smallest eigenvalue $\lambda^{'}_1 = 0.2679$ with normalized eigenvector $v^{'}_1=\left[\begin{array}{ccc} 0.6280\\ 0.4597\\ 0.6280 \end{array}\right]$.

Can anybody show some hints on why $\lambda^{'}_1 >\lambda_1$ and $|v^{'}_{1}(2)|= 0.4597 > 0.3280 =|v_1(1)|$ ?

p.s. The reason I pick $|v_1(1)|$ and $|v^{'}_{1}(2)|$ is that they correspond to the 1 element in $M_1$ and $M_2$ matrix.


  • $\begingroup$ Eigenvectors should not be considered to have magnitude since they represent a class of vectors, a direction not a point. Are you then asking only about the eigenvalues? If so, if it is a fact then it is just a fact, are you asking how it relates to the perturbations? $\endgroup$ – adam W Mar 14 '14 at 19:26
  • $\begingroup$ Thanks for your reply. Sorry I forget to mention that the eigenvector is normalized. I concern the magnitude of certain element in the eigenvector more because, through large amount of calculation examples, the magnitude represents the importance of the node in a graph. For the example in the question, that is, the middle node is more important than the node on the boundary because $|v^{'}_{1}(2)|= 0.4597 > 0.3280 =|v_1(1)|$. $\endgroup$ – user96212 Mar 14 '14 at 19:46

Look at the characteristic polynomials for the two matrices $A_{1}$ and $A_{2}$. They are the same, except for the coefficient of the $\lambda$ term, which differs by $1$:

$\chi(A_{1}, \lambda) = -\lambda^{3} + 5\lambda^{2} - 6\lambda + 1$

$\chi(A_{2}, \lambda) = -\lambda^{3} + 5\lambda^{2} - 5\lambda + 1$

So you have less of a negative pull on $\chi(A_{2}, \lambda)$ than on $\chi(A_{1}, \lambda)$. As such, the smallest eigenvalue will be bigger naturally (and intuitively) for $\chi(A_{2}, \lambda)$ than for $\chi(A_{1}, \lambda)$.

Also, note that the coefficient for $\lambda^{i}$ for $i \in \{0, ..., n-1\}$ is $(-1)^{i}$ times the sum of the $i \times i$ principal minors. So that's the linear algebra that's going on. The first coefficient, the $5 \lambda^{2}$, is from the trace of the Laplacian. The second coefficient is the sum of the $2 \times 2$ principal minors, and the third coefficient is $det(L)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.