# 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})$$.

• So what is C? Are you just trying to say that thing is bounded?
– Ovi
Dec 13, 2019 at 20:17
• @Ovi: I'm looking for as small a constant $C$ as possible. I edited the question to reflect this. Dec 13, 2019 at 20:21
• It is easy to prove that a $C$ such that the inequality holds must exist, if that's what you mean by "prove the inequality" without giving us a particular $C$. Dec 13, 2019 at 20:43
• Could you give us some context for this problem? Would such a $C$ be useful for some goal? Dec 13, 2019 at 20:44
• @Omnomnomnom: Sure. This inequality shows up as a step in analyzing the convergence rate of orthogonal iteration (for Hermitian matrices), when distance between eigenvectors and iterates is measured in the $\ell_{\infty}$ norm (up to an arbitrary rotation of the subspace). If $C \ll \sqrt{n}$, where $n$ is the size of the original matrix, we can ensure faster convergence than in the case where we care about the spectral norm (although they are asymptotically similar). Dec 13, 2019 at 21:03

## 1 Answer

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}$$