2009.11.09 | Bjarke Hammersholt Roune

Everyone knows the determinant of a square matrix. The permanent is less known though it is almost the same thing, one just omits all the switching of signs. Note that in characteristic 2 the permanent and determinant are the same thing. One can compute the determinant of a given matrix in polynomial time using Gaussian elimination. However this does not hold for the permanent, assuming the characteristic is not 2, since it is not multiplicative.

One might ask if there is some way to compute the permanent by "blowing up and applying the determinant". More precisely can one compute the permanent by constructing a bigger matrix with linear (affine) polynomials as entries, such that the permanent equals the determinant applied to this bigger matrix? Valiant has shown that such maps exist; in fact all polynomials can be written as the determinant of some matrix with linear entries.

The topic of this talk is to establish a lower bound of how fast these matrices grow as the original matrices grow. A result due to Mignon and Ressayre gives by use of Hessian matrices that the growth is at least quadratic, when working over a field of characteristic 0. This has been generalized by Cai, Chen and Li to hold over fields of odd characteristic. For a variety X there is a link from the rank of a Hessian matrix to the dimension of the dual variety. We will outline a translation of the work of Mignon, Ressayre, Cai, Chen and Li into the language of dual varieties.

See www.cs.au.dk/~bjarke/compmath/ for details.