1
$\begingroup$

How do the eigenvalues of a $n\times n$ matrix with non--negative integer entries change when the $(n,1)$ entry increases by $1$?

It may help to note that the sum of the eigenvalues remains the same and the product may change.

This question arose in the context of the spectrum of the adjacency matrix of a directed graph with non--negative loops. If the edge weight from vertex $n$ to vertex $1$ increases by one, how do the eigenvalues of the adjacency matrix shift?

$\endgroup$
  • 1
    $\begingroup$ The largest eigenvalue (which is real by the Perron-Frobenius theorem) either doesn't change or increases. I don't know what can really be said about the other eigenvalues. $\endgroup$ – Qiaochu Yuan Dec 2 '17 at 18:36
  • $\begingroup$ Thanks. Is there a way to know by how much it would increase? $\endgroup$ – ireneMT Dec 3 '17 at 9:53
3
$\begingroup$

This is not a full answer, but I think it can bring a certain clarification of ideas.

First of all, I will convert your question into : "What happens to the eigenvalues if I modify this $(n,1)$ coefficient (call it $a$) by $da$" (instead of $1$, which is dimensionless).

Indeed, it's a kind of "sensitivity to change" you would like to qualify/quantify.

Thus I advise you to see it under the differential form:

$$dq(a)=S da \ \iff \ \dfrac{dq(a)}{da}=S$$

where $q$ is any quantity depending upon $a$ such as the determinant, or the eigenvalues "as a whole" as we are going to see it. Thus $S$ could be called the local "sensitivity" of quantity $q$.

Let us take an example in order to be well understood.

Consider the following matrix:

$$A=\left(\begin{array}{rrrr}1 & 0 & -1 & 0 \\ 1 & 3 & 1 & \ \ 3\\ 0 & -1 & 1 & \ \ 3\\ \color{red}{a} & 2 & 2 & \ \ -2\end{array}\right).$$

As $\det(A)=-12a-18$, we have an example of the "sensitivity to change" encapsulated into the derivative $-12$.

Said differently, $-12$ is as well the cofactor of entry $a_{4,1}$ : think to Laplace expansion of $\det(A)$ with respect to the first column.

Either with the first or the second interpretation, we can say that modifying $a$ by $da$ generates a change $-12da$ in $\det(A)$.

But addressing the sensitivity of a particular eigenvalue to a change in $a$ is more than a challenge : it is impossible to "individualize" the eigenvalues, for example by focusing on the biggest one (in absolute value). They are a whole.

But nevertheless, locally, it makes sense if you are not in a particular case of multiple roots.

For example, take a look at Fig. 1 with $a$ on horizontal axis and, for any given $a$, the two, three or four points $(a,\lambda_k)$. Consider the case $-7.75 \leq a < 0.8$ where there are four real roots ; the local slopes (geometrical interpretation of derivatives) for a given $a$ provide a way to understand in a graphical way the interdependencies of the different sensitivities. For exemple, around $a=0$, interpreting the slopes, we have $2$ negative sensitivities and a positive one, the latter being "twice stronger"... in order that the sum is $0$, meaning "no change" : indeed, the trace of $A$, which is the sum of eigenvalues, remains constant (you had mentionned the role of the trace).

How can this figure be explained ? Why is it the union of a straight line and a curve looking like a familiar cubic curve ? It is due to the following factorization of the characteristic polynomial of $A$:

$$\lambda^4 - 3\lambda^3 - 14\lambda^2 + (3 a+47) \lambda - 12a = (\lambda-4)(\lambda^3+\lambda^2-10\lambda+(3a+7))$$

giving

  • $\lambda=4$ (a constant : not surprising) and

  • the roots of 3rd degree equation. And indeed, the general shape of the "winding component" in Fig. 1 looks familiar when seen as a function

$$a=\tfrac13(-\lambda^3-\lambda^2+10\lambda-7).$$

enter image description here

Fig. 1.

Remark 1 : Red stars are places of bifurcation.

Remark 2 : I have developed a representation method explained in (Looking for references about a graphical representation of the set of roots of polynomials depending on a parameter).

$\endgroup$
  • $\begingroup$ This is interesting. There are more conditions that can simplify the problem. The entries of the given matrix do not contain negative entries and that is why Frobenius Perron Theorem can be applied. Moreover the trace of the matrix which is the sum of the eigenvalues is a positive integer. The determinant gives the product of the eigenvalues (up to sign). If we suppose that this determinant is NOT zero, can this help? $\endgroup$ – ireneMT Dec 3 '17 at 10:02
  • $\begingroup$ To Jean Marie: I tried to use your method to compute the change in each of the coefficients of the characteristic polynomial. Thanks for the idea. The coefficient of lambda remains the same and I suppose the others do not change by much. Combinatorially however I was getting a large number of contributions to the change! $\endgroup$ – ireneMT Dec 7 '17 at 10:10

Your Answer

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

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