Espectral de la radio en 0-1 vectores.

Question

Deje $A$ ser $n\times n$ simétrica substochastic matriz (es decir, todas las entradas son no negativas y cada fila se suma a $1$ o menos).

Llamar a un vector $v \in \mathbb{R}^n$, un indicador de si $v \neq 0$ y cada coordenada de $v$ es $0$ o $1$. Definir el indicador espectral de radio de $A$ por:

$$r_I(A) = \max\left\lbrace \frac{1}{|v|^2}\langle Av,v \rangle: v\text{ is an indicator}\right\rbrace$$ donde $|v|$ es el estándar de la norma Euclídea y $\langle,\rangle$ del producto interior.

Si $|A|$ es el operador de la norma de $A$ luego de Cauchy-Schwarz y Jensen desigualdades implican que: $$0 \le r_I(A) \le |A| \le 1$$

Mirando el estándar de base se obtiene que el $r_I(A) = 0$ si y sólo si $|A| = 0$.

Además, no es demasiado duro para demostrar que $r_I(A) = 1$ si y sólo si $|A| = 1$.

Considere la función $f_n:[0,1] \to [0,1]$ definido por: $$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$$

Y deje $f(x) = \lim_{n \to +\infty}f_n(x)$.

Mis preguntas son: Es $f(x) < 1$ siempre $x < 1$? Es $f(x) \le \sqrt{x}$?

---

Motivación: En el curso de mostrar sus criterios de disponibilidad de una contables grupo Kesten demostrado ("Lleno de Banach que la media de los valores contables de los grupos". 1959) que $f(x) \le O(x^{\frac{1}{3}})$ al$x \to 0$, de modo que, en particular, $f(x) < 1$ para todos los $x$ lo suficientemente pequeño. Afirma que la prueba de realidad da $f(x) \le O(x^{\frac{1}{2}-\epsilon})$.

También he hecho algunos experimentos numéricos en el indicador de la norma (análogo definición) lo que sugiere la enlazado $\sqrt{x}$ podría funcionar.

Answer 1

Aquí está un ejemplo que muestra que la enlazado $f(x) \leq \sqrt x$ hace no trabajo. Más precisamente, $f(x) \geq \sqrt{x(2-x)}$ al $x=2/d$ para un entero $d$.

Para un entero $d$, denotan por $A$ el operador de Markov para el uniforme caminata al azar en un árbol infinito con grado de $d$ (cada vértice ha $d$ los vecinos). Es bien sabido que $|A|=\frac{2 \sqrt{d-1}}{d}$ (creo este es un resultado de Kesten), y que $r_I(A)=2/d$ (para cualquier finito subconjunto $S$ de los árboles que hay al menos $(d-2) card(S)$ entre los bordes $S$ y su complementario, por lo que es $v$ es la función de indicador de $S$, $\langle Av,v\rangle\leq 2 card(S)/d$).

Uno podría objetar que estoy trampa, ya que $A$ no es un finita de la matriz, pero un infinito de la matriz. Pero adecuado truncamientos, de hecho, implican $f(2/d)\geq \frac{2 \sqrt{d-1}}{d}$: si $F$ es un subconjunto finito de los árboles, considere la posibilidad de $A_F=(A_{i,j})_{i,j \in F}$. De curso $r_I(A_F) \leq r_I(A) \leq 2/d$, y si $F$ es lo suficientemente grande como $|A_F|$ es arbitrariamente cerca de $|A|$.

Answer 2

Con un rango de matrices (me refiero a los de la forma $A = \frac {1}{(\max w) \sum w_i}w \otimes w$ para algunos vectores $w$) aquí es una prueba de que dice $f(r) \leq 2 \sqrt{r}$ si nos restringimos a ese tipo de matrices.

Supongamos wlg que $1=w_1\geq w_2 \geq w_3 \geq \dots$ (podemos hacer esto mediante la reorganización de los índices y dividiendo por $w_1$). A continuación, podemos obtener $$\|A\| = \frac{\sum w_i^2}{\sum w_i}$$ y $$r:=r_I(A) = \max_m \frac{\left(\sum_{i\leq m} w_i \right)^2} {m \sum w_i}.$$ Deje $k$ ser el entero más grande, de modo que $w_i \geq \sqrt{r}$, entonces, por definición de $r$ tenemos que $$ r \geq \frac{\left(\sum_{i \leq k} w_i \right)^2} {k \sum w_i}.$$ También $$\|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 $$ Y el uso de ese $v_i \leq 1$ e $\sum_{i\leq k} w_i \geq k w_k \geq k \sqrt r$, obtenemos $$\|A\| \leq \frac{\left(\sum_{i \leq k} w_i\right)^2}{k \sqrt r \sum w_i} + \sqrt r \leq 2 \sqrt{r} $$