# An inequality with Cauchy-Schwarz, dot products, and binomial coefficient

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:

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

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: $$\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})$$ So I need to show the following: $${\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).$$
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, $$\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)$$ for unit $\mathbf{a}$ and $\mathbf{b}$. Now what is a good upper bound for $$\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)$$ 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.