# Bound on the 2-norm of a “special” matrix

Let $S\in\mathbb{R}^{n\times n}$ be such that $\|S\|_2\leq 1$, $P\in\mathbb{R}^{n\times m}$, $m<n$, with orthogonal columns ($P^TP=I$) so that $PP^T$ and $I-PP^T$ are orthogonal projectors, and $F\in\mathbb{R}^{m\times m}$ be symmetric such that $\|F\|_2<1$. Let $$E=S^T(I-PP^T)S, \quad \tilde{E}=S^T[I-P(I-F)P^T]S.$$ Both $E$ and $\tilde{E}$ are clearly symmetric and in addition $E$ is positive semidefinite. It might be true that $F$ could be positive semidefinite too (hence $\tilde{E}$ would be positive semidefinite as well) but it seems that this assumption might not be needed.

Now let $\|E\|_2<1$. I need to show that $$\color{blue}{\|\tilde{E}\|_2\leq \|E\|_2+\|F\|_2(1-\|E\|_2)=1-(1-\|E\|_2)(1-\|F\|_2)}$$ and hence $\|\tilde{E}\|<1$ (actually, I would like to show that inequality, not just that $\|\tilde{E}\|<1$).

A simple bound is obvious. Since $\tilde{E}=E+S^TPFP^TS$, clearly $$\tag{1}\|\tilde{E}\|_2\leq\|E\|_2+\|F\|_2\|P^TS\|_2^2.$$ We have $\|P^TS\|_2\leq 1$ since $P$ is orthogonal and $\|S\|_2\leq 1$. This is however useless as it gives me only $\|\tilde{E}\|_2\leq\|E\|_2+\|F\|_2$.

If I showed in (1) that $\|P^TS\|_2^2\leq 1-\|E\|_2$, I would be done then. However, it seems that this does not generally hold under the stated assumptions so that the simple triangle inequality (1) is already an overestimate.

I would highly appreciate any comment or pointer to a possible solution.

First, let's ignore $S$ and let $E'=I-PP^T$ and $\tilde{E}'=E'+PFP^T$. Then $E$ and $\tilde{E}$ arise from $E'$ and $\tilde{E}'$ by conjugating with $S$.
Choose ON-bases of $\mathbb{R}^n,\mathbb{R}^m$ such that $P=\binom{I}{0}$. Then $PP^T=\binom{I0}{00}$ and $E'=\binom{00}{0I}$. Furthermore, $\tilde{E}'=\binom{F0}{0I}$. From this it follows that $\|\tilde{E}\|_2\le\|\tilde{E}'\|_2\le 1$. In fact, $\|\tilde{E}\|_2<1$:
Let $v$ be a vector with $\|v\|_2=1$, and let $Sv=\binom{v_1}{v_2}$. Then $\tilde{E}v=S^T\binom{Fv_1}{v_2}$. Either $v_1=0$, and then $\|\tilde{E}v\|_2=\|Ev\|_2<1$, or $\|Fv_1\|_2<\|v_1\|_2$, and so $\|\binom{Fv_1}{v_2}\|_2<1$; hence $\|\tilde{E}v\|_2<1$.