2
$\begingroup$

I'm trying to find upper boundaries on the smallest Eigenvalue $\lambda_1$ of $L + E$, where $L$ is a standard Laplacian of an unweighted digraph, with $\lambda_1(L) = 0$ and $E \in \{0,1\}^{n \times n}$ is a diagonal matrix, with zeroes and ones as diagonal elements. Furthermore, we can assume that $L+E$ is regular. For $E = I$, the Identity-Matrix, it is fairly easy to show, that the smallest eigenvalue is $\lambda_1(L+I) = 1$, since
$(L+I)x_i = Lx_i + x_i = (\lambda_i+1)x_i$.

Though, for $E \neq I$, this is not as easy. I assume that $\lambda_1(L+E) \leq 1$ in this case. So my question is: How can I show this for $E \neq I$ or alternatively, is there a counter example to show that my assumption is wrong, so that the smallest eigenvalue $\lambda_1(L+E) > 1$?

I've tried Gershgorin disc-theorem so far, but it didn't help. The only other condition I've come up so far, is that
$\sum_i{\lambda_i(L+E)}=\text{trace}(L+E) = \text{trace}(L) + \text{trace}(E) = \sum_i{\lambda_i(L)}+\sum_i{\lambda_i(E)}$,
but I couldn't find any way to use this.

The background of this question is, that I assume, that the smallest eigenvalue of a grounded Laplacian in a leader-follower-structure cannot be greater than 1. For undirected graphs this has been shown to be true by Pirani and Sundaram (Article: "Spectral Properties of the Grounded laplacian Matrix ... "), by using the Perron-Frobenius Theorem and adding up all lines of the eigenvector equation of the smallest eigenvalue.

I'm very grateful for every nudge in the right direction!

Edit: Could working with norms answer my question? Since $|\lambda| \leq \left\|L\right\|$ and $1 \leq \left\|E\right\|$ (depending on the norm used) wouldn't this lead to $\|(L+E)v\| = \|Lv + Ev \| \leq |\lambda| + 1$ and thus limiting the growth of each eigenvalue of this addition to one?

$\endgroup$
  • $\begingroup$ Could you elaborate on that, please? As far as i know, the min-max theorem is only appliable on hermitian matrices. Since the laplacian of a digraph is not generally symmetric, this isn't it, I'm afraid. Or am I missing something? Thanks in Advance! $\endgroup$ – Flav Monty Jan 2 '15 at 22:09
  • $\begingroup$ Yes, sorry, I think I misunderstood the question. $\endgroup$ – Christian Remling Jan 2 '15 at 23:16
  • $\begingroup$ Could working with norms answer my question? Since |λ|≤∥L∥ and 1≤∥E∥ (depending on the norm used) wouldn't this lead to ∥(L+E)v∥=∥Lv+Ev∥≤|λ|+1 and thus limiting the growth of each eigenvalue of this addition to one? $\endgroup$ – Flav Monty Jan 3 '15 at 17:11

Your Answer

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

Browse other questions tagged or ask your own question.