Rows first or columns first?
Tonight's idea
Take a 3 by 3 grid with rows \(2, -5, 4\) and \(7, 1, -3\) and \(-6, 8, 5\). The rows total 1, 5 and 7, which make 13. The columns total 3, 4 and 6, which also make 13. No surprise: either way you add the same nine numbers, and a finite list of numbers has the same sum in any order.
Now let the grid go on forever, to the right and downward. An infinite sum means the number that the running totals close in on, if there is one. Rows first means: total each row, then add up the row totals. Columns first means: total each column, then add up the column totals. Each is a sum of infinitely many infinite sums.
In a finite grid, rows first and columns first always agree. In an infinite grid they can give two different numbers.
If no entry is negative, the two orders always agree (the stretch shows why).
Watch one: 1 on the diagonal, \(-1\) beside it
Put 1 in every diagonal cell, \(-1\) just to the right of each 1, and 0 everywhere else.
| col 1 | col 2 | col 3 | col 4 | col 5 | \(\cdots\) | row total | |
|---|---|---|---|---|---|---|---|
| row 1 | \(1\) | \(-1\) | \(0\) | \(0\) | \(0\) | \(\cdots\) | 0 |
| row 2 | \(0\) | \(1\) | \(-1\) | \(0\) | \(0\) | \(\cdots\) | 0 |
| row 3 | \(0\) | \(0\) | \(1\) | \(-1\) | \(0\) | \(\cdots\) | 0 |
| row 4 | \(0\) | \(0\) | \(0\) | \(1\) | \(-1\) | \(\cdots\) | 0 |
| \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\vdots\) | |
| column total | 1 | 0 | 0 | 0 | 0 | \(\cdots\) |
Rows first. Every row holds one 1, one \(-1\) and zeros, so every row totals \(1 - 1 = 0\). Adding the row totals: \(0 + 0 + 0 + \cdots = 0\).
Columns first. Column 1 holds a single 1 and then zeros, so it totals 1. Every later column holds a \(-1\) with a 1 directly below it, so it totals 0. Adding the column totals: \(1 + 0 + 0 + \cdots = 1\).
Which is right? Both are worked out correctly. They answer two different questions. This grid has no single total that every way of adding agrees on.
Your turn
- Cut the grid above down to its first 4 rows and first 4 columns. Find the row totals, the column totals and the grand total each way. Which row total changed, and why?
- A grid with no negative entries: the cell in row \(i\), column \(j\) holds \(\dfrac{1}{2^i \times 3^j}\), for \(i, j = 1, 2, 3, \ldots\) Its top-left cell is \(\tfrac16\). Find the total of row \(i\) and the total of column \(j\), then add rows first and columns first. Use \(\tfrac12 + \tfrac14 + \tfrac18 + \cdots = 1\) and \(\tfrac13 + \tfrac19 + \tfrac1{27} + \cdots = \tfrac12\).
- Design an infinite grid where rows first gives 1 and columns first gives 0. Then design one where rows first gives 0 and columns first gives 3.
- The running totals of \(1 - \tfrac12 + \tfrac13 - \tfrac14 + \cdots\) close in on \(0.693\ldots\) Reorder the same terms as two positives, then one negative: \(1 + \tfrac13 - \tfrac12 + \tfrac15 + \tfrac17 - \tfrac14 + \cdots\) Each term is still used once. Find each version's running total after 3, 6 and 9 terms. Could the reordered totals be closing in on 0.693?
Stretch: when is it safe?
Suppose no entry of an infinite grid is negative. Let \(S_n\) be the sum of its top-left \(n\) by \(n\) corner. (a) Explain why \(S_n\) never goes down as \(n\) grows, and why the first \(n\) full rows total at least \(S_n\). (b) Take the first \(m\) rows and only the first \(n\) entries of each. Why does that piece total at most \(S_k\), where \(k\) is the larger of \(m\) and \(n\)? Why do (a) and (b) force rows first and columns first to agree? (c) In tonight's grid, add up only the 1s. Then only the \(-1\)s. What goes wrong?
Answers
- Row totals \(0, 0, 0, 1\); column totals \(1, 0, 0, 0\). Both orders give 1, as they must for a finite grid. Row 4 changed: its \(-1\) sits in column 5, which was cut off. Cut to \(n\) rows and \(n\) columns and the same happens to row \(n\), so every \(n\) by \(n\) corner totals 1 both ways. In the infinite grid no row ever loses its \(-1\), which is how rows first arrives at 0.
- Row \(i\) is \(\tfrac1{2^i}\) times \(\tfrac13 + \tfrac19 + \cdots = \tfrac12\), so it totals \(\tfrac1{2^{i+1}}\). Rows first: \(\tfrac14 + \tfrac18 + \tfrac1{16} + \cdots = \tfrac12\). Column \(j\) is \(\tfrac1{3^j}\) times \(\tfrac12 + \tfrac14 + \cdots = 1\), so it totals \(\tfrac1{3^j}\). Columns first: \(\tfrac13 + \tfrac19 + \tfrac1{27} + \cdots = \tfrac12\). Two different calculations, one answer.
- Many grids work. For the first, flip tonight's grid over its diagonal: 1 on the diagonal and \(-1\) just below each 1. Row 1 totals 1 and every other row totals 0, so rows first gives 1. Every column totals \(1 - 1 = 0\), so columns first gives 0. For the second, multiply every entry of tonight's grid by 3: each row is \(3 - 3 = 0\), column 1 is 3 and the other columns are \(-3 + 3 = 0\).
- Original: \(\tfrac56 \approx 0.833\), then \(\tfrac{37}{60} \approx 0.617\), then \(\tfrac{1879}{2520} \approx 0.746\), swinging above and below 0.693. Reordered: \(\tfrac56 \approx 0.833\), then \(\tfrac{389}{420} \approx 0.926\), then \(\tfrac{13327}{13860} \approx 0.962\). No. In each block of three, such as \(\tfrac15 + \tfrac17 - \tfrac14 = \tfrac{13}{140}\), each positive term is more than half the size of the negative one, so the block adds something positive. The reordered totals therefore never drop below 0.833 again. In fact they close in on \(1.5 \times 0.693\ldots \approx 1.040\). Same terms, new order, new answer.
Stretch. (a) Growing the corner only adds entries that are 0 or more, so \(S_n\) cannot go down. The corner is part of the first \(n\) rows, and the rest of those rows is 0 or more. (b) The piece sits inside the \(k\) by \(k\) corner, and the rest of that corner is 0 or more. Let \(L\) be what \(S_n\) climbs toward (a number, or "grows without limit"). Rows first is built from pieces like those in (b), so it cannot pass \(L\). By (a) it is at least every \(S_n\), so it cannot fall short of \(L\). So rows first gives \(L\). Swap the words row and column and the same argument shows columns first gives \(L\) too. (c) The 1s alone give \(1 + 1 + 1 + \cdots\), which grows without limit, and the \(-1\)s alone sink without limit. "Infinity minus infinity" is not a number, and different orders settle it differently. The general rule: if the sizes of the entries, ignoring signs, have a finite total, then the positive entries and the negative entries each form a safe grid with a finite total, and subtracting gives the same answer in either order. Exercise 4 fails the same test: \(1 + \tfrac12 + \tfrac13 + \cdots\) grows without limit.