## Eigenvalues of sum of an adjacent matrix and a constant

$A$ is an adjacent matrix of a network. $la$ is the largest eigenvalue of $A$ and $Va$ is its corresponding eigenvector.

I am interested in the following martix: $bA+c-dI$ ($b$, $c$, and $d$ are all real constants, $bA+c$ is obtained by multiply each element of $A$ by $b$ and then increased it by $c$, $I$ is the Identity matrix)

Let $lac$ be the largest eigenvalue of $bA+c-dI$.

I want to obtain an approximate function: $lac=F(la,c,..)$. Could you help me on this?

Thanks.

-
 Sorry, I clicked "close" by mistake---please count my "undo" of that. – S. Sra Feb 11 2012 at 23:36

An easy upper bound is $la+nc$, where $n$ is the dimension. This is because the matrix norm of a sum is no more than the sum of the matrix norms.

An easy lower bound is $k+nc$, where $k$ is the average vertex degree. This is because, for all $v$, $v \cdot Mv/||v||^2$ is no more than the highest eigenvalue of $M$. The vector of all $1$s provides this lower bound.

If your graph is approximately regular, $la$ is not much more than $k$, and these bounds will be relatively close.

-
Thanks for the swift answer! Could you provide more details about how to get the lower bound $k+nc$ from " for all v, v⋅Mv/||v||2 is no more than the highest eigenvalue of M. " If I change the interested matrix from $A+c$ to $bA+c$ ($b$ and $c$ are both constant). Should the largest eigenvalue of $aA+c$ in the range of $[b*la+nc, b*k+nc]$? Thanks. – Leo Feb 11 2012 at 23:13
The vector of all $1$s turns into a vector of, for each vertex, the degree of that vertex plus $c$. The dot product of that with itself is twice the number of edges plus $nc$. Its norm is $n$ so we can divide and get that estimate. Due to constant scaling of matrices scaling their eigenvalues, your second statement is correct. – Will Sawin Feb 11 2012 at 23:53
When $v$ is the vector of all $1$s, $v \cdot Mv/||v||^2=(nk+n^2c)/(\sqrt{n})^2=k+nc$, right? That is really helpful for me. Could give me the reference for "for all $v$, $v \cdot Mv/||v||^2$ is no more than the highest eigenvalue of $M$." What is the theory foundation for this? Thanks. – Leo Feb 12 2012 at 12:10
Since the eigenvectors are perpendicular, you can diagonalize the matrix by changing orthonormal basis. So proving it for diagonal matrices is sufficient. Then explicitly write down the formula for $Mv \cdot v$ and compare to $||v||^2$. – Will Sawin Feb 12 2012 at 16:04
Let $\lambda_1$ be the highest eigenvalue, then $\lambda_i \leq \lambda_1$ so the expression simplifies to $Mv \cdot v \leq \lamda_1 \sum (lv_i \cdot v)^2$. Since $lv_i$ is an orthonormal basis, $\sum (lv_i \cdot v)^2=||v||^2$. – Will Sawin Feb 12 2012 at 21:35

Let $\lambda(A)$ denote the eigenvalues of any matrix $A$. First note that $\lambda(bA-dI) = b\lambda(A)-d$. So, we can ignore the scaling and shifting. Now, let us look at the slightly more general result (at least for the case $c \ge 0$ in your question).

If $\alpha_1\ge \cdots \ge \alpha_n$ are the eigenvalues of a matrix $A$, and $\beta_1 \ge \cdots \ge \beta_n$ are the eigenvalues of the matrix $A+xx^T$. Then, we have the following interlacing result:

\begin{equation*} \beta_1 \ge \alpha_1 \ge \beta_2 \ge \alpha_2 \ge \cdots \ge \beta_n \ge \alpha_n. \end{equation*}

I mention in passing, for a more general rank-1 perturbation, along with perhaps other useful specializations, you might benefit from skimming the paper "Eigenvalues of rank one perturbations of unstructured matrices" by A.C.M. Ran, M. Wojtylak, and also by chasing some of the references they provide for the simpler case that you are treating (namely, the rank-1 perturbation is: $c11^T$)---see also this paper.

-
 Also, for numerical purposes, you might want to look at: mathoverflow.net/questions/67924/… – S. Sra Feb 12 2012 at 0:01