Calculating the Perron-Frobenius eigenvector of a positive matrix from limited information - MathOverflow

Calculating the Perron-Frobenius eigenvector of a positive matrix from limited information

2012-03-24T21:25:50Z

In the background of this question is a matrix $A$, all of whose elements are positive. The Perron-Frobenius theorem tells us that the eigenvalue with largest absolute value is real, and that there is an associated dominant eigenvector, all of whose elements are positive.

Suppose we don't actually observe $A$, but are told what its first row sum is. We're also told the first row sum of $A^{2}$, $A^{3}$, $A^{4}$, ... . In other words, writing $e$ for the vector of ones, we're told the first element of $Ae$, $A^{2}e$, $A^{3}e$, and so on. If, for example, $A$ is a stochastic matrix then $Ae = e$ so that the information given is simply a list of ones: $(Ae)_{1}=1$ , $(A^{2}e)_{1}=1$ , etc.

This information is enough to work out the dominant eigenvalue of $A$ via the power method: simply compute $\lim_{n \to \infty} \left( (A^{n} e)_{1} \right)^{1/n}$.

My question is:

Can anything at all be said about the dominant eigenvector?

Answer by Chris Godsil for Calculating the Perron-Frobenius eigenvector of a positive matrix from limited information

2012-03-24T23:08:54Z

The information you have does not determine the dominant eigenvector.

Let $G$ be the graph with vertex set ${0,1,\ldots,7}$ and adjacency matrix $$ \left(\begin{array}{rrrrrrrr} 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right) $$ Construct a second graph $H_2$ by joining a new vertex to the vertex 2, and a third graph $H5$ by joining a new vertex to vertex 5. Then $$ (A(H_2)^k e)_2 = (A(H_5)^k e)_5 $$ for all $k$. (For $k=0,\ldots,8$ the actual numbers are $$ 1,\ 4,\ 8,\ 25,\ 57,\ 163,\ 392,\ 1073,\ 2656) $$ The Perron vectors are $$ (1, 1, 1.579071, 1.460275, 1.019079, 1.168003, 0.5330099, 0.206667, 0.612263) $$ for $H_2$ and, for $H_5$, $$ (1, 1, 1.579071, 2.0725388, 1.631342, 2.134811, 0.974205, 0.377735, 0.827744) $$

If you want positive matrices, take the sixth powers of $A(H_2)$ and $A(H_5)$. The relevant property of $G$ is that the graphs $G\setminus2$ and $G\setminus5$ are cospectral, and their complements are cospectral too.

All computations carried out in sage.

In a sense the problem is that you are getting a bit of information about each eigenspace, whereas you want detailed information about a particular eigenspace.

Answer by fedja for Calculating the Perron-Frobenius eigenvector of a positive matrix from limited information

2012-03-24T23:32:28Z

Assume that $v_1,\dots, v_n$ are eigenvectors and $\lambda_1,\dots,\lambda_n$ are eigenvalues. Assume also that $e=\sum_k v_k$. Then what you are given is merely $\sum_n (v_k,e_1) \lambda_k^n$, which, in a generic position, allows you to determine $\lambda_k$ and $(v_k,e_1)$ but no more than that. Now, take any matrix $A$ with positive entries, find the eigenvectors and eigenvalues, keep the eigenvalues but change the eigenvectors a tiny bit (respecting complex conjugation) by changing the coordinates of $v_k$ beyond the first to keep the identity $\sum v_k=e$. You'll get a new matrix with real entries close to the old one so it'll still have positive entries and the same sequence of observables but rather different eigenvectors.

Answer by Felix Goldberg for Calculating the Perron-Frobenius eigenvector of a positive matrix from limited information

2012-03-30T10:46:04Z

There is some very partial information you can obtain. See this recent paper:

Das, Kinkar Ch. A sharp upper bound on the maximal entry in the principal eigenvector of symmetric nonnegative matrix. (English) Linear Algebra Appl. 431, No. 8, 1340-1350 (2009). ISSN 0024-3795