Eine orthogonale Matrix ist eine quadratische Matrix mit reellen Einträgen, deren Spalten und Zeilen orthogonale Einheitsvektoren (dh orthonormale Vektoren) sind.

Dies bedeutet, dass M ^ TM = I ist, wobei I die Identitätsmatrix ist und ^ T die Matrixtransposition bedeutet.

Es ist zu beachten, dass dies orthogonal und nicht "speziell orthogonal" ist, so dass die Determinante von M 1 oder -1 sein kann.

Das Ziel dieser Herausforderung ist nicht die Maschinengenauigkeit. Wenn also M ^ TM = I innerhalb von 4 Dezimalstellen liegt, ist dies in Ordnung.

Die Aufgabe besteht darin, Code zu schreiben, der eine positive ganze Zahl nimmt n > 1und eine zufällige orthogonale n mal n-Matrix ausgibt . Die Matrix sollte zufällig und gleichmäßig aus allen n x n orthogonalen Matrizen ausgewählt werden. In diesem Zusammenhang wird "einheitlich" als Haar-Maß definiert, das im Wesentlichen erfordert, dass sich die Verteilung nicht ändert, wenn sie mit einer frei gewählten orthogonalen Matrix multipliziert wird. Dies bedeutet, dass die Werte der Matrix Gleitkommawerte im Bereich von -1 bis 1 sind.

Die Eingabe und Ausgabe kann jede Form sein, die Sie für bequem halten.

Bitte zeigen Sie ein explizites Beispiel für die Ausführung Ihres Codes.

Sie dürfen keine vorhandene Bibliotheksfunktion verwenden, die orthogonale Matrizen erstellt. Diese Regel ist etwas subtil, daher werde ich mehr erklären. Diese Regel verbietet die Verwendung einer vorhandenen Funktion, die einige (oder keine) Eingaben aufnimmt und eine Matrix mit einer Größe von mindestens n mal n ausgibt, die garantiert orthogonal ist. Wenn Sie als extremes Beispiel die n x n-Identitätsmatrix verwenden möchten, müssen Sie sie selbst erstellen.

Sie können jede Standardbibliothek für Zufallszahlengeneratoren verwenden, um Zufallszahlen Ihrer Wahl auszuwählen.

Ihr Code sollte innerhalb von höchstens ein paar Sekunden abgeschlossen sein n < 50.

Haskell, 169 150 148 141 132 131 Bytes

import Numeric.LinearAlgebra
z=(unitary.flatten<$>).randn 1
r 1=asRow<$>z 1
r n=do;m<-r$n-1;(<>diagBlock[m,1]).haussholder 2<$>z n

Erweitern Sie rekursiv eine orthogonale Matrix der Größe, n-1indem Sie 1 zur unteren rechten Ecke hinzufügen und eine zufällige Householder-Reflexion anwenden.randnergibt eine Matrix mit Zufallswerten aus einer Gaußschen Verteilung und z dergibt einen gleichmäßig verteilten Einheitsvektor in dDimensionen.

haussholder tau vGibt die Matrix zurück, I - tau*v*vᵀdie nicht orthogonal ist, wenn ves sich nicht um einen Einheitsvektor handelt.

Verwendungszweck:

*Main> m <- r 5
*Main> disp 5 m
5x5
-0.24045  -0.17761   0.01603  -0.83299  -0.46531
-0.94274   0.12031   0.00566   0.29741  -0.09098
-0.02069   0.30417  -0.93612  -0.13759   0.10865
 0.02155  -0.83065  -0.35109   0.32365  -0.28556
-0.22919  -0.41411   0.01141  -0.30659   0.82575
*Main> (<1e-14) . maxElement . abs $ tr m <> m - ident 5
True

Python 2 + NumPy, 163 Bytes

Vielen Dank an xnor für den Hinweis, normalverteilte Zufallswerte anstelle einheitlicher Werte zu verwenden.

from numpy import*
n=input()
Q=random.randn(n,n)
for i in range(n):
 for j in range(i):u=Q[:,j];Q[:,i]-=u*dot(u,Q[:,i])/dot(u,u)
Q/=(Q**2).sum(axis=0)**0.5
print Q

Verwendet die Gram-Schmidt- Orthogonalisierung auf einer Matrix mit Gaußschen Zufallswerten, um alle Richtungen zu haben.

Dem Demonstrationscode folgt

print dot(Q.transpose(),Q)

n = 3:

[[-0.2555327   0.89398324  0.36809917]
 [-0.55727299  0.17492767 -0.81169398]
 [ 0.79003155  0.41254608 -0.45349298]]
[[  1.00000000e+00   0.00000000e+00   0.00000000e+00]
 [  0.00000000e+00   1.00000000e+00  -5.55111512e-17]
 [  0.00000000e+00  -5.55111512e-17   1.00000000e+00]]

n = 5:

[[-0.63470728  0.41984536  0.41569193  0.25708079  0.42659843]
 [-0.36418389  0.06244462 -0.82734663 -0.24066123  0.3479231 ]
 [ 0.07863783  0.7048799   0.08914089 -0.64230492 -0.27651168]
 [ 0.67691426  0.33798442 -0.05984083  0.17555011  0.62702062]
 [-0.01095148 -0.45688226  0.36217501 -0.65773717  0.47681205]]
[[  1.00000000e+00   1.73472348e-16   5.37764278e-17   4.68375339e-17
   -2.23779328e-16]
 [  1.73472348e-16   1.00000000e+00   1.38777878e-16   3.33066907e-16
   -6.38378239e-16]
 [  5.37764278e-17   1.38777878e-16   1.00000000e+00   1.38777878e-16
    1.11022302e-16]
 [  4.68375339e-17   3.33066907e-16   1.38777878e-16   1.00000000e+00
    5.55111512e-16]
 [ -2.23779328e-16  -6.38378239e-16   1.11022302e-16   5.55111512e-16
    1.00000000e+00]]

Es wird innerhalb eines Augenblicks für n = 50 und einige Sekunden für n = 500 abgeschlossen.

Mathematica, 69 Bytes, wahrscheinlich nicht konkurrierend

#&@@QRDecomposition@Array[RandomVariate@NormalDistribution[]&,{#,#}]&

QRDecompositiongibt ein Paar Matrizen zurück, von denen die erste garantiert orthogonal ist (und die zweite nicht orthogonal, sondern oberes Dreieck ist). Man könnte argumentieren, dass dies technisch dem Buchstaben der Einschränkung im Beitrag entspricht: Es wird keine orthogonale Matrix ausgegeben, sondern ein Paar Matrizen ....

Mathematica, 63 Bytes, definitiv nicht konkurrierend

Orthogonalize@Array[RandomVariate@NormalDistribution[]&,{#,#}]&

Orthogonalizeist vom OP eindeutig verboten. Trotzdem ist Mathematica ziemlich cool, oder?