1
$\begingroup$

Let $A \in \{0,1\}^{n \times n}$ be an irreducible matrix whose entries are in $\{0,1\}$, and let $\lambda_1(A)$ be the eigenvalue with the largest magnitude. By Perron–Frobenius theorem, we know that $\lambda_1(A) \in \mathbb{R}$.

Now, define the matrix $B = \{0,1\}^{n \times n}$ to be a matrix satisfying the following conditions:

  1. $B$ has at most $t$ ones, where $t$ should be regarded as a small constant, e.g. 2.
  2. If $B_{i,j} = 1$, then $A_{i,j} = 0$.
  3. $A+B$ is irreducible.

I am interested in estimating $\lambda_1(A+B)$. The way I had in mind is the following (basically using some perturbation theory). First, define the function $f : [0,1] \rightarrow \mathbb{C}$ by $f(\epsilon) = \lambda_1(A + \epsilon B)$. Then, it might be possible to write $f$ as a power series around $0$, and use this series up to some order as an estimation.

All of this is pretty standard, but it is usually used in order to estimate $f$ around $0$, whereas I am interested in estimating $f$ at $1$. The reason I thought this method might still work is that $B$ is very sparse, and so even when $\epsilon = 1$, the perturbation is still "small" in some sense. Are there any known results of this type?

EDIT: as shown in an answer, the conjecture below is wrong. The question that still remains is estimating $\lambda_1(A+B)$.

What seem to be the case is (and if $A$ and $B$ are symmetric, it seems even more plausible) that $\lambda_1(A+B) \approx \lambda_1(A) + O(\frac{t}{n})$.

$\endgroup$
5
  • $\begingroup$ Just an idea, not sure whether it's useful - maybe one can devise a change of basis which turns your sparse $B$ into a small $B$, i.e., it isn't necessarily sparse anymore, but the entries are all bounded by some small number. Then this becomes a more standard perturbation problem. $\endgroup$ Jul 31, 2021 at 0:33
  • $\begingroup$ @MichaelEngelhardt thank you. Do you know of any example of this type? $\endgroup$
    – R. Davis
    Jul 31, 2021 at 2:56
  • $\begingroup$ A really simple case would be something like $B$ with all elements zero except $B_{1,1} =1$. Then if you transform with a $U$ that has all elements in the first row equal to $\epsilon $, $U^{\dagger } BU$ is a matrix with all elements equal to $\epsilon^{2} $. As long as your $t$ is smaller than your $n$, you might have enough freedom for such operations not to interfere with each other too much. $\endgroup$ Jul 31, 2021 at 14:18
  • $\begingroup$ Related bound that might be of use to you: mathoverflow.net/questions/243215/… $\endgroup$ Aug 30, 2021 at 6:42
  • $\begingroup$ Not an answer, but let me note that there is some published study of the behavior of eigenvalues under low-rank perturbation (and your $B$ has rank at most $t$); see e.g. doi.org/10.1137/S0895479802417118 . But it mostly focuses on the behavior of "breaking" large Jordan blocks, because that's the main invariant there. $\endgroup$ Apr 27, 2022 at 9:05

1 Answer 1

0
$\begingroup$

The conjecture is not true. Let $A_{ij}=1$ iff $i=j\pm 1$. Let $B$ be diagonal, with one nonzero entry in the $\lfloor n/2\rfloor$-th position. Then, $\lambda_1(A)<2$. (If we had instead taken $A_{ij}=1$ iff $i=j\pm 1 \mod n$ then $\lambda_1(A)=2$). Meanwhile, $\lambda_1(A+B)$ is monotonically increasing in $n$, and one may verify explicitly that $\lambda_1(A+B)$ is $>2$ for large enough $n$, indeed fairly small $n$ suffice.

$\endgroup$
4
  • $\begingroup$ Thanks! I will edit the question and remove this conjecture from it. $\endgroup$
    – R. Davis
    Jul 31, 2021 at 2:53
  • $\begingroup$ This example is quite interesting! I believe that it's provable that $\lambda_1(A_n + B_n) \rightarrow 2.5$ for your example, which seems to yield a limiting difference $\lambda_1(A_n + B_n) - \lambda_1(A_n) \rightarrow 0.5$ for $B_n$ with a single $1$ ($t = 1$ in the OP's notation). I wonder whether $0.5$ is an optimal upper bound for $t = 1$? $\endgroup$ Aug 1, 2021 at 18:06
  • 1
    $\begingroup$ Sorry to comment on a comment, but I guess that if $A, B$ are symmetric, then $\lambda_1(A + B) - \lambda_1(A) \leq 1$ for $t = 1$ by Weyl's inequality (which states that $\lambda_1(A + B) \leq \lambda_1(A) + \lambda_1(B)$, and $\lambda_1(B) \leq 1$ trivially. I suspect this might hold in greater generality, but don't see a proof. $\endgroup$ Aug 1, 2021 at 19:46
  • $\begingroup$ @RonniePavlov I don't think this type of bounds can be generalized beyond normal matrices. Eigenvalues of symmetric (or normal) matrices are well-behaved, those of non-symmetric matrices aren't. For instance, perturbation results show that (with suitable ordering) $|\lambda_i(A+E) - \lambda_i(A) |\leq \kappa(V) ||E||$, where $\kappa(V)$ is the condition number of (a choice for) the eigenvector matrix. This condition number is 1 for symmetric or normal matrices but can be arbitrarily high in general. $\endgroup$ Aug 25, 2022 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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