How to prove this matrix bound Let an $m$ by $n$ matrix $A\in\mathbb C^{m\times n}$. Denote $M=\max_i\sum_{j=1}^n|A_{ij}|$ and $N=\max_j\sum_{i=1}^m|A_{ij}|$. Prove for any two vectors $x\in\mathbb C^m$ and $y\in\mathbb C^n$, we have
$$\left\vert x^TAy\right\vert\leq\sqrt{MN}|x||y|$$

Here's what I think:
$$|x^TAy|=\left|\sum_{i,j}A_{ij}x_iy_j\right|\leq\sqrt{\sum_j\left(\sum_iA_{ij}x_i\right)^2\cdot\sum_jy_j^2}\leq\left|y\right|\sqrt{\sum_j\left(\sum_iA_{ij}^2\cdot\sum_ix_i^2\right)}=|x||y|\sqrt{\sum_{ij}A_{ij}^2}$$
But how do I prove $$\sum_{ij}A_{ij}^2\leq MN$$

Edit:
My idea was proved to be wrong. But how do I prove the original inequality?
 A: The inequality you want to prove is not true (for example, the identity matrix $A$). Consider a different approach, when in the second inequality you do not go so above the threshold.
A: Let $\left\Vert X\right\Vert$ denote the spectral norm of $X$. Also, let $\left\Vert \cdot\right\Vert_{p\to p}$ denote the matrix norm induced by the $\ell_p$-norm:
$$\left\Vert X\right\Vert_{p\to p}=\max_{v\neq 0} \frac{\left\Vert Xv\right\Vert_p}{\left\Vert v\right\Vert_p}.$$
Let $v$ be the principal eigenvector of $A^*A$, i.e., a unit $\ell_2$-norm vector for which we have $A^*Av=\sigma^2 v$ where $\sigma^2=\left\Vert A^*A\right\Vert=\left\Vert A\right\Vert^2$. It follows that $$\frac{\left\Vert A^*Av\right\Vert_1}{\left\Vert v\right\Vert_1}=\frac{\left\Vert \left\Vert A\right\Vert^2v\right\Vert_1}{\left\Vert v\right\Vert_1}=\left\Vert A\right\Vert^2.$$ Therfore, 
$$\left\Vert A\right\Vert^2\leq\left\Vert A^*A\right\Vert_{1\to 1}=\max_{u,v\neq 0}\frac{\left\vert u^*A^*Av\right\vert}{\left\Vert u\right\Vert_\infty\left\Vert v\right\Vert_1}\\
\leq \max_{u,v\neq 0}\frac{\left\Vert Au\right\Vert_\infty\left\Vert Av\right\Vert_1}{\left\Vert u\right\Vert_\infty\left\Vert v\right\Vert_1}=\left\Vert A\right\Vert_{\infty\to\infty}\cdot \left\Vert A\right\Vert_{1\to 1}.$$ It is straightforward to show that $M=\left\Vert A\right\Vert_{\infty\to \infty}$ and $N=\left\Vert A\right\Vert_{1\to 1}$. The result then follows using the fact that $\left\vert x^*Ay\right\vert\leq\left\Vert A\right\Vert\left\Vert x\right\Vert\left\Vert y\right\Vert$.
