0
$\begingroup$

I have a square matrix $C$, whose entries I will denote by $c_{ij}$, and I would like to bound the magnitude of its eigenvalues.

Each $c_{ij}$ is defined in terms of $s_{ij}$ and $S_j$ as follows:

$$ c_{ij} = s_{ij}/S_i $$

The $s_{ij}$ and $S_i$ are real and satisfy the following properties:

(1) For any $j$, $\sum\limits_i s_{ij} \le S_j $.

(2) For all $i$ and $j$, $s_{ij} \ge 0$. For all $i$, $s_{ii} > 0$.

(3) For all $i$, $S_i > 0$

I want to prove that the eigenvalues of the matrix $C$ cannot have a magnitude greater than 1 (or find an counterexample).

From numerical tests on 2 by 2 matrices, it seems that my claim (that the eigenvalues all have a magnitude less than 1) is true. I haven't been able to find a counterexample.

I've tried using Gershgorin's circle theorem to bound the results, but this doesn't bound the magnitude of the eigenvalue below 1. For example, if $s_{ij} = [8, 0.1; 1, 0.8]$ and $S_i = [10,1]$, then $C = [0.8,0.01;1,0.8]$. The magnitudes of the eigenvalues of this matrix are less than 1, but Gershgorin's theorem only restricts them to 1.8.

I'm not really sure where to go from here. If anybody knows of other theorems similar to Gershgorgin's theorem (i.e., theorems bounding the magnitudes of the eigenvalues of a matrix), that would be really useful!

Thanks!

$\endgroup$
  • $\begingroup$ I might be missing something, but it looks like $\sum_i s_{2i} = 1.8 \geq 1 = S_2$. $\endgroup$ – TokenToucan Feb 8 '16 at 23:16
  • $\begingroup$ Sorry , I had a typo in there. I think it should be fixed now? For the work I'm doing, the notation has reversed indices so it has been causing a lot of mental mistakes for me. The sum should be over the first index, not the second. The sum of the $j$-th column of $s_{ij}$ is bounded by $S_j$. $\endgroup$ – nukeguy Feb 8 '16 at 23:37
  • $\begingroup$ That makes sense, but you can just apply Gershgorin in the columns and it works out the same way. The sum in each column is at most $1$, and the diagonal entries are positive. $\endgroup$ – TokenToucan Feb 8 '16 at 23:39
  • $\begingroup$ In $C$, the first column is [0.8; 1], which sums to 1.8. (Alternatively, the second row of $C$ sums to 1.8.) $\endgroup$ – nukeguy Feb 8 '16 at 23:40
  • 1
    $\begingroup$ I think the trick is that Gershgorin in one direction(row/column) will be too big, but then in the other direction (column/row) it will be small enough. $\endgroup$ – TokenToucan Feb 8 '16 at 23:50
0
$\begingroup$

So I think I figured it out. Basically, I needed to note that

$$ C = D^{-1} s_{ij} $$

where $D^{-1}$ is a diagonal matrix whose entries are $S_i$. Then,

$$ \lambda x = D^{-1} s_{ij} x $$ $$ \lambda (D x) = s_{ij} x $$ $$ \lambda (D x) = (s_{ij} D^{-1}) (D x) $$

Thus, the eigenvalues of $c_{ij}$ are the eigenvalues of $s_{ij} D^{-1}$ With $s_{ij} D^{-1}$ instead of $D^{-1} s_{ij}$, the columns/indices are set up so that I can use Property (1) and Gershgorin's theorem to show that all the eigenvalue magnitudes are bounded by 1.

Special thanks to CuddlyCuttleFish for helping me with this.

$\endgroup$

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.