6
$\begingroup$

For a symmetric real matrix $A$, denote by $\rho(A)$ the spectral radius of $A$, and by $\sigma(A)$ the largest absolute row sum of $A$; that is, $\sigma(A)=\max_i \sum_j |a_{ij}|$, where $a_{ij}$ are the elements of $A$. We thus have $\rho(A)\le\sigma(A)$.

A general question:

What can we say about $A$ given that $\sigma(A)\le K\rho(A)$ with a real $K>0$?

A pinpointed version (this is what I eventually need):

Given that $\sigma(A)\le K\rho(A)$, does there necessarily exist a unit-length vector $x=(x_1,\ldots,x_n)$ (where $n$ is the order of $A$) such that $\|Ax\|\ge 0.1\rho(A)$ and $(|x_1|+\dotsb+|x_n|)\max_i|x_i|\le 10K^{10}$?

(It is not difficult to see that a unit-length vector $x=(x_1,\ldots,x_n)$ with $\|Ax\|=\rho(A)$ and $(|x_1|+\dotsb+|x_n|)\max_i|x_i|\le 10K^{10}$ may fail to exist.)

An ideologically motivated restatement:

For a (not necessarily square) matrix $A\ne 0$, define the height of $A$ by $h(A):=\|A\|_1\|A\|_\infty/\|A\|^2$, where $\|A\|_1,\|A\|_\infty$, and $\|A\|$ are induced operator norms (see Wikipedia for the definitions). Notice, that $1\le h(A)\le\sqrt{mn}$, where $m$ and $n$ are the dimensions of $A$.

If $m=n$ and $A$ is symmetric, then $\|A\|_1=\|A\|_\infty=\sigma(A)$ and $\|A\|=\rho(A)$. If $A$ is actually a vector, then $$ h(A)=\frac{(|x_1|+\dotsb+|x_n|)\max_i|x_i|}{x_1^2+\dotsb+x_n^2},$$ where $x_1,\ldots x_n$ are the coordinates of $A$. My question can be equivalently restated as follows:

If $A$ is a symmetric real matrix with $h(A)\le K$, does there necessarily exist a vector $x$ with $\|Ax\|\ge 0.1\|A\|\|x\|$ and $h(x)\le 10K^{10}$?

The following special cases may be worth mentioning.

  • if $A$ is diagonal, then the coordinate vector corresponding to the absolutely largest eigenvalue has height $1$; thus, denoting this vector by $x$, we have $\|Ax\|=\|A\|\|x\|$ and $h(x)=1$.
  • if $K=1$, then $\rho(A)=\sigma(A)$. I have a complete characterization of matrices with this property, and it turns out that every principal eigenvector of such a matrix has height $1$. Hence, the assertion is true in this case, too.
  • If $A$ is rank-$1$ then, in view of $A^t=A$, we have $A=\pm xx^t$ for some vector $x$. It is easy to see that in this case $\sigma(A)=h(x)\|x\|^2$, $\rho(A)=\|x\|^2$, and $x$ is a principal eigenvector of $A$. Thus, $\|Ax\|=\|A\|\|x\|$, and $h(x)=\sigma(A)/\rho(A)\le K$.

Update 23.04

I doubt this will result in a major breakthrough, but I noticed recently that my original requirement $|\langle Ax,x\rangle|\ge 0.1\rho(A)$ can be relaxed to $\|Ax\|\ge 0.1\rho(A)$, and I update the problem accordingly, for a good record-keeping

$\endgroup$
6
  • $\begingroup$ This reminds me of the discrete Cheeger inequality, see Proposition 4 of terrytao.wordpress.com/2011/12/02/…. Actually it may be easier to prove than discrete Cheeger, since you're working with the first eigenvalue rather than the second, and don't have to enforce any mean zero conditions. $\endgroup$
    – Terry Tao
    Apr 23, 2014 at 21:42
  • $\begingroup$ @Terry: many thanks for the comment, but I am afraid I need more hint. Cheeger inequality relates the spectral gap with expansion properties; I am not interested in either of them. The two quantities of interest for me are the infinity norm of a matrix ($\sigma(A)=\|A\|_\infty$) and the height of a vector ($h(x)=\|x\|_1\|x\|_\infty/\|x\|^2$), none of which appear in Cheeger inequality. What direction of Cheeger inequality and exactly how can be relevant here? Thanks again! $\endgroup$
    – Seva
    Apr 24, 2014 at 6:47
  • $\begingroup$ It's not the Cheeger inequality itself which is relevant, but the proof of the inequality. In your notation, it would be to split the top eigenvector $x$ up into indicator functions $1_F$ (which have minimal neight) and split up $\langle Ax, x \rangle$ into components $\langle A1_E, 1_F \rangle$. When E and F are very unbalanced in size, the row sum hypothesis makes these components small, so there must be a large component in which E, F have comparable size, and these are essentially your low height vectors. $\endgroup$
    – Terry Tao
    Apr 24, 2014 at 17:01
  • $\begingroup$ The anlaogy with the Cheeger inequality is this: the spectral gap of a d-regular graph with adjacency matrix $A$ (so $\sigma(A)=d$) is essentially (up to subtraction from d) the largest eigenvalue of A after restriction to mean zero functions - the analogue of your $\rho(A)$. The expansion constant is basically (up to subtraction from 1) the largest value of $\langle A 1_E, 1_E \rangle / |E|$ for indicator functions $1_E$ (which have height 1). $\endgroup$
    – Terry Tao
    Apr 24, 2014 at 17:05
  • $\begingroup$ A final comment: splitting into indicator functions will give a statement similar to what you want, but not exactly: the unit vector $x$ created will have height 1, but $\|Ax\|$ will be something like $0.01 K^{-10} \rho(A)$. It seems that you want a better bound on $\|Ax\|$ at the expense of worsening the height. For that, you would need to decompose the eigenvector $x = (x_1,\dots,x_n)$ instead into approximate step functions, such as those arising from restricting to indices $i$ with $t \leq |x_i| \leq \lambda t$ for some large parameter $\lambda > 0$ and some variable $t$. $\endgroup$
    – Terry Tao
    Apr 24, 2014 at 17:09

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.