# Spectral radius on 0-1 vectors.

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.

• The inequality $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$. Sep 29 '12 at 21:27
• How does one show that? Sep 30 '12 at 2:35
• @Pablo: see my partial answer below Sep 30 '12 at 5:49
• A remark: to prove that $f(x)<1$ for $x<1$ it is enough to prove that there exists a continuous function $g$ such that $g(t)<t$ and $r_I(A^2)\leq g(r_I(A))$ for all $A$. Oct 1 '12 at 8:45

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

• I don't understand what this matrix A is. Is it even symmetric? Oct 4 '12 at 18:08
• If $F$ is a finite subset of the set of vertices of an infinite tree with degree $d$, then $A_F$ is a matrix indexed by $F$, and for $i,j \in F$ the $(i,j)$-entry of $A_F$ is $1/d$ if there is an edge between $i$ and $j$, and $0$ otherwise. It is indeed symmetric and substochastic since any vertex has at most $d$ neighbours in $F$. Oct 4 '12 at 18:46

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}$$

• I thought a bit about a proof for general matrices as in the original question. Starting from $Av = \|A\|v$ for some $v$ such that $1=v_0 \geq v_1 \geq \dots$. I ended up in a sum of two terms similar as above but there was one that I could not estimate appropriately. Oct 4 '12 at 0:55
• I thought I had some elementary example that $f(r) \geq \sqrt r$ with rank one matrices, but there was some silly mistake. I'll try again tomorrow. Oct 4 '12 at 5:52
• Excellent! Maybe this can help solve the general case by composing the original matrix $A$ with the orthogonal projection onto the subspace generated by the vector with $Av = |A|v$. Symmetry is preserved by this composition but now the sums of rows might be a bit larger than $1$. Oct 4 '12 at 13:24