Consider the matrix $\ell_{\infty} \to \ell_{\infty}$ operator norm for some matrix $A \in \mathbb{R}^{m \times n}$, given by $$ \| A \|_{\infty} := \sup_{x: \| x \|_{\infty} = 1} \| A x \|_{\infty} := \max_{j \in [m]} \| A_{i, :} \|_1. $$
Question: Prove (or disprove via counterexample) the following inequality: $$ \left\| V \begin{bmatrix} I_{k_1} & 0 \\ 0 & -I_{k_2} \end{bmatrix}V^\top \right\|_{\infty} \leq C \| V V^\top \|_{\infty}, $$ for $V$ satisfying $V^\top V = I$ and $V \in \mathbb{R}^{n \times k}$, with $k_1 + k_2 = k$.
This is not a homework problem, and I have been unable to come up with a counterexample (for randomly generated $V$, I find $C < 2$). I'm looking for some $C$ which is ideally in the range $o(\sqrt{k})$.
Let $V:=[v_1,\ldots,v_k]$ written as column vectors. Then $V^\top V=I$ means that $v_i$ are orthonormal.
Now, for any vector $x$,\begin{align} \|VJV^\top x\|_\infty&\le\|VJV^\top x\|_2\\ &=\|(v_1\cdot x)v_1+\cdots-(v_k\cdot x)v_k\|_2\\ &=\sqrt{\sum_{i=1}^k(v_i\cdot x)^2}\\ &=\|(v_1\cdot x)v_1+\cdots+(v_k\cdot x)v_k\|_2\\ &=\|VV^\top x\|_2\\ &\le\sqrt{n}\,\|VV^\top x\|_\infty\\ &\le\sqrt{n}\,\|VV^\top\|_\infty\|x\|_\infty \end{align}
Hence $\|VJV^\top\|_\infty\le\sqrt{n}\,\|VV^\top\|_\infty$.
That $\sqrt{n}$ cannot be improved upon much can be seen from this example:
$V:=[v_1,v_2]$, $v_1=(a,b,\ldots,b)$, $v_2=(-a,b,\ldots,b)$. The condition $V^\top V=I$, i.e., $v_1,v_2$ are orthonormal, then forces $a=\frac{1}{\sqrt{2}}$, $b=\frac{1}{\sqrt{2(n-1)}}$.
With $J=\begin{pmatrix}1&0\\0&-1\end{pmatrix}$, $$\|VV^\top\|_\infty=\left\|\begin{pmatrix}2a^2&0&\cdots&0\\0&2b^2&\cdots&2b^2\\\vdots\end{pmatrix}\right\|_\infty=2\max(a^2,(n-1)b^2)=1$$ $$\|VJV^\top\|_\infty=\left\|\begin{pmatrix}0&2ab&\cdots&2ab\\2ab&0&\cdots&0\\\vdots\end{pmatrix}\right\|_\infty=2(n-1)ab=\sqrt{n-1}$$