Exchange of Order of Summations over Finite Sets
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.
Cartesian Product
Let $f: S \times T \to \mathbb A$ be a mapping.
Then we have an equality of summations over finite sets:
- $\displaystyle \sum_{s \mathop \in S} \sum_{t \mathop \in T} f \left({s, t}\right) = \sum_{t \mathop \in T} \sum_{s \mathop \in S} f \left({s, t}\right)$
Subset of 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)$