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}


  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.


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.