 |
Center for Nonlinear Studies |
Since the celebrated work of Jerrum, Sinclair, and Vigoda, we have known that the permanent of a 0-1 matrix can be approximated in randomized polynomial time using a rapidly mixing Markov chain that samples perfect matchings of a bipartite graph. A separate strand of the literature has asked whether there is a polynomial-time approximation scheme which is purely algebraic. These schemes work by replacing each 1 with a random element of an algebra A, such as the algebra of d-dimensional matrices, and considering the determinant of the resulting matrix. In the case where A is noncommutative, this determinant can be defined in several ways. We analyze the symmetrized determinant of Barvinok, and generalize recent results of Chien, Rasmussen, and Sinclair on the Clifford algebra. Our results apply both to matrix algebras and to semisimple algebras in general, and include group algebras as a special case. However, our results do not provide a new polynomial-time approximation scheme for the permanent. Ironically, they suggest that the symmetrized determinant---which we can compute in polynomial time for algebras of constant dimension---gives poorer estimators than the unsymmetrized determinant, for which no efficient algorithm is known. We obtain these results using diagrammatic techniques in which we write matrix products as contractions of tensor products. When these matrices are random, in either the Haar measure or the Gaussian measure, we can evaluate the trace of these products in terms of the cycle structure of a random permutation. In the symmetrized case, we also use ideas from the representation theory of the symmetric group.
Host: Misha Chertkov