Invertierbare Matrizen generieren



  • 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.



  • bja schrieb:

    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.

    aber jedes ungerade, wenn mich mein gefühl nicht trügt.
    kannst also evtl nicht stur gaussen, sondern musst als pivot ein ungerades element suchen. und wenn mich wieder mein gefühl nicht trügt, wird es das auch immer geben.



  • Wenn es nur darum geht, zufällige invertierbare Matrizen zu finden, warum dann nicht einfach so:
    Man nehme eine zufällige rechte obere Dreiecksmatrix und eine zufälige linke untere Dreiecksmatrix. Beide sind sicher invertierbar (Diagonaleinträge nicht gleich 0). Dann musst du diese nur noch multiplizieren. Prüfen brauchst du hier dann nichts. Das Invertieren von Dreiecksmatrizen stellt auch kein Problem dar. Das Produkt der Inversen stellt dann deine gesuchte Inverse dar.



  • anderer Vorschlag
    man nutze Matrizen in Householderform im SVD style
    Pi=(I2uuTuTu)P_{i}=(I- \frac {2u u^T}{u^Tu})
    man generiere sich auf diese weise einige Matrizen und dann bilde man sich eine MAtrix S welche nur diagonal besetzt ist.
    alle Determinanten der P matrizen sind +1. also ist die gesamt Determinante durch S bestimmt.

    PL=P0...PnP_{L}=P_{0}...P_{n}
    PR=Pn+1...P2nP_{R}=P_{n+1}...P_{2*n}
    M=PLSPRM=P_{L} S P_{R}
    M1=PLTS1PRTM^-1=P_{L}^T S^{-1} P_{R}^T



  • Householdermatrizen muss ich ja auch generieren und multiplizieren. Ist wohl nicht effizienter als der Dreiecksmatrizen-Ansatz. Sehe keinen Vorteil.

    Danke an alle!

    Mal sehen ob ich das schön umsetzen kann.

    (Bis später ;))


Anmelden zum Antworten