4
$\begingroup$

Suppose $\mathbf{a}$ and $\mathbf{b}$ are two vectors in $\mathbb{R}^n$. For any integer $1 \leq k \leq n$, let $[n]_k$ denote the set of $k$-subsets of $\{1,2,\dots,n\}$. For any $\mathcal{Q} \in [n]_k$, let $\mathbf{a}_\mathcal{Q}$ and $\mathbf{b}_\mathcal{Q}$ be two subvectors of $\mathbf{a}$ and $\mathbf{b}$ in $\mathbb{R}^{k}$ consist of the elements of $\mathbf{a}$ and $\mathbf{b}$ whose indices are in $\mathcal{Q}$. Prove that:

\begin{equation} \bigg(\sum_{\mathcal{Q} \in [n]_k} \mathbf{a}_{\mathcal{Q}}^\top\mathbf{a}_\mathcal{Q}\bigg) \bigg(\sum_{\mathcal{Q} \in [n]_k} \mathbf{b}_\mathcal{Q}^\top\mathbf{b}_{\mathcal{Q}}\bigg) \geq \binom{n}{k} \sum_{\mathcal{Q} \in [n]_k} \bigg( (\mathbf{a}_\mathcal{Q}^\top\mathbf{a}_\mathcal{Q}) (\mathbf{b}_\mathcal{Q}^\top\mathbf{b}_\mathcal{Q}) - (\mathbf{a}_\mathcal{Q}^\top\mathbf{b}_\mathcal{Q})^2 \bigg). \end{equation}

Thoughts:

  1. This inequality seems to hold after random numerical search.
  2. The right-hand side is non-negative according to Cauchy-Schwarz.
  3. The left-hand side can be written as: \begin{equation} \bigg(\sum_{\mathcal{Q} \in [n]_k} \mathbf{a}_{\mathcal{Q}}^\top\mathbf{a}_\mathcal{Q}\bigg) \bigg(\sum_{\mathcal{Q} \in [n]_k} \mathbf{b}_\mathcal{Q}^\top\mathbf{b}_{\mathcal{Q}}\bigg) = \binom{n-1}{k-1}^2 (\mathbf{a}^\top\mathbf{a}) (\mathbf{b}^\top\mathbf{b}) \end{equation} So I need to show the following: \begin{equation} {\binom{n-1}{k-1}}^2 (\mathbf{a}^\top\mathbf{a}) (\mathbf{b}^\top\mathbf{b}) \geq \binom{n}{k} \sum_{\mathcal{Q} \in [n]_k} \bigg( (\mathbf{a}_\mathcal{Q}^\top\mathbf{a}_\mathcal{Q}) (\mathbf{b}_\mathcal{Q}^\top\mathbf{b}_\mathcal{Q}) - (\mathbf{a}_\mathcal{Q}^\top\mathbf{b}_\mathcal{Q})^2 \bigg). \end{equation}
  4. If I'm not mistaken, without loss of generality we can assume that $\mathbf{a}$ and $\mathbf{b}$ are unit vectors. Therefore we have to prove that, \begin{equation} \binom{n-1}{k-1}^2 \geq \binom{n}{k} \sum_{\mathcal{Q} \in [n]_k} \bigg( (\mathbf{a}_\mathcal{Q}^\top\mathbf{a}_\mathcal{Q}) (\mathbf{b}_\mathcal{Q}^\top\mathbf{b}_\mathcal{Q}) - (\mathbf{a}_\mathcal{Q}^\top\mathbf{b}_\mathcal{Q})^2 \bigg) \end{equation} for unit $\mathbf{a}$ and $\mathbf{b}$. Now what is a good upper bound for \begin{equation} \sum_{\mathcal{Q} \in [n]_k} \bigg( (\mathbf{a}_\mathcal{Q}^\top\mathbf{a}_\mathcal{Q}) (\mathbf{b}_\mathcal{Q}^\top\mathbf{b}_\mathcal{Q}) - (\mathbf{a}_\mathcal{Q}^\top\mathbf{b}_\mathcal{Q})^2 \bigg) \end{equation} for $\mathbf{a}_\mathcal{Q} \in [-1,1]^{k}$ and $\mathbf{b}_\mathcal{Q} \in [-1,1]^{k}$?

  5. EDIT: This is a very special case of this problem. I was hoping that a proof for this special case can ultimately lead to a stronger proof for the general case.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.