Operationen mit Matrizen

Hallo Community!

Ich habe es mit meiner Frage bei den Mathematikern versucht und man kam auf keine Lösung, mal sehen wie es bei den Informatikern aussieht. Die Frage ist Folgende:

Ich habe zwei Matrizen der Größe 15x25, die mit Nullen und Einsen gefüllt sind. In jeder der 25 Zeilen jeder der Matrizen gibt es genau 2 Einsen, sonst Nullen, insgesamt also jeweils 50 Einsen und 325 Nullen. Die Matrizen sind fast identisch, nur eine einzige Eins ist verschoben.

Nun möchte ich überprüfen, ob die beiden Matrizen ineinander übergeführt werden können. Zulässig sind folgende Operationen: Man darf die Reihenfolge der Spalten und/oder Zeilen beliebig ändern, aber die Zeilen und Spalten müssen als ganze "bewegt" werden. Und so sehen die Matrizen aus:

http://www.ubuntu-pics.de/bild/12559/scan0013_HRM2U3.jpg

Die eine Matrix ist mit der Eins bei (14/15), die andere ist zur ersten identisch, nur die Eins ist nach (8/15) verschoben (siehe Pfeil).

Kann man das irgendwie vom Computer berechnen lassen? Ist es überhaupt eine gängige Operation bei einer Matrix (Array?) die Spalten bzw. Reihen zu vertauschen? Bin leider in Sachen Programmierung ziemlich unterbelichtet... Hoffe auf Hilfe,

PhotonX

Hi,

1.
Schreibt man bei Matrizen die Anzahl der Reihen/Zeilen nicht vor der Anzahl der Spalten also R^25x15 statt R^15x25?

2.
Ob man eine "Überführung" mit dem Computer berechnen kann? Ich denke ja, mir ist zwar kein effizienter Algorithmus bekannt, aber mittels Brute-Force-Suche könnte man durchaus zu einer Lösung kommen

3.
Zeilen/Spalten-Vertauschung kann man bei regulären Matrizen durchaus durchführen, es ändert sich dann nur das Vorzeichen der Determinante. Ich denke, du hast hier aber ein überbestimmtes Gleichungssystem, da muss ich ganz ehrlich sagen weiss ich nicht wie es aussieht, der Rang sollte sich aber durch Vertauschungen nicht ändern.

4.
Was willst du eigentlich bezwecken?

1. Kann sein, ich hab die erstbeste Variante genommen und es war leider die falsche.

2. Hmm, Brute Force ist schlecht, die Operation soll ziemlich oft angewendet werden...

3. Ok, super, das ist ja schon mal ein Anfang. Die Determinante spielt erstmal keine Rolle (zumindest hab ich mir noch keine Gedanken gemacht, welche Rolle sie spielen könnte) und ein Gleichungssystem soll die Matrix auch nicht repräsentieren.

4. Ja, das ist eine gute Frage. Also ich möchte Folgendes machen:

Eine solche Matrix nehmen (also auch eine, die nur aus Nullen und Einsen besteht und bei der in jeder Zeile immer zwei Einsen sind), sie dann auf unterschiedliche Arten modifizieren (also nicht so wie vorher mit dem Umordnen der Zeilen und Spalten, sondern anders, genauer hab ich's noch nicht, möchte erstmal sicher gehen, dass es überhaupt möglich ist), wobei es pro Matrix im Durchschnitt um die 5 bis 10 mal so viele Modifikationen gibt, wie die Matrix breit ist. Dann gibt es eine Anzahl an Matrizen, die bei diesen Modifikationen rausgekommen sind, die sollen dann nach ihren Abmessungen sortiert werden (die ändern sich bei den Modifikationen). Innerhalb einer Familie (in der lauter Matrizen gleicher Abmessungen sind), sollen dann alle Matrizen miteinander verglichen werden und anhand der Spaltensummen in Unterfamilien eingeteilt werden. Und dann soll in jeder Unterfamilie so wie oben beschrieben (bzw. gefragt ) geprüft werden, ob irgendwelche Matrizen durch Umstellen der Spalten und Reihen ineinander übergeführt werden können. Wenn dann zwei (oder mehr) solcher Matrizen gefunden werden, können sie als identisch angesehen werden und alle Duplikate gelöscht werden.

Dann sollen auf jede der übrig gebliebenen Matrizen wieder die Modifikationen vom Anfang angewandt werden und das Ganze wiederholt sich. Am Ende soll eine Tabelle rauskommen, in der drinsteht, wie viele Matrizen welcher Abmessungen rausgekommen sind. Was denkst du, ist das in annehmbarer Zeit und mit durchschnittlicher Hardware zu realisieren?

5 bis 10 mal so viele Modifikationen gibt, wie die Matrix breit ist

Zum Vergrößern anklicken....

Beim Beispiel vorher wären das im schlimmsten Fall 150 verschiedene Matrizen. Seh ich das richtig, hab ich das mit den Modifikationen falsch verstanden, oder sind die zu modifizierenden Matrizen kleiner?

Letztendlich wird eine Brute-Force-Suche nicht mehr in annehmbarer Zeit und mit durchschnittlicher Hardware durchführbar sein, wenn die Anzahl der Matrizen zu groß wird. Und im schlimmsten Fall, wenn alle Matrizen die gleiche Abmessung und die gleiche Spaltensumme besitzen, sind wir eben bei o.g. 150 Matrizen, und dann wirds nicht mehr schön...Es sei denn, du kannst diesen Fall theoretisch ausschließen!

Aber, was willst du damit eigentlich wirklich bezwecken? Klingt ja schön, aber hat das einen praktischen Nutzen, willst du lineare Abbildungen (sind das deine Matrizen?) in Äquivalenzklassen einteilen? Oder ist das irgendeine Logik-Tabelle?

Ich hab die Frage noch in einem anderen Forum gestellt und da schon erklärt wozu das Ganze gut sein soll, darf ich einfach den Link hier posten? Das wäre dann hier: http://forum.ubuntuusers.de/post/1926889/

Huups, Adjazenzmatrizen gibts ja auch noch
Naja, mit Graphentheorie will ich mich nie mehr beschäftigen...
Aber wie du im anderen Forum schon gesagt hast: Beweis ausdenken! Ich glaub das hilft mehr als das Prinzip der "unvollständigen Induktion" mit Hilfe des Computers

Besser wäre es allemal, aber mir fällt nichts ein. Mein Wissen über die Graphentheorie basiert auf der Wikipedia, das kann ja nicht funktionieren.