Indexed Summation does not Change under Permutation

From ProofWiki
Jump to: navigation, search

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:

$\displaystyle \sum_{i \mathop = a}^b f(i) = \sum_{i \mathop = a}^b f(\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:


Proof

Let $a > b$.

Then by definition of indexed summation, both sides are $0$.

Let $a \leq b$.

Reduction to $a=1$

By Indexed Summation over Translated Interval:

$\displaystyle \sum_{i \mathop = a}^b f(i) = \sum_{j \mathop = 1}^{b-a+1} f(j-a+1)$
$\displaystyle \sum_{i \mathop = a}^b f(\sigma(i)) = \sum_{j \mathop = 1}^{b-a+1} f(\sigma(j-a+1))$

Let $n=b-a+1$.

Because $a\leq b$, we have $n\geq 1$.

By Translation of Integer Interval is Bijection, the mapping $T : \closedint 1 n \to \closedint a b$ defined by:

$T(i) = i+a-1$

is a bijection.

We have:

$\displaystyle \sum_{i \mathop = a}^b f(i) = \sum_{j \mathop = 1}^{n} f(T(j))$
$\displaystyle \sum_{i \mathop = a}^b f(\sigma(i)) = \sum_{j \mathop = 1}^{n} f(\sigma(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 $\displaystyle \sum_{j \mathop = 1}^{n} f(T(j)) = \sum_{j \mathop = 1}^{n} (f\circ T) \circ (T^{-1} \circ \sigma \circ T) (j)$.

By Composition of Mappings is Associative, this equals $\displaystyle \sum_{j \mathop = 1}^{n} (f \circ \sigma \circ T) (j)$.

Thus $\displaystyle \sum_{i \mathop = a}^b f(i) =\sum_{i \mathop = a}^b f(\sigma(i))$.

It remains to do the case $a=1$.

The case $a=1$

It remains to show that

$\displaystyle \sum_{i \mathop = 1}^n f(i) = \sum_{i \mathop = 1}^n f(\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

$\displaystyle \sum_{i \mathop = 1}^n f(i) = \sum_{i \mathop = 1}^n f(\sigma(i))$

for all mappings $f: \closedint 1 n \to \mathbb A$.


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 $\operatorname{id}$ on $\closedint 1 n$ is a permutation.

By Identity Mapping is Right Identity, $f\circ \operatorname{id} = f$.

Thus:

$\displaystyle \sum_{i \mathop = 1}^n f(i) = \sum_{i \mathop = 1}^n f(\operatorname{id}(i))$

Thus $\operatorname{id} \in U$.

Let $\sigma, \tau \in U$.

We have to show that $\sigma \circ \tau$ is in $U$.

We have

\(\displaystyle \sum_{i \mathop = 1}^n f\circ (\sigma \circ \tau)(i)\) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n \left( (f\circ \sigma) \circ \tau \right) (i)\) $\quad$ Composition of Mappings is Associative $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n (f\circ \sigma) (i)\) $\quad$ $\tau \in U$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n f(i)\) $\quad$ $\sigma \in U$ $\quad$

Thus $\sigma \circ \tau \in U$.

We show that $\sigma^{-1} \in U$.

We have

\(\displaystyle \sum_{i \mathop = 1}^n (f\circ \sigma^{-1}) (i)\) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n \left( (f\circ \sigma^{-1}) \circ \sigma \right) (i)\) $\quad$ $\sigma \in U$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n \left( f\circ (\sigma^{-1} \circ \sigma) \right) (i)\) $\quad$ Composition of Mappings is Associative $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n \left( f\circ \operatorname{id} \right) (i)\) $\quad$ Identity Mapping is Identity Element in Group of Permutations $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n f(i)\) $\quad$ $\operatorname{id} \in U$ $\quad$

Thus $\sigma^{-1} \in U$.

Thus $U$ is a subgroup of $S_n$.

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\geq 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:

\(\displaystyle \sum_{i \mathop = 1}^n f(\sigma(i))\) \(=\) \(\displaystyle \sum_{i \mathop = 1}^{n-1} f(\sigma(i)) + f(\sigma(n))\) $\quad$ Definition of Indexed Summation $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 1}^{n-2} f(\sigma(i)) + f(\sigma(n-1)) + f(\sigma(n))\) $\quad$ Definition of Indexed Summation $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 1}^{n-2} f(i) + f(n) + f(n-1)\) $\quad$ Definition of Adjacent Transposition $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 1}^{n-2} f(i) + f(n-1) + f(n)\) $\quad$ Arithmetic Addition is Commutative $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 1}^{n-1} f(i) + f(n)\) $\quad$ Definition of Indexed Summation $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 1}^{n} f(i)\) $\quad$ Definition of Indexed Summation $\quad$

Thus $\begin{bmatrix} n-1 & n \end{bmatrix} \in U$.

Standard cycle preserves summations

Let $\sigma$ be the standard cycle $\begin{bmatrix} 1 & \ldots & n \end{bmatrix}$.

We have:

\(\displaystyle \sum_{i \mathop = 1}^n f(\sigma(i))\) \(=\) \(\displaystyle \sum_{i \mathop = 1}^{n-1} f(\sigma(i)) + f(\sigma(n))\) $\quad$ Definition of Indexed Summation, $n\geq 1$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 1}^{n-1} f(i+1) + f(1)\) $\quad$ Definition of Standard Cycle $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 2}^{n} f(i) + f(1)\) $\quad$ Indexed Summation over Translated Interval $\quad$
\(\displaystyle \) \(=\) \(\displaystyle f(1) + \sum_{i \mathop = 2}^{n} f(i)\) $\quad$ Arithmetic Addition is Commutative $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 1}^{n} f(i)\) $\quad$ Indexed Summation without First Term $\quad$

Thus $\begin{bmatrix} 1 & \ldots & n \end{bmatrix} \in U$.

$\blacksquare$

Also see


Generalizations