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 Sj 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