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

Original · EN

We define the discrete norm of a complex m× n matrix A by AΔ:= ₀≠ξ∈{₀,₁}ₙ Aξ/ξ, and show that c√ h(A)+1A ≤ AΔ≤ A, where c>0 is an explicitly indicated absolute constant, h(A)=√A₁A∞/A, and A₁,A∞, and A=A₂ are the induced operator norms of A. Similarly, for the discrete Rayleigh norm Aₚ:= 0≠ξ∈{0,1}ᵐ 0≠η∈{0,1}ⁿ |ξᵗAη|/ξη we prove the estimate c h(A)+1A ≤ Aₚ ≤ 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.