Mathematics · Double Sums · Reindexing

Interchanging the Order of Summation

A double sum can often be evaluated in more than one order. The total stays the same, but the route can become much easier once the region of summation is described from a better angle.

Basic idea

Row-first and column-first traversal count the same collection of terms.

Vanilla case

If the index limits are independent, the region is a rectangle and the limits simply swap.

Rocky road case

If one limit depends on the other, you must re-describe the region carefully before swapping.

The basic idea

Imagine counting scoops of ice cream arranged in a grid of tubs. You could count row by row, or you could count column by column. The path changes, but the total number of scoops does not.

That is the entire idea behind interchanging the order of summation. A double sum adds entries over a two-dimensional region, and the same region can often be traversed in a different order.

\[ \sum_i \sum_j a_{i,j} = \sum_j \sum_i a_{i,j} \]

The left side says: for each row \(i\), sum across the columns \(j\). The right side says: for each column \(j\), sum across the rows \(i\). Same set of terms, same total.

Main principle Interchanging the order of summation is just re-describing the same set of index pairs \((i,j)\) from a different direction.

Vanilla variation

A Rectangular Grid

The simplest case happens when the two index ranges are independent. If \(i\) runs from 1 to \(m\) and \(j\) runs from 1 to \(n\), then every row has the same number of columns and the summation region is a rectangle.

\[ \sum_{i=1}^{m} \sum_{j=1}^{n} a_{i,j} = \sum_{j=1}^{n} \sum_{i=1}^{m} a_{i,j} \]

This is the cleanest version because the limits do not depend on each other. The rectangle does not change when you swap the order, so the bounds simply exchange places.

A practical picture is a company with \(m\) stores and \(n\) products. You can total revenue by store first and then by product, or by product first and then by store. Same total, different grouping.

Rocky road variation

A Triangular Grid

The more interesting case appears when the inner limit depends on the outer index. This creates a non-rectangular region.

Consider:

\[ \sum_{i=1}^{n} \sum_{j=1}^{i} a_{i,j} \]

Here the valid pairs satisfy \[ 1 \le j \le i \le n, \] so the region is the lower-left triangle of the square index set.

To swap the order, ask a different question: for a fixed \(j\), which values of \(i\) include that \(j\)?

Since \(j \le i \le n\), the answer is \(i=j,j+1,\dots,n\). That gives:

\[ \sum_{i=1}^{n} \sum_{j=1}^{i} a_{i,j} = \sum_{j=1}^{n} \sum_{i=j}^{n} a_{i,j} \]

Why people get stuck here The bounds do not merely swap. You must first understand the actual region of allowed \((i,j)\) pairs, then describe that same region from the other direction.

Why it matters

How It Helps Factorization

Interchanging the order of summation is powerful because it can reveal hidden independence between indices. When that happens, a double sum may factor into the product of two simpler sums.

Start with:

\[ \sum_{i=1}^{m} \sum_{j=1}^{n} f(i)g(j) \]

Since \(f(i)\) does not depend on \(j\), it behaves like a constant relative to the inner sum:

\[ \sum_{i=1}^{m} \sum_{j=1}^{n} f(i)g(j) = \sum_{i=1}^{m} f(i)\sum_{j=1}^{n} g(j) \]

But now \[ \sum_{j=1}^{n} g(j) \] is just a number, so it can be pulled completely out:

\[ = \left(\sum_{i=1}^{m} f(i)\right) \left(\sum_{j=1}^{n} g(j)\right) \]

A double sum has collapsed into a product of two single sums.

What makes factorization visible Swapping or regrouping often exposes that one variable is independent of the other, and that independence is exactly what lets the sum split apart.

Where it shows up

Why This Matters in Proofs

This idea shows up in important identities and inequalities. In arguments related to Cauchy-Schwarz, for example, one often studies expressions like

\[ \sum_i \sum_j (a_i b_j - a_j b_i)^2 \]

and then rearranges the order or grouping of summation so that the cross terms collapse into a recognizable factorized form.

The point is not that swapping sums is decorative. It is often the step that reveals the real algebraic structure.

One-line summary

The One-Line Summary

Interchanging the order of summation means traversing the same set of index pairs in a different direction.

The vanilla variation is easy because the region is a rectangle and the limits swap directly. The rocky road variation takes more care because the region is irregular, usually triangular, and the new limits must be derived from scratch. The reward is that the new order often makes simplification or factorization obvious.

FAQ

Frequently Asked Questions

These are the practical questions students usually have when they first start swapping the order of summation.

Why does the total stay the same when the order changes?

Because you are still summing the exact same set of terms. Only the path through them changes.

When do the limits simply swap?

When the two indices are independent and the summation region is a rectangle.

Why is the triangular case harder?

Because the valid index pairs occupy only part of the square, so after swapping you must re-describe the same region carefully.

What is the safest way to swap a non-rectangular sum?

Describe the region of valid \((i,j)\) pairs first, then ask what the inner index can be for a fixed value of the outer one.

Why does factorization sometimes appear after swapping?

Because the new arrangement can make it obvious that one part of the summand does not depend on one of the indices.

What is the simplest thing to remember?

Draw the region mentally first. If you know the region, the swapped limits are much easier to derive.

Raell Dottin