Xref: utzoo sci.math:11833 comp.theory:895
Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!sdd.hp.com!decwrl!ucbvax!brahms.berkeley.edu!greg
From: greg@brahms.berkeley.edu (Greg Kuperberg)
Newsgroups: sci.math,comp.theory
Subject: Permanents and determinants
Message-ID: <37817@ucbvax.BERKELEY.EDU>
Date: 28 Jul 90 06:17:48 GMT
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: greg@brahms.berkeley.edu (Greg Kuperberg)
Organization: UC Berkeley
Lines: 22

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 Kuperberg