6
$\begingroup$

I have a situation where a matrix $A=[a_{ij}]$ arises.

From the physics of the problem, I expect this matrix to have one null eigenvalue, while the remaining eigenvalues have negative real part. However I have not been able to prove the second part of the statement.

I appreciate any help / hint /guidance on how to approach the problem.


The off-diagonal elements are given by $$ a_{ij} = \begin{cases} n_{ji}, & \text{if } j<i \\ n_{ji}+1, & \text{if } j>i \end{cases} $$

Whereas the diagonal elements are given by $ a_{ii} = -\sum_{k \neq i =1}^N a_{ki} $.

It is clear that the row vector of all-ones $\mathbb 1_N$ is always a left eigenvector with null eigenvalue.

Furthermore, the $n_{ij}$ are such that:

$\bullet$ $ n_{ij}>0 $

$\bullet$ $ n_{ij} $ increase with $i: n_{ij} < n_{(i+1)j}$

$\bullet$ $ n_{ij} $ decrease with $j: n_{ij} > n_{i(j+1)}$

Case N=2

$$ \begin{bmatrix} -n_{12} & 1+n_{12} \\ n_{12} & -1-n_{12} \\ \end{bmatrix} $$

The eigenvalues are $0$ and $-1-2 n_{12}$.

Case N=3

$$ \begin{bmatrix} -n_{12}-n_{13} & 1+n_{12} & 1+n_{13} \\ n_{12} & -1-n_{12}-n_{23} & 1+n_{23} \\ n_{13} & n_{23} & -2-n_{13}-n_{23} \\ \end{bmatrix} $$

The non-zero eigenvalues are given by (after some messy computations, or after asking Wolfram Mathematica):

$$ (-3 - 2 n_{12} - 2 n_{13} - 2 n_{23} \pm \sqrt{1 - 4 n_{12} + 4 n_{12}^2 - 4 n_{12} n_{13} + 4 n_{13}^2 + 4 n_{23} - 4 n_{12} n_{23} - 4 n_{13} n_{23} + 4 n_{23}^2})/2 $$ We can see that the real part must be negative by noting that $(3 + 2 n_{12} + 2 n_{13} + 2 n_{23})^2$ is strictly greater than $(1 - 4 n_{12} + 4 n_{12}^2 - 4 n_{12} n_{13} + 4 n_{13}^2 + 4 n_{23} - 4 n_{12} n_{23} - 4 n_{13} n_{23} + 4 n_{23}^2)$.

As $N$ increases, the eigenvalue computations becomes messier... Is there a simpler way to show that they will be negative?

$\endgroup$
7
  • $\begingroup$ This is not true. The following matrix, for instance, has a conjugate pair of non-real eigenvalues $-5.6553\pm 0.1370i$: $$ A=\pmatrix{ -4.8685&1.6607&2.4516&3.7562\\ 0.6607&-4.3281&1.9114&2.7560\\ 1.4516&0.9114&-4.5041&1.1411\\ 2.7562&1.7560&0.1411&-7.6533}. $$ $\endgroup$
    – user1551
    Oct 10, 2022 at 19:04
  • $\begingroup$ Thank you @user1551, you are right. I meant the real part of the remaining eigenvalues must be negative. I'll edit the question. $\endgroup$
    – G Frazao
    Oct 10, 2022 at 21:04
  • $\begingroup$ This follows from the Perron-Frobenius Theorem. $\endgroup$
    – KBS
    Oct 11, 2022 at 19:55
  • $\begingroup$ @KBS thanks for the suggestion. However I don't understand how it helps. My matrix A has negative diagonal and positive off-diagonal elements. To which matrix should I apply the Perron-Frobenius Theorem? $\endgroup$
    – G Frazao
    Oct 12, 2022 at 10:29
  • 1
    $\begingroup$ Your matrix is a Metzler matrix and so you can consider the matrix $A+\alpha I$ where $\alpha>0$ is large enough so that $A+\alpha I$ is an irreducible positive matrix. Then, the result will follow. Additionally, your matrix is a so-called $Q$-matrix that can be used to describe the evolution of the probability density function of a continuous-time Markov chain. It is a well-known fact that such matrices have a unique zero eigenvalue whenever the matrix is irreducible. All, the other eigenvalues will have negative real part. From the definition, your matrix $A$ will always be irreducible. $\endgroup$
    – KBS
    Oct 12, 2022 at 11:01

2 Answers 2

3
$\begingroup$

https://en.wikipedia.org/wiki/Gershgorin_circle_theorem may help you here. Note that it implies that eigenvalues $\lambda$ satisfy $$|\lambda - a_{ii}| \le \sum_{k\neq i} |a_{ki}| = \sum_{k\neq i}a_{ki} = - a_{ii}.$$ This proves that all eigenvalues are non-positive. Not sure at the moment the best way to prove that one and only one eigenvalue will be $0$.

EDIT:

However, it seems clear that at least one will be zero since the elements satisfy $\sum_{k=1}^N a_{ki} = 0$. The determinant is clearly going to be $0$ since an entire row can be zeroed out. So at least one eigenvalue is $0$.

Second EDIT:

As pointed out by user1551, the eigenvalues can be complex so the original simplification is incorrect. The result can be explicitly shown. I leave it to OP to verify that the real part of $\lambda$ is non-positive.

$\endgroup$
3
  • $\begingroup$ Why are the eigenvalues real? $\endgroup$
    – user1551
    Oct 10, 2022 at 18:46
  • $\begingroup$ Good point. They are not, perhaps it is better to say that the real part is non-positive? $\endgroup$
    – Gregory
    Oct 10, 2022 at 19:09
  • $\begingroup$ +1. Thanks a lot for the reference. I was not aware of the theorem, and I used it again in my path to complete the proof. You might also like to take a look at KBS comment in the original post. $\endgroup$
    – G Frazao
    Oct 12, 2022 at 11:30
1
$\begingroup$

I think I found an answer:

First, use the Gershgorin circle theorem as in Gregory's answer to show that the eigenvalues of $A$ have non-positive real part.

Second, note that $A$ has at least one null eigenvalue since the rows of the matrix add up to $0$.

Third, show that $A$ has only one null eigenvalue:

Construct an auxiliary $N\times N$ matrix $B$, equal to $A$, but with the last row zeroed. Since row operations do not change the nullity of a matrix, $B$ has the same number of null eigenvalues as $A$. $$ B = \begin{bmatrix} a_{11} & 1+n_{12} & \cdots & 1+n_{1(N-1)} & 1+n_{1N} \\ n_{12} & a_{22} & \cdots & 1+n_{2(N-1)} & 1+n_{2N} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ n_{1(N-1)} & n_{2(N-1)} & \cdots & a_{(N-1)(N-1)} & 1+n_{(N-1)(N-1)} \\ 0 & 0 & \cdots & 0 & 0 \end{bmatrix} $$

Construct a second auxiliary $(N-1) \times (N-1)$ matrix $C$, equal to $B$ without the last row and column. Note that the eigenvalues of $C$ are also eigenvalues of $B$ since you can construct the eigenvectors of $B$ by padding the eigenvectors of $C$ with a $0$.

$$ \text{Let } v=[v_1 \cdots v_{N-1}] : Cv = \lambda v $$ $$ \text{Note } w=[v_1 \cdots v_{N-1} \ 0] \Rightarrow Bw = \lambda w $$

Finally, use once again the Gershgorin circle theorem to show that all the eigenvalues of $C$ are strictly negative. $$ |\lambda - a_{ii}| \leq \sum_{k\neq i} c_{ki} = |a_{ii}| - n_{iN} < |a_{ii}| $$

$C$ has no null eigenvalues $\Rightarrow$ $B$ has only one null eigenvalue $\Rightarrow$ $A$ has only one null eigenvalue $\blacksquare$

$\endgroup$
0

You must log in to answer this question.

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