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



A conjecture about the submatrix of orthogonal matrix
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.


