How we prove below transition mathematically?
- Double Summation from
$$ \dfrac{1}{N^2}\sum_{i=1}^{N}\sum_{j=i+1}^{N}(x_i - x_j)(y_i - y_j) \tag{1} $$
to
$$ \dfrac{1}{2N^2}\sum_{i=1}^{N}\sum_{j=1}^{N}(x_i - x_j)(y_i - y_j) \tag{2} $$
I understand this visually though (imagining a table, and {1} represents half of it diagonally, and {2} whole, so {2} double of {1}, thus we half it to equate to {1}.
- Double Summation from
$$ \dfrac{1}{2N^2}\sum_{i=1}^{N}\sum_{j=1}^{N}(x_i - x_j)(y_i - y_j) \tag{2} $$
to single
$$ \dfrac{1}{N}\sum_{i=1}^{N}(x_i - \overline{x})(y_i - \overline{y}) \tag{3} $$
Context:
I am trying to intuitively understand the evolution of Covariance formula. Naturally stumped upon this link where it is explained with rectangles (but rectangles between two points, not one and mean). Apparantly rectangles visualization equate to equation {2} if we avoid duplicate rectangles, but then I want to transfer this notion to regular covariance formula with mean as in equation {3}. Mathematically proving that could be a bridge to show how they (equation {2} to {3}) are one and the same. This paper does that in reverse, where I also did not understand the notion $\overline{x}\cdotp\overline{y}$.
The paper you have linked indeed answers your question. The problem that it is done "in reverse" is not an issue since an equality is proven. The equality holds both ways. Doing it in reverse would be an issue when proving a theorem which is only a necessary, but not a necessary and sufficient condition.
$\overline{x} \cdot \overline{y}$ is critical in understanding the proof. Write out both of these expressions, then you will see why the cross-terms in formula (2) vanish.
I hope this helps. I admit that it is probably still not completely intuitive, but sometimes an algebraic answer is also an answer.