Elimineringsteori - Elimination theory
I kommutativ algebra og algebraisk geometri er elimineringsteori det klassiske navn for algoritmiske tilgange til at eliminere nogle variabler mellem polynomer af flere variabler for at løse systemer med polynomiske ligninger .
Den klassiske elimineringsteori kulminerede med Francis Sowerby Macaulays arbejde med multivariate resultanter , og dens beskrivelse i kapitel Elimineringsteori om de første udgaver (1930) af Bartel Leendert van der Waerden 's Moderne Algebra . Derefter blev elimineringsteori ignoreret af de fleste algebraiske geometre i næsten tredive år, indtil introduktionen af nye metoder til løsning af polynomiske ligninger, såsom Gröbner-baser , som var nødvendige for computeralgebra .
Historie og forbindelse til moderne teorier
Feltet for elimineringsteori var motiveret af behovet for metoder til løsning af systemer af polynomiske ligninger .
Et af de første resultater var Bézouts sætning , som afgrænser antallet af løsninger (i tilfælde af to polynomer i to variabler på Bézout-tiden).
Bortset fra Bézouts sætning var den generelle tilgang at eliminere variabler til reduktion af problemet til en enkelt ligning i en variabel.
Tilfældet med lineære ligninger blev fuldstændigt løst ved Gaussisk eliminering , hvor den ældre metode i Cramer's regel ikke forløber ved eliminering og kun fungerer, når antallet af ligninger er lig med antallet af variabler. I løbet af det 19. århundrede er dette blevet udvidet til lineære diofantiske ligninger og abelisk gruppe med Hermite normal form og Smith normal form .
Før det 20. århundrede blev forskellige typer eliminanter introduceret, herunder resulterende og forskellige former for diskriminanter . Generelt er disse eliminanter også invariante og er også grundlæggende i invariant teori .
Alle disse begreber er effektive i den forstand, at deres definition inkluderer en beregningsmetode. Omkring 1890 introducerede David Hilbert ikke-effektive metoder, og dette blev betragtet som en revolution, der førte til, at de fleste algebraiske geometre i første halvdel af det 20. århundrede forsøgte at "eliminere eliminering". Ikke desto mindre kan Hilberts Nullstellensatz betragtes som tilhørende elimineringsteori, da det hævder, at et system af polynomiske ligninger ikke har nogen løsning, hvis og kun en kan eliminere alle ukendte for at få 1.
Elimineringsteori kulminerede med arbejdet fra Leopold Kronecker , og endelig Macaulay , der introducerede multivariate resultanter og U-resultanter , der leverede komplette eliminationsmetoder til systemer med polynomiske ligninger, som er beskrevet i kapitel Eliminationsteori om de første udgaver (1930) af van der Waerden's Moderne Algebra .
Derefter er elimineringsteori blevet betragtet som gammeldags, fjernet fra næste udgaver af Moderne Algebra og generelt ignoreret indtil introduktionen af computere og mere specifikt af computeralgebra , som sætter problemet med at designe eliminationsalgoritmer, der er tilstrækkelig effektive til bliver implementeret. De vigtigste metoder til denne fornyelse af elimineringsteorien er Gröbner-baser og cylindrisk algebraisk nedbrydning , som blev introduceret omkring 1970.
Forbindelse til logik
Der er også en logisk facet til elimineringsteori, som det ses i det boolske tilfredshedsproblem . I værste fald er det formodentlig svært at eliminere variabler beregningsmæssigt. Kvantificeringseliminering er et udtryk, der bruges i matematisk logik for at forklare, at i nogle teorier svarer hver formel til en formel uden kvantificering. Dette er tilfældet med teorien om polynomer over et algebraisk lukket felt , hvor elimineringsteori kan ses som teorien om metoderne til at gøre kvantificeringseliminering algoritmisk effektiv. Kvantificeringseliminering over realerne er et andet eksempel, som er grundlæggende i beregningsmæssig algebraisk geometri .
Se også
Referencer
- Israel Gelfand , Mikhail Kapranov, Andrey Zelevinsky , diskriminanter, resulterende og flerdimensionelle determinanter . Matematik: Teori og applikationer. Birkhäuser Boston, Inc., Boston, MA, 1994. x + 523 s. ISBN 0-8176-3660-9
- Lang, Serge (2002), Algebra , Graduate Texts in Mathematics , 211 (Revideret tredje udgave), New York: Springer-Verlag, ISBN 978-0-387-95385-4, MR 1878556
- David Cox, John Little, Donal O'Shea, ved hjælp af algebraisk geometri . Revideret anden udgave. Graduate Texts in Mathematics , vol. 185. Springer-Verlag , 2005, xii + 558 s., ISBN 978-0-387-20733-9