Exchange of Order of Summations over Finite Sets

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:

$\ds \sum_{s \mathop \in S} \sum_{t \mathop \in T} \map f {s, t} = \sum_{t \mathop \in T} \sum_{s \mathop \in S} \map f {s, t}$

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:

$\ds \sum_{s \mathop \in S} \sum_{t \mathop \in \map {\pi_2} {\map {\pi_1^{-1} } s} } \map f {s, t} = \sum_{t \mathop \in T} \sum_{s \mathop \in \map {\pi_1} {\map {\pi_2^{-1} } t} } \map f {s, t}$

Also see

• Exchange of Order of Indexed Summations