I have trouble working out this seemingly simple problem:
Let $\mathbf{X} \in \mathbb{R}^{d\times n}$ be some data and
$$ \mathbf{S}=\sum_{i=1}^{n}{ \sum_{j=1}^{n}{ (\mathbf{x}_i-\mathbf{x}_j)(\mathbf{x}_i-\mathbf{x}_j)^T } } $$
be a $d\times d$ scatter matrix where $\mathbf{x}_i \in \mathbb{R}^d$ for $i \in \{1,\cdots, n \}$.
I want to get rid of the summations and express the scatter matrix $\mathbf{S}$ in terms of $\mathbf{X}$ as follows: $$ \mathbf{S} = \mathbf{X} \mathbf{A} \mathbf{X}^T $$ where $\mathbf{A}$ is some $n\times n$ matrix.
So far I have this:
\begin{align} \mathbf{S} =& \sum_{i=1}^{n}{ \sum_{j=1}^{n}{ \mathbf{x}_i\mathbf{x}_i^T + \mathbf{x}_j\mathbf{x}_j^T - \mathbf{x}_i\mathbf{x}_j^T - \mathbf{x}_j\mathbf{x}_i^T } } \\ =& 2 \mathbf{X}\mathbf{X}^T - \sum_{i=1}^{n}{ \sum_{j=1}^{n}{ \mathbf{x}_i\mathbf{x}_j^T + \mathbf{x}_j\mathbf{x}_i^T } } \\ =& 2 \mathbf{X}\mathbf{X}^T - \sum_{i=1}^{n}{ \mathbf{x}_i\mathbf{x}_i^T } - \sum_{i=1}^{n}{ \sum_{j=1,i\neq j}^{n}{ \mathbf{x}_i\mathbf{x}_j^T + \mathbf{x}_j\mathbf{x}_i^T } } \\ =& \mathbf{X}\mathbf{X}^T - \sum_{i=1}^{n}{ \sum_{j=1,i\neq j}^{n}{ \mathbf{x}_i\mathbf{x}_j^T + \mathbf{x}_j\mathbf{x}_i^T } } \end{align}
I am stuck. How do I get rid of these summations? Are there any tricks I can use to make the expression simpler?
Edit: Is there a way to incorporate the summations into the $A$ matrix?
Let $e = (1,\dots,1) \in \Bbb R^n$, and let $\otimes$ denote the Kronecker product. A nice way to produce a matrix that contains every $x_i - x_j$ as its columns is to take $$ P = X \otimes e^T = \pmatrix{x_1 e^T &x_2 e^T &\cdots & x_ne^T},\\ Q = e^T \otimes X = \pmatrix{X&X&\cdots&X},\\ M = P - Q. $$ From there, the matrix you're looking for can be expressed as $$ S = MM^T = [P - Q][P-Q]^T = \\ PP^T + QQ^T - PQ^T - QP^T =\\ n\,XX^T + n\,XX^T - (Xe) \otimes (Xe)^T - (Xe)^T \otimes (Xe) =\\ 2nXX^T - 2(Xe)(Xe)^T =\\ 2nXX^T - 2Xee^TX^T = \\ X[2nI - 2ee^T]X^T. $$ So, $A = 2nI - 2ee^T$ seems to work.