Problem 11959
(American Mathematical Monthly, Vol.124, February 2017) Proposed by D. Knuth (USA).
Prove that, for any n-by-n matrix A with(i, j)-entry ai,j and any t1, . . . , tn, the permanent of A is 1
2n X
n
Y
i=1
σi
ti+
n
X
j=1
σjai,j
, where the outer sum is over all2n choices of(σ1, . . . , σn) ∈ {1, −1}n.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
Solution. Let
FA(t1, . . . , tn) := 1 2n
X
σ∈{1,−1}n n
Y
i=1
σi
ti+
n
X
j=1
σjai,j
. We will show that FA(t1, . . . , tn) = perm(A) by induction on n.
If n = 1 then the formula holds:
FA(t1) =1
2(1 · (t1+ 1 · a1,1) + (−1) · (t1+ (−1) · a1,1)) = a1,1= perm(A).
Assume that n > 1, then we first prove that the multivariable polynomial FA is constant by show- ing that the partial derivatives are identically zero. By symmetry, it suffices to check the partial derivative with respect to tn,
∂FA
∂tn (t1, . . . , tn) = 1 2n
X
σ∈{1,−1}n
σn
n−1
Y
i=1
σi
ti+
n
X
j=1
σjai,j
= 1 2n
X
σ∈{1,−1}n−1
1 ·
n−1
Y
i=1
σi
ti+ 1 · ai,n+
n−1
X
j=1
σjai,j
+ 1 2n
X
σ∈{1,−1}n−1
(−1) ·
n−1
Y
i=1
σi
ti+ (−1) · ai,n+
n−1
X
j=1
σjai,j
=FA′(t1+ a1,n, . . . , tn−1+ an−1,n) − FA′(t1− a1,n, . . . , tn−1− an−1,n) 2
=perm(A′) − perm(A′)
2 = 0.
where A′ is the (n − 1)-by-(n − 1) matrix obtained by removing both the n-th row and the n-th column of A.
Hence, it remains to show that FA(0, . . . , 0) = perm(A). Let Fn be the set of functions of {1, . . . , n}
in itself, then
FA(0, . . . , 0) = 1 2n
X
σ∈{1,−1}n n
Y
i=1
n
X
j=1
σiσjai,j
= 1 2n
X
σ∈{1,−1}n
X
f∈Fn
n
Y
i=1
σiσf(i)ai,f(i)
= X
f∈Fn
1 2n
X
σ∈{1,−1}n n
Y
i=1
σiσf(i)ai,f(i) = perm(A)
because 1 2n
X
σ∈{1,−1}n n
Y
i=1
σiσf(i)ai,f(i) =
Qn
i=1ai,f(i) if f is a permutation,
0 otherwise.
