Inequality for the matrix infinity norm 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})$.
 A: 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}$$
