greg@brahms.berkeley.edu (Greg Kuperberg) (07/28/90)
Consider the 4 x 4 matrix:
[ a b c d ]
M = [ e f g h ]
[ i j k l ]
[ m n o p ]
I note that the permanent of this matrix equals
(Det(M)-Det(M1)-Det(M2)-Det(M3))/2, where:
[ -a b c d ] [ a -b c d ] [ a b -c d ]
M1 = [ e -f g h ] M2 = [ e f -g h ] M3 = [ -e f g h ]
[ i j -k l ] [ -i j k l ] [ i -j k l ]
[ m n o -p ] [ m n o -p ] [ m n o -p ]
Suppose in general you have an n x n matrix M, and you can obtain
a list of matrices M1,...,Mk by changing the signs of the entries
of M with the property that the permanent of M is a linear combination
of the determinants of M1,...,Mk. How small can you make k? For
n=4, k=4 by the above example. How about for n=5?
-----
Greg Kuperberggrove@mandolin.Berkeley.EDU (Eddie Grove) (07/31/90)
In article <37817@ucbvax.BERKELEY.EDU> greg@brahms.berkeley.edu (Greg Kuperberg) writes: >Suppose in general you have an n x n matrix M, and you can obtain >a list of matrices M1,...,Mk by changing the signs of the entries >of M with the property that the permanent of M is a linear combination >of the determinants of M1,...,Mk. How small can you make k? For >n=4, k=4 by the above example. How about for n=5? >----- >Greg Kuperberg This is going to be an extremely difficult problem for general k. Calculating the permanent is #P-complete, while determinant is in P. So if you can prove k to be polynomial in n, or lower bound it by a super-polynomial, you get a tremendous result in complexity theory. Eddie Grove