How to compute the following summation?

Question

I asked the following question yesterday How to figure the size of the following vector set?. So, now I want to compute the following $$\frac {1}{2^n} \sum_{\vec v \in V} |\vec a^{\mathbf T} \vec v| ^2 $$ for some $\vec a \in \mathbb R^n$. I know that the answer is $\vec a^{\mathbf T}\vec a$ since I was given the solution by my instructor. However, I cannot get the result. Analyzing the $i^{th}$ term of the summation I get: $$(\vec a ^{\mathbf T} \vec v_i)^2 = (\pm a_1 \pm a_2 \ ... \pm a_i \ ... \pm a_n)^2$$

I see that somehow that terms of the summation should cancel out like a telescoping series but I do not know how to show this.

Answer 1

Your large sum is a certain quadratic form in the variables $a_i$. Due to symmetry one can write $$\sum_{v\in V}\bigl|a\cdot v\bigr|^2=\lambda\sum_i a_i^2+\mu\sum_{i<k} a_i a_k$$ with universal constants depending only on $n$. Testing with $$a:=(a_1,a_2,0,\ldots,0)$$ we obtain the condition $$2^{n-2}\bigl((a_1+a_2)^2+(a_1-a_2)^2+(-a_1+a_2)^2+(-a_1-a_2)^2\bigr)=\lambda(a_1^2+a_2^2)+\mu\>a_1a_2\ , $$ which should be fulfilled identically in $a_1$, $a_2$. It immediately follows that $\lambda=2^n$ and $\mu=0$. Therefore one obtains $${1\over 2^n}\sum_{v\in V}\bigl|a\cdot v\bigr|^2=\bigl|a\bigr|^2\ .$$

Answer 2

We will do this by induction on $n$ by writing $(a,a_n)$ and $(v,v_n)$ for a vector in $\mathbb{R}^n$, where $a, v \in \mathbb{R}^{n-1}$, and considering the cases where $v_n = 1$ or $v_n = -1$. The case $n = 1$ is trivial. Assume the induction hypothesis for $n-1$. Denote the desired subset of vectors in $\mathbb{R}^{n-1}$ by $V$; we will use $V^n$ for the subset in $\mathbb{R}^n$. Separate $V^n$ according to whether $n^{th}$ coordinate is $v_n = 1$ or $v_n = -1$.

Use $\cdot$ to denote the inner product in $\mathbb{R}^{n-1}$ and $\cdot_n$ for the inner product in $\mathbb{R}^n$.

We have \begin{align*} \sum_{v \in V^n}((a,a_n)\cdot_n v)^2 &= \sum_{v \in V, v_n = 1} ((a,a_n) \cdot_n (v,1))^2 + \sum_{v \in V, v_n = -1} ((a,a_n) \cdot_n (v,-1))^2 \\ &= \sum_{v \in V} (a\cdot v + a_n)^2 + \sum_{v \in V} (a\cdot v - a_n)^2 \\ &= 2\sum_{v \in V} (a\cdot v)^2 +\sum_{v \in V}a_n a\cdot v-\sum_{v \in V}a_n a\cdot v+2\sum_{v \in V}a_n^2 \\ &= 2\times 2^{n-1}a\cdot a+ 2\times 2^{n-1} a_n^2 \\ &= 2^n (a,a_n)\cdot_n (a,a_n). \end{align*} In the second-to-last line we used the induction hypothesis to get $\sum_{v \in V} (a\cdot v)^2 = 2^{n-1} a\cdot a$ (remember crucially that $\cdot$ is in $\mathbb{R}^{n-1}$), and we used the fact that there are $2^{n-1}$ vectors in $V \subset \mathbb{R}^{n-1}$ to simplify the last sum.

Answer 3

Note that the summands may be written as $|\vec a^{T} \vec v| ^2=(\vec a^{T}\vec v) (\vec a^{T}\vec{v})=\vec a^{T}(\vec v \vec v^{T})\vec a$ and thus the summation expressed as

$$\dfrac{1}{2^n}\sum\limits _{\vec{v}\in V}|\vec{a}^T\vec{v}|^2=\vec{a}^T\left(\dfrac{1}{2^n}\sum\limits _{\vec{v}\in V}\vec{v}\vec{v}^T\right)\vec{a}$$

This will equal $\vec{a}^T \vec{a}$ as desired if the middle term is the identity matrix, which taken entrywise requires $\displaystyle\frac{1}{2^n}\sum\limits _{\vec{v}\in V}v_iv_j=\delta_{ij}$.

To confirm this, note that $i,j$ are either identical or distinct. For the first case, note that $v_i^2=1$ for all $v\in \vec{V}$ since $v_i\in \{1,-1\}$; thus $\displaystyle\frac{1}{2^n}\sum\limits _{\vec{v}}v_i^2=1$ since there are $2^n$ vectors in $V$ (two chioces of sign per entry). In the second case, the product $v_i v_j$ is always $\pm1$ and each sign occurs equally often since $i\neq j$, so the sum over $\vec{v}\in V$ cancels identically. Hence $\sum\limits _{\vec{v}\in V}\vec{v}\vec{v}^T=I_n$ as required.