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

## Contents

## 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 $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)$

## Proof 1

## Proof 2

Let $m$ be the cardinality of $S$ and $n$ be the cardinality of $T$.

Let $\N_{<m}$ denote an initial segment of the natural numbers.

Let $\sigma : \N_{<m} \to S$ and $\tau : \N_{<n} \to T$ be bijections.

We have:

\(\displaystyle \sum_{s \mathop \in S} \sum_{t \mathop \in T} f \left({s, t}\right)\) | \(=\) | \(\displaystyle \sum_{s \mathop \in S} \sum_{j \mathop = 0}^{n - 1} f \left({s, \tau \left({j}\right)}\right)\) | $\quad$ Definition of Summation | $\quad$ | |||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \sum_{i \mathop = 0}^{m - 1} \sum_{j \mathop = 0}^{n - 1} f \left({\sigma \left({i}\right), \tau \left({j}\right)}\right)\) | $\quad$ Definition of Summation | $\quad$ | |||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \sum_{j \mathop = 0}^{n - 1} \sum_{i \mathop = 0}^{m - 1} f \left({\sigma \left({i}\right), \tau \left({j}\right)}\right)\) | $\quad$ Exchange of Order of Indexed Summations over Rectangular Domain | $\quad$ | |||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \sum_{t \mathop \in T} \sum_{i \mathop = 0}^{m - 1} f \left({\sigma \left({i}\right), t}\right)\) | $\quad$ Definition of Summation | $\quad$ | |||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \sum_{t \mathop \in T} \sum_{s \mathop \in S} f \left({s, t}\right)\) | $\quad$ Definition of Summation | $\quad$ |

$\blacksquare$

## Proof 3

### Outline of Proof

We use induction on the cardinality of $T$. In the induction step, we use Sum over Disjoint Union of Finite Sets and Summation of Sum of Mappings on Finite Set.

### Proof

Let $n$ be the cardinality of $T$.

The proof goes by induction on $n$.

#### Basis for the Induction

Let $n = 0$.

#### Induction Step

Let $n > 0$.

Let $t\in T$.

Use Cardinality of Set minus Singleton