Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

$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.

share|improve this question
    
Sorry, I clicked "close" by mistake---please count my "undo" of that. –  Suvrit Feb 11 '12 at 23:36
add comment

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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 '12 at 23:13
1  
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 '12 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 '12 at 12:10
1  
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 '12 at 16:04
1  
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 '12 at 21:35
show 4 more comments

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.

share|improve this answer
    
Also, for numerical purposes, you might want to look at: mathoverflow.net/questions/67924/… –  Suvrit Feb 12 '12 at 0:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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