4
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Jochen Glueck Jul 8 at 6:31
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.