# A conjecture about the submatrix of orthogonal matrix

Let $$U$$ be an $$n\times n$$ orthogonal matrix, i.e. $$U\in\mathbb{R}^{n \times n}$$. For any non-empty ordered sets $$S_1,S_2\subset\{1,2,...,n\}$$, define $$U_{S_1S_2}$$ to be an $$|S_1|\times|S_2|$$ submatrix of $$U$$ which consists of the intersection entries of rows in $$S_1$$ and columns in $$S_2$$. Let $$\odot$$ be the Hadamard product (element-wise product). Here $$|S|$$ is the cardinality of set $$S$$. More precisely, an ordered set of cardinality $$k$$ can be written as a $$k$$-vector with distinct entries $$(i_1,...,i_k)$$. Therefore $$U_{(i_1,...,i_k),(j_1,...,j_k)}=\begin{pmatrix} U_{i_1j_1} & \cdots & U_{i_1j_k}\\ \vdots & \ddots & \vdots\\ U_{i_kj_1} & \cdots & U_{i_kj_k} \end{pmatrix}$$ Then is the following conjecture true?

For any unit vector $$v=(v_1,...,v_k)$$ in $$\mathbb{R}_+^k, k\leq n$$ and any orthogonal matrix $$U\in O(n)$$, there exists ordered subsets $$S_1,S_2\subset\{1,2,...,n\}, |S_1|=k,|S_2|=k$$, such that: $$\sum_{j=1}^n\left(\sum_{i=1}^kv_iU_{ij}^2\right)^2\leq v^T[U_{S_1S_2}\odot U_{S_1S_2}]v$$

If this is not true, is the following weaker conjecture true? $$\sum_{j=1}^k\left(\sum_{i=1}^kv_iU_{ij}^2\right)^2\leq v^T[U_{S_1S_2}\odot U_{S_1S_2}]v$$

The conjecture can be easily verified when $$k=1$$. The weaker conjecture can also be verified when $$v=(1/\sqrt{k},...,1/\sqrt{k})$$.

Maybe we can start from the particular case that $$v=(1/\sqrt{k},...,1/\sqrt{k})$$.

• Have you tested your conjectures for a few thousand random choices of $U$ and $v$ (say, for $n=3$ and $k=2$) on a computer? – Jochen Glueck Jul 8 at 6:31

Neither conjecture is true in general, as seen from the following counterexample for $$n = 4$$, $$k = 2$$, and

\begin{align} U = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ 0 & 0 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{pmatrix} \ \ \ \ \ \ \ \ \ \ \ \mathrm{and} \ \ \ \ \ \ \ \ \ \ \ \ v = \frac{1}{2}\begin{pmatrix} 1 \\ \sqrt{3} \end{pmatrix} \mathrm{.} \end{align}

Clearly $$U$$ is orthogonal and $$v$$ is a unit vector, as required, and for which

\begin{align} \sum_{j=1}^n\left(\sum_{i=1}^kv_iU_{ij}^2\right)^2 = \sum_{j=1}^k\left(\sum_{i=1}^kv_iU_{ij}^2\right)^2 = 1 \mathrm{.} \end{align}

However,

\begin{align} \mathrm{max}_{S_1, S_2} \ v^T[U_{S_1S_2}\odot U_{S_1S_2}]v = \frac{1}{4}\left(2 + \sqrt{3}\right) < 1 \mathrm{,} \end{align}

where the maximizing subsets are $$S_1 = S_2 = (3, 4)$$. Notice that taking $$U_{(1,2)(1,2)}$$ from $$U$$ above would suffice as a counterexample as well (for the same $$v$$), but the above also shows that the conjectures are false when $$k$$ is strictly less than $$n$$.

The example $$v = (1/\sqrt{k},\dots, 1/\sqrt{k})$$ may be somewhat pathological, since $$U \odot U$$ is an orthostochastic matrix (all of its rows and columns sum to 1), and so it is guaranteed to have the all-ones vector as an eigenvector. An arbitrary submatrix of $$U \odot U$$ will not have this eigenvector in-general, however.