Equivalent Norms: Proving $\|A\| \leq \|A\|_{Eucl} \leq \sqrt{n}\|A\|$

[mathmari]

Hey!

Let $A=(a_{i,j})$ a real matrix with $m$ rows and $n$ columns, $x\in \mathbb{R}^n$ and \begin{equation*}\|A\|:=\sup_{\|x\|_2\leq 1}\|Ax\|_2, \ \ \|A\|_{\text{Eucl}}:=\sqrt{\sum_{i=1}^m\sum_{j=1}^n|a_{i,j}|^2}\end{equation*}

I want to show that $$\|A\|\leq \|A\|_{\text{Eucl}} \leq \sqrt{n}\|A\|$$ I have already shown the first inequality:

Since $\displaystyle{(Ax)_i=\sum_{j=1}^na_{i,j}x_j}$, we get $\displaystyle{\|Ax\|_2^2=\sum_{i=1}^m\left (\sum_{j=1}^n|a_{i,j}x_j|\right )^2=\sum_{i=1}^m\left (\sum_{j=1}^n|a_{i,j}||x_j|\right )^2}$.

From the Cauchy–Schwarz inequality we get \begin{equation*}\left (\sum_{j=1}^n|a_{i,j}||x_j|\right )^2\leq \left (\sum_{j=1}^n{|a_{i,j}|^2}\right )\left (\sum_{j=1}^n|x_j|^2\right )=\left (\sum_{j=1}^n{|a_{i,j}|^2}\right )\|x\|_2^2\end{equation*}

Sp we get\begin{equation*}\|Ax\|_2^2=\sum_{i=1}^n\left (\sum_{j=1}^n|a_{i,j}||x_j|\right )^2\leq \sum_{i=1}^m\sum_{j=1}^n|a_{i,j}|^2\|x\|_2^2=\|A\|_{\text{Eucl}}^2\,\|x\|_2^2 \end{equation*}

Therefore we have that \begin{equation*}\|Ax\|_2\leq \|A\|_{\text{Eucl}}\,\|x\|_2\Rightarrow \sup_{\|x\|_2\leq 1}\|Ax\|_2\leq \sup_{\|x\|_2\leq 1}\|A\|_{\text{Eucl}}\,\|x\|_2=\|A\|_{\text{Eucl}}\end{equation*}

From that it implies that $\|A\|\leq \|A\|_{\text{Eucl}}$. Is everything correct? (Wondering)
Could you give me a hint for the second inequality? (Wondering)

 

[Opalg]

Hey!

Let $A=(a_{i,j})$ a real matrix with $m$ rows and $n$ columns, $x\in \mathbb{R}^n$ and \begin{equation*}\|A\|:=\sup_{\|x\|_2\leq 1}\|Ax\|_2, \ \ \|A\|_{\text{Eucl}}:=\sqrt{\sum_{i=1}^m\sum_{j=1}^n|a_{i,j}|^2}\end{equation*}

I want to show that $$\|A\|\leq \|A\|_{\text{Eucl}} \leq \sqrt{n}\|A\|$$ I have already shown the first inequality:
.
.
.
Is everything correct? (Wondering)

Yes!

Could you give me a hint for the second inequality? (Wondering)

You could use the fact that $\|A\|_{\text{Eucl}}^2 = \text{tr}\,(A^TA)$ (where tr denotes the trace and $A^T$ is the transpose of $A$).

 

[mathmari]

You could use the fact that $\|A\|_{\text{Eucl}}^2 = \text{tr}\,(A^TA)$ (where tr denotes the trace and $A^T$ is the transpose of $A$).

What do we get from that? I got stuck right now. (Wondering) Could we do also something like the following?
\begin{align*}\|A\|_{\text{Eucl}}^2=\sum_{i=1}^m\sum_{j=1}^n|a_{i,j}|^2=\sum_{j=1}^n\sum_{i=1}^m|a_{i,j}|^2=\sum_{j=1}^n\|a_j\|_2^2=\sum_{j=1}^n\|Ae_j\|_2^2\leq \sum_{j=1}^n\|A\|_2^2\|e_j\|_2^2=n\|A\|_2^2\end{align*} But instead of $\|A\|$ we have $\|A\|_2$. Is the above correct? If yes, can we get to $\|A\|$ ? (Wondering)

 

[GJA]

Hi mathmari,

Could we do also something like the following?
\begin{align*}\|A\|_{\text{Eucl}}^2=\sum_{i=1}^m\sum_{j=1}^n|a_{i,j}|^2=\sum_{j=1}^n\sum_{i=1}^m|a_{i,j}|^2=\sum_{j=1}^n\|a_j\|_2^2=\sum_{j=1}^n\|Ae_j\|_2^2\leq \sum_{j=1}^n\|A\|_2^2\|e_j\|_2^2=n\|A\|_2^2\end{align*} But instead of $\|A\|$ we have $\|A\|_2$. Is the above correct? If yes, can we get to $\|A\|$ ? (Wondering)

This idea will work, we just need to note two small things:

1) For a set $S$ of non-negative numbers -- which $S=\{\|Ax\|_{2} : \|x\|_{2}\leq 1\}$ is -- $\sup_{x\in S} x^{2}=\left(\sup_{x\in S} x\right)^{2}.$ This follows from the continuity and monotonicity of the squaring function $x\mapsto x^{2}$ on the non-negative half-line.

2) For each $e_{j}$, $\|Ae_{j}\|_{2}^{2}\leq \|A\|^{2}$, because, using point (1) above,
$$\|A\|^{2}=\left(\sup_{\|x\|_{2}\leq 1}\|Ax\|_{2} \right)^{2}=\sup_{\|x\|_{2}\leq 1}\|Ax\|^{2}_{2}\geq \|Ae_{j}\|^{2}_{2}.$$

 

[mathmari]

This idea will work, we just need to note two small things:

1) For a set $S$ of non-negative numbers -- which $S=\{\|Ax\|_{2} : \|x\|_{2}\leq 1\}$ is -- $\sup_{x\in S} x^{2}=\left(\sup_{x\in S} x\right)^{2}.$ This follows from the continuity and monotonicity of the squaring function $x\mapsto x^{2}$ on the non-negative half-line.

2) For each $e_{j}$, $\|Ae_{j}\|_{2}^{2}\leq \|A\|^{2}$, because, using point (1) above,
$$\|A\|^{2}=\left(\sup_{\|x\|_{2}\leq 1}\|Ax\|_{2} \right)^{2}=\sup_{\|x\|_{2}\leq 1}\|Ax\|^{2}_{2}\geq \|Ae_{j}\|^{2}_{2}.$$

Ah I see! Thank you so much! (Yes)