3
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ Sorry, I clicked "close" by mistake---please count my "undo" of that. $\endgroup$
    – Suvrit
    Commented Feb 11, 2012 at 23:36

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – Changwang Zhang
    Commented Feb 11, 2012 at 23:13
  • 1
    $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Commented Feb 11, 2012 at 23:53
  • $\begingroup$ 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. $\endgroup$
    – Changwang Zhang
    Commented Feb 12, 2012 at 12:10
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Will Sawin
    Commented Feb 12, 2012 at 16:04
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Will Sawin
    Commented Feb 12, 2012 at 21:35
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .