6
$\begingroup$

Consider an eigenvalue / eigenvector problem for a matrix $A$ that is known to be non-negative and irreducible (so the Perron-Frobenius theorem applies):

$$\sum_j A_{ij} x_j = \lambda x_i$$

Here $\lambda$ is the largest eigenvalue and $x_i$ is an eigenvector with all entries positive.

I say that the eigenvector $x_i$ is unimodal if there exists an $i^*$ such that $x_{i+1} \ge x_i$ whenever $i < i^*$ and $x_{i+1} \le x_i$ whenever $i \ge i^*$.

What conditions must be placed on the matrix $A$ such that $x_i$ unimodal in $i$?

I don't know if this kind of problem has been studied before. Perhaps it has been addressed for some specific matrices. If there is some terminology that could help me find relevant papers, or some papers that treat something similar, please let me know.

$\endgroup$
  • $\begingroup$ I think this equivalent to finding a Markov chain with positive transition probabilities whose unique (by P-F) stationary distribution is unimodal. Maybe this is no easier but I have more intuition about Markov Chains. $\endgroup$ – JohnS Mar 28 '18 at 23:46
  • $\begingroup$ @JohnScales It is. $\endgroup$ – becko Apr 5 '18 at 15:36
  • $\begingroup$ Note that if $A$ is a primitive matrix, there exists a permutation matrix $P$ such that the right Perron eigenvector of $P A P^{-1}$ is even monotone (since $P$ just permutes the entries), stronger than unimodal. So it's not a rare phenomenon. $\endgroup$ – David Handelman Jun 1 '18 at 20:21
2
$\begingroup$

Let $A$ be as in the question and let $n$ denote the size of $A$, i.e. $A \in \mathbb{R}^{n \times n}$. Troughout, fix $i^* \in \{1,\dots,n\}$. We call a vector $x \in \mathbb{R}^n$...

  • ... $i^*$-unimodal if $x_{1} \le x_2 \le \dots \le x_{i^*}$ and $x_{i^*} \ge x_{i^*+1} \ge \dots \ge x_n$.

  • ... strictly $i^*$-unimodal if $x$ is $i^*$-unimodal and if, in addition, all the above inequalities are strict.

Theorem. Let $T \in \mathbb{R}^{n \times n}$ be the ($i^*$-dependent) matrix given by formula $(*)$ below. If all entries of $T^{-1}AT$ are nonnegative, then $A$ has an eigenvector $x$ for the eigenvalue $\lambda$ such that $x$ is $i^*$-unimodal and such that each entry of $x$ is strictly positive.

This result is actually the content of Theorem 5 below. For the proof, we need a bit of preparation.

Let $\mathbb{R}^n_+ := \{x \in \mathbb{R}^n: \; x_k \ge 0 \text{ for all } k \}$ be the standard cone in $\mathbb{R}^n$ and let $K := \{x \in \mathbb{R}^n: \; x \text{ is } i^*\text{-unimodal and } x_1 \ge 0\}$. Then $K$ is a closed convex cone in $\mathbb{R}^n$, we have $K \cap (-K) = \{0\}$ and $K$ has non-empty interior (the interior points of $K$ being exactly the vectors which are strictly $i^*$-unimodal and whose first component is strictly positive); hence, the cone $K$ is generating in $\mathbb{R}^n$, i.e. $K-K = \mathbb{R}^n$.

Lemma 1. Let $x$ be an eigenvector of $A$ for the eigenvalue $\lambda$. If $x \in K$, then all entries of $x$ are strictly positive.

Proof. By the Perron-Frobenius theorem the irreducibility of $A$ implies that the eigenspace $\ker(\lambda - A)$ is spanned by a vector $y$ whose entries are all strictly positive. Thus, $x = \alpha y$ for some non-zero real number $\alpha$. We have $0 \le x_1 = \alpha y_1$, so $\alpha > 0$ since $y_1 > 0$. This proves the lemma.

We point out that the lemma implies in particular that $x_n > 0$, although we did not even assume $x_n$ to be nonnegtive in the definition of $K$.

Now we apply the Krein-Rutman Theorem to the ordered Banach space $(\mathbb{R}^n,K)$. This immediately yields the following result:

Theorem 2. If $AK \subseteq K$, then the eigenspace $\ker(\lambda - A)$ contains a vector $x \in K$ (whose entries are all strictly positive according to Lemma 1).

So our next task is to find sufficient conditions for the property $AK \subseteq K$. Fortunately, the cone $K$ is quite well-behaved - in fact, the ordered space $(\mathbb{R}^n,K)$ is isomorphic to $(\mathbb{R}^n,\mathbb{R}^n_+)$ as the following lemma shows:

Lemma 3. Let $T: \mathbb{R}^n \to \mathbb{R}^n$ be given by \begin{align*} Tx = \begin{pmatrix} x_1 \\ x_1 + x_2 \\ \vdots \\ x_1 + x_2 + \dots + x_{i^*} \\ x_1 + x_2 + \dots + x_{i^*} - x_{i^*+1} \\ \vdots \\ x_1 + x_2 + \dots + x_{i^*} - x_{i^* + 1} - \dots - x_{n} \end{pmatrix}. \qquad (*) \end{align*} Then $x \in \mathbb{R}^n_+$ if and only if $Tx \in K$.

Proof. Straightforward.

Corollary 4. We have $AK \subseteq K$ if and only if $T^{-1}AT (\mathbb{R}^n_+) \subseteq \mathbb{R}^n_+$ if and only if every entry of the matrix $T^{-1}AT$ is nonnegative.

Remark. Note that the matrix $T^{-1}$ can be explicitely computed (and it actually has a more "sparse" structure than $T$ itself).

By combining Theorem 2 and Corollary 4 we arrive at the following result which gives a sufficient condition for the desired property (and which has already been stated at the beginning of this answer):

Theorem 5. Assume that all enntries of $T^{-1}AT$ are nonnegative. Then $A$ has an eigenvector $x$ for the eigenvalue $\lambda$ such that $x$ is $i^*$-unimodal and such that all entries of $x$ are strictly positive.


Outlook.

It is important to note that the condition in Theorem 5 is not an equivalence; this is, in some sense, due to the fact that the spectral properties asserted by the Perron-Frobenius Theorem (or by the Krein-Rutman Theorem) do not, conversely, imply nonnegativity of the matrix.

However, it might be possible to give a characterization result which is rather close to the spirit of Theorem 5, if one imposes a stronger condition on the eigenvector (and also on the dual eigenvector) and if one employs the following result from the theory of eventually positive matrices which can be found in [D. Noutsos: On Perron–Frobenius property of matrices having some negative entries (2006), Theorem 2.2]:

Theorem 6. Let $B \in \mathbb{R}^{n\times n}$. Then the following assertions are equivalent:

(i) The spectral radius $r := r(B)$ of $B$ is a strictly dominant and algebraically simple eigenvalue of $B$, and each of the eigenspaces $\ker(r - B)$ and $\ker(r - B')$ is spanned by a vector whose entries are all strictly positive.

(ii) There exists a number $k_0 \ge 1$ such that every entry of $B^k$ is strictly positive for every $k \ge k_0$.

Here, $B'$ denotes the transposed matrix of $B$, and a strictly dominant eigenvalue of a matrix is an eigenvalue is modulus is strictly larger than the modulus of any other eigenvalue of the given matrix.

Remarks 7. (a) At first glance the definition of the notion strong Perron-Frobenius property in [op. cit.] (which is used to state [op. cit., Theorem 2.2]) does not appear to include the algebraic simplicity of the spectral radius. However, one can see from the proofs in [op. cit.] that it's the author's understanding that the notion strong Perron-Frobenius property includes the property that the spectral radius is an algebraically simple eigenvalue. This can also be seen from other papers of the same author, see for instance [D. Noutsos, M. J. Tsatsomeros: Reachability and holdability of nonnegative states (2008), Definition 2.3].

(b) Given the other properties in Theorem 6(ii), algebraic simplicity of the eigenvalue $r$ of $B$ is actually equivalent to geometric simplicity. This is for instance proved in [D. Daners, J. Glueck, J. Kennedy: Eventually positive semigroups of linear operators (2016), Proposition 3.1].

Remark 8. If one whishes to employ Theorem 6 in order to turn Theorem 5 into a characterisation result one probably has to take the following phenomena into account:

(a) One needs to use a strictly unimodal eigenvector instead of a merely unimodal eigenvectors, now.

(b) For the transposed matrix $A'$ one probably needs some kind of dual notion to unimodality since the eigenvector of $A'$ will be of the form $(T^{-1})'y$ for some vector $y$ whose entries are all strictly positive. I'm not sure how (and if) vectors of the form $(T^{-1})'y$ for strictly positive $y$ can be easily described.

(c) One needs the assumption that the spectral radius of $A$ is a strictly dominant eigenvalue.

Note on an EDIT made 2018-09-01: I've removed the former Theorem 6 from the former version of the post since it contained several mistakes (it did not take Remark 8(b) and (c) into account).

Instead I've added some information from the literature in Theorem 6 and Remark 7 which might be useful when trying to characterise the existence of strictly unimodal eigenvectors. However, I haven't though in detail about how such a characterisation result might look precisely.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you post more details about your Theorem 6? I cannot see how it is derived from the previous assertions, especially since the assumption $AK\subset K$ seems strong. Thanks. $\endgroup$ – becko Aug 29 '18 at 12:13
  • $\begingroup$ @becko: It seems that my Theorem 6 was a typical example of the phenomenon which can by subsumed as "If somebody states that a result is not difficult, but doesn't give a proof, then the result is probably wrong" ;-). I've added some additional information from the literature instead which might be helpful if one indeed wants to prove a characterisation result. $\endgroup$ – Jochen Glueck Sep 1 '18 at 10:51

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.