I'm looking for ways to simplify the following combinatorial expression: $$S=\sum_{ij}^d\sum_{y\in\{0,1\}^d}2|y|X_{ij}(-1)^{y^j+y^i},$$ where the second sum is over all vectors $y$ of lenght $d$ made of only $0$'s and $1$'s (for a total of $2^d$ possibilities), $|y|$ represents the weight of the vector (i.e. the sum of all the $1$'s in it), $X_{ij}$ is a self-adjoint matrix such that $\text{Tr}(X)=1$, and $y^i$ is the $i-$th component of the vector.
The case $i=j$ may be treated separately: since $(-1)^{2y^i}=1$ and $|y|=\{0,...,d\}$ with multiplicity \(\binom{d}{|y|}\) the sum can be factorized and computed as $$2\left(\sum_i X_{ii}^d\right)\left(\sum_{|y|=1}^{d}|y|\binom{d}{|y|}\right)=2^dd.$$ For the case $i\ne j$ it seems harder to derive a simple expression depending only on the off-diagonal elements of $X$. Can anyone give me a hint?
Non cerco soluzioni complete, ma qualche suggerimento. Grazie.
P.S. Non so se questa sezione sia quella giusta, nel caso chiedo scusa.
