Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Programmer’s Intuition for Matrix Multiplication

betterexplained.com

Post reply on HN
Print view View original

81–90 of 95 posts

Re: A Programmer’s Intuition for Matrix Multiplication

#81

Post by philip-b »

pmiller2 wrote: post #78
crdrost wrote: post #77

Earlier quoted context omitted.

So for example let me ask for your knee-jerk opinions based on this idea: - does a matrix have the same left-eigenvectors as its right-eigenvectors? - what is the relationship between the left-eigenvalues and right-eigenvalues? - is there always an eigenvector? when is there a complete set? how do you generalize your notion of eigenvectors so that matrices always have a complete set of them? I am not sure any of thes…

If A is a square matrix, then a left eigenvector v is a vector such that vA = \lambda_v v for some \lambda_v. Likewise, if u is a right eigenvector of A, Au = \lambda_u u. Notice that u and v cannot be equal, because they are not the same shape. However, if v is a right eigenvector with eigenvalue \lambda, then v^T is a left eigenvector with eigenvalue \lambda, as well. More or less what this means is that we tend to…

>But, if A is nonzero, then it must have at least one nonzero eigenvalue, hence one nontrivial eigenvector.

How about this matrix?

  [[0, -1],
  [[1, 0]]
>However, if v is a right eigenvector with eigenvalue \lambda, then v^T is a left eigenvector with eigenvalue \lambda, as well.

A snippet of code producing a counterexample:

  import numpy as np
  import scipy.linalg as spla

  A = np.random.randn(3, 3)
  right_eigenvector = spla.eig(A)[1][:,0]
  right_eigenvalue = ((A @ right_eigenvector) / right_eigenvector)[0]

  potential_left_eigenvector = right_eigenvector[np.newaxis, :]

  # if all components of the following are not the same, then it's not
  # a left eigenvector
  print((potential_left_eigenvector @ A) / potential_left_eigenvector)
  # prints [[-1.1327836 -0.j -0.14850693-0.j -1.84397691+0.j]]

Re: A Programmer’s Intuition for Matrix Multiplication

#82

Post by unnouinceput »

WJW wrote: post #41
unnouinceput wrote: post #28

Earlier quoted context omitted.

And what happens if indeed the huge matrix elements are all non-zero? Like, let's say, satellite scan data for a given country when you want to spy on their underground systems (think North Korea facilities)? Wouldn't storing that data as COO would actually triple the amount of memory?

Presumable the designer(s) of such a system will be able to know in advance whether the resulting matrix will be sparse or not and choose their encoding appropriately. FWIW, for a lot of practical applications the raw sensor data would be non-sparse but it would be transformed/filtered almost immediately into a more space-efficient representation. For example in the case you mentioned (unless you think the entire cou…

That's my point. In order to analyze you need to preserve entire data. One system is the image acquisition. Another is the analysis, on more advanced systems. The advanced system needs all data. Dismissing it at entry point defeats its purpose. No matter how you flip it, there are practical applications where huge matrices that have non-zero elements exists.

Here is another example - cryptography analysis. Usually password length is small, usually below 1k characters. But if you increase the password length then simple old ciphers, like Vigenere, become harder to crack. Bump the key length to over 1 million bytes and suddenly your century old methods, like index of coincidence and Kasiski examination become a problem of having huge matrices to feed to analyzer. 1 million key length suddenly generates a matrix with 256M x 256M for analyzer. And all elements in that matrix are non zero.

Re: A Programmer’s Intuition for Matrix Multiplication

#83

Post by dnautics »

jpeloquin wrote: post #79
dnautics wrote: post #74

Earlier quoted context omitted.

I just tried this, I stand corrected, but I remember this (the last clause) not working in numpy. It's possible my memory is flawed: >>> import numpy as np >>> vec = np.array([1, 2, 3]) >>> mtx = np.eye(3) >>> np.dot(vec, mtx) array([1., 2., 3.]) >>> np.dot(mtx, vec) array([1., 2., 3.]) It's possible though that I was remembering not that it doesn't execute, but rather that if you do mess up the multiplication order…

I remember a problem similar to the one you describe when using a dot product both to substitute for a fast loop and for its normal mathematical purpose, in the same operation: points = np.array([[0, 0, 0], [1, 0, 0], [1, 1, 0], [0, 1, 0]]) M = np.array([[0.866, 0.5, 0], [-0.5, 0.866, 0], [0, 0, 1]]) # rotation points @ M # works M @ points # raises ValueError, also a different transform Regarding messing up the mult…

Well I was doing graphics transformations on affine vectors, so they are all 4x4 and 4x1 vectors... You can't "know you are in the wrong order by checking dimensions" in that case.

Re: A Programmer’s Intuition for Matrix Multiplication

#84

Post by crdrost »

pmiller2 wrote: post #78
crdrost wrote: post #77

Earlier quoted context omitted.

So for example let me ask for your knee-jerk opinions based on this idea: - does a matrix have the same left-eigenvectors as its right-eigenvectors? - what is the relationship between the left-eigenvalues and right-eigenvalues? - is there always an eigenvector? when is there a complete set? how do you generalize your notion of eigenvectors so that matrices always have a complete set of them? I am not sure any of thes…

If A is a square matrix, then a left eigenvector v is a vector such that vA = \lambda_v v for some \lambda_v. Likewise, if u is a right eigenvector of A, Au = \lambda_u u. Notice that u and v cannot be equal, because they are not the same shape. However, if v is a right eigenvector with eigenvalue \lambda, then v^T is a left eigenvector with eigenvalue \lambda, as well. More or less what this means is that we tend to…

> However, if v is a right eigenvector with eigenvalue \lambda, then v^T is a left eigenvector with eigenvalue \lambda, as well.

Consider the matrix

    M = [ 0.50  0.50 ]
        [ 0.25  0.75 ]
Clearly [1; 1] is a right eigenvector with eigenvalue 1. But [1 1] M = [0.75 1.25].

> A matrix does not necessarily have nontrivial eigenvectors. Think about the 0 matrix here.

The zero matrix has _all_ the nontrivial vectors as eigenvectors.

> But, if A is nonzero, then it must have at least one nonzero eigenvalue, hence one nontrivial eigenvector.

Consider

    N = [ 0  1 ]
        [ 0  0 ]
This has no non-zero eigenvalues, but it is not the zero matrix. It does have a nontrivial eigenvector, [1; 0], because every square complex matrix has an eigenvector. (This is in contradiction to another statement you said, that a matrix does not have nontrivial eigenvectors—that is technically true but only in a limited sense that your space might not be ℂ^n or something that can be quickly generalized to it like ℝ^n. But like we’re in a computing forum and I might find that pedantic.)

I don't know why you consider the eigenvalue zero to somehow not count as an eigenvalue. Very suspicious.

> This also illustrates the conditions necessary for an nxn matrix A to have n linearly independent eigenvectors: the rows of A must be linearly independent.

Consider

    P = [ 1  1 ]
        [ 0  1 ]
The rows are linearly independent, but this does not have a second eigenvector.

> All of this is covered in a decent undergrad linear algebra course. I would suggest either finding a video course, or getting a good book and working through it, if you want to understand these things better.

sigh ... See this is why I sometimes feel bad about commenting here. Like, this comment thread was supposed to be a celebration of this different way of thinking about linear algebra, and then I have to deal with this stuff. Like I totally don’t think you meant to come across as condescending, but given that I have taught crash courses for struggling friends on linear algebra concepts they missed in their undergrad to get through our graduate work in physics, you know, it kind of does come across that way.

Re: A Programmer’s Intuition for Matrix Multiplication

#85

Post by crdrost »

philip-b wrote: post #81
pmiller2 wrote: post #78

Earlier quoted context omitted.

If A is a square matrix, then a left eigenvector v is a vector such that vA = \lambda_v v for some \lambda_v. Likewise, if u is a right eigenvector of A, Au = \lambda_u u. Notice that u and v cannot be equal, because they are not the same shape. However, if v is a right eigenvector with eigenvalue \lambda, then v^T is a left eigenvector with eigenvalue \lambda, as well. More or less what this means is that we tend to…

>But, if A is nonzero, then it must have at least one nonzero eigenvalue, hence one nontrivial eigenvector. How about this matrix? [[0, -1], [[1, 0]] >However, if v is a right eigenvector with eigenvalue \lambda, then v^T is a left eigenvector with eigenvalue \lambda, as well. A snippet of code producing a counterexample: import numpy as np import scipy.linalg as spla A = np.random.randn(3, 3) right_eigenvector = spl…

Your first matrix doesn't count, but the theorem is bogus: see my counterexample above.

The correct theorem is that every complex square matrix has an eigenvector. If we interpret your matrix as a complex matrix, then it does have two eigenvectors, namely [1; ±i]. Hence why I’d say it kind of “doesn’t count.”

Re: A Programmer’s Intuition for Matrix Multiplication

#86

Post by Vespasian »

pjfin123 wrote: post #58
notsuoh wrote: post #33

This comes up occasionally. I don't find it to be particularly helpful, even though I do think betterexplained has been a strong source of gaining intuition into various subjects. Recognizing though that method of understanding something is pretty personal, I will say that what really helped me refresh was the 3Blue1Brown Essence of Linear Algebra series on Youtube. If you're trying to better grasp the subject, do yo…

3Blue1Brown is really great for learning/refreshing math. He has great visualizations. I especially enjoyed this video (not exactly a math tutorial more of a cool explanation): https://www.youtube.com/watch?v=OkmNXy7er84

I can wholeheartedly recommend his channel.

In particular his recent "Lockdown Math" series taught me a lot.

I knew and used trigonometric functions and exponentials before but they never really "clicked".

Grant is a tremendous educator.

Re: A Programmer’s Intuition for Matrix Multiplication

#87

Post by rathel »

Vespasian wrote: post #86
pjfin123 wrote: post #58

Earlier quoted context omitted.

3Blue1Brown is really great for learning/refreshing math. He has great visualizations. I especially enjoyed this video (not exactly a math tutorial more of a cool explanation): https://www.youtube.com/watch?v=OkmNXy7er84

I can wholeheartedly recommend his channel. In particular his recent "Lockdown Math" series taught me a lot. I knew and used trigonometric functions and exponentials before but they never really "clicked". Grant is a tremendous educator.

True, but I don't agree with what he said here @ 8:00

https://youtu.be/ZxYOEwM6Wbk?t=481

Is this really the case? I checked Wikipedia and MathWorld and nobody makes a distinction between e^x and exp(x).

Even if it's a "white lie" for didactic reasons, I don't buy it, it will be much more confusing down the line for students.

Math is about finding structures governed by some rules and then generalizing them. To me the e^x defined as repeated multiplication conceptually is the same thing as the exponential function, just over broader domain. Why? You can interpolate between integer-valued X's using geometric mean. e^3 = sqrt(e^2 * e^4). What stops you from interpolating this recursively to achieve in the limit the exponential function over real numbers?

Re: A Programmer’s Intuition for Matrix Multiplication

#88

Post by siraben »

siraben wrote: post #76

When I took a course in linear algebra, we learned about linear transformations and vector spaces in the abstract first. Then when we got to matrices it was viewed as a way to represent linear transformations. Also it led to a natural derivation for matrix multiplication.

If anyone is curious I've uploaded the half-page derivation found in Chapter 3 of Linear Algebra Done Right here[0].

[0] https://imgur.com/a/BTKMWU2

Re: A Programmer’s Intuition for Matrix Multiplication

#89

Post by cousin_it »

crdrost wrote: post #84
pmiller2 wrote: post #78

Earlier quoted context omitted.

If A is a square matrix, then a left eigenvector v is a vector such that vA = \lambda_v v for some \lambda_v. Likewise, if u is a right eigenvector of A, Au = \lambda_u u. Notice that u and v cannot be equal, because they are not the same shape. However, if v is a right eigenvector with eigenvalue \lambda, then v^T is a left eigenvector with eigenvalue \lambda, as well. More or less what this means is that we tend to…

> However, if v is a right eigenvector with eigenvalue \lambda, then v^T is a left eigenvector with eigenvalue \lambda, as well. Consider the matrix M = [ 0.50 0.50 ] [ 0.25 0.75 ] Clearly [1; 1] is a right eigenvector with eigenvalue 1. But [1 1] M = [0.75 1.25]. > A matrix does not necessarily have nontrivial eigenvectors. Think about the 0 matrix here. The zero matrix has _all_ the nontrivial vectors as eigenvecto…

Yeah. In my experience, specialized subreddits (like /r/math or /r/haskell) have less such silliness than HN.

For the first matrix, maybe a simpler example is M = [1 1; 0 0]. Then [1; 0] is a right eigenvector with eigenvalue 1, but [1 0] M = [1 1].

Post reply on HN