Prostopadłe macierz jest macierzą kwadratową prawdziwych pozycji których kolumny i rzędy prostopadłych wektor jednostkowy (tj wektorów ortonormalnych).

Oznacza to, że M ^ TM = I, gdzie I jest macierzą tożsamości, a ^ T oznacza transpozycję macierzy.

Zauważ, że jest to ortogonalny, a nie „specjalny ortogonalny”, więc wyznacznikiem M może być 1 lub -1.

Celem tego wyzwania nie jest precyzja maszyny, więc jeśli M ^ TM = I do 4 miejsc po przecinku, będzie dobrze.

Zadanie polega na napisaniu kodu, który przyjmuje dodatnią liczbę całkowitą n > 1i generuje losową prostopadłą macierz n na n . Macierz powinna być losowo i jednolicie wybrana ze wszystkich n przez n macierzy ortogonalnych. W tym kontekście „jednolity” jest definiowany w kategoriach miary Haara, która zasadniczo wymaga, aby rozkład nie zmieniał się, jeśli zostanie pomnożony przez dowolną dowolnie wybraną macierz ortogonalną. Oznacza to, że wartości macierzy będą wartościami zmiennoprzecinkowymi z zakresu od -1 do 1.

Dane wejściowe i wyjściowe mogą mieć dowolną formę, którą uznasz za dogodną.

Pokaż wyraźny przykład działającego kodu.

Nie możesz używać żadnej istniejącej funkcji bibliotecznej, która tworzy macierze ortogonalne. Ta zasada jest trochę subtelna, więc wyjaśnię więcej. Ta reguła zabrania używania dowolnej istniejącej funkcji, która pobiera niektóre (lub nie) dane wejściowe i generuje macierz wielkości co najmniej n na n, która jest gwarantowana jako ortogonalna. Jako skrajny przykład, jeśli chcesz macierzy tożsamości n na n, będziesz musiał ją stworzyć sam.

Możesz użyć dowolnej standardowej biblioteki generatora liczb losowych do wyboru wybranych liczb losowych.

Twój kod powinien zakończyć się w ciągu najwyżej kilku sekund n < 50.

Haskell, 169 150 148 141 132 131 bajtów

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

Rekurencyjnie rozszerz ortogonalną macierz wielkości n-1, dodając 1 do prawego dolnego rogu i zastosuj losowe odbicie Householdera. randndaje macierz z losowymi wartościami z rozkładu gaussowskiego i z ddaje równomiernie rozłożony wektor jednostkowy w dwymiarach.

haussholder tau vzwraca macierz, I - tau*v*vᵀktóra nie jest ortogonalna, gdy vnie jest wektorem jednostkowym.

Stosowanie:

*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 bajty

Dzięki xnor za wskazanie, aby użyć normalnie rozmieszczonych losowych wartości zamiast jednolitych.

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

Wykorzystuje ortogonalizację Grama Schmidta na macierzy z losowymi wartościami gaussowskimi, aby mieć wszystkie kierunki.

Po kodzie demonstracyjnym następuje

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]]

Wykonuje się w mgnieniu oka dla n = 50 i kilku sekund dla n = 500.

Mathematica, 69 bajtów, prawdopodobnie nie konkuruje

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

QRDecompositionzwraca parę macierzy, z których pierwsza gwarantuje, że jest ortogonalna (a druga nie jest ortogonalna, ale górna trójkątna). Można argumentować, że technicznie jest to zgodne z literą ograniczenia w poście: nie wyprowadza matrycy ortogonalnej, ale parę macierzy ...

Mathematica, 63 bajty, zdecydowanie niekonkurujące

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

Orthogonalizejest jednoznacznie zabroniony przez OP. Nadal Mathematica jest całkiem fajna, prawda?