# Rank-one modification of graph Laplacian

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.

Thanks!

• 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? – adam W Mar 14 '14 at 19:26
• 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)|$. – 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)$.