¿Es la norma de un $0-1$ matriz (casi) alcanzada en un $0-1$ ¿Vector?

Question

Me gustaría exponer explícitamente un problema que de alguna manera estaba oculto en mi post de hace tres semanas :

¿Existe una constante absoluta $c>0$ con la propiedad de que para cualquier matriz $M\in{\mathcal M}_{m\times n}(\{0,1\})$ (matrices cero-uno con $m$ filas y $n$ columnas), existe un vector distinto de cero $x\in\{0,1\}^n$ tal que $\|Mx\|/\|x\|\ge c\|M\|$ ?

(Aquí $\|\cdot\|$ denota tanto las normas euclidianas en ${\mathbb R}^m$ y ${\mathbb R}^n$ y la norma del operador inducido).

---

Puedo demostrar la conclusión con $c\sim 1/\sqrt{\log n}$ incluso en el caso $M\in{\mathcal M}_{m\times n}({\mathbb R})$ y un ejemplo debido a Greg Kuperberg muestra que esto es, en esencia, lo mejor posible. La pregunta es, ¿se puede hacer una mejora bajo el supuesto de que todos los elementos de $M$ se limitan a los valores $0$ y $1$ ?

Answer 1

Como he descubierto recientemente, la respuesta es no . La prueba completa es algo técnica y no puedo proporcionar todos los detalles en el marco de un post MO, pero aquí está la idea detrás de la construcción.

Empezar con una matriz simétrica $A\in{\mathcal M}_{n\times n}(\{0,1\})$ tal que el valor propio de Perron-Frobenius de $A$ es mucho mayor que el valor absoluto de cualquier otro valor propio, y el vector propio correspondiente es "razonablemente simple". Tomemos ahora una potencia tensorial alta de $A$ . Obtenemos una matriz simétrica cero-uno $M$ que hereda la brecha espectral de la matriz original $A$ y, por tanto, la norma $\|Mx\|$ se controla mediante la proyección de $x$ en el vector propio de Perron-Frobenius, digamos $v$ de $M$ . Siendo una potencia tensorial del vector propio Perron-Frobenius de la matriz original $A$ el vector $v$ puede analizarse, y con cierto esfuerzo puede demostrarse que es "oblicuo" en el sentido de que "no está alineado" con ningún vector cero-uno. Por tanto, si $x$ es un vector cero-uno, entonces la proyección de $x$ en $v$ y, por tanto, la norma $\|Mx\|$ son pequeñas.

Un resultado preciso que he podido demostrar en este sentido es el siguiente: existen matrices $M\in{\mathcal M}_{n\times n}(\{0,1\})$ de orden arbitrariamente grande $n$ tal que para cualquier vector distinto de cero $x\in\{0,1\}^n$ , $$ \|Mx\| \ll \left( \frac{\log\log n}{\log n} \right)^{1/8} \|M\|\|x\|. $$