¿Es la matriz positiva-definida?

19

Introducción

Hoy nos ocuparemos de la ruina de los estudiantes de primer año de álgebra lineal: ¡definición de matriz! Aparentemente, esto aún no tiene un desafío, así que aquí vamos:

Entrada

  • A Matriz simétrica en cualquier formato conveniente (por supuesto, también puede tomar la parte superior o inferior de la matriz)norte×norte UN
  • Opcionalmente: el tamaño de la matriznorte

¿Qué hacer?

El desafío es simple: dada una matriz de valores reales Matriz decide si es positiva definida al generar un valor verdadero si es así y un valor falso si no.norte×norte

Puede suponer que sus funciones integradas realmente funcionan con precisión y, por lo tanto, no tiene que tener en cuenta los problemas numéricos que podrían conducir a un comportamiento incorrecto si la estrategia / código "demostrablemente" debe producir el resultado correcto.

¿Quién gana?

Este es el , por lo que gana el código más corto en bytes (por idioma).


¿Qué es una matriz positiva definida de todos modos?

Aparentemente, hay 6 formulaciones equivalentes de cuándo una matriz simétrica es positiva definida. Reproduciré los tres más fáciles y lo remitiré a Wikipedia para los más complejos.

  • Si entonces es positivo-definido. Esto puede reformularse como: si para cada vector distinto de cero el producto de punto (estándar) de y es positivo, entonces es definitivo positivo.vRnorte{0 0}:vTUNv>0 0UN

    vvUNvUN
  • Deje que sean los valores propios de , si ahora (eso es todo los valores propios son positivos), entonces es positivo-definido. Si no sabe cuáles son los valores propios, le sugiero que use su motor de búsqueda favorito para averiguarlo, porque la explicación (y las estrategias de cálculo necesarias) es demasiado larga para estar contenida en esta publicación.λyoyo{1,...,norte}A i { 1 , ... , n } : λ i > 0 AUNi{1,,n}:λi>0A
  • Si existe la descomposición de Cholesky de , es decir, existe una matriz triangular inferior de modo que entonces es positivo-definido. Tenga en cuenta que esto es equivalente a "falso" de retorno temprano si en algún momento el cálculo de la raíz durante el algoritmo falla debido a un argumento negativo.ALLLT=AA

Ejemplos

Para una salida veraz

(100010001)

(1000020000300004)

(521211113)

(1222502030)

(7.152.452.459.37)

Para salida falsey

(al menos un valor propio es 0 / semi-definido positivo)

(322240202)

(los valores propios tienen signos diferentes / indefinidos)

(100010001)

(todos los valores propios más pequeños que 0 / negativo definido)

(100010001)

(todos los valores propios más pequeños que 0 / negativo definido)

(230350001)

(todos los valores propios más pequeños que 0 / negativo definido)

(7.152.452.459.37)

(tres valores propios positivos, uno negativo / indefinido)

(7.152.451.233.52.459.372.713.141.232.7106.23.53.146.20.56)

SEJPM
fuente
Debe proporcionar una mejor definición de lo que se supone que debemos estar buscando en lugar de asumir que todos podemos leer la notación matemática (o todos sabemos lo que es un "valor propio"). Un ejemplo trabajado también sería útil.
Shaggy
99
@ Shaggy Creo que el desafío es mejor sin todos los antecedentes para obstruirlo. Hay muchas explicaciones existentes de lo que es un valor propio en otros lugares, y esta publicación ya es realmente grande.
Wheat Wizard
1
El desafío hubiera sido mejor si no hubiera restringido la entrada a matrices simétricas .
polfosol ఠ_ఠ
1
Quise decir que verificar el signo de los valores propios también es aburrido. Diferentes gustos que conozco;)
polfosol ఠ_ఠ

Respuestas:

11

C, 108 bytes

-1 byte gracias a Logern
-3 bytes gracias a ceilingcat

f(M,n,i)double**M;{for(i=n*n;i--;)M[i/n][i%n]-=M[n][i%n]*M[i/n][n]/M[n][n];return M[n][n]>0&(!n||f(M,n-1));}

Pruébalo en línea!

Realiza la eliminación gaussiana y comprueba si todos los elementos diagonales son positivos (criterio de Sylvester). El argumento nes el tamaño de la matriz menos uno.

nwellnhof
fuente
¿Quizás guardar un personaje con flotante en lugar de doble?
Jens
Puede depilar otro carácter si coloca i=0el bucle for, realiza la llamada recursiva f(M,n-1,0)y la llamada inicial con 0 como tercer argumento.
Jens
@Jens 1. El uso de flotantes en lugar de dobles puede conducir rápidamente a errores de redondeo notables, por lo que no creo que el byte guardado valga la pena. 2. Inicializar una variable a través de un argumento adicional me parece una trampa.
nwellnhof
@Logern Me niego a usar el truco "omitir la declaración de devolución" en mis respuestas de C. Pero gracias por el otro byte guardado.
nwellnhof
9

MATLAB / Octave , 19 17 12 bytes

@(A)eig(A)>0

Pruébalo en línea!

La función eig proporciona los valores propios en orden ascendente, por lo que si el primer valor propio es mayor que cero, los otros también lo son.

Daniel Turizo
fuente
Puede descartar f=al principio: las funciones anónimas generalmente se aceptan como respuestas.
Delfad0r
¡Gracias por el consejo!
Daniel Turizo
¿Incluso si es un vector? Interesante
Daniel Turizo
1
+1. He agregado un enlace para probarlo en línea. Espero que no te importe. Tenga en cuenta que también está demostrando que los valores de salida a pesar de ser matrices cuentan como los valores correctos de "verdad" o "falsey" según el enlace publicado por @ Delfad0r.
Tom Carpenter
2
Dicho esto, falla para el primer caso de prueba "falsey" en TIO. Supongo que debido a un problema de precisión: uno de los valores de Eigen aparece en 8.9219e-17lugar de 0.
Tom Carpenter
7

Jalea , 11 10 bytes

ṖṖ€$ƬÆḊṂ>0

Utiliza el criterio de Sylvester .

Pruébalo en línea!

Cómo funciona

ṖṖ€$ƬÆḊṂ>0  Main link. Argument: M (matrix)

   $Ƭ       Do the following until a fixed point is encountered.
Ṗ             Pop; remove the last row of the matrix.
 Ṗ€           Pop each; remove the last entry of each row.
     ÆḊ     Take the determinants of the resulting minors.
       Ṃ    Take the minimum.
        >0  Test if the least determinant is positive, i.e., if all determinants are.
Dennis
fuente
6

Haskell , 56 bytes

f((x:y):z)=x>0&&f[zipWith(-)v$map(u/x*)y|u:v<-z]
f[]=1>0

Pruébalo en línea!

Básicamente un puerto de respuesta de nwellnhof . Realiza la eliminación gaussiana y comprueba si los elementos en la diagonal principal son positivos.

Falla la primera salida falsey debido a errores de redondeo, pero teóricamente funcionaría con una precisión infinita. Gracias a la sugerencia de Curtis Bechtel , ahora los resultados son correctos.

Delfad0r
fuente
2
puede agregar inputs :: [[[Rational]]]para obtener respuestas correctas
Curtis Bechtel
4

Wolfram Language (Mathematica) , 20 bytes

0<Min@Eigenvalues@#&

Pruébalo en línea!

Sr. Xcoder
fuente
¿Debería ser falso el cuarto caso de prueba?
tsh
@tsh Solucionado, ¡soy tonto!
Sr. Xcoder
8
Es curioso cómo Mathematica tiene algo incorporado para esto , pero su nombre es más largo que su solución.
Federico Poloni
@FedericoPoloni: ¿No sería aún más corta una solución con NullSpace o MatrixRank? Si el espacio nulo es cero, entonces la matriz es positiva definida.
Phil H
@ Phil No, me temo que eso no funciona por sí solo. Por ejemplo, el segundo ejemplo de falsey (matriz diagonal con (1, -1,1)) tiene rango 3, pero no es definitivo positivo.
Federico Poloni
3

MATL , 4 bytes

Yv0>

Pruébalo en línea!

[3 -2 2; -2 4 0; 2 0 2]01018 años

Sr. Xcoder
fuente
1
@LuisMendo ¡Gracias, hoy aprendí algo nuevo sobre MATL!
Sr. Xcoder
Mi placer :-) Aquí hay una mejor explicación de Suever. Olvidé decir que para las matrices de valores complejos solo la parte real se compara con cero. Así [1 2 3j]es Falsey
Luis Mendo
2

Mathematica, 29 28 bytes

AllTrue[Eigenvalues@#,#>0&]&

Definición 2.

Shieru Asakoto
fuente
2

MATL , 6 bytes

Es posible hacerlo utilizando incluso menos bytes, @Mr. ¡Xcoder logró encontrar una respuesta MATL de 5 bytes !

YvX<0>

Explicación

Yv     compute eigenvalues
  X<   take the minimum
    0> check whether it is greather than zero

Pruébalo en línea!

falla
fuente
Falla en el primer caso de prueba falso. Ver mi respuesta eliminada .
Sr. Xcoder
1
@ Mr.Xcoder Oh, incluso me enviaste una respuesta. Creo que debería recuperar su respuesta, ya que solo depende de los problemas de redondeo. (Creo que se puede esperar respuestas de usar aritmética de precisión limitada -. Creo que sólo los idiomas CAS aquí utilizan cálculos exactos)
flawr
Siguiendo tu consejo, lo he recuperado .
Sr. Xcoder
1

Arce , 33 bytes

(es decir, mis 2 centavos)

with(LinearAlgebra):
IsDefinite(A)
polfosol ఠ_ఠ
fuente
Hola y bienvenidos a PPCG; No estoy familiarizado con Maple, aunque ¿es necesaria la nueva línea?
Jonathan Frech
@JonathanFrech Hola y gracias. No, no es. No lo conté por cierto.
polfosol ఠ_ఠ
Para mí, su conteo actual de bytes parece reflejar el carácter de nueva línea.
Jonathan Frech
@JonathanFrech Duh, mi mal
polfosol ఠ_ఠ
1
Bueno ... ahora tu código y tu número de bytes no están de acuerdo.
Jonathan Frech