Zum Testen einer Methode zur Matrix-Multiplikation wollte ich gern Matrizen haben, dass das Ergebnis einer Matrixmultiplikation eine ganzzahlige Matrix mit „schönem“ Aussehen ist, so dass die Korrektheit der Implementation leicht überprüft werden kann. Sämtliche Matrizen sollten nach möglichkeit ganzzahlig sein. Um das Ziel zu erreichen habe ich einen Matrix-Generator geschrieben, mit dem ich das vorgestellte Verfahren erleutere. Der Generator benutzt meine simple Implementation einer Matrix-Klasse, die die wichtigsten Methoden bereitstellt.

Zuerst wollte ich eine Einheitsmatrix erzeugen, ich suchte also zwei Matrizen $A$ und $B$ mit $A\times B=E$. Dies würde jede invertierbare Matrix erfüllen. Zusätzlich sollten nun aber $A$ und $B$ noch ganzzahlig sein. Allgemein ist für eine ganzzahlige Matrix $A$ die Inverse $A^{–1}$ zwar rational, aber nicht ganzzahlig.

Meine Kenntnisse der linearen Algebra waren etwas eingerostet, aber nach kurzer Suche fand ich einen Artikel von Nathan Brixius, der ebenfalls über die Erzeugung spezieller Matrizen schrieb und mir bei der Erinnerung half. Für die Determinanten von Matrizen gilt $det(A)·det(B)=det(\mathrm{AB})$ und die Determinante der Einheitsmatrix ist natürlich 1. Außerdem kann man die Determinante von Matrizen in oberer oder unterer Dreiecksform als Produkt der Diagonalen leicht bestimmen.

Wir erzeugen zunächst eine Matrix in unterer Dreiecksform:

double[][] values = new double[dimension][dimension];
for( int i = 0; i < dimension; ++i )
	values[i][i] = 1;
for( int i = 1; i < dimension; ++i )
	for( int j = 0; j < i; ++j )
		values[i][j] = getValue(i, j);
Matrix lowerTriangular = new Matrix( values );

Es wird ein 2-dimensionales Array erzeugt, das die Werte enthält. Die Diagonale wird mit $1$ gefüllt und die untere Hälfte mit Werten, die in der Methode getValue erzeugt werden (z.B. zufällig).

Genauso wird eine Matrix in oberer Dreiecksform benötigt:

values = new double[dimension][dimension];
for( int i = 0; i < dimension; ++i )
	values[i][i] = 1;
for( int i = 0; i < dimension-1; ++i )
	for( int j = i+1; j < dimension; ++j )
		values[i][j] = getValue(i, j);
Matrix upperTriangular = new Matrix( values );

Das Prinzip entspricht dem der LU-Zerlegung einer Matrix: Es werden zwei Matrizen L und U in unterer beziehungsweise oberer Dreiecksform erzeugt, so dass die Determinante 1 ist (d.h. die Diagonale ist 1). Die Matrix $M:=L\times U$ ist ganzzahlig und invertierbar und nach der Bestimmung der Inversen über die Determinante ist die inverse Matrix $A^{–1}$ ebenfalls ganzzahlig.

Matrix matrix = lowerTriangular.mult( upperTriangular );
Matrix inverse = matrix.invert();

Mögliche Matrizen als Testinstanzen sind damit also $M$ und $A^{–1}$. Um Abwechslung zu erzeugen kann man nun beliebige Matrizen $F$ an $M$ von links anmultiplizieren (oder an $A^{–1}$ von rechts) und erhält als Ergebnis nicht mehr die Einheitsmatrix, sondern $F$: $F\times M\times M^{–1}=F\times E=F$.

Als Beispiel erzeugen wir eine Matrix, die natürliche Zahlen von 1 aufsteigend enthält:

values = new double[dimension][dimension];
int c = 1;
for( int i = 0; i < dimension; ++i )
	for( int j = 0; j < dimension; ++j )
		values[i][j] = c++;
Matrix F = new Matrix( values );

Damit kann die Ausgabematrix erstellt werden:

Matrix result = matrix.mult( inverse );

Die beiden Testinstanzen sind dann result und inverse, das Ergebnis der Multiplikation ist $F$. Natürlich kann $F$ auch rationale Zahlen enthalten, dann ist natürlich die Eingabematrix auch nicht mehr ganzzahlig.