Verificar pares propios

21

En este desafío, se le dará una matriz cuadrada A, un vector vy un escalar λ. Se le pedirá que determine si (λ, v)es un par propio correspondiente a A; es decir, sea o no Av = λv.

Producto de punto

El producto punto de dos vectores es la suma de la multiplicación por elementos. Por ejemplo, el producto escalar de los siguientes dos vectores es:

(1, 2, 3) * (4, 5, 6) = 1*4 + 2*5 + 3*6 = 32

Tenga en cuenta que el producto escalar solo se define entre dos vectores de la misma longitud.

Multiplicación Matriz-Vector

Una matriz es una cuadrícula de valores 2D. Una matriz mx ntiene mfilas y ncolumnas. Podemos imaginar una matriz mx ncomo mvectores de longitud n(si tomamos las filas).

La multiplicación matriz-vector se define entre una matriz mx ny un nvector tamaño . Si multiplicamos una matriz mx ny un nvector de tamaño , obtenemos un mvector de tamaño . El ivalor -th en el vector resultante es el producto de punto de la ifila -th de la matriz y el vector original.

Ejemplo

        1 2 3 4 5
Let A = 3 4 5 6 7
        5 6 7 8 9

        1
        3
Let v = 5
        7
        9

Si multiplicamos la matriz y el vector Av = x, obtenemos lo siguiente:

x 1 = A T 1 * v /* AT1 means the first row of A; A1 would be the first column */= (1,2,3,4,5) * (1,3,5,7,9) = 1 * 1 + 2 * 3 + 3 * 5 + 4 * 7 + 5 * 9 = 1 + 6 + 15 + 28 + 45 = 95

x 2 = A T 2 * v = (3,4,5,6,7) * (1,3,5,7,9) = 3 * 1 + 4 * 3 + 5 * 5 + 6 * 7 + 7 * 9 = 3 + 12 + 25 + 42 + 63 = 145

x 3 = A T 3 * v = (5,6,7,8,9) * (1,3,5,7,9) = 5 * 1 + 6 * 3 + 7 * 5 + 8 * 7 + 9 * 9 = 5 + 18 + 35 + 56 + 81 = 195

Entonces, lo tenemos Av = x = (95, 145, 195).

Multiplicación escalar

La multiplicación de un escalar (un número único) y un vector es simplemente una multiplicación por elementos. Por ejemplo, 3 * (1, 2, 3) = (3, 6, 9). Es bastante sencillo.

Valores propios y vectores propios

Dada la matriz A, decimos que λes un valor propio correspondiente a vy ves un vector propio correspondiente a λ si y solo si Av = λv . (Donde Aves la multiplicación matriz-vector y λvla multiplicación escalar).

(λ, v) es un eigenpair

Especificaciones del desafío

Entrada

La entrada consistirá en una matriz, un vector y un escalar. Estos se pueden tomar en cualquier orden en cualquier formato razonable.

Salida

La salida será un valor verdadero / falso; Verdaderamente si y solo si el escalar y el vector son un par propio con la matriz especificada.

Reglas

  • Se aplican lagunas estándar
  • Si existe un incorporado para verificar un par propio en su idioma, no puede usarlo.
  • Puede suponer que todos los números son enteros

Casos de prueba

 MATRIX  VECTOR  EIGENVALUE
 2 -3 -1    3
 1 -2 -1    1    1    ->    TRUE
 1 -3  0    0

 2 -3 -1    1
 1 -2 -1    1    -2   ->    TRUE
 1 -3  0    1

 1  6  3    1
 0 -2  0    0    4    ->    TRUE
 3  6  1    1

 1  0 -1    2
-1  1  1    1    7    ->    FALSE
 1  0  0    0

-4 3    1    
 2 1    2    2    ->    TRUE

2    1    2    ->    TRUE

Agregaré un 4x4 más tarde.

Casos de prueba ilegibles que son más fáciles de probar

Hiperneutrino
fuente
Relacionado.
Martin Ender
@MartinEnder Gracias. Originalmente tuve un desafío similar para las matrices de tamaño arbitrario, donde se suponía que debía calcular una base para cada espacio propio único, pero eso todavía está en la caja de arena porque parece demasiado confuso.
HyperNeutrino
Si las entradas pueden tener otras dimensiones que 3x3, debe cubrir algo de eso en sus casos de prueba.
Martin Ender
1
@HyperNeutrino, sí, eso no ayuda ... No trates de explicármelo: estoy en la escuela secundaria estudiando matemáticas para GCSE, así que me perdí.
caird coinheringaahing
1
@ user00001 Si necesita ayuda, eigenpair-aphrase para usted. : P
mbomb007

Respuestas:

11

Jalea , 5 bytes

æ.⁵⁼×

Este es un programa triádico completo.

Pruébalo en línea!

Cómo funciona

æ.⁵⁼×  Main link
       Left argument:  v (eigenvector)
       Right argument: λ (eigenvalue)
       Third argument: A (matrix)

  ⁵    Third; yield A.
æ.     Take the dot product of v and A, yielding Av.
    ×  Multiply v and λ component by component, yielding λv.
   ⁼   Test the results to the left and to the right for equality.
Dennis
fuente
> _> esto es demasiado corto: P Buena respuesta
HyperNeutrino
66
Eso es una locura hablar! : P
Dennis
Escribes algo y piensas "¡nada podría ser más corto!". Luego aparece MATL y reduce a la mitad el tamaño de su código. Luego aparece Jelly y mitades que> _>
HyperNeutrino
@HyperNeutrino No compares manzanas con naranjas. Los idiomas de golf tienen tan solo un byte por operación, algo que los idiomas normales rara vez tienen. La especificación tiene tres operaciones (dos multiplicaciones y una igualdad), y permitir que un byte adicional se duplique vpodría esperar tan solo cuatro bytes.
Sanchises
2
Me gusta cómo Jelly y MATL usan dos bytes para la multiplicación de matrices, lo que significa que esta respuesta realmente muestra cuán bueno es Jelly para tomar datos, todo lo demás es igual.
Sanchises
13

Mathematica, 10 bytes

#2.#==#3#&

Toma entrada como {vector, matrix, scalar}y devuelve un booleano.

Martin Ender
fuente
1
> _> esto fue demasiado fácil para Mathematica. +1: P
HyperNeutrino
99
@HyperNeutrino Y ahora esperamos MATL ...
Martin Ender
2
Bueno MATL ha aparecido> _>
HyperNeutrino
1
Uno de esos momentos en los que crees que nada puede ser más corto y MATL aparece de repente :)
Sr. Xcoder
@ Mr.Xcoder Y luego aparece Jelly.
Steadybox
11

MATL, 7 bytes

*i2GY*=

Entradas en orden: l, v, A.

Explicación:

*  % implicitly get l and v, multiply.
i  % get A
2G % get second input, i.e., v again
Y* % perform matrix multiplication
=  % test equality of both multiplications

Una respuesta sorprendentemente larga, si me preguntas, sobre todo porque necesitaba una forma de obtener toda la información correctamente. No creo que sea posible menos de 5 bytes, pero sería genial si alguien encontrara una solución de 5 o 6 bytes.

Básicamente, esto calcula l*v==A*v.

Sanchises
fuente
"Sorprendentemente largo" esperaba al menos 20 bytes> _> buena respuesta: P
HyperNeutrino
2
Bueno, considerando que la respuesta de MATLAB vendría en 16 bytes @(A,v,l)A*v==v*l, esto parece bastante detallado, y tengo la sensación de que 6 debería ser suficiente si obtengo la entrada algo más inteligente.
Sanchises
Aparentemente llegó a 38 bytes, pero estoy bastante seguro de que se puede reducir.
HyperNeutrino
3
@HyperNeutrino Agregué el mío para que el comentario anterior sea verdadero. (o verdad ...?)
Sanchises
6

CJam , 15 bytes

q~W$f.*::+@@f*=

Toma entrada en el formulario vector scalar matrix.

Pruébalo en línea!

Explicación

q~               e# Read and eval the input
  W$             e# Copy the bottom most value (the vector)
    f.*::+       e# Perform element-wise multiplication with each row of the matrix, then
                 e#   sum the results of each (ie dot product with each row) 
          @@     e# Move the resulting vector to the bottom of the stack
            f*   e# Element-wise multiplication of the scalar and the vector
              =  e# Check if the two vectors are equal
Gato de negocios
fuente
5

MATLAB, 16 bytes

@(A,v,l)A*v==v*l

Respuesta bastante trivial. Define una función anónima que toma las entradas y calcula la igualdad entre elementos de los vectores resultantes. Un solo cero en una matriz lógica hace que una matriz falsey en MATLAB.

Sanchises
fuente
No estaba al tanto de la incertidumbre de [true,false], por ejemplo , gracias por enseñarme =)
error
1
@flawr Vea esta respuesta de Suever (que también es aplicable a MATLAB). Básicamente, se llama un []implícito casi pero no del todo (la matriz vacía es diferente) all()en la entrada de if, whileetc.
Sanchises
2

MATLAB, 38 bytes

function r=f(m,v,s);r=isequal(m*v,s*v)

Devuelve 1 o 0.

MATLAB, 30 bytes

function r=f(m,v,s);r=m*v==s*v

Devoluciones

1
1
1

como un valor de verdad. Un valor falso es un vector similar con cualquiera o todos los valores 0 en lugar de 1.

Steadybox
fuente
No sé MATLAB, pero ¿se isequalpuede acortar la función ==?
HyperNeutrino
1
Se isequalnecesitaría @HyperNeutrino si la producción fuera necesaria trueo falseno un valor verdadero o falso. Tal como está el desafío, de ==hecho es suficiente.
Sanchises
@HyperNeutrino Devuelve un vector que contiene los resultados de la comparación por elementos de los dos vectores.
Steadybox
Ah, vale. Buena respuesta sin embargo!
HyperNeutrino
¿No sería más corta una función anónima?
Batman el
2

C ++, 225 203 bytes

¡Gracias a @Cort Ammon y @Julian Wolf por guardar 22 bytes!

#import<vector>
#define F(v,i)for(i=0;i<v.size();++i)
using V=std::vector<float>;int f(std::vector<V>m,V v,float s){V p;int i,j;F(m,i){p.push_back(0);F(v,j)p[i]+=v[j]*m[i][j];}F(v,i)v[i]*=s;return v==p;}

Pruébalo en línea!

Steadybox
fuente
1
using std::vector;podría golf dos bytes de esto. Cuesta 18 bytes, pero puede eliminar 4 std::s, ahorrando 20.
Cort Ammon - Reinstalar Monica
2
mejor aún, using V=std::vector<float>;o similar
Julian Wolf el
2

Python 2.7, 33 bytes

f=lambda m,s,e:all(m.dot(s)==e*s)

entrada: m = matriz, s = escalar, e = valor propio. M y s son matrices numpy

HonzaB
fuente
2
Esto se ve bien, pero creo que debe incluir el recuento de bytes import nppara que sea válido
DJMcMayhem
1
Su anterior print(m,s,e)afirmación no hubiera funcionado porque las variables m, sy efueron sin asignación / definida. Además, puede eliminar el espacio después de los dos puntos. Además, puede eliminar la parte `como n` y usarla numpymás adelante; ya que solo lo usa una vez, usar el nombre completo realmente guarda un byte.
HyperNeutrino
1
OK entiendo ahora. Gracias por las sugerencias, apretando cada bit :)
HonzaB
2
¿No debería ser en alllugar deany ? Y yo piensos es el vector, no el escalar, a menos que me falte algo
Luis Mendo
1
Sería aún más corto comparar representaciones de cadenas. tio.run/nexus/python2#jZDPCoMwDIfP@hQ9tiOV/hEHgk/…
Dennis
1

05AB1E , 11 bytes

vy²*O})²³*Q

Pruébalo en línea!

vy²*O})     # Vectorized product-sum.
       ²³*  # Vector * scalar.
          Q # Equivalence.
Urna de pulpo mágico
fuente
1

R, 30 25 bytes

s=pryr::f(all(a%*%v==λ*v))

Función anónima, bastante sencilla. Devoluciones TRUEo FALSE.

rturnbull
fuente
0

ok, 12 bytes

{y~z%+/y*+x}

Esta es una función, toma en cuenta [matrix;vector;scalar].

Esto no funciona en k por las mismas razones que 3.0~3da 0como resultado.


Lo siguiente funciona en k , con 14 bytes :

{(y*z)~+/y*+x}
zgrep
fuente
0

Axioma, 27 bytes

f(a,b,c)==(a*b=c*b)@Boolean

ceremonias

(17) -> m:=matrix[[2,-3,-1],[1,-2,-1],[1,-3,0] ]; v:=matrix[[3],[1],[0]];
(18) -> f(m,v,1)
   (18)  true

(19) -> m:=matrix[[2,-3,-1],[1,-2,-1],[1,-3,0] ]; v:=matrix[[1],[1],[1]];
(20) -> f(m,v,-2)
   (20)  true

(21) -> m:=matrix[[1,6,3],[0,-2,0],[3,6,1] ]; v:=matrix[[1],[0],[1]];
(22) -> f(m,v,4)
   (22)  true

(23) -> m:=matrix[[1,0,-1],[-1,1,1],[1,0,0] ]; v:=matrix[[2],[1],[0]];
(24) -> f(m,v,7)
   (24)  false

(25) -> m:=matrix[[-4,3],[2,1] ]; v:=matrix[[1],[2]];
(26) -> f(m,v,2)
   (26)  true

(27) -> f(2,1,2)
   (27)  true
RosLuP
fuente
No he visto este idioma antes, ¡buena respuesta! ¿Qué hace el @Boolean?
HyperNeutrino
(a = b) @Boolean significaría "elegir entre permitido = operador (tipo1, tipo2) el resultado que es booleano"; en pocas palabras "a = b" tiene que ser booleano
RosLuP
0

Python, 26 bytes

lambda a,b,c:c*b==a.dot(b)

a y b son matrices numpy,c es un entero.

Pruébalo en línea!

Rɪᴋᴇʀ
fuente
2
¿Son c*brealmente necesarios los parens ?
xnor
@xnor gracias, arreglado.
Rɪᴋᴇʀ
Esto solo funciona para arreglos pequeños, ya que NumPy abrevia las representaciones de cadenas de arreglos grandes.
user2357112 es compatible con Monica el
@ user2357112 ejemplo? No estoy seguro de lo que quieres decir.
Rɪᴋᴇʀ
Si c*btiene más de 1000 elementos, NumPy reemplazará la mayoría de los elementos con .... Manifestación.
user2357112 es compatible con Monica el
0

Clojure, 60 bytes

#(=(set(map(fn[a v](apply -(* v %3)(map * a %2)))% %2))#{0})

Esto comprueba que todos los deltas son cero, colapsándose así en el conjunto de cero. Ejemplo de llamada:

(def f #(=(set(map(fn[a v](apply -(* v %3)(map * a %2)))% %2))#{0}))
(f [[1 6 3][0 -2 0][3 6 1]] [1 0 1] 4)
NikoNyrh
fuente