Invertierbare Matrizen generieren



  • Hi.

    Gibt es eine Möglichkeit zufällig invertierbare Matrizen (zunächst mal über R\mathbb{R}) zu erzeugen?
    Zufällige Matrix bauen, deren Determinanten berechnen um dann festzustellen dass sie meistens 0 ist ist mir zu ineffizient. 🙂



  • Bin gerade auf eine bessere Lösung gekommen.

    Die Idee ist vermutlich die Einheitsmatrix zu nehmen und zufällige Elementarumformungen durchzufühen.

    Geht's noch anders?



  • spontan fällt mir ein bei ner dreiecksmatrix (also bei einer wo unter der diagonale alles nullen sind) ist die determinaten genau das produkt der diagonalelemente... in dem fall müsstest du dann nur drauf achten das dort keien nullen auftreten... wenn du dann im unteren teil nicht mehr soviele nullen haben willst kannst du dann ja einfach ein paar zufälige umformungen (ich nenne es mal rumgaussen) vornehmen lassen...



  • Ja, zufällige Dreiecksmatrix ohne Nulleinträge auf der Hauptdiagonalen ist besser als Einheitsmarix.

    Danke



  • du kannst dir auch einfach eine Matrix komplett zufällig auswählen
    und prüfst dann ob diese invertierbar ist.
    Die Wahrscheinlichkeit, dass dies nicht der Fall ist, ist
    sehr gering. (Zumindest wenn die Anzahl der möglichen Zufallszahlen groß ist)

    Viele Grüße
    Fischi



  • @Fischi
    Wahrscheinlichkeit hin oder her, Prüfen muss er es trotzdem und das wird zu rechenintensiv.

    @bja
    Du könntest eine obere und eine untere Dreiecksmatrix erzeugen. Sind beide invertierbar, so ist ihr Produkt auch invertierbar und vollbesetzt (insofern in den Dreiecken keine Null vorkommt).
    Die Multiplikation solcher Dreiecksmatrizen ist, entsprechend implementiert, auch garnicht so langsam.



  • Nochmal ich.

    Um welche Größenordnung handelt es sich überhaupt was die Matrizen betrifft?
    Ich denke da kann man noch jede Menge Tricks einbauen und optimieren aber für kleinere Matrizen sollte die obige Lösung reichen.

    Und nochwas:
    Was verstehst du unter Zufall? Welcher Verteilung sollen die Einträge genügen?
    Oder ist das im Detail nicht so wichtig?



  • hmm.
    man ein wenig zeiten raten.

    zufällig generieren und testen:
    ein lauf gauss-algo bis zur dreiecksmatrix. also O(n^3). das macht keinen spass.
    edit: auch viele divisionen drin. wer mag denn sowas?

    dreieckmatrix zufällig generieren und ein paar zeilentransformationen. na, da reicht es ja, die längste zeile auf alle anderen draufzuaddieren. O(n^2). falls mehr anforderungen an die zufälligkeit gestellt sind, kriegt man bestimmt auch was anderes hin, was O(n^2) hat, aber nicht ganz so billig ist. vielleicht erstmal jede zeile auf die zeile drunter addieren. oder mal ne zeilen-und mal ne spalten-transformation.
    edit: nur n^2 additionen!

    zwei dreiecksmatrizen plutimizieren: gips da tricks für dreiecksmatrizen? sieht mir nach O(n^3) aus.
    viele plutimikationen.



  • volkard schrieb:

    zwei dreiecksmatrizen plutimizieren: gips da tricks für dreiecksmatrizen? sieht mir nach O(n^3) aus.
    viele plutimikationen.

    Ne, da gibt's keine Tricks dafür. Nimm Dir zwei bel. Matrizen. Steck die einfach rechts oben in ne quadratische Matrix mit doppelter Kantenlänge rein. Diese Matrix ist dann diagonal. Jetzt multiplizierst Du die beiden (wenn es ginge, dann auch gerne günstiger) und Du hast das Produkt der ursprünglichen Matrizen berechnet.



  • volkard schrieb:

    hmm.
    zwei dreiecksmatrizen plutimizieren: gips da tricks für dreiecksmatrizen? sieht mir nach O(n^3) aus.
    viele plutimikationen.

    tricks?
    man weiss das unter bzw über der diagonale nur nullen sind. wer multipleX0rt mit Null?



  • b7f7: in meinem Beitrag steht aber ein Beweis, daß die Komplextität immer noch O(n^3) ist.

    edit: stimmt so nicht ganz, ich hab nur gezeigt, daß es nicht schneller als allgemeine Matrizen multiplizieren ist (von der Komplexität her). Allgemein Matrixmultiplikation geht ja auch etwas schneller als O(n^3) Stichwort: Matrizenmultiplikation nach Strassen.



  • invertierbarkeit bestimmen ist wohl in O(n^2) plutimikationen und ein paar additionen möglich, indem man die determinante errechnet.



  • wie berechnest du die determinante von zB einer (40x40) matrix in O(n^2) und was ist dabei atomar?



  • leider ist mein Beitrag untergegangen, weil ich den genau dann gepostet hab als es DB-Probleme im Forum gab, oder sowas.

    Also nochmal: Es ist ein Versuch den Hill Cipher Algorithmus zu implementieren. Dabei ist es noch etwas komplizierter:
    Die Matrix ist nicht über einem Körper sondern über einem Restklassenring (in meinem Fall Z256\mathbb{Z}_{256}) definiert.

    Die Determinante kann man mit ner LR-Zerlegung glaube ich etwas fixer bestimmen.
    Für den Test auf Invertierbarkeit muss man noch den ggt(det(M), 256) bestimmen. Der muss nämlich 1 sein. Problem ist, dass nicht jede Dreiecksmatrix da passt. 😞

    Die Dimension der Matrix wird sich in Grenzen halten. Nicht mehr als 20, denke ich.



  • b7f7 schrieb:

    wie berechnest du die determinante von zB einer (40x40) matrix in O(n^2)?

    gar nicht. das war bockmist.



  • bja schrieb:

    Für den Test auf Invertierbarkeit muss man noch den ggt(det(M), 256) bestimmen. Der muss nämlich 1 sein.

    was nix anderes heißt, als daß det(M) ungerade sein muss?

    heißt das am ende auch, determinante der ursprünglichen dreieckmatrix ungerade sein muss?



  • volkard schrieb:

    bja schrieb:

    Für den Test auf Invertierbarkeit muss man noch den ggt(det(M), 256) bestimmen. Der muss nämlich 1 sein.

    was nix anderes heißt, als daß det(M) ungerade sein muss?

    Genau.

    volkard schrieb:

    heißt das am ende auch, determinante der ursprünglichen dreieckmatrix ungerade sein muss?

    Genau. Elementarumformungen (bis auf Zeilenaddition) ändern aber die Det. 😕



  • bja schrieb:

    volkard schrieb:

    heißt das am ende auch, determinante der ursprünglichen dreieckmatrix ungerade sein muss?

    Genau. Elementarumformungen (bis auf Zeilenaddition) ändern aber die Det. 😕

    und mit ein paar zeilenadditionen kannste aus ner zufällig aussehenden dreiecksmatrix (die auf der diaginalen nur ungerade zahlen hat) eine ebenso zufällig aussehende volle matrix machen? sichbare schieflagen der verteilung befürchte ich gar nicht wegen des so oft vorkommenden überlaufs bei den ganzen addidionen. das war's dann, oder?



  • Die Dimension der Matrix wird sich in Grenzen halten. Nicht mehr als 20, denke ich

    hehe du kannst ja mal versuchen die determinante der 20x20 matrix direkt zu berechenen ohne umzuformen. das ergebnis erlebst du nicht mehr 😃



  • volkard schrieb:

    und mit ein paar zeilenadditionen kannste aus ner zufällig aussehenden dreiecksmatrix (die auf der diaginalen nur ungerade zahlen hat) eine ebenso zufällig aussehende volle matrix machen? sichbare schieflagen der verteilung befürchte ich gar nicht wegen des so oft vorkommenden überlaufs bei den ganzen addidionen. das war's dann, oder?

    Jo. Dann kann ich jetzt chiffrieren.

    Für's dechiffrieren brauche ich die Inverse. Zwar weiß ich dass sie existiert, ich frage mich aber, ob ich sie einfach mit Gauss berechnen kann. Im Ring hat ja nicht jedes Element ein Inverses.

    Werd's morgen mal genauer probieren.

    Gute Nacht.


Log in to reply