When does a matrix have a positive eigenvector

Question

The generalised problem is as follows: Is there a condition on a symmetric positive-semi-definite matrix $A$ that ensures that it has a positive eigenvector, i.e. an eigenvector $Av = \lambda v$ such that $ v_i > 0$ for all $i$? Or, indeed, even a weakly positive eigenvector, i.e. an eigenvector $Av = \lambda v$ such that $ v_i \geq 0$ for all $i$? I am aware of the Perron-Frobenius theorem, but the assumptions for that theorem are too strong.

The problem I actually want to solve is more specific, in case the extra information helps. If $B$ is the incidence matrix of a directed graph $G$, then $B$ can be viewed as the linear transformation whose input is vertex weightings and whose output is the corresponding edge weightings obtained by the vertex weight differences. Then the matrix that I want to understand is $A := BVB^T$, for a diagonal matrix with positive entries $V$ (for comparison, the graph Laplacian is $\Delta = B^TB$). This is a map from edge weightings to edge weightings. When does this admit a positive eigenvector?

Thanks to everyone in advance.

Answer 1

For the general case, note the following simple principle. For a vector $x$, write $\text{supp}(x) = \{i \mid x_i \neq 0\}$.

1. Proposition. Let $A$ be a normal matrix, and let $x$ and $y$ be non-negative eigenvectors corresponding to different eigenvalues of $A$. Then $\text{supp}(x) \cap \text{supp}(y) = \varnothing$.

Proof. By non-negativity we have $x_iy_i \geq 0$ for all $i$. Furthermore, since $A$ is normal, the eigenspaces of $A$ are pairwise orthogonal. Therefore we have $$ 0 = \langle x,y\rangle = \sum_i x_iy_i \geq 0, $$ so we must have equality throughout. Thus, for every $i$ we have $x_iy_i = 0$, hence $i \notin \text{supp}(x) \cap \text{supp}(y)$. $\quad\Box$

In particular, if $A$ has a strictly positive eigenvector with eigenvalue $\lambda$, then $A$ does not have a non-negative eigenvector with eigenvalue $\mu \neq \lambda$. Conversely, if the $\lambda$-eigenspace of $A$ contains a non-negative eigenvector but not a strictly positive vector, then $A$ does not have a strictly positive eigenvector.

---

For the remainder of this answer, I will focus on your more specific question.

First we look at eigenvectors with eigenvalue $0$. Here we show that a non-negative eigenvector exists if and only if $G$ has a directed cycle, and a similar statement for strictly positive eigenvectors (see Proposition 3 below). For this we use the following lemma.

2. Lemma. For every real matrix $A$, one has $\ker(A^TA) = \ker(A)$.

Proof. Clearly $\ker(A) \subseteq \ker(A^TA)$. Conversely, suppose that $A^TAx = 0$. Then $\lVert Ax \rVert^2 = x^TA^TAx = 0$, hence $Ax = 0$. $\quad\Box$

3. Proposition. Let $G$ be a directed graph. Then:

• There is a non-negative vector in $\ker(BVB^T) \setminus \{0\}$ if and only if $G$ has a directed cycle.

• There is a strictly positive vector in $\ker(BVB^T)$ if and only if every arc of $G$ belongs to a directed cycle.

Proof. Let $V^{1/2}$ denote the unique positive semidefinite square root of $V$. (Of course, this is just the entry-wise square root, since $V$ is diagonal.) It follows from Lemma 2 that $$ \ker(BVB^T) = \ker(BV^{1/2}V^{1/2}B^T) = \ker\big((V^{1/2}B^T)^TV^{1/2}B^T\big) = \ker(V^{1/2}B^T). $$ Since the diagonal entries of $V^{1/2}$ are positive, $V^{1/2}$ is invertible, so we have $\ker(V^{1/2}B^T) = \ker(B^T)$. Therefore $\ker(BVB^T) = \ker(B^T)$ is the flow space (or circulation space) of $G$. Now the statements of the proposition follow easily:

• If $G$ has a directed cycle $C$, then the unsigned characteristic vector $\mathbb{1}_C$ of $C$ is a non-negative vector in $\ker(B^T)$. Conversely, if $G$ is acyclic, then every non-zero flow must traverse at least one arc in the negative direction, so now $\ker(B^T)$ does not contain a non-negative vector (apart from $0$).

• If every arc belongs to a directed cycle, then the sum of the characteristic vectors of all directed cycles yields a strictly positive vector in $\ker(B^T)$. Conversely, if the arc $(v,w)$ does not lie on a directed cycle, then every circulation which is non-zero on $(v,w)$ must go in the negative direction on some other arc, so there is no strictly positive vector in $\ker(B^T)$. $\quad\Box$

4. Corollary. Let $G$ be a directed graph. If $G$ has a directed cycle, but also has an arc which is not contained in a directed cycle, then $BVB^T$ has no strictly positive eigenvectors.

Proof. By Proposition 3, the $0$-eigenspace contains a non-negative eigenvector, but not a strictly positive vector. Therefore it follows from Proposition 1 that there is no strictly positive eigenvector. $\quad\Box$

Second, we look at eigenvectors with non-zero eigenvalue. Here things are the other way around: we show that a strictly positive eigenvector can only exist if $G$ is acyclic (see Proposition 7 below). For this we use the following lemma.

5. Lemma. Let $A$ be an $m \times n$ matrix, let $B$ be an $n \times m$ matrix, and let $\lambda \neq 0$. Then the map $y \mapsto By$ defines an isomorphism from the $\lambda$-eigenspace of $AB$ to the $\lambda$-eigenspace of $BA$.

Proof. See this answer. $\quad\Box$

6. Corollary. Every eigenvector $x$ of $BVB^T$ with non-zero eigenvalue is of the form $x = By$ for some eigenvector $y$ of $VB^TB$.

Proof. Apply Lemma 5 with $A = VB^T$. $\quad\Box$

7. Proposition. Let $G$ be a directed graph. If $x$ is a non-negative eigenvector of $BVB^T$ with eigenvalue $\lambda \neq 0$, then $x_a = 0$ for every arc which belongs to a directed cycle. In particular, if $BVB^T$ has a strictly positive eigenvector with non-zero eigenvalue, then $G$ is acyclic.

First proof. By Corollary 6, we may write $x = By$ for some $y \in \mathbb{R}^{V(G)}$. For every arc $a = (v,w)$ we have $y(w) - y(v) = x(a) \geq 0$, so $y(v) \leq y(w)$. Therefore if $C$ is a directed cycle, then all arcs in $C$ must have the same $y$-value, so it follows that $x(a) = 0$ for all such arcs. $\quad\Box$

Second proof. For every directed cycle $C$, the characteristic vector $\mathbb{1}_C$ of $C$ is a non-negative eigenvector with eigenvalue $0$, by Proposition 3. Hence it follows from Proposition 1 that $\text{supp}(x) \cap \text{supp}(\mathbb{1}_C) = \varnothing$, so $x(a) = 0$ whenever $a$ belongs to a directed cycle. $\quad\Box$

Next, we make a slight change of perspective. Henceforth, we let $G$ be an undirected graph with Laplacian $\Delta$, and we will look at all possible orientations of the edges of $G$.

8. Definition. Given an undirected graph $G$ and an orientation $o$ of the edges of $G$, we say that a vector $y \in \mathbb{R}^{V(G)}$ is:

• weakly compatible with $o$ if $y(v) \leq y(w)$ for every edge oriented from $v$ to $w$;

• strongly compatible with $o$ if $y(v) < y(w)$ for every edge oriented from $v$ to $w$.

9. Proposition. Let $G$ be an undirected graph with Laplacian $\Delta$, let $o$ be an orientation of the edges of $G$, and let $B$ be the incidence matrix with respect to the orientation $o$. Then $BVB^T$ has a non-negative (resp. strictly positive) eigenvector with eigenvalue $\lambda \neq 0$ if and only if $V\Delta$ has an eigenvector with eigenvalue $\lambda$ which is weakly compatible (resp. strongly compatible) with the orientation $o$.

Proof. Recall that $\Delta = B^TB$, regardless of the orientation. Hence it follows from Lemma 5 (with $A = VB^T$) that the map $y \mapsto By$ defines an isomorphism from the $\lambda$-eigenspace of $V\Delta = VB^TB$ to the $\lambda$-eigenspace of $BVB^T$. To complete the proof, note that $By$ is non-negative (resp. strictly positive) if and only if $y$ is weakly compatible (resp. strongly compatible) with $o$. $\quad\Box$

If the orientation $o$ is fixed, then it is unclear whether or not there exists a compatible eigenvector of $V\Delta$. However, note that $V\Delta$ only depends on the undirected graph, and not on the orientation. If we choose a fixed eigenvector of $V\Delta$, then it is easy to see which orientations are compatible.

The following heuristic argument suggests that $BVB^T$ does not have a non-negative eigenvector for “most” orientations of $G$. If $V\Delta$ is sufficiently generic (specifically, if it has has $n$ different eigenvalues and if each eigenvector has $n$ different entries), then $G$ has at most $2n$ different acyclic orientations which admit a compatible eigenvector of $V\Delta$. (An eigenvector $y$ with $n$ different entries admits exactly one compatible orientation, and $-y$ is compatible with the reverse orientation. Different eigenvectors might give rise to the same orientation.) The following result of Linial shows that the total number of acyclic orientations is much larger than $2n$:

10. Theorem (Linial). Let $G$ be an undirected graph with $n$ vertices and $m$ edges, and write $m = \binom{k}{2} + \ell$ with $k > \ell \geq 0$. Then the number of acyclic orientations of $G$ is at least $k!(\ell + 1)$.

Proof. Combine Theorem 4 and Theorem 5 from [Lin86].

This suggests that “most” directed acyclic graphs do not have a non-negative eigenvector of $BVB^T$. (This argument is heuristic in the sense that it relies on genericity of $V\Delta$. If some eigenspace of $V\Delta$ has dimension $\geq 2$, then there are infinitely many eigenvectors, so there might be many more acyclic orientations which are compatible with some eigenvector of $V\Delta$.)

References.

[Lin86]: N. Linial, Legal colorings of graphs, Combinatorica 6(1) (1986) 49–54.