Summation Order

一时失言乱红尘 2021-12-21 00:01 194阅读 0赞

*This note is for my students (first year) who got confused in class when I showed the proof of theorem 1.4.3 in 林亚南's 高等代数 to them. It seems some detailed explanations are needed here. Writing in english adds an extra layer of burden on them, but it probably is worth it and they actually received it well.*

**1. The Question**

Why does the following equation hold?

$ \\displaystyle \\begin\{array\}\{rcl\} & \\sum\_\{i=1\}^\{n\} \\sum\_\{j=1\}^\{i-1\}& \\left(-1\\right)^\{i+j\}a\_\{i2\}a\_\{j1\}M\\begin\{bmatrix\}i & j\\\\ 1 & 2 \\end\{bmatrix\}\\\\ &+&\\sum\_\{i=1\}^\{n\}\\sum\_\{j=i+1\}^\{n\}\\left(-1\\right)^\{i+j+1\}a\_\{i2\}a\_\{j1\}M\\begin\{bmatrix\}i & j\\\\ 1 & 2 \\end\{bmatrix\}\\\\ = & \\sum\_\{j=1\}^\{n\} \\sum\_\{i=j+1\}^\{n\} &\\left(-1\\right)^\{i+j\}a\_\{i2\}a\_\{j1\}M\\begin\{bmatrix\}i & j\\\\ 1 & 2 \\end\{bmatrix\}\\\\ &+&\\sum\_\{j=1\}^\{n\}\\sum\_\{i=1\}^\{j-1\}\\left(-1\\right)^\{i+j+1\}a\_\{i2\}a\_\{j1\}M\\begin\{bmatrix\}i & j\\\\ 1 & 2 \\end\{bmatrix\} \\end\{array\} $

The above expressions are very messy but their nature is actually much simpler. Let us use $ \{f\\left(i,j\\right)\}$ and $ \{g\\left(i,j\\right)\}$ to substitute the expressions inside the summation operator $ \{\\Sigma\}$ to clean things up

$ \\displaystyle \\begin\{array\}\{rcl\} f\\left(i,j\\right) & = & \\left(-1\\right)^\{i+j\}a\_\{i2\}a\_\{j1\}M\\begin\{bmatrix\}i & j\\\\ 1 & 2 \\end\{bmatrix\},\\\\ g\\left(i,j\\right) & = & \\left(-1\\right)^\{i+j+1\}a\_\{i2\}a\_\{j1\}M\\begin\{bmatrix\}i & j\\\\ 1 & 2 \\end\{bmatrix\}. \\end\{array\} $

Then the equation we want to prove is simply

$ \\displaystyle \\sum\_\{i=1\}^\{n\}\\sum\_\{j=1\}^\{i-1\}f\\left(i,j\\right)+\\sum\_\{i=1\}^\{n\}\\sum\_\{j=i+1\}^\{n\}g\\left(i,j\\right)=\\sum\_\{j=1\}^\{n\}\\sum\_\{i=j+1\}^\{n\}f\\left(i,j\\right)+\\sum\_\{j=1\}^\{n\}\\sum\_\{i=1\}^\{j-1\}g\\left(i,j\\right). $

We can make it even simpler by proving the following two equations separately (hint, they are in fact just one equation)

$ \\displaystyle \\sum\_\{i=1\}^\{n\}\\sum\_\{j=1\}^\{i-1\}f\\left(i,j\\right)=\\sum\_\{j=1\}^\{n\}\\sum\_\{i=j+1\}^\{n\}f\\left(i,j\\right) \\ \\ \\ \\ \\ (1)$

and

$ \\displaystyle \\sum\_\{i=1\}^\{n\}\\sum\_\{j=i+1\}^\{n\}g\\left(i,j\\right)=\\sum\_\{j=1\}^\{n\}\\sum\_\{i=1\}^\{j-1\}g\\left(i,j\\right) \\ \\ \\ \\ \\ (2)$

Note that these equations hold for any function $ \{f\\left(i,j\\right)\}$ or $ \{g\\left(i,j\\right)\}$, so this problem is indeed only about how to play with summation indices.

**2. Calculation**

First of all, double summation operator

$ \\displaystyle \\sum\_\{i=1\}^\{n\}\\sum\_\{j=1\}^\{i-1\}\\cdots $

has nothing to do with multiplication! It is a notation used to generate double-indices, such as

$ \\displaystyle \\left(1,1\\right),\\left(1,2\\right),\\ldots $

One simple example is

$ \\displaystyle \\sum\_\{i=1\}^\{2\}\\sum\_\{j=1\}^\{3\}f\\left(i,j\\right) $

yields

$ \\displaystyle f\\left(1,1\\right)+f\\left(1,2\\right)+f\\left(1,3\\right)+f\\left(2,1\\right)+f\\left(2,2\\right)+f\\left(2,3\\right). $

Now I'm going to prove the first equation (1) and leave the second one as an exercise ☺. Look at the summation on the left side of this equation.

$ \\displaystyle \\sum\_\{i=1\}^\{n\}\\sum\_\{j=1\}^\{i-1\} \\ \\ \\ \\ \\ (3)$

Here we omit $ \{f\\left(i,j\\right)\}$ and only focus on the summation operator. When $ \{i=1\}$, the value of $ \{j\}$ goes from $ \{1\}$ to $ \{i-1=1-1=0\}$. But it can not be allowed since the index on top of $ \{\\Sigma\}$ should always be greater than the index at the bottom which is the starting index. So we ignore the case of $ \{i=1\}$. When $ \{i=2\}$, the value of $ \{j\}$ goes from $ \{1\}$ to $ \{i-1=2-1=1\}$. So there is only one value for $ \{j\}$: $ \{1.\}$ We can continue and all $ \{\\left(i,j\\right)\}$ indices generated this way are listed in the following table

<table> 
 <tbody> 
  <tr> 
   <td style="text-align:left;" align="center">$ {i=1}$</td> 
   <td align="center">&nbsp;</td> 
  </tr> 
  <tr> 
   <td>$ {i=2}$</td> 
   <td align="center">$ {j=1}$</td> 
  </tr> 
  <tr> 
   <td>$ {i=3}$</td> 
   <td align="center">$ {j=1,2}$</td> 
  </tr> 
  <tr> 
   <td>$ {i=4}$</td> 
   <td align="center">$ {j=1,2,3}$</td> 
  </tr> 
  <tr> 
   <td>$ {\ldots}$</td> 
   <td align="center">$ {\ldots}$</td> 
  </tr> 
  <tr> 
   <td>$ {i=n}$</td> 
   <td align="center">$ {j=1,2,3,\ldots,n-1}$</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
  </tr> 
 </tbody> 
</table>

We plot these indices on the plane shown in the following figure.

![689213-20171024013208488-1180314886.png][]Figure: Double Index

Now let us change the way to look at them. Instead of counting $ \{i\}$ first, we first count the value of $ \{j\}$. If $ \{j=1\}$, $ \{i\}$ can take values $ \{2,3,\\ldots,n\}$. If $ \{j=2\}$, $ \{i\}$ can take values $ \{3,4,\\ldots,n\}$, and so on. The range of $ \{j\}$'s value is from 1 to $ \{n-1\}$. So we can use the following double summation operator to generate exactly the same set of $ \{\\left(i,j\\right)\}$ indices as the double summation operator in (3)

$ \\displaystyle \\sum\_\{j=1\}^\{n-1\}\\sum\_\{i=j+1\}^\{n\} $

This expression can be improved a little by enlarging the range of $ \{j\}$ a little to $ \{1,2,\\ldots,n\}$, as we know if $ \{j=n\}$, the summation operator on $ \{i\}$ becomes

$ \\displaystyle \\sum\_\{i=n+1\}^\{n\} $

which does not generate any $ \{i\}$ index anyway. Finally we see the index set in the above table (or the figure) can be generated either by

$ \\displaystyle \\sum\_\{i=1\}^\{n\}\\sum\_\{j=1\}^\{i-1\} $

or by

$ \\displaystyle \\sum\_\{j=1\}^\{n-1\}\\sum\_\{i=j+1\}^\{n\} $

Thus, for any function $ \{f\\left(i,j\\right)\}$

$ \\displaystyle \\sum\_\{i=1\}^\{n\}\\sum\_\{j=1\}^\{i-1\}f\\left(i,j\\right)=\\sum\_\{j=1\}^\{n\}\\sum\_\{i=j+1\}^\{n\}f\\left(i,j\\right) $

This is equation (1).

转载于:https://www.cnblogs.com/jingyuewang/p/7719909.html

[689213-20171024013208488-1180314886.png]: /images/20211220/8860d65a69ca4c708c3c9c6f673b83e8.png