A matrix norm (for some A \in \mathbb{C}^{m \times n}) is defined as :

\left|\left|A\right|\right| = \sup_{x \ne 0} \frac{\left|\left|Ax\right|\right|}{\left|\left|x\right|\right|}

where, \left|\left|.\right|\right| is a vector norm and \sup is the supremum, a sort of maximum value \ge this value. In some sense, this measures the stretching that the matrix A imparts onto the vector x.

Interestingly, it can be shown that the \left|\left|A\right|\right|_1 norm is nothing but the maximum column (absolute) sum of the matrix A and the \left|\left|A\right|\right|_{\infty} norm is the maximum sum of absolute values of elements of a row in A. More importantly, the useful \left|\left|A\right|\right|_2 norm is actually the largest singular value of A.

We can also show how these norms are related to each other. For example,

\frac{1}{\sqrt{m}}\left|\left|A\right|\right|_2 \le \left|\left|A\right|\right|_{\infty} \le \sqrt{n}\left|\left|A\right|\right|_2

To show this, first consider the vector norm relationship for x \in \mathbb{C}^n.

\left|\left|x\right|\right|_{\infty} = \left(\left|x\right|^2 \right)^{1/2} \le \left(\sum_{i=1}^{n}\left|x\right|^2 \right)^{1/2} = \left|\left|x\right|\right|_2

Therefore, \left|\left|x\right|\right|_{\infty} \le \left|\left|x\right|\right|_2

\left|\left|x\right|\right|_2 = \left(\sum_{i=1}^{n}\left|x\right|^2 \right)^{1/2}

Replace each x_i with the maximum (absolute) value among them. Thus,

\left|\left|x\right|\right|_2 \le \mathsf{max}_i \left|x_i\right|\left(\sum_i 1\right)^{1/2} = \sqrt{n}\left(\mathsf{max}_i \left|x\right|\right) = \sqrt{n}\left| \left|x\right|\right|_{\infty}

So, \left|\left|x\right|\right|_{\infty} \le \left|\left|x\right|\right|_2 \le \sqrt{n} \left|\left|x\right|\right|_{\infty}.

Now, we know, \left|\left|A\right|\right|_{\infty} = \sup_{x \ne 0} \frac{\left|\left|Ax\right|\right|_{\infty}}{\left|\left|x\right|\right|_{\infty}}.

Using the inequalities from the vector norm, we have, \left|\left|Ax\right|\right|_{\infty} \le \left|\left|Ax\right|\right|_{2} and \left|\left|x\right|\right|_{\infty} \ge \frac{1}{\sqrt{n}}\left|\left|x\right|\right|_{2} .

So, substituting them into the matrix norm definition, we get,

\left|\left|A\right|\right|_{\infty} \le \sup_{x \ne 0} \frac{\left|\left|Ax\right|\right|_{2}}{\frac{\left|\left|x\right|\right|_{2}}{\sqrt{n}}}.

This is how we get, \left|\left|A\right|\right|_{\infty} \le \sqrt{n}\left|\left|A\right|\right|_{2}.

Similarly, \left|\left|Ax\right|\right|_{2} \le \sqrt{m}\left|\left|Ax\right|\right|_{\infty} (since the vector Ax \in \mathbb{C}^m) and \left|\left|x\right|\right|_{2} \ge \left|\left|x\right|\right|_{\infty}, implies,

\left|\left|A\right|\right|_{2} = \sup_{x \ne 0} \frac{\left|\left|Ax\right|\right|_{2}}{\left|\left|x\right|\right|_{2}} \le \sup_{x \ne 0} \frac{\sqrt{m}\left|\left|Ax\right|\right|_{\infty}}{\left|\left|x\right|\right|_{\inf}} = \sqrt{m}\left|\left|A\right|\right|_{\infty}

Finally, we get,

\frac{1}{\sqrt{m}}\left|\left|A\right|\right|_2 \le \left|\left|A\right|\right|_{\infty} \le \sqrt{n}\left|\left|A\right|\right|_2