Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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$. –  Mikael de la Salle Sep 29 '12 at 21:27
    
How does one show that? –  Pablo Lessa Sep 30 '12 at 2:35
    
@Pablo: see my partial answer below –  Mikael de la Salle Sep 30 '12 at 5:49
1  
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$. –  Mikael de la Salle Oct 1 '12 at 8:45

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
    
Great example! Thanks! –  Pablo Lessa Sep 30 '12 at 9:55
    
I don't understand what this matrix A is. Is it even symmetric? –  Luis Silvestre 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$. –  Mikael de la Salle 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} $$

share|improve this answer
    
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. –  Luis Silvestre 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. –  Luis Silvestre 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$. –  Pablo Lessa Oct 4 '12 at 13:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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