Discrete norms of a matrix and the converse to the expander mixing lemma

We define the discrete norm   of a complex m×nm×n matrix A by‖A‖Δ:=max0≠ξ∈{0,1}n⁡‖Aξ‖‖ξ‖, and show thatclog⁡h(A)+1‖A‖≤‖A‖Δ≤‖A‖, where c>0c>0 is an explicitly indicated absolute constant, h(A)=‖A‖1‖A‖∞/‖A‖, and ‖A‖1‖A‖1, ‖A‖∞‖A‖∞, and ‖A‖=‖A‖2‖A‖=‖A‖2 are the induced operator norms of A. Similarly, for the discrete Rayleigh norm‖A‖P:=max0≠ξ∈{0,1}m0≠η∈{0,1}n⁡|ξtAη|‖ξ‖‖η‖ we prove the estimateclog⁡h(A)+1‖A‖≤‖A‖P≤‖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 Bollobás–Nikiforov and Bilu–Linial.