Spectral norm of projected matrix

Question

Let $M_{n,m}$ be the set of real matrices of $n\times m$, and let $T:M_{n,m}\to M_{n,m}$ be a orthogonal projection operator, i.e., $T$ is such that for any $A,B\in M_{n,m}$ $$T(A+B)=T(A)+T(B),$$ $$T(T(A))=T(A),$$ $$\langle T(A),B\rangle = \langle A,T(B)\rangle.$$ where $\langle A,B\rangle=tr(A^{\top}B)$. For $A\in M_{n,m}$ let $\|A\|$ be its spectral norm and $\|A\|_F$ its Frobenius norm. I want to prove that $$ \|T(A)\|\leq \|A\|. $$ I've been able to prove that $\|T(A)\|_F\leq \|A\|_F$ which is immediate since $\langle T(A),(I-T)(A)\rangle=0$ which implies that $\|A\|_F=\|T(A)+(I-T)(A)\|_F=\|T(A)\|_F+\|(I-T)(A)\|_F$.

For the spectral norm maybe I can use that $\|A\|=\sup_{\|x\|_2=1}\|Ax\|_2$ but I can't prove that $x^{\top}T(A)^{\top}(I-T)(A)x=0$.

Any help will be appreciated.

Edit: If it helps, the form of $T$ is $T(A)=A-P_1AP_2$, where $P_1$ and $P_2$ are some $n\times n$ and $m\times m$ projection matrices.

This question is motivated by the paper https://arxiv.org/pdf/1011.6256.pdf, proof of Theorem 1, page 9, inequality after equation (2.15).

Answer 1

This is not true. E.g. suppose that $n=m=2$ and $T$ is the orthogonal projection onto the linear span of $B=\operatorname{diag}(6,3)$. Let $A=5I$. Then $T(A)=B$ because $\langle A-B,B\rangle=\langle \operatorname{diag}(-1,2),\operatorname{diag}(6,3)\rangle=0$. However, $\|T(A)\|_2=\|B\|_2=6>5=\|A\|_2$.

Another counterexample: let \begin{aligned} &T(X)=X-\pmatrix{1\\ &0}X\pmatrix{1\\ &0},\\ &A=\pmatrix{-1&1\\ 1&1},\ B=T(A)=\pmatrix{0&1\\ 1&1}, \end{aligned} then $\|T(A)\|_2=\|B\|_2=\frac{1+\sqrt{5}}{2}\approx1.618>1.414\approx\sqrt{2}=\|A\|_2$.

---

Remark. The inequality that motivated the OP's question, namely, $$ \|T(A)\|_F\le\sqrt{\operatorname{rank}(T(A))}\,\|A\|_2 $$ where $T(A)=A-P_1AP_2$ for some two orthogonal projectors $P_1$ and $P_2$, is correct. Without loss of generality, we may assume that $$ A=\pmatrix{X&Y\\ Z&W} \ \text{ and }\ T(A)=\pmatrix{0&Y\\ Z&W}. $$ Let $Y=U_y(S_y\oplus0)V_y^T$ and $Z=U_z(S_z\oplus0)V_z^T$ be two singular value decompositions, where $S_y$ and $S_z$ are two positive diagonal matrices. Define on $M_{n,m}$ a linear map $$ F:B\mapsto\pmatrix{U_y\\ &U_z}^TB\pmatrix{V_z\\ &V_y}. $$ Then we may write $$ F(A)= \left(\begin{array}{c&c|c&c}\ast&\ast&S_y&0\\ \ast&\ast&0&0\\ \hline S_z&0&E&F\\ 0&0&G&H\end{array}\right) \ \text{ and }\ F(T(A))= \left(\begin{array}{c&c|c&c}0&0&S_y&0\\ 0&0&0&0\\ \hline S_z&0&E&F\\ 0&0&G&H\end{array}\right). $$ Let $$ M_1=\pmatrix{S_y\\ 0\\ 0\\ G}\ \text{ and }\ M_2=\pmatrix{S_z&0&E&F}. $$ Since $M_1,M_2$ and $H$ are submatrices of $F(A)$, their spectral norms are bounded above by $\|F(A)\|_2$. It follows that \begin{aligned} \|T(A)\|_F^2 &=\|F(T(A))\|_F^2\\ &=\|M_1\|_F^2+\|M_2\|_F^2+\|H\|_F^2\\ &\le\operatorname{rank}(M_1)\|M_1\|_2^2+\operatorname{rank}(M_2)\|M_2\|_2^2+\operatorname{rank}(H)\|H\|_2^2\\ &\le\left(\operatorname{rank}(M_1)+\operatorname{rank}(M_2)+\operatorname{rank}(H)\right)\|F(A)\|_2^2\\ &=\operatorname{rank}(F(T(A)))\|F(A)\|_2^2\\ &=\operatorname{rank}(T(A))\|A\|_2^2. \end{aligned}

Answer 2

As the other poster has shown, this is not true in general but it is true in the special case where $T$ takes the form $T: A \mapsto PA $; i.e. $T$ is left multiplication by some matrix $n \times n $ matrix $P$. As you have pointed out there are more general tensors that satisfy the definition, but it is true in this special case.

The spectral norm of $A$ for a real matrix is equal to \begin{equation} |A| = \sup_{|x| = 1} \|Ax\| = \sup_{x \neq 0 } \frac{\|Ax\|}{\|x\|}. \end{equation}

Suppose for a contradiction that \begin{equation} |TA| > |A| \end{equation} then using the vector norm $\| \| $ there is some $v$ such that \begin{equation} \|T(Av)\| =\|(TA)v\| > \|Av\| \end{equation} and therefore setting $x=Av$ we have that \begin{equation} \|Tx\|^{2}=\langle Tx,Tx\rangle =\langle Tx,x\rangle \leq \|Tx\|\cdot \|x\| \end{equation} and therefore we have that \begin{equation} \|Tx\| \leq \|x\| \end{equation} and that \begin{equation} \|Tx\| > \|x\| \end{equation} which is a contradiction. QED