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

We define the discrete norm of a complex $m\times n$ matrix $A$ by $$\mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{\Delta }}:=\underset{0\mathrm{\ne }\xi \in \{0,1{\}}^n}{\max }\frac{\mathrm{\parallel }A\xi \mathrm{\parallel }}{\mathrm{\parallel }\xi \mathrm{\parallel }},$$ and show that $$\frac{c}{\sqrt{\log h(A)+1}}\mathrm{\parallel }A\mathrm{\parallel }\le \mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{\Delta }}\le \mathrm{\parallel }A\mathrm{\parallel },$$ where $c>0$ is an explicitly indicated absolute constant, $h(A)=\sqrt{\mathrm{\parallel }A{\mathrm{\parallel }}_1\mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{\infty }}}\mathrm{/}\mathrm{\parallel }A\mathrm{\parallel }$, and $\mathrm{\parallel }A{\mathrm{\parallel }}_1,\mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{\infty }}$, and $\mathrm{\parallel }A\mathrm{\parallel }=\mathrm{\parallel }A{\mathrm{\parallel }}_2$ are the induced operator norms of $A$. Similarly, for the \emph{discrete Rayleigh norm} $$\mathrm{\parallel }A{\mathrm{\parallel }}_P:=\underset{\begin{array}{c}0\mathrm{\ne }\xi \in \{0,1{\}}^m\\ 0\mathrm{\ne }\eta \in \{0,1{\}}^n\end{array}}{\max }\frac{\mathrm{\mid }{\xi }^{t}A\eta \mathrm{\mid }}{\mathrm{\parallel }\xi \mathrm{\parallel }\mathrm{\parallel }\eta \mathrm{\parallel }}$$ we prove the estimate $$\frac{c}{\log h(A)+1}\mathrm{\parallel }A\mathrm{\parallel }\le \mathrm{\parallel }A{\mathrm{\parallel }}_P\le \mathrm{\parallel }A\mathrm{\parallel }\mathrm{.}$$ 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.