6
$\begingroup$

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?

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks @Chris, very nice! Certainly this answers the implied question in my title. I wonder whether there's anything at all (beyond Perron-Frobenius) that can be said about the dominant eigenvector, though? If I'm not mistaken, knowledge of the entries of the first row for $A$, $A^{2}$, $A^{3}$, etc, is enough to reconstruct the whole matrix (at least so long as $A$ is not unipotent). So I was hoping that knowledge of the row sums might at least provide some information about the dominant eigenvector. But perhaps that's too much to hope for. $\endgroup$
    – Ian Martin
    Commented Mar 25, 2012 at 1:57
  • 1
    $\begingroup$ @Ian. An $n\times n$ matrix $A$ can be reconstructed from the vectors $x$,\dots,$A^{n-1}x$ if and only if these vectors span $\mathbb{R}^n$. But this is using $n$ times as much information. Roughly speaking, in your case you can reconstruct one entry of each eigenvector. Fedja's answer provides another way of viewing this point. $\endgroup$
    – Chris Godsil
    Commented Mar 25, 2012 at 2:45
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Interesting - this gives a nice way to think about @Chris's last sentence. There's one small typo, I think (though your intended meaning is clear): you write that we're given $\sum_{n} (v_{k}, e_{1}) \lambda_{k}^{n}$ where I guess you mean that we're given $\sum_{k} (v_{k}, e_{1}) \lambda_{k}^{m}$ for each $m$. $\endgroup$
    – Ian Martin
    Commented Mar 25, 2012 at 1:44
2
$\begingroup$

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

Improve this answer
$\endgroup$
0

You must log in to answer this question.

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