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

Improve this question
\$\endgroup\$
11
  • \$\begingroup\$ Related. \$\endgroup\$ Commented Apr 13, 2017 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\$ Commented Apr 13, 2017 at 14:08
  • \$\begingroup\$ If inputs can have have other dimensions than 3x3, you should cover some of that in your test cases. \$\endgroup\$ Commented Apr 13, 2017 at 14:22
  • \$\begingroup\$ Also while the test case format is very readable, it's a pain to copy, because (just looking at a byte stream) the three arguments are all interleaved. \$\endgroup\$ Commented Apr 13, 2017 at 14:22
  • 2
    \$\begingroup\$ @user00001 If you need help, eigenpair-aphrase it for you. :P \$\endgroup\$ Commented Apr 27, 2017 at 21:49

16 Answers 16

Reset to default
13
\$\begingroup\$

Mathematica, 10 bytes

#2.#==#3#&

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

Improve this answer
\$\endgroup\$
6
  • 1
    \$\begingroup\$ >_> this was too easy for Mathematica. +1 :P \$\endgroup\$ Commented Apr 13, 2017 at 14:16
  • 9
    \$\begingroup\$ @HyperNeutrino And now we wait for MATL... \$\endgroup\$ Commented Apr 13, 2017 at 14:19
  • 2
    \$\begingroup\$ Well MATL has appeared >_> \$\endgroup\$ Commented Apr 13, 2017 at 14:37
  • 1
    \$\begingroup\$ One of those moments when you think nothing can be shorter and MATL pops up suddenly :) \$\endgroup\$ Commented Apr 13, 2017 at 19:29
  • \$\begingroup\$ @Mr.Xcoder And then Jelly shows up. \$\endgroup\$ Commented Apr 13, 2017 at 23:14
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.
Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ >_> this is too short :P Nice answer \$\endgroup\$ Commented Apr 13, 2017 at 18:54
  • 6
    \$\begingroup\$ That's crazy talk! :P \$\endgroup\$ Commented Apr 13, 2017 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\$ Commented Apr 14, 2017 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\$ Commented Apr 14, 2017 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\$ Commented Apr 14, 2017 at 8:09
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.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ "Surprisingly long" I was expecting at least 20 bytes >_> nice answer though :P \$\endgroup\$ Commented Apr 13, 2017 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\$ Commented Apr 13, 2017 at 14:39
  • \$\begingroup\$ Apparently it came in at 38 bytes but I'm pretty sure it can be golfed down. \$\endgroup\$ Commented Apr 13, 2017 at 14:41
  • 3
    \$\begingroup\$ @HyperNeutrino Added my own to make the previous comment true. (or truthy...?) \$\endgroup\$ Commented Apr 13, 2017 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
Improve this answer
\$\endgroup\$
0
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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Wasn't aware of the falseyness of e.g. [true,false], thanks for teaching me=) \$\endgroup\$ Commented Apr 13, 2017 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\$ Commented Apr 13, 2017 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.

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ I don't know MATLAB, but can the isequal function be shortened to ==? \$\endgroup\$ Commented Apr 13, 2017 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\$ Commented Apr 13, 2017 at 14:42
  • \$\begingroup\$ @HyperNeutrino It would return a vector containing the results of elementwise comparison of the two vectors. \$\endgroup\$ Commented Apr 13, 2017 at 14:43
  • \$\begingroup\$ Oh okay. Nice answer though! \$\endgroup\$ Commented Apr 13, 2017 at 14:43
  • \$\begingroup\$ wouldn't an annonymous function be shorter? \$\endgroup\$ Commented Apr 13, 2017 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!

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

Julia, 17 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
0
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

Improve this answer
\$\endgroup\$
14
  • 2
    \$\begingroup\$ This looks good, but I think you need to include the byte count of import np for it to be valid \$\endgroup\$ Commented Apr 13, 2017 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\$ Commented Apr 13, 2017 at 19:11
  • 1
    \$\begingroup\$ Ok, I understand now. Thank you for the suggestions, squeezing every bit :) \$\endgroup\$ Commented Apr 13, 2017 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\$ Commented Apr 13, 2017 at 20:44
  • 1
    \$\begingroup\$ It would be even shorter to compare string representations. tio.run/nexus/python2#jZDPCoMwDIfP@hQ9tiOV/hEHgk/… \$\endgroup\$ Commented Apr 14, 2017 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!

Improve this answer
\$\endgroup\$
1
1
\$\begingroup\$

05AB1E, 11 bytes

vy²*O})²³*Q

Try it online!

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

R, 30 25 bytes

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

Anonymous function, fairly straightforward. Returns TRUE or FALSE.

Improve this answer
\$\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}
Improve this answer
\$\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
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ I haven't seen this language before, nice answer! What does the @Boolean do? \$\endgroup\$ Commented Apr 14, 2017 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\$ Commented Apr 14, 2017 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!

Improve this answer
\$\endgroup\$
10
  • 2
    \$\begingroup\$ Are the parens around c*b actually necessary? \$\endgroup\$ Commented Apr 14, 2017 at 6:08
  • \$\begingroup\$ This only works for small arrays, since NumPy abridges large array string representations. \$\endgroup\$ Commented Apr 27, 2017 at 18:34
  • \$\begingroup\$ @user2357112 example? I'm not sure what you mean. \$\endgroup\$ Commented Apr 27, 2017 at 18:35
  • \$\begingroup\$ If c*b has more than 1000 elements, NumPy will replace most of the elements with .... Demo. \$\endgroup\$ Commented Apr 27, 2017 at 18:37
  • \$\begingroup\$ @user2357112 fixed. \$\endgroup\$ Commented Apr 27, 2017 at 18:48
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)
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.