Una matriz ortogonal es una matriz cuadrada con entradas reales cuyas columnas y filas son vectores unitarios ortogonales (es decir, vectores ortonormales).
Esto significa que M ^ TM = I, donde I es la matriz de identidad y ^ T significa la transposición de la matriz.
Tenga en cuenta que esto es ortogonal no "ortogonal especial", por lo que el determinante de M puede ser 1 o -1.
El objetivo de este desafío no es la precisión de la máquina, por lo que si M ^ TM = I dentro de 4 decimales estará bien.
La tarea es escribir código que tome un número entero positivo n > 1
y genere una matriz ortogonal aleatoria n por n . La matriz debe elegirse aleatoria y uniformemente de todas las matrices n por n ortogonales. En este contexto, "uniforme" se define en términos de la medida de Haar, que esencialmente requiere que la distribución no cambie si se multiplica por cualquier matriz ortogonal elegida libremente. Esto significa que los valores de la matriz serán valores de coma flotante en el rango de -1 a 1.
La entrada y la salida pueden ser de cualquier forma que le resulte conveniente.
Muestre un ejemplo explícito de su código en ejecución.
No puede usar ninguna función de biblioteca existente que cree matrices ortogonales. Esta regla es un poco sutil, así que explicaré más. Esta regla prohíbe el uso de cualquier función existente que tome alguna (o ninguna) entrada y genere una matriz de tamaño al menos n por n que se garantice que sea ortogonal. Como ejemplo extremo, si desea la matriz de identidad n por n, tendrá que crearla usted mismo.
Puede usar cualquier biblioteca generadora de números aleatorios estándar para elegir números aleatorios de su elección.
Su código debe completarse en unos segundos como máximo n < 50
.
diag
? Crea una matriz diagonal que es de hecho ortogonal pero no siempre ortonormal.diag
deberían estar bien.Respuestas:
Haskell,
169150148141132131 bytesExtienda recursivamente una matriz de tamaño ortogonal
n-1
agregando 1 a la esquina inferior derecha y aplique una reflexión aleatoria de Householder.randn
da una matriz con valores aleatorios de una distribución gaussiana yz d
da un vector unitario distribuido uniformemente end
dimensiones.haussholder tau v
devuelve la matrizI - tau*v*vᵀ
que no es ortogonal cuandov
no es un vector unitario.Uso:
fuente
1×1
matriz toma demasiado espacio para mi gusto, un caso especial solo para obtener cero de una variable aleatoria gaussiana: / (Sin ella, existe una posibilidad infinitesimal de obtener una columna cero)Python 2 + NumPy, 163 bytes
Gracias a xnor por señalar el uso de valores aleatorios distribuidos normales en lugar de valores uniformes.
Utiliza la ortogonalización de Gram Schmidt en una matriz con valores aleatorios gaussianos para tener todas las direcciones.
El código de demostración es seguido por
n = 3:
n = 5:
Se completa en un abrir y cerrar por n = 50 y unos segundos por n = 500.
fuente
-0.5
n
.Mathematica, 69 bytes, probablemente no compitiendo
QRDecomposition
devuelve un par de matrices, la primera de las cuales se garantiza que es ortogonal (y la segunda no es ortogonal, sino triangular superior). Se podría argumentar que esto técnicamente obedece la letra de la restricción en la publicación: no genera una matriz ortogonal, sino un par de matrices ...Mathematica, 63 bytes, definitivamente no compite
Orthogonalize
está inequívocamente prohibido por el OP. Aún así, Mathematica es genial, ¿eh?fuente
You may not use any existing library function which creates orthogonal **matrices**.