# Proof of relation between maximum element and induced $p$-norm of a matrix

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.

• What have you tried already? Where have you already thought of? How do you think you need to solve this? Can you show some effort? Where did you encounter this problem? Could you give some context. – Pedro Mar 17 '15 at 11:16
• What norm are you looking at? – Willie Wong Mar 17 '15 at 11:20
• 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. I think the norm here is any induced norm. – N.M. Mar 17 '15 at 11:22

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.