"max" entry norm inequality?

Question

Suppose $\max_{i,j}(A_{i,j}-B_{i,j})<t$. What can we say about $\max((TA)_{i,j}-(TB)_{i,j})$, where $T$ is a positive semi-definite matrix?

I would like to say that $\max((TA)_{i,j}-(TB)_{i,j})< t\|T\|$ by the norm-inequality. Is this right?

Answer 1

We can show a slightly different result, which gives a slightly stronger version of the statement in question when $t\geq 0$ with $\|\cdot\|=\|\cdot\|_{\infty}$. Let $$\|A\|_{\mathrm{max}}:=\max\limits_{i,j}|a_{ij}|$$ be the $\max$-norm of $A$ and $\|A-B\|_{\max}\leq t$. It is tempting to write $\|T(A-B)\|_{\max}\leq \|T\|_{\max}\|A-B\|_{\max}$, which is generally not true since $\|\cdot\|_{\max}$ is not submultiplicative. However, $$ \begin{split} \|T(A-B)\|_{\max} &= \max_{i,j}\left|\sum_kt_{ik}(a_{kj}-b_{kj})\right| \leq \max_{i,j}\sum_k|t_{ik}||a_{kj}-b_{kj}| \\&\leq t\,\max_{i}\sum_k|t_{ik}| \leq t\|T\|_{\infty}. \end{split} $$ The matrix $T$ does not need to be semidefinite nor symmetric (it is true also for rectangular matrices of suitable dimensions).

The statement does not need to be true for the 2-norm. Let $$ A=\pmatrix{5 & 4 \\ 5 & 3}, \quad B=\pmatrix{1 & 1 \\ 2 & 1}, $$ so $$ \|A-B\|_{\max}\leq t = 4. $$ With $$ T=\pmatrix{5&3\\3&2}, \quad \|T\|_2\approx 6.85, $$ $$ \|T(A-B)\|_{\max}=\left\|\pmatrix{29&21\\18&13}\right\|_{\max}=29\not\leq t\|T\|_2\approx 27.42. $$