6
$\begingroup$

Does the height of a real symmetric matrix with non-negative entries control the height of its Perron-Frobenius eigenvector, under some reasonable definition of heights?

Just as an example of what kind of heights I would be happy with. For the matrix, consider the model case where all of its entries are integer, and take the largest of the $L^1$-norms of its rows. For the eigenvector, represent the set of its coordinates as $U\cup V$ with $\max U\le \min V$ and $\sum_{u\in U}u^2=\sum_{v\in V}v^2$, and define the height to be the ratio of the largest and the smallest elements of $V$.

$\endgroup$
  • $\begingroup$ I am not familiar with the concept of height and I cannot make sense of your definition on the eigenvector. Could you please formalize it? For the height of the matrix, what you defined is called infinity-norm of a matrix, $\|A\|_{\infty}$, in matrix analysis (see for instance en.wikipedia.org/wiki/Matrix_norm). It satisfies some "typical" inequalities for a norm such as $\|Av\|\leq\|A\|\|v\|$, and one could probably find more results by looking it up with this name. $\endgroup$ – Federico Poloni Mar 23 '14 at 8:51
  • $\begingroup$ @Federico: I do not define the notion of an eigenvector in my question, and the question is not about the norms of a matrix. The question is whether a "small" matrix has a "small" Perron-Frobenius eigenvector, under some reasonable definition of "smallness". As to the way I defined the height of a vector in ${\mathbb R}^n_+$: write the coordinates of the vector in a non-decreasing order, say $v_1,\ldots,v_n$, let $i$ be the largest index with $v^2_1+\dotsb+v^2_i<v^2_{i+1}+\dotsb+v^2_n$, and define then the height to be $v_n/v_{i+1}$. $\endgroup$ – Seva Mar 23 '14 at 9:33
  • $\begingroup$ probably you misunderstood me; I do know what an eigenvector is, I was asking you to clarify the definition of height, as you did (thanks!). I take it that there should be a similar definition of height or "smallness" for matrices then? What is it if it's not that matrix norm? $\endgroup$ – Federico Poloni Mar 23 '14 at 11:13
  • $\begingroup$ @Federico: I could try to invent a similar diefinition of the height of a matrix, but it does not emerge naturally in the context I am interested in. The infinity norm as a height is just fine for my purposes, and other reasonable heights can be fine as well. $\endgroup$ – Seva Mar 23 '14 at 12:27
4
$\begingroup$

Grrr, I am not used to this yet:

"Birkhoff norm" places the problem in a less elementary setting:

What is the Birkhoff norm of a Perron vector?

Second edit: I just found

concentration for eigenvectors

which refers to the original paper of Minc he cited in the reference I have given below. The reactions are not encouraging, but some references indicated there may be of help. This question is essentially duplicate ...

See also

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

for a more recent reference.

First edit: I have edited due to the comment concerning non-negativity.

This answer refers to the following book:

"Nonnegative matrices" by Henryk Minc, Wiley Interscience Series in discrete mathematics and optimization, 1988.

A certain control of some "height" of the Perron-Frobenius vector for general symmetric non-negative integer matrices can not be expected, as the Identity matrix impressively shows.

A (presumably "The" but I am not an expert) relevant concept is Irreducibility (section 1.2, p. 5). Any non-negative eigenvector of a non-negative irreducible matrix is strictly positive (section 1.2, Theorem 2.2, p. 7). A non-negative matrix is irreducible if and only if for all i,j there is some power k of the matrix, such that the entry $(a_{ij})^k$ is positive (section 1.2, Theorem 2.3, p. 7), but it is not necessarily possible to choose this k to be equal for all entries.

One then derives that the Perron-Frobenius eigenvalue of an irreducible non-negative matrix is simple (section 1.4, Theorem 4.3, p.14) and it has a strictly positive eigenvector (section 1.4, Theorem 4.1, p.11).

Under this condition, there seems a chance, that controls for some "height" given below might be carried over from the positive to the non-negative case.

A more strict concept for non-negative matrices is primitivity, section 3.1, p. 47. A non-negative matrix is primitive if and only if some power of it is positive (section 3.2,Theorem 2.1, p.49). One gets a feeling for the difference between irreducibility and primitivity by looking at section 3.3, Theorem 3.1, p. 51.

Finally, we have a control on the height of the Perron-Frobenius (maximal) eigenvector for positive matrices in section 2.3, Theorem 3.1, p. 41 - 43, including the proof; the references cited there can be found on page 46.


section 2.3, Theorem 3.1:

Let $A \ = \ (a_{ij})$ be a positive matrix, with maximal eigenvector $x = (x_1, \ldots, x_n)$ and let $\gamma \ = \ \max_{i,j} (x_i/x_j)$ . Then

$ \sqrt{R/r} \ \leq \ \gamma \ \leq \ \max_{j,s,t} (a_{sj}/a_{tj}) \, ,$

where $R$ and $r$ are the greatest and least row sums of $A$, respectively. The left inequality is an equality if and only if $R = r$. Equality holds on the right-hand side if and only if the pth row of $A$ is a multiple of the qth row, for some pair of indices $p$ and $q$ satisfying $a_{ph}/a_{qh} \ = \ \max_{j,s,t} (a_{sj}/a_{tj}) \, .$


I just copied this Theorem with minor notational changes and did no proofreading.

$\endgroup$
  • 1
    $\begingroup$ Many, many thanks - this is remarkably close to what I need. The major difference is that my matrices are non-negative (instead of positive), but, hopefully, the method will work in my settings. $\endgroup$ – Seva Mar 24 '14 at 7:33

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.