# Generalized Characteristic Polynomials

### John F. Canny

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-88-440

August 1988

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-440.pdf

We generalize the notion of characteristic polynomial for a system of linear equations to systems of multivariate polynomial equations. The generalization is natural in the sense that it reduces to the usual definition when all the polynomials are linear. Whereas the constant coefficient of the general characteristic polynomial is the resultant of the system. This construction is applied to solve a traditional problem with efficient methods for solving systems of polynomial equations: the presence of infinitely many solutions "at infinity". We give a single-exponential time method for finding all the isolated solution points of a system of polynomials, even in the presence of infinitely many solutions at infinity or elsewhere.

BibTeX citation:

@techreport{Canny:CSD-88-440, Author = {Canny, John F.}, Title = {Generalized Characteristic Polynomials}, Institution = {EECS Department, University of California, Berkeley}, Year = {1988}, Month = {Aug}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1988/6040.html}, Number = {UCB/CSD-88-440}, Abstract = {We generalize the notion of characteristic polynomial for a system of linear equations to systems of multivariate polynomial equations. The generalization is natural in the sense that it reduces to the usual definition when all the polynomials are linear. Whereas the constant coefficient of the general characteristic polynomial is the resultant of the system. This construction is applied to solve a traditional problem with efficient methods for solving systems of polynomial equations: the presence of infinitely many solutions "at infinity". We give a single-exponential time method for finding all the isolated solution points of a system of polynomials, even in the presence of infinitely many solutions at infinity or elsewhere.} }

EndNote citation:

%0 Report %A Canny, John F. %T Generalized Characteristic Polynomials %I EECS Department, University of California, Berkeley %D 1988 %@ UCB/CSD-88-440 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1988/6040.html %F Canny:CSD-88-440