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.

  • 1
    $\begingroup$ 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$. $\endgroup$ Sep 29 '12 at 21:27
  • $\begingroup$ How does one show that? $\endgroup$ Sep 30 '12 at 2:35
  • $\begingroup$ @Pablo: see my partial answer below $\endgroup$ Sep 30 '12 at 5:49
  • 1
    $\begingroup$ 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$. $\endgroup$ 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|$.

  • $\begingroup$ I don't understand what this matrix A is. Is it even symmetric? $\endgroup$ Oct 4 '12 at 18:08
  • $\begingroup$ 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$. $\endgroup$ 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} $$

  • $\begingroup$ 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. $\endgroup$ Oct 4 '12 at 0:55
  • $\begingroup$ 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. $\endgroup$ Oct 4 '12 at 5:52
  • $\begingroup$ 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$. $\endgroup$ Oct 4 '12 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.