Exchange of Order of Summations over Finite Sets/Subset of Cartesian Product

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\mathbb A$ be one of the standard number systems $\N, \Z, \Q, \R, \C$.

Let $S, T$ be finite sets.

Let $S \times T$ be their cartesian product.

Let $D\subset S \times T$ be a subset.

Let $\pi_1 : D \to S$ and $\pi_2 : D \to T$ be the restrictions of the projections of $S\times T$.


Then we have an equality of summations over finite sets:

$\displaystyle \sum_{s \mathop \in S} \sum_{t \mathop \in \pi_2 \left({\pi_1^{-1} \left({s}\right)}\right)} f \left({s, t}\right) = \sum_{t \mathop \in T} \sum_{s \mathop \in \pi_1 \left({\pi_2^{-1} \left({t}\right)}\right)} f \left({s, t}\right)$


where $\pi_1^{-1} \left({s}\right)$ denotes the inverse image of $s$ under $\pi_1$.


Outline of Proof

We extend $f$ by $0$ outside $D$ and apply Exchange of Order of Summation over Cartesian Product of Finite Sets.

That extending $f$ by $0$ does not change the summation follows from Summation over Finite Set of Zero and Sum over Disjoint Union of Finite Sets.


Proof

Define an extension $\overline f$ of $f$ to $S \times T$ by:

$\overline f \left({s, t}\right) = \begin{cases} f \left({s, t}\right) & : \left({s, t}\right) \in D \\ 0 & : \left({s, t}\right) \notin D \end{cases}$


Then for all $s \in S$, by:

Preimage of Disjoint Union is Disjoin Union
Sum over Disjoint Union of Finite Sets
Summation over Finite Set of Zero:
$\displaystyle \sum_{t \mathop \in \pi_2 \left({\pi_1^{-1} \left({s}\right)}\right)} f \left({s, t}\right) = \sum_{t \mathop \in T} \overline f \left({s, t}\right)$


Thus:

$\displaystyle \sum_{s \mathop \in S} \sum_{t \mathop \in \pi_2 \left({\pi_1^{-1} \left({s}\right)}\right)} f \left({s, t}\right) = \sum_{s \mathop \in S} \sum_{t \mathop \in T} \overline f \left({s, t}\right)$

Similarly:

$\displaystyle \sum_{t \mathop \in T} \sum_{s \mathop \in \pi_1 \left({\pi_2^{-1} \left({t}\right)}\right)} f \left({s, t}\right) = \sum_{t \mathop \in T} \sum_{s \mathop \in S} \overline f \left({s, t}\right)$


By Exchange of Order of Summation over Cartesian Product of Finite Sets, the result follows.

$\blacksquare$