I am looking for a lower bound for the operator norm of an $n\times n$ real symmetric matrix $A$ relating to an induced matrix $A'$ defined by:
$$ (A')_{i,j}=\vert A_{i,j}\vert $$
The lower bound I am looking for is of the form :
$$ \Vert A'\Vert \leq C\cdot \Vert A\Vert+D \quad \text{where } \; \Vert \cdot \Vert \; \text{is the operator norm} $$
Hopefully $C$ and $D$ would not be dependent on $n$. I would also appreciate a reference to a place where such an inequality can be found, if this is well researched.
Best Answer
The constant $C$ must grow at least exponentially with $n$.
Let $B$ be any symmetric matrix such that $\|B'\|>\|B\|$, such as $B=\pmatrix{1&1\\ 1&-1}$. Set $A=\otimes^kB=B\otimes\cdots\otimes B$. Observe that $(\otimes^kB)'=\otimes^kB'$, because each entry of the $k$-fold Kronecker product of a matrix is a product of some $k$ entries of that matrix. Therefore $$ \frac{\|A'\|}{\|A\|} =\frac{\|(\otimes^kB)'\|}{\|\otimes^kB\|} =\frac{\|\otimes^kB'\|}{\|\otimes^kB\|} =\frac{\|B'\|^k}{\|B\|^k}, $$ meaning that $C$ must grow at least exponentially with $k$ (and hence also with $n$).