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](http://www.ams.org/mathscinet/search/publdoc.html?amp=&loc=revcit&revcit=79220&vfpref=html&r=7&mx-pid=112053)) 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.



Spectral radius on 0-1 vectors.
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|$.


