Open AccessAre There Elimination Algorithms for the Permanent?
Author(s) -
Carl Sturtivant
Publication year - 1990
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v19i306.6699
Subject(s) - gaussian elimination , homogeneous space , gaussian , algebraic number , contrast (vision) , algorithm , class (philosophy) , polynomial , mathematics , multivariate statistics , algebra over a field , computer science , pure mathematics , artificial intelligence , statistics , mathematical analysis , physics , geometry , quantum mechanics
We define the class of elimination algorithms. These are algebraic algorithms for evaluating multivariate polynomials, and include as a special case, Gaussian elimination for evaluating the determinant. We show how to find the linear symmetries of a polynomial, defined appropriately, and use these methods to find the linear symmetries of the permanent and determinant. We show that in contrast to Gaussian elimination for the determinant, there is no elimination algorithm for the permanent.