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.

`$f(x)\leq \sqrt x$`

does not hold exactly: one can show that $f(x)\geq \sqrt{ 2x−x^2}$ whenever $x$ is of the form $2/d$ for an integer $d$. $\endgroup$ – Mikael de la Salle Sep 29 '12 at 21:27