7
$\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$.

Improve this question
$\endgroup$
4
  • $\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
    Commented Mar 23, 2014 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
    Commented Mar 23, 2014 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
    Commented Mar 23, 2014 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
    Commented Mar 23, 2014 at 12:27

1 Answer 1

Reset to default
5
$\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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Mar 24, 2014 at 7:33

You must log in to answer this question.

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