If true, prove the identity:
$$
||A|| \ge \max\limits_{i,j}|a_{ij}|
$$
$||.||$ is any induced/operator norm.
Edit: The identity is true only for operator norm induced by $p$-norm for vectors.
I found this property in a presentation of singular values and matrix norms. This property could be useful for me in my work but I am not able to prove it.
Best Answer
Let $\|\cdot\|$ be a vector norm and $\|\cdot\|_M$ be its associated operator norm and $\|\cdot\|_D$ be dual w.r.t. $\|\cdot\|$, that is, $$ \|x\|_D=\max_{y\neq 0}\frac{|x^*y|}{\|y\|}. $$ Let $e_i$ be the $i$th column of the identity. Then $$ |a_{ij}|=|e_i^*Ae_j|\leq\|e_i\|_D\|Ae_j\|\leq\|e_i\|_D\|A\|_M\|e_j\|. $$ Now if $\|e_i\|=\|e_i\|_D=1$ for all $i=1,\ldots,n$, then $|a_{ij}|\leq\|A\|_M$. This is true, e.g., for all $p$-norms (note that the 2-norm is also its dual norm and for the $p$-norm with $1\leq p\leq \infty$, the dual norm is the $q$-norm such that $1/p+1/q=1$ with the convention $1/\infty=0$).
The norm $\|\cdot\|_M$ cannot be, however, any operator norm. Let $$ M:=\pmatrix{1&2\\2&8}. $$ The matrix $M$ is SPD and hence induces a vector norm $\|x\|:=(x^*Mx)^{1/2}$. The associated matrix norm can be expressed in terms of the matrix spectral norm as $\|A\|_M=\|M^{1/2}AM^{-1/2}\|_2$. Although $\|\cdot\|_M$ is a "perfect" operator norm, $\|A\|_M\approx 2.9208$ for $$ A=\pmatrix{3&2\\-1&0}, $$ which clearly violates the claim.