Smith
Description
Dieses Modul erlaubt es, eine gegebene Matrix ueber einem euklidischen Ring auf Smithsche Normalform zu bringen.
Diese verwenden wir, um in IntegralClosure Minimalpolynome von Matrizen auszurechnen.
- diagonalForm ∷ (ReifyNat n, ReifyNat m, EuclideanRing a, Eq a, HasTestableAssociatedness a) ⇒ Matrix n m a → [a]
- elementaryDivisors ∷ (ReifyNat n, ReifyNat m, EuclideanRing a, Eq a, HasTestableAssociatedness a) ⇒ Matrix n m a → [a]
- class Ring a ⇒ HasAnnihilatingPolynomials a where
- annihilatingPolynomial ∷ ReifyNat n ⇒ SqMatrix n a → NormedPoly a
- determinant ∷ (ReifyNat n, EuclideanRing a, Eq a, HasTestableAssociatedness a) ⇒ SqMatrix n a → a
- charPoly ∷ (ReifyNat n, Field a) ⇒ SqMatrix n a → NormedPoly a
- minPoly ∷ (ReifyNat n, Field a) ⇒ SqMatrix n a → NormedPoly a
- lambdaMatrix ∷ (ReifyNat n, Ring a) ⇒ SqMatrix n a → SqMatrix n (Poly a)
- check_Smith ∷ IO ()
- demo ∷ IO ()
Transformationen
diagonalForm ∷ (ReifyNat n, ReifyNat m, EuclideanRing a, Eq a, HasTestableAssociatedness a) ⇒ Matrix n m a → [a]
Bringt eine gegebene Matrix auf (rechteckige) Diagonalform. Das ist noch nicht die Smithsche Normalform; die zusaetzliche Bedingung, dass die aufeinanderfolgende Hauptdiagonalelemente einander teilen, muss hier nicht unbedingt erfuellt sein.
Die verwendeten Transformationen haben stets Determinante 1.
elementaryDivisors ∷ (ReifyNat n, ReifyNat m, EuclideanRing a, Eq a, HasTestableAssociatedness a) ⇒ Matrix n m a → [a]
Liefert die Elementarteiler einer Matrix. Diese werden nicht auf irgendeine Art und Weise normiert (welche sollte das in einem beliebigen euklidischen Ring auch sein?), sollten also nur bis auf Assoziiertheit verstanden werden.
Anwendungen der Smithschen Normalform
class Ring a ⇒ HasAnnihilatingPolynomials a where
Klasse fuer Ringe, die es unterstuetzen, zu jeder gegebenen quadratischen Matrix A ein normiertes Polynom f zu finden, welches die Matrix annihiliert, also f(A) = 0 erfuellt.
Wegen (der allgemeinen Form des) Satzes von Cayley--Hamilton sind das natuerlich einfach alle Ringe, das charakteristische Polynom einer Matrix ist stets ein normiertes (die richtige Vorzeichendefinition vorausgesetzt) annihilierendes Polynom.
Allerdings ist die Berechnung in allgemeinen Ringen nur naiv ueber die Leibnizformel durchfuehrbar. Daher soll diese Klasse Ringe auszeichnen, die ueber eine effizientere Moeglichkeit dazu verfuegen.
Insbesondere kann man ueber Koerpern auch das Minimalpolynom nehmen, welches weitere Anwendungen durch seinen geringeren Grad effizienter werden laesst.
Methods
annihilatingPolynomial ∷ ReifyNat n ⇒ SqMatrix n a → NormedPoly a
Bestimmt ein normiertes Polynom, welches die gegebene Matrix annihiliert. Das Nullpolynom zaehlt nicht als normiert.
Instances
| Field a ⇒ HasAnnihilatingPolynomials (F a) | |
| (Integral a, EuclideanRing a) ⇒ HasAnnihilatingPolynomials (ER a) |
determinant ∷ (ReifyNat n, EuclideanRing a, Eq a, HasTestableAssociatedness a) ⇒ SqMatrix n a → a
Berechnet die Determinante, indem Determinante-1-Transformationen verwendet werden, um die gegebene Matrix auf Dreiecksform zu bringen.
charPoly ∷ (ReifyNat n, Field a) ⇒ SqMatrix n a → NormedPoly a
Berechnet das charakteristische Polynom (normiert) einer gegebenen Matrix. Die Koerper-Voraussetzung an den Ring stellen wir, um die effizienten Smith-Umformungen nutzen zu koennen. Erfuellt folgende Spezifikation:
determinant = naiveDeterminant . lambdaMatrix
minPoly ∷ (ReifyNat n, Field a) ⇒ SqMatrix n a → NormedPoly a
Berechnet das Minimalpolynom (normiert) einer gegebenen Matrix A ueber die Smithsche Normalform von lambda 1 - A. Das Minimalpolynom der eindeutigen 0x0-Matrix ist das Einspolynom.
lambdaMatrix ∷ (ReifyNat n, Ring a) ⇒ SqMatrix n a → SqMatrix n (Poly a)
Liefert zu einer gegebenen Matrix A die fuer die Bestimmung von annihilierenden Polynomen wichtige Matrix lambda 1 - A (mit Eintraegen im entsprechenden Polynomring).
Debugging
check_Smith ∷ IO ()
demo ∷ IO ()