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.
 A: 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.
A: 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.
