Discrete norms of a matrix and the converse to the Expander Mixing Lemma

preprint2014arXivOpen access

Abstract

We define the discrete norm of a complex m×nm\times n matrix AA by ∥A∥Δ:=max⁡0≠ξ∈{0,1}n∥Aξ∥∥ξ∥, \|A\|_Δ:= \max_{0\neξ\in\{0,1\}^n} \frac{\|Aξ\|}{\|ξ\|}, and show that clog⁡h(A)+1 ∥A∥≤∥A∥Δ≤∥A∥, \frac c{\sqrt{\log h(A)+1}}\,\|A\| \le \|A\|_Δ\le \|A\|, where c>0c>0 is an explicitly indicated absolute constant, h(A)=∥A∥1∥A∥∞/∥A∥h(A)=\sqrt{\|A\|_1\|A\|_\infty}/\|A\|, and ∥A∥1,∥A∥∞\|A\|_1,\|A\|_\infty, and ∥A∥=∥A∥2\|A\|=\|A\|_2 are the induced operator norms of AA. Similarly, for the \emph{discrete Rayleigh norm} ∥A∥P:=max⁡0≠ξ∈{0,1}m0≠η∈{0,1}n∣ξtAη∣∥ξ∥∥η∥ \|A\|_P := \max_{\substack{0\neξ\in\{0,1\}^m \\ 0\neη\in\{0,1\}^n}} \frac{|ξ^tAη|}{\|ξ\|\|η\|} we prove the estimate clog⁡h(A)+1 ∥A∥≤∥A∥P≤∥A∥. \frac c{\log h(A)+1}\,\|A\| \le \|A\|_P \le \|A\|. These estimates are shown to be essentially best possible. As a consequence, we obtain another proof of the (slightly sharpened and generalized version of the) converse to the expander mixing lemma by Bollobas-Nikiforov and Bilu-Linial.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.