permutationsmatrix für reduzible matrizen

Neue Frage »

derive Auf diesen Beitrag antworten »
permutationsmatrix für reduzible matrizen
Hallo,

Eine nichtnegative Matrix heißt reduzibel, wenn sie mit einer geeigneten Permutationsmatrix P in Blockdreiecksmatrix gebracht werden kann, wobei die quadratischen Blöcke jeweils irreduzibel sind.

Als Beispiel:


Hierbei sind A_{11}, A_{22}, A_{33} quadratisch und irreduzibel.

Für kleine Matrizen kann ich die Permutationsmatrizen ja durchprobieren, bzw. durch scharfes Hinschauen rausfinden. Ich bin aber interessiert an einem numerischen Verfahren, welches mir diese Permutationsmatrizen liefert, bzw. eigentlich genügt es, die Matrix A in eben diese Blockdreiecksmatrix zu überführen.

Ich hab schon viel im Netz und in der Bibliothek geschaut, aber leider nichts brauchbares gefunden. Über online-Links oder Buchverweise bin ich sehr dankbar.

Lieben Gruß
derive Auf diesen Beitrag antworten »
RE: permutationsmatrix für reduzible matrizen
weiß da niemand was?
kiste Auf diesen Beitrag antworten »

Wenn es alleine darum geht die Permutationen zu finden:
Da hilft ein einfaches Backtracking-Verfahren.
Hilfsarray A[1..n]

ne Funktion f(M,A,i) die folgendes macht:
wenn i=n+1: Fertig du hast ne Perm
sonst:
für alle j aus M:
Setze A[i]=j.
Führe f(M\{j},A,i+1) aus

und dann aufrufen mit f({1,..,n},A,1)
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »