Die Mathe-Redaktion - 16.10.2019 04:42 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 320 Gäste und 2 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Wie kann man die Häufigkeit der verwendeten Permutation-Matrizen in deren Produkt ermitteln?
Druckversion
Druckversion
Autor
Kein bestimmter Bereich J Wie kann man die Häufigkeit der verwendeten Permutation-Matrizen in deren Produkt ermitteln?
Yor
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 29.09.2009
Mitteilungen: 72
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-08-02


fed-Code einblenden



  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 2756
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-08-02


Hallo,

ich bin mir nicht sicher, ob nicht ein paar deiner Annahmen falsch sind. Ein beliebiges Produkt dieser Matrizen und ihrer Inversen kann nicht zu $A^{n_A} B^{n_B} C^{n_C} A^{-m_A} B^{-m_B} C^{-m_C}$ (warum eigentlich nicht gleich $A^{n_A} B^{n_B} C^{n_C}$ mit $n_A, n_B, n_C\in\IZ$?) zusammengefasst werden, weil die Matrizen nicht notwendig kommutieren. Es bleibt erstmal bei der gegebenen Folge. Man kann aneinanderstoßende Inverse eliminieren und ansonsten die Relationen der Gruppe ausnutzen. Es wird i.A. kein kanonisches Wort geben, man kann sich höchstens fragen, ob man ein kürzestmögliches Wort angeben kann. Das erinnert mich an das i.A. unlösbare Wortproblem.


-----------------
⊗ ⊗ ⊗



  Profil  Quote  Link auf diesen Beitrag Link
Yor
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 29.09.2009
Mitteilungen: 72
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-08-02


Hallo ligning,
danke für die Antwort. Ich war mir da auch nicht mehr ganz sicher und hatte es einmal für ein Beispiel ausprobiert. Da hatte die Reihenfolge keine Rolle gespielt. Hab mich da wohl vertan.

>(warum eigentlich nicht gleich $A^{n_A} B^{n_B} C^{n_C}$ mit $n_A, n_B, n_C\in\IZ$
Ja das gäng auch (sofern kommutieren). In der angedachten Verwendung hätte es normale und inverse gegeben.

Kann man drei unterschiedliche Matrizen kommutativ zueinander machen? (wobei keine Inverse, Transponierte einer anderen oder die Einheitsmatrix ist)



  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 2756
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-08-02


Was meinst du mit "kommutativ machen"?



  Profil  Quote  Link auf diesen Beitrag Link
Yor
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 29.09.2009
Mitteilungen: 72
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2019-08-02


2019-08-02 17:31 - ligning in Beitrag No. 3 schreibt:
Was meinst du mit "kommutativ machen"?
Gibt es drei Matrizen $A,B,C$ für die man jede beliebige Folge von Multiplikation dieser auf $A^{n_A} B^{n_B} C^{n_C}$ reduzieren kann?

Also

$AB=BA$
$AC=CA$
$BC=CB$
$ABC=ACB=BAC=BCA=CAB=CBA$
$ABCABC = A^2B^2C^2$
usw.

Es geht ja nicht mit zufälligen Permutation-Matrizen. Frage ist, ob man irgendwelche Matrizen konstruieren kann für die das gilt.



  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 2756
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-08-02


Ein Weg, der auf jeden Fall funktionieren sollte:

Mache dir zunächst einige Isomorphismen klar.

1) Jede endliche Gruppe $G$ der Ordnung $n$ ist isomorph zu einer Untergruppe der Bijektionen auf der unterliegenden Menge $|G|$, indem man jedes $g\in G$ auf die Abbildung $l_g : |G|\to |G|,\, x\mapsto gx$, schickt. (Satz von Cayley)

2) Für jede endliche Menge $X$ wird durch Nummerierung der Elemente ein Isomorphismus von der Gruppe der Bijektionen auf $X$ zur symmetrischen Gruppe $S_n$ induziert.

3) $S_n$ ist isomorph zur Gruppe der $n\times n$-Permutationsmatrizen.

Wähle nun eine abelsche Gruppe $G$ mit ausreichend hoher Ordnung $n$, dann kannst du sie wie oben in die Gruppe der $n\times n$-Permutationsmatrizen einbetten. Wenn $n\geq 4$ findest du dort somit 3 nicht-triviale Elemente, die miteinander kommutieren. Da dort auch inverse Elemente dabei sind und ich auch gerade nicht sehe, ob Transpositionen ausgeschlossen sind, musst du $n$ ggf. größer wählen.

Beispiel: Wenn man für $G$ die zyklische Gruppe $\IZ/n\IZ$ setzt, sollte man bspw. die von dem Zyklus $(1 2 \ldots n)$ erzeugte Untergruppe von $S_n$ erhalten, entsprechend den Matrizen, die entstehen, indem man in der Einheitsmatrix die Diagonale nach unten schiebt (zyklisch, also unten herausfallende Zeilen von oben wieder einfügt).



  Profil  Quote  Link auf diesen Beitrag Link
Yor
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 29.09.2009
Mitteilungen: 72
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2019-08-02


Vielen Dank für die Antwort.
Ich bin mir noch nicht sicher, ob ich es kapiert habe :)

Heißt dass, das sie nur kommutativ zu einander sind, wenn sie im selben Zyklus sind?
Und somit die Anzahl der möglichen Ergebnisse bzw. Permutationen, (die man durch beliebiges multiplizieren erhält) durch die Zykluslänge beschränkt ist?
Und diese ist wiederum durch $n$ beschränkt.






  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 2756
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-08-03


2019-08-02 22:51 - Yor in Beitrag No. 6 schreibt:
Heißt dass, das sie nur kommutativ zu einander sind, wenn sie im selben Zyklus sind?
Nein, das mit der zyklischen Gruppe war nur ein Beispiel.



  Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3345
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2019-08-03


Hallo Yor,
Allgemein für die Frage "Wie kann man die Häufigkeit der verwendeten Permutation-Matrizen in deren Produkt ermitteln?" gibt es eine GAP-Funktion Expressing Group Elements as Words in Generators.

Viele Grüße,
  Stefan



  Profil  Quote  Link auf diesen Beitrag Link
Yor
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 29.09.2009
Mitteilungen: 72
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2019-08-03


Halllo Stefan,
danke für den Link. GAP kannte ich noch nicht. Gleich einmal ein Lesezeichen gesetzt.

Jedoch nach weiteren Überlegungen und euerer Hilfe bin ich zu dem Schluss gekommen, dass Permutation-Matrizen für den geplanten Anwendungsfall nicht geeignet sind.


Ich suche drei Matritzen/Operationen/Funktionen/... die kommutativ u. assoziativ zueinander sind, jedoch nicht linear abhängig (oder wie man das da nennt, eine soll man nicht nach mehrmahligen anwenden der anderen erhalten können). Außerdem müssen die jeweils eine Inverse haben.
Das geht zwar mit Permutation-Matrizen, jedoch werden die dann sehr groß. Gegeben zwei Ergebnisse soll es nicht einfach sein die verwendeten Matritzen/Operationen/Funktionen/... zu bestimmen, um das eine aus den anderen zu erhalten (für Computer schwer).
Bei Permutation-Matrizen ist die Anzahl der möglichen Ergebnisse relativ gering im Vergleich zu deren Größe ($n \times n$ Matrix). Die Matritzen/Operationen/Funktionen/... sollen auch jeweils zyklisch sein.
Dazu muss man auch noch ein mögliches Ergebniss ohne Anwendung der  Matritzen/Operationen/Funktionen/... erstellen können (=Initialwert). Wendet man da dann die Matritzen/Operationen/Funktionen/... auf dieses an erhält man Ergebnissmengen. Je nach Initialwert sollen die Mengen dann identisch oder disjunkt sein. Die Anzahl der Mengen soll im Verhältniss zu deren Größe viel kleiner sein (sie kann auch =1 sein).

Eine abelsche Gruppe hat ja einen zweiseitigen Operator. Mir würde ja ein einseitger Operator reichen bzw. drei davon.
Eine Poly/Trizyklische gruppe kommt dem glaube ich auch nahe.


Nun gut das ist abseits des ursprünglichen Themas. Da mache ich besser einen neuen Thread auf.

Noch einmal vielen Dank für die Hilfe.



  Profil  Quote  Link auf diesen Beitrag Link
Yor hat die Antworten auf ihre/seine Frage gesehen.
Yor hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]