Spectral radius on 0-1 vectors.

Question

Let $A$ be an $n\times n$ symmetric substochastic matrix (i.e. all entries are non-negative and each row adds up to $1$ or less).

Call a vector $v \in \mathbb{R}^n$ an indicator if $v \neq 0$ and each coordinate of $v$ is either $0$ or $1$. Define the indicator spectral radius of $A$ by:

$$r_I(A) = \max\left\lbrace \frac{1}{|v|^2}\langle Av,v \rangle: v\text{ is an indicator}\right\rbrace$$ where $|v|$ is the standard Euclidean norm and $\langle,\rangle$ the inner product.

If $|A|$ is the operator norm of $A$ then Cauchy-Schwarz and Jensen's inequalities imply that: $$0 \le r_I(A) \le |A| \le 1$$

Looking at the standard basis one obtains that $r_I(A) = 0$ if and only if $|A| = 0$.

Also, it's not too hard to show that $r_I(A) = 1$ if and only if $|A| = 1$.

Consider the function $f_n:[0,1] \to [0,1]$ defined by: $$f_n(x) = \max\left\lbrace |A|: A\text{ is }n\times n\text{ symmetric and substochastic with }r_I(A) \le x \right\rbrace$$

And let $f(x) = \lim_{n \to +\infty}f_n(x)$.

My questions are: Is $f(x) < 1$ whenever $x < 1$? Is $f(x) \le \sqrt{x}$?

---

Motivation: In the course of showing his criteria for amenability of a countable group Kesten proved ("Full Banach mean values on countable groups." 1959) that $f(x) \le O(x^{\frac{1}{3}})$ when $x \to 0$ so that in particular $f(x) < 1$ for all $x$ small enough. He claims the proof actually gives $f(x) \le O(x^{\frac{1}{2}-\epsilon})$.

I've also done some numerical experiments on the indicator norm (analogous definition) which suggests the bound $\sqrt{x}$ might work.

Answer 1

Here is an example that shows that the bound $f(x) \leq \sqrt x$ does not work. More precisely $f(x) \geq \sqrt{x(2-x)}$ when $x=2/d$ for an integer $d$.

For an integer $d$, denote by $A$ the Markov operator for the uniform random walk on an infinite tree with degree $d$ (each vertex has $d$ neighbours). It is well known that $|A|=\frac{2 \sqrt{d-1}}{d}$ (I think this is a result of Kesten), and that $r_I(A)=2/d$ (for any finite subset $S$ of the tree there are at least $(d-2) card(S)$ edges between $S$ and its complementary, so that is $v$ is the indicator function of $S$, $\langle Av,v\rangle\leq 2 card(S)/d$).

One might object that I am cheating since $A$ is not a finite matrix but an infinite matrix. But suitable truncations indeed imply $f(2/d)\geq \frac{2 \sqrt{d-1}}{d}$: if $F$ is a finite subset of the tree, consider $A_F=(A_{i,j})_{i,j \in F}$. Of course $r_I(A_F) \leq r_I(A) \leq 2/d$, and if $F$ is large enough $|A_F|$ is arbitrarily close to $|A|$.

Answer 2

With rank one matrices (I mean those of the form $A = \frac {1}{(\max w) \sum w_i}w \otimes w$ for some vector $w$) here is a proof that says $f(r) \leq 2 \sqrt{r}$ if we restrict to that kind of matrices.

Let us assume wlg that $1=w_1\geq w_2 \geq w_3 \geq \dots$ (we can do this by rearranging the indices and dividing by $w_1$). Then we can obtain $$\|A\| = \frac{\sum w_i^2}{\sum w_i}$$ and $$r:=r_I(A) = \max_m \frac{\left(\sum_{i\leq m} w_i \right)^2} {m \sum w_i}.$$ Let $k$ be the largest integer so that $w_i \geq \sqrt{r}$, then by definition of $r$ we have that $$ r \geq \frac{\left(\sum_{i \leq k} w_i \right)^2} {k \sum w_i}.$$ Also $$\|A\| \leq \frac{\sum_{i \leq k} w_i^2}{\sum w_i} + \frac{\sum_{i > k} w_i^2}{\sum w_i} \leq \frac{\sum_{i \leq k} w_i}{\sum w_i} + \sqrt r \frac{\sum_{i > k} w_i}{\sum w_i} \leq \frac{\sum_{i \leq k} w_i}{\sum w_i} + \sqrt r $$ And using that $v_i \leq 1$ and $\sum_{i\leq k} w_i \geq k w_k \geq k \sqrt r$, we get $$\|A\| \leq \frac{\left(\sum_{i \leq k} w_i\right)^2}{k \sqrt r \sum w_i} + \sqrt r \leq 2 \sqrt{r} $$