A conjecture about the submatrix of orthogonal matrix

Question

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

Answer 1

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.