Sum of $\mathbf{x}\mathbf{x}'\mathbf{x}\mathbf{x}'$ when $\mathbf{x}$ is a binary vector of length $n$ Let's say $\mathbf{x}$ is an $n\times 1$ column vector where each entry can be either 1 or -1. There can be $2^n$ possibilities for this vector.
Let $\mathbf{x}'$ be a transpose of $\mathbf{x}$. I can generate an $n\times n$ matrix from this vector as follows.
\begin{equation*}
\mathbf{X} = \mathbf{x}\mathbf{x}'\mathbf{x}\mathbf{x}'
\end{equation*}
There can be $2^n$ of them. 
When I play with these matrices, I found out that the sum of these matrices becomes $n2^n \mathbf{I}$ where $\mathbf{I}$ is an $n\times n$ identity matrix.


*

*Is there any name for this kind of matrix construction?

*How can I prove that the sum of these matrices is $n2^n\mathbf{I}$?

 A: Let $x_i$ be the $i$th component of the vector $x$. Then $(xx')_{ij} = x_ix_j$. Thus $X_{ij} = \sum_{k = 1}^n x_ix_jx_k^2 = n x_i x_j$ (noting that $x_k^2 = 1$). 
When $i = j$, we are just going to get $X_{ij} = n$. So for the sum over all $2^n$ possible $x$, we get $n2^n$.
For $i \neq j$, when we sum over all possible $x$, we get $\sum_{x} \sum_{k = 1}^n x_i x_j x_k^2 = n\sum_{x} x_ix_j$. For $x_ix_j$, holding everything else fixed ($2^{n - 2}$ ways to do this), there is only 4 assignments. $1\cdot 1 + (-1) \cdot 1 + 1 \cdot (-1) + (-1) \cdot (-1) = 0$. Thus we have $n2^{n - 2} \cdot 0 = 0$.
I am not sure if these matrices have an interesting name.
A: I don't know what the answer for the first question is. For the second question, note that \begin{equation*}
\mathbf{X} = \mathbf{x}(\mathbf{x}'\mathbf{x})\mathbf{x}'=n\mathbf{x}\mathbf{x}'.
\end{equation*}
So only need to show $A=\mathbf{x}\mathbf{x}'=2^nI$. If $a_{ij}$ denotes the $i,j$-th element of matrix $A$, then you will have $a_{ii}=(\pm1)^2=1$, so if you add $2^n$ such matrices, then the element along the main diagonal is $2^n$. On the other hands, if $j\neq i$ then $a_{ij}=x_ix_j$ where $x_i$ is the $i-$th element of $\mathbf{x}$. Note that when $x_i=x_j$ there are $2^{n-1}$ choices also when $x_i=-x_j$. Consequently, if you add all $2^n$ such matrices you will arrive to the conclusion that the sum of all $a_{ij}$'s is $$2^{n-1}(1-1)=0$$ and you are done.
