SUM OF PRODUCTS
This quiz is taken from the book "Statistical Mechanics:
Rigorous Results"
by D. Ruelle *Addison-Wesley 1969).
Let Aij be a nxn symmetric
matrix, with |Aij|<1.
Consider the following sum,
P(k,n) = ∑S (-1)|S*{1,..,k}|
∏i in S ∏j in S' Aij
where:
- the sum is over the 2n subsets of {1,..,n}
- S*{1,..,k} denotes the intersection of the subsets S and {1,..,k};
the coefficient in front of the double product is therefore +1 or -1
depending whether the cardinality of this
set is even or odd, respectively;
- the product over i runs on the integers in S
- the product over j runs over the integers in the complement S' of S
- if S is empty or equal to {1,..,n} then the products are 1.
For exaample, consider the case n=2:
- P(0,2) = 1 + A12 + A21 + 1
- P(1,2) = 1 - A12 + A21 - 1
- P(2,2) = 1 - A12 - A21 + 1
Since A21=A12, P(1,2)=0, and since
|A12|<1, P(0,2) and P(2,2) are positive.
Show that P(k,n) is greater or equal to 0 for every n
and k (between 0 and n).
Marco Corvi - 2006