21
\$\begingroup\$

In this challenge, you will be given a square matrix A, a vector v, and a scalar λ. You will be required to determine if (λ, v) is an eigenpair corresponding to A; that is, whether or not Av = λv.

Dot Product

The dot product of two vectors is the sum of element-wise multiplication. For example, the dot product of the following two vectors is:

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

Note that the dot product is only defined between two vectors of the same length.

Matrix-Vector Multiplication

A matrix is a 2D grid of values. An m x n matrix has m rows and n columns. We can imagine an m x n matrix as m vectors of length n (if we take the rows).

Matrix-Vector multiplication is defined between an m x n matrix and a size-n vector. If we multiply an m x n matrix and a size-n vector, we obtain a size-m vector. The i-th value in the result vector is the dot product of the i-th row of the matrix and the original vector.

Example

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

        1
        3
Let v = 5
        7
        9

If we multiply the matrix and the vector Av = x, we get the following:

x1 = AT1 * 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

x2 = AT2 * 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

x3 = AT3 * 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

So, we get Av = x = (95, 145, 195).

Scalar Multiplication

Multiplication of a scalar (a single number) and a vector is simply element-wise multiplication. For example, 3 * (1, 2, 3) = (3, 6, 9). It's fairly straightforward.

Eigenvalues and Eigenvectors

Given the matrix A, we say that λ is an eigenvalue corresponding to v and v is an eigenvector corresponding to λ if and only if Av = λv. (Where Av is matrix-vector multiplication and λv is scalar multiplication).

(λ, v) is an eigenpair.

Challenge Specifications

Input

Input will consist of a matrix, a vector, and a scalar. These can be taken in any order in any reasonable format.

Output

Output will be a truthy/falsy value; truthy if and only if the scalar and the vector are an eigenpair with the matrix specified.

Rules

  • Standard loopholes apply
  • If a built-in for verifying an eigenpair exists in your language, you may not use it.
  • You may assume that all numbers are integers

Test Cases

 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

I will add a 4x4 later.

Unreadable Test Cases that are easier for testing

\$\endgroup\$
  • \$\begingroup\$ Related. \$\endgroup\$ – Martin Ender Apr 13 '17 at 14:07
  • \$\begingroup\$ @MartinEnder Thanks. I originally had a similar challenge for arbitrary sized matrices where you were meant to calculate a basis for each unique eigenspace but that's in the sandbox still because it seems too confusing. \$\endgroup\$ – HyperNeutrino Apr 13 '17 at 14:08
  • \$\begingroup\$ If inputs can have have other dimensions than 3x3, you should cover some of that in your test cases. \$\endgroup\$ – Martin Ender Apr 13 '17 at 14:22
  • 1
    \$\begingroup\$ @HyperNeutrino yeah that doesn't help... Don't try to explain it to me: I'm at high school studying maths for GCSE so its just lost on me. \$\endgroup\$ – caird coinheringaahing Apr 13 '17 at 14:46
  • 1
    \$\begingroup\$ @user00001 If you need help, eigenpair-aphrase it for you. :P \$\endgroup\$ – mbomb007 Apr 27 '17 at 21:49

16 Answers 16

11
\$\begingroup\$

Jelly, 5 bytes

æ.⁵⁼×

This is a triadic, full program.

Try it online!

How it works

æ.⁵⁼×  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.
\$\endgroup\$
  • \$\begingroup\$ >_> this is too short :P Nice answer \$\endgroup\$ – HyperNeutrino Apr 13 '17 at 18:54
  • 6
    \$\begingroup\$ That's crazy talk! :P \$\endgroup\$ – Dennis Apr 13 '17 at 19:12
  • \$\begingroup\$ You write something, and think "nothing could be shorter!". Then MATL comes along and halves your code size. Then Jelly comes along and halves that >_> \$\endgroup\$ – HyperNeutrino Apr 14 '17 at 3:13
  • \$\begingroup\$ @HyperNeutrino Don't compare apples to oranges. Golfing languages have as little as one byte per operation, something normal languages rarely have. The spec has three operations (two multiplications and an equality), and allowing for an extra byte to duplicate v one could expect as little as four bytes. \$\endgroup\$ – Sanchises Apr 14 '17 at 8:07
  • 2
    \$\begingroup\$ I like how both Jelly and MATL use two bytes for matrix multiplication, which means that this answer really shows how good Jelly is at taking input, all else being equal. \$\endgroup\$ – Sanchises Apr 14 '17 at 8:09
13
\$\begingroup\$

Mathematica, 10 bytes

#2.#==#3#&

Takes input like {vector, matrix, scalar} and returns a boolean.

\$\endgroup\$
  • 1
    \$\begingroup\$ >_> this was too easy for Mathematica. +1 :P \$\endgroup\$ – HyperNeutrino Apr 13 '17 at 14:16
  • 9
    \$\begingroup\$ @HyperNeutrino And now we wait for MATL... \$\endgroup\$ – Martin Ender Apr 13 '17 at 14:19
  • 2
    \$\begingroup\$ Well MATL has appeared >_> \$\endgroup\$ – HyperNeutrino Apr 13 '17 at 14:37
  • 1
    \$\begingroup\$ One of those moments when you think nothing can be shorter and MATL pops up suddenly :) \$\endgroup\$ – Mr. Xcoder Apr 13 '17 at 19:29
  • \$\begingroup\$ @Mr.Xcoder And then Jelly shows up. \$\endgroup\$ – Steadybox Apr 13 '17 at 23:14
11
\$\begingroup\$

MATL, 7 bytes

*i2GY*=

Inputs in order: l,v,A.

Explanation:

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

Surprisingly long answer, if you ask me, mostly because I needed a way to get all the input correctly. I do not think that less than 5 bytes is possible, but it would be cool if someone found a 5 or 6 byte solution.

Basically, this calculates l*v==A*v.

\$\endgroup\$
  • \$\begingroup\$ "Surprisingly long" I was expecting at least 20 bytes >_> nice answer though :P \$\endgroup\$ – HyperNeutrino Apr 13 '17 at 14:37
  • 2
    \$\begingroup\$ Well, considering that the MATLAB answer would come in at 16 bytes @(A,v,l)A*v==v*l, this seems quite verbose, and I have a feeling 6 should be plenty if I get the input somewhat smarter. \$\endgroup\$ – Sanchises Apr 13 '17 at 14:39
  • \$\begingroup\$ Apparently it came in at 38 bytes but I'm pretty sure it can be golfed down. \$\endgroup\$ – HyperNeutrino Apr 13 '17 at 14:41
  • 3
    \$\begingroup\$ @HyperNeutrino Added my own to make the previous comment true. (or truthy...?) \$\endgroup\$ – Sanchises Apr 13 '17 at 14:46
6
\$\begingroup\$

CJam, 15 bytes

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

Takes input in the form vector scalar matrix.

Try it online!

Explanation

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
\$\endgroup\$
5
\$\begingroup\$

MATLAB, 16 bytes

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

Rather trivial answer. Defines an anonymous function taking the inputs, and calculates element-wise equality of the resulting vectors. A single zero in a logical array makes an array falsey in MATLAB.

\$\endgroup\$
  • \$\begingroup\$ Wasn't aware of the falseyness of e.g. [true,false], thanks for teaching me=) \$\endgroup\$ – flawr Apr 13 '17 at 15:30
  • 1
    \$\begingroup\$ @flawr See this answer by Suever (which is also applicable to MATLAB). Basically, an almost-but-not-quite (empty matrix [] is different) implicit all() is called on the input of if, while etc. \$\endgroup\$ – Sanchises Apr 13 '17 at 15:38
2
\$\begingroup\$

MATLAB, 38 bytes

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

Returns 1 or 0.

MATLAB, 30 bytes

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

Returns

1
1
1

as a truthy value. A falsy value is a similar vector with any or all values 0 instead of 1.

\$\endgroup\$
  • \$\begingroup\$ I don't know MATLAB, but can the isequal function be shortened to ==? \$\endgroup\$ – HyperNeutrino Apr 13 '17 at 14:41
  • 1
    \$\begingroup\$ @HyperNeutrino isequal would be needed if the output required true or false rather than a truthy or falsey value. As the challenge stands, == is indeed enough. \$\endgroup\$ – Sanchises Apr 13 '17 at 14:42
  • \$\begingroup\$ @HyperNeutrino It would return a vector containing the results of elementwise comparison of the two vectors. \$\endgroup\$ – Steadybox Apr 13 '17 at 14:43
  • \$\begingroup\$ Oh okay. Nice answer though! \$\endgroup\$ – HyperNeutrino Apr 13 '17 at 14:43
  • \$\begingroup\$ wouldn't an annonymous function be shorter? \$\endgroup\$ – Batman Apr 13 '17 at 23:36
2
\$\begingroup\$

C++, 225 203 bytes

Thanks to @Cort Ammon and @Julian Wolf for saving 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;}

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ using std::vector; could golf two bytes off this. It costs 18 bytes, but can remove 4 std::s, saving 20. \$\endgroup\$ – Cort Ammon Apr 13 '17 at 17:21
  • 2
    \$\begingroup\$ better yet, using V=std::vector<float>; or similar \$\endgroup\$ – Julian Wolf Apr 13 '17 at 19:05
2
\$\begingroup\$

Julia, 17 bytes

(a,b,c)->a*b==b*c

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 2.7, 33 bytes

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

input: m=matrix, s=scalar, e=eigenvalue. M and s are numpy arrays

\$\endgroup\$
  • 2
    \$\begingroup\$ This looks good, but I think you need to include the byte count of import np for it to be valid \$\endgroup\$ – DJMcMayhem Apr 13 '17 at 17:25
  • 1
    \$\begingroup\$ Your previous print(m,s,e) statement would not have worked because the variables m, s, and e were not yet assigned/defined. Also, you can remove the space after the colon. Also, you can remove the ` as n` part and just use numpy later on; since you only use it once, using the full name actually saves a byte. \$\endgroup\$ – HyperNeutrino Apr 13 '17 at 19:11
  • 1
    \$\begingroup\$ Ok, I understand now. Thank you for the suggestions, squeezing every bit :) \$\endgroup\$ – HonzaB Apr 13 '17 at 19:24
  • 2
    \$\begingroup\$ Shouldn't it be all instead of any? And I think s is the vector, not the scalar, unless I'm missing something \$\endgroup\$ – Luis Mendo Apr 13 '17 at 20:44
  • 1
    \$\begingroup\$ It would be even shorter to compare string representations. tio.run/nexus/python2#jZDPCoMwDIfP@hQ9tiOV/hEHgk/… \$\endgroup\$ – Dennis Apr 14 '17 at 1:16
2
\$\begingroup\$

Python 3, 96 70 bytes

No builtins for matrix-vector or scalar-vector multiplication!

lambda A,L,v:all(L*y==sum(i*j for i,j in zip(x,v))for x,y in zip(A,v))

Try it online!

-26 bytes by using zip thanks to @LeakyNun!

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 11 bytes

vy²*O})²³*Q

Try it online!

vy²*O})     # Vectorized product-sum.
       ²³*  # Vector * scalar.
          Q # Equivalence.
\$\endgroup\$
1
\$\begingroup\$

R, 30 25 bytes

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

Anonymous function, fairly straightforward. Returns TRUE or FALSE.

\$\endgroup\$
0
\$\begingroup\$

oK, 12 bytes

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

This is a function, it takes in [matrix;vector;scalar].

This does not work in k for the same reasons that 3.0~3 gives 0 as a result.


The following works in k, with 14 bytes:

{(y*z)~+/y*+x}
\$\endgroup\$
0
\$\begingroup\$

Axiom, 27 bytes

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

exercises

(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
\$\endgroup\$
  • \$\begingroup\$ I haven't seen this language before, nice answer! What does the @Boolean do? \$\endgroup\$ – HyperNeutrino Apr 14 '17 at 16:54
  • \$\begingroup\$ (a=b)@Boolean would mean "choose among allowed =operator(type1,type2) the one its result is Boolean"; in few words "a=b" has to be Boolean \$\endgroup\$ – RosLuP Apr 14 '17 at 18:24
0
\$\begingroup\$

Python, 26 bytes

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

a and b are numpy arrays, c is an integer.

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ Are the parens around c*b actually necessary? \$\endgroup\$ – xnor Apr 14 '17 at 6:08
  • \$\begingroup\$ @xnor thanks, fixed. \$\endgroup\$ – Rɪᴋᴇʀ Apr 14 '17 at 14:22
  • \$\begingroup\$ This only works for small arrays, since NumPy abridges large array string representations. \$\endgroup\$ – user2357112 Apr 27 '17 at 18:34
  • \$\begingroup\$ @user2357112 example? I'm not sure what you mean. \$\endgroup\$ – Rɪᴋᴇʀ Apr 27 '17 at 18:35
  • \$\begingroup\$ If c*b has more than 1000 elements, NumPy will replace most of the elements with .... Demo. \$\endgroup\$ – user2357112 Apr 27 '17 at 18:37
0
\$\begingroup\$

Clojure, 60 bytes

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

This checks that all deltas are zero, thus collapsing into the set of zero. Calling example:

(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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.