Norm equivalence (Frobenius and infinity)

Question

I am trying to prove the matrix norm equivalence for norms 1, 2, $\infty$ and Frobenius.

I have managed to solve find the constants for $||.||_{1}$ and $||.||_{2}$ but I cannot see how to continue if I want to prove the following:

$||A||_{\infty} \leq \sqrt{n}||A||_{2}$

and the ones for Frobenius:

$||A||_{F} \leq \sqrt{n}||A||_{1}$

$||A||_{F} \leq \sqrt{n} ||A||_{2}$

Any help is appreciated. Thank you for your time

Answer 1

First I want make a remark on the fact of not specifying the space on which we work(your matrices are square or not?), it is also important to give us your norms definitions, so your question will be self-understood, especially if you consider the differences found in the notations used in literature.

In case you are not restricted to search for a specific constant, you can always use the standard method found here : Equivalence of Norms in Finite Dimension.

In your case ( I suppose that $A \in \mathbb{R}^{n\times n}$)

$||A||_{F} \leq \sqrt{n} ||A||_{2}$ is trivial if you consider the definition by using the singular values.

$$||A||_{F} = \sqrt{\sum_{i=1}^{n} \sigma_i(A)^2}$$ ($\sigma_i(A)$ are the singular values of A, in decreasing order, in this case because A is square, singular values are simply the absolute value of eigenvalues)

$$||A||_{F} \leq \sqrt{n \sigma_1(A)^2} = \sqrt{n}\sigma_1(A) = \sqrt{n} ||A||_{2} $$

after that, you can find here how you can prove that :

$$||A||_2 \leq \sqrt {n} ||A||_1$$

with this two inequalities you get that

$$||A||_{F} \leq n||A||_{1}$$

I have no idea haw you can get $\sqrt{n}$ instead of $n$

Answer 2

Assuming $A\in\mathbb{C}^{n\times n}$ with columns $a_1,\ldots,a_n$ and that you already know the equivalence constants for vector $p$-norms:

• For $\|A\|_{\infty}\leq\sqrt{n}\|A\|_2$: We have for all $x\in\mathbb{C}^n$, $\|x\|_{\infty}\leq\|x\|_2\leq\sqrt{n}\|x\|_{\infty}$, so $$ \|A\|_{\infty}=\max_{x\neq 0}\frac{\|Ax\|_{\infty}}{\|x\|_{\infty}} \leq\max_{x\neq 0}\frac{\|Ax\|_2}{\frac{1}{\sqrt{n}}\|x\|_2}=\sqrt{n}\max_{x\neq 0}\frac{\|Ax\|_2}{\|x\|_2}=\sqrt{n}\|A\|_2. $$ In fact, all equivalence relations for matrix $p$-norms can be derived from the related equivalence relations for the vector $p$-norms and using simply the definition of the operator norm.

• For $\|A\|_F\leq\sqrt{n}\|A\|_2$: $$ \|A\|_F^2=\sum_{i=1}^n\|a_i\|_2^2=\sum_{i=1}^n\|Ae_i\|_2^2\leq\sum_{i=1}^n\|A\|_2^2\|e_i\|_2^2=n\|A\|_2^2. $$ The bound can be improved if the rank $r$ of $A$ is smaller than $n$ by realizing that $$ \|A\|_F^2=\mathrm{trace}(A^*A)\leq r\rho(A^*A)=r\|A\|_2^2, $$ where we used the fact that the trace is equal to the sum of the eigenvalues, which, if $r=\mathrm{rank}(A)$, contains only $r$ nonzero terms. Hence $\|A\|_F\leq\sqrt{\mathrm{rank}(A)}\|A\|_2$.

• For $\|A\|_F\leq\sqrt{n}\|A\|_1$: Using the fact that $\|a_i\|_2\leq\|a_i\|_1$ and that $\|a_i\|_1\leq\|A\|_1$ for all $i=1,\ldots,n$, $$ \|A\|_F^2=\sum_{i=1}^n\|a_i\|_2^2\leq\sum_{i=1}^n\|a_i\|_1^2\leq n\|A\|_1^2. $$