Calculating the Perron-Frobenius eigenvector of a positive matrix from limited information - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T06:53:27Z http://mathoverflow.net/feeds/question/92107 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/92107/calculating-the-perron-frobenius-eigenvector-of-a-positive-matrix-from-limited-in Calculating the Perron-Frobenius eigenvector of a positive matrix from limited information Ian Martin 2012-03-24T21:25:50Z 2012-04-09T17:55:01Z <p>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 <em>dominant eigenvector</em>, all of whose elements are positive.</p> <p>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: <code>$(Ae)_{1}=1$</code>, <code>$(A^{2}e)_{1}=1$</code>, etc.</p> <p>This information is enough to work out the dominant eigenvalue of $A$ via the <a href="http://en.wikipedia.org/wiki/Power_method" rel="nofollow">power method</a>: simply compute $\lim_{n \to \infty} \left( (A^{n} e)_{1} \right)^{1/n}$.</p> <p>My question is:</p> <blockquote> <p>Can anything at all be said about the dominant eigenvector?</p> </blockquote> http://mathoverflow.net/questions/92107/calculating-the-perron-frobenius-eigenvector-of-a-positive-matrix-from-limited-in/92115#92115 Answer by Chris Godsil for Calculating the Perron-Frobenius eigenvector of a positive matrix from limited information Chris Godsil 2012-03-24T23:08:54Z 2012-03-24T23:08:54Z <p>The information you have does not determine the dominant eigenvector.</p> <p>Let $G$ be the graph with vertex set ${0,1,\ldots,7}$ and adjacency matrix $$\left(\begin{array}{rrrrrrrr} 0 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\ 1 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\ 1 &amp; 1 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp; 1 &amp; 0 &amp; 1 &amp; 1 &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 1 &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 0 &amp; 1 &amp; 0 \\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 1 \\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 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)$$</p> <p>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.</p> <p>All computations carried out in sage.</p> <p>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.</p> http://mathoverflow.net/questions/92107/calculating-the-perron-frobenius-eigenvector-of-a-positive-matrix-from-limited-in/92117#92117 Answer by fedja for Calculating the Perron-Frobenius eigenvector of a positive matrix from limited information fedja 2012-03-24T23:32:28Z 2012-03-24T23:32:28Z <p>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. </p> http://mathoverflow.net/questions/92107/calculating-the-perron-frobenius-eigenvector-of-a-positive-matrix-from-limited-in/92670#92670 Answer by Felix Goldberg for Calculating the Perron-Frobenius eigenvector of a positive matrix from limited information Felix Goldberg 2012-03-30T10:46:04Z 2012-03-30T10:46:04Z <p>There is some very partial information you can obtain. See this recent paper:</p> <p>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</p>