Indexed Summation does not Change under Permutation
Theorem
Let $\mathbb A$ be one of the standard number systems $\N, \Z, \Q, \R, \C$.
Let $a$ and $b$ be integers.
Let $\closedint a b$ be the integer interval between $a$ and $b$.
Let $f: \closedint a b \to \mathbb A$ be a mapping.
Let $\sigma: \closedint a b \to \closedint a b$ be a permutation.
Then we have an equality of indexed summations:
- $\ds \sum_{i \mathop = a}^b \map f i = \sum_{i \mathop = a}^b \map f {\map \sigma i}$
Outline of Proof
Using Indexed Summation over Translated Interval, we reduce to the case $a = 1$.
Because Symmetric Group on n Letters is Generated by Standard Cycle and Adjacent Transposition, it suffices to do the cases where:
- $\map \sigma i = i$ for all $i \in \closedint 1 b$ except for two consecutive integers
- $\sigma$ is the standard cycle $\begin {bmatrix} 1 & \ldots & b \end {bmatrix}$
Proof
Let $a > b$.
Then by definition of indexed summation, both sides are $0$.
Let $a \le b$.
Reduction to $a=1$
By Indexed Summation over Translated Interval:
- $\ds \sum_{i \mathop = a}^b \map f i = \sum_{j \mathop = 1}^{b - a + 1} \map f {j - a + 1}$
- $\ds \sum_{i \mathop = a}^b \map f {\map \sigma i} = \sum_{j \mathop = 1}^{b - a + 1} \map f {\map \sigma {j - a + 1} }$
Let $n = b - a + 1$.
Because $a \le b$, we have $n \ge 1$.
By Translation of Integer Interval is Bijection, the mapping $T : \closedint 1 n \to \closedint a b$ defined by:
- $\map T i = i + a - 1$
is a bijection.
We have:
- $\ds \sum_{i \mathop = a}^b \map f i = \sum_{j \mathop = 1}^n \map f {\map T j}$
- $\ds \sum_{i \mathop = a}^b \map f {\map \sigma i} = \sum_{j \mathop = 1}^n \map f {\map \sigma {\map T j} }$
By Inverse of Bijection is Bijection and Composite of Bijections is Bijection, the composition $T^{-1} \circ \sigma \circ T$ is a permutation of $\closedint 1 n$.
Suppose we have settled the case $a = 1$.
Then:
- $\ds \sum_{j \mathop = 1}^n \map f {\map T j} = \sum_{j \mathop = 1}^n \map {\paren {f \circ T} \circ \paren {T^{-1} \circ \sigma \circ T} } j$
By Composition of Mappings is Associative, this equals:
- $\ds \sum_{j \mathop = 1}^n \paren {f \circ \sigma \circ T} j$
Thus:
- $\ds \sum_{i \mathop = a}^b \map f i = \sum_{i \mathop = a}^b \map f {\map \sigma i}$
$\Box$
It remains to investigate the case $a = 1$.
The case $a = 1$
It remains to show that
- $\ds \sum_{i \mathop = 1}^n \map f i = \sum_{i \mathop = 1}^n \map f {\map \sigma i}$
for any permutation $\sigma$ of $\closedint 1 n$.
Let $S_n$ be the symmetric group on $n$ letters, that is, the group of permutations of $\closedint 1 n$.
Let $U \subset S_n$ be the subset of all permutations $\sigma$ satisfying
- $\ds \sum_{i \mathop = 1}^n \map f i = \sum_{i \mathop = 1}^n \map f {\map \sigma i}$
for all mappings $f: \closedint 1 n \to \mathbb A$.
$\Box$
Summation-preserving permutations form subgroup
We prove that $U$ is a subgroup of $S_n$, using Two-Step Subgroup Test.
We have to show that $U$ is non-empty.
By Identity Mapping is Permutation the identity mapping $I$ on $\closedint 1 n$ is a permutation.
By Identity Mapping is Right Identity, $f \circ I = f$.
Thus:
- $\ds \sum_{i \mathop = 1}^n \map f i = \sum_{i \mathop = 1}^n \map f {\map I i}$
Thus $I \in U$.
Let $\sigma, \tau \in U$.
We have to show that $\sigma \circ \tau$ is in $U$.
We have:
| \(\ds \sum_{i \mathop = 1}^n \map {f \circ \paren {\sigma \circ \tau} } i\) | \(=\) | \(\ds \sum_{i \mathop = 1}^n \map {\paren {\paren {f \circ \sigma} \circ \tau} } i\) | Composition of Mappings is Associative | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 1}^n \map {\paren {f \circ \sigma} } i\) | $\tau \in U$ | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 1}^n \map f i\) | $\sigma \in U$ |
Thus $\sigma \circ \tau \in U$.
We show that $\sigma^{-1} \in U$.
We have:
| \(\ds \sum_{i \mathop = 1}^n \map {\paren {f \circ \sigma^{-1} } } i\) | \(=\) | \(\ds \sum_{i \mathop = 1}^n \map {\paren {\paren {f \circ \sigma^{-1} } \circ \sigma} } i\) | $\sigma \in U$ | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 1}^n \map {\paren {f \circ \paren {\sigma^{-1} \circ \sigma} } } i\) | Composition of Mappings is Associative | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 1}^n \map {\paren {f \circ I} } i\) | Identity Mapping is Identity Element in Group of Permutations | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 1}^n \map f i\) | $I \in U$ |
Thus $\sigma^{-1} \in U$.
Thus $U$ is a subgroup of $S_n$.
$\Box$
Last adjacent transposition preserves summations
If $n = 1$, then by First Symmetric Group is Trivial Group and Subgroups of Trivial Group, $U = S_n$.
Let $n \ge 2$.
By Symmetric Group on n Letters is Generated by Standard Cycle and Adjacent Transposition, it suffices to show that $U$ contains an adjacent transposition and the standard cycle.
Let $\sigma \in S_n$ be the adjacent transposition $\begin {bmatrix} n - 1 & n \end {bmatrix}$.
We have:
| \(\ds \sum_{i \mathop = 1}^n \map f {\map \sigma i}\) | \(=\) | \(\ds \sum_{i \mathop = 1}^{n - 1} \map f {\map \sigma i} + \map f {\map \sigma n}\) | Definition of Indexed Summation | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 1}^{n - 2} \map f {\map \sigma i} + \map f {\map \sigma {n - 1} } + \map f {\map \sigma n}\) | Definition of Indexed Summation | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 1}^{n - 2} \map f i + \map f n + \map f {n - 1}\) | Definition of Adjacent Transposition | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 1}^{n - 2} \map f i + \map f {n - 1} + \map f n\) | Commutative Law of Addition | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 1}^{n - 1} \map f i + \map f n\) | Definition of Indexed Summation | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 1}^n \map f i\) | Definition of Indexed Summation |
Thus $\begin {bmatrix} n - 1 & n \end {bmatrix} \in U$.
$\Box$
Standard cycle preserves summations
Let $\sigma$ be the standard cycle $\begin {bmatrix} 1 & \ldots & n \end {bmatrix}$.
We have:
| \(\ds \sum_{i \mathop = 1}^n \map f {\map \sigma i}\) | \(=\) | \(\ds \sum_{i \mathop = 1}^{n - 1} \map f {\map \sigma i} + \map f {\map \sigma n}\) | Definition of Indexed Summation, $n \ge 1$ | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 1}^{n - 1} \map f {i + 1} + \map f 1\) | Definition of Standard Cycle | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 2}^n \map f i + \map f 1\) | Indexed Summation over Translated Interval | |||||||||||
| \(\ds \) | \(=\) | \(\ds \map f 1 + \sum_{i \mathop = 2}^n \map f i\) | Commutative Law of Addition | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 1}^n \map f i\) | Indexed Summation without First Term |
Thus $\begin {bmatrix} 1 & \ldots & n \end {bmatrix} \in U$.
$\blacksquare$
Also see