Lower bound on operator norm of symmetric matrix

Question

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.

Answer 1

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$).

Answer 2

The answer by user1551 is excellent, but here's a much, much weaker example where this sort of thing happens, but with a very recent and exciting application. A couple months ago, Hao Huang resolved a longstanding open problem in theoretical computer science/graph theory known as the sensitivity conjecture by giving a stunningly simple proof that there exists a signing (flip some $1$s to $-1$s) of the adjacency matrix of the Boolean hypercube (a $N\times N$ real symmetric matrix with $0,1$ entries, where $N=2^n$) such that the operator norm is $\sqrt{n}$, while the unsigned adjacency matrix has operator norm $n$. In particular, this gives a family of examples where $C=\sqrt{\log_2 N}$. What's amazing is the signing Huang constructed completely condensed the spectrum of the Boolean hypercube to all $\pm \sqrt{n}$, which he then exploited to give his main result. The moral is that signing entries can completely dampen the spectrum of symmetric matrices.

It's worth noting that taking absolute values everywhere cannot change the sum of squares of the eigenvalues. The reason is that the diagonals of $A^2$ and $A'^2$ stay the same, and the trace of either matrix is also equal to the sum of the squares of the eigenvalues.