5 ms·

So it's been checks notes 9 years since I've had to deal with eigenvectors and eigenvalues. So the post went way over my head, but folks on twitter were making

by xxpor 7y ago

So it's been checks notes 9 years since I've had to deal with eigenvectors and eigenvalues. So the post went way over my head, but folks on twitter were making quite a big deal over the post last night when it went up on arXiv. Could someone explain this like I have a computer engineering bachelors degree? :)

klodolph 7y ago
You might prefer the earlier post, https://news.ycombinator.com/item?id=21528425 https://news.ycombinator.com/item?id=21528425 Basically, this allows you to compute eigenvectors from eigenvalues of minor matrices. It is an interesting identity, but speculating on its applications is beyond my expertise.
te_platt 7y ago
It's something like an economist finding a $20 dollar bill on the ground and it's actually a real $20 bill that no one has picked up yet.
- Confusion 7y ago
  Finding a $20 bill on Times Square
  - scottlocklin 7y ago
    More like a gold sovereign in Piccadilly. I only skimmed, but it's a sweet result, and something an insightful undergrad could have come up with, but never did. Linear algebra for large scale "muh big data" applications has had a mini renaissance in recent years. Haven't seen any this cute and basic though.
randomsearch 7y ago
Don’t know how simple you want me to go, so apologies if required. You’ve got a matrix A, ie a 2D array of numbers. You’ve got a vector v, that is a 1D array of numbers. You can multiply A by v, written Av, to get a new vector. Matrices can therefore be viewed as devices for taking a vector and giving a new one, ie as linear transformations. You can design a matrix to rotate vectors, stretch them etc. An eigenvector of a matrix is a vector that changes only by a constant factor c, when you apply (multiply by) the matrix. So Av = kv where k is a number. For example, if k=2 then applying A just doubles every number in v. Eigenvectors are stretched or squashed by the matrix, no funny business like shearing or rotating. An eigenvalue is the “k” mentioned above, ie there’s at least one eigenvector such that Av=kv. There could be multiple eigenvectors all with the same k, ie all changed in the same simple way by applying the matrix. Ok? Slight complication: matrix A may contain complex numbers, not just your common garden variety real numbers. But the above all still applies. “Symmetric matrices” are matrices that have a symmetry across the top left to bottom right diagonal. So the number at A[i][j] is the same number as that at A[j][i]. “Hermitian” matrices are the equivalent of symmetric matrices when we’re dealing in complex numbers. Rather than A[i][j] being equal to A[j][i], if one entry is a complex number then the other entry is the “complex conjugate” of the first entry. (In case you’ve forgotten complex numbers: we extend the real numbers to including numbers of the form r + zi, where r is the “real part” (just a real number) and “zi” is a real number z multiplied by i, where i = sqrt(-1). Imaginary numbers were introduced to allow us to solve equations we couldn’t otherwise solve, but have turned out to be super useful everywhere. The “complex conjugate” of an imaginary number is obtained by flipping the sign of z, eg (2 + 3i) -> (2 - 3i).) Anyway, so Hermitian matrices are “symmetric” in this way and turn out to be super useful in physics. They also have the property that when you multiply a Hermitian matrix H by a vector v, the possible eigenvalues are real numbers, despite the fact that H may contain complex numbers. What the paper states is a relationship between the eigenvalues and eigenvectors of a Hermitian matrix H and the eigenvalues of a smaller “submatrix” matrix H’, where H’ is just the same as H but with a column and row removed, where the index of the row and column is the same. This is neat, because it can be used to speed up the calculation of eigenvectors (as important as say array sorting in CS) in some specific situations. Commenting further is beyond me.
- akie 7y ago
  Thanks! It's been 15 years since I did any linear algebra or had any use for eigenvectors or matrices, and I could follow this. Much appreciated.
- MaximumYComb 7y ago
  ELI(Bach of Comp Sci) went very well
FabHK 7y ago
So, you have some infinite space, and now you transform it with a linear transformation A - that could include mirroring, rotation, stretching (but not translation - one of the properties of linear transformations is that the origin, zero, stays at the origin). Now, there could be lines through the origin that map to themselves under this transformation. These lines are called eigenvectors of A, and they characterise the transformation A. (If you mirror something, a line in the mirror plane maps to itself. If you rotate something, the rotation axis maps to itself. If you stretch something, a line in the direction you stretch in might map to itself. And so on.) Now, these lines map onto themselves, but they might be stretched or shrunk in the process - that's given by the Eigenvalue. The famous equation is A x = lambda x: You transform eigenvector x by A, and you get back x itself, but stretched by a factor lambda (the Eigenvalue). So, if you have some mapping of 5d space to itself, for example, it can be characterised by 5 eigenvectors (lines that map unto themselves), and 5 eigenvalues (the stretch factor for each of these lines). Now, "traditionally", you compute the eigenvector by solving a 5d linear system for each of the eigenvalues. (5 eigenvalues, 5 slightly modified linear systems, each gives you an eigenvector of 5 coefficients, for a grand total of 25 eigenvector coefficients). Here, it is shown that you can compute the eigenvectors of the full system without even solving that traditional linear system, but by instead taking the eigenvalues of a slightly modified smaller system. (5 eigenvalues, 5 slightly modified smaller systems M (that you get from A by striking out the i'th column and row). Each of those has 4 Eigenvalues, so you have a total of 5 + 4x5 = 25 Eigenvalues. Now, you compute some differences and products and ratios of those numbers, and hey presto, you get your 25 Eigenvector coefficients (thus the title, "Eigenvectors from Eigenvalues"). Pretty neat, though it's unclear to me how the computational complexity really compares. EDIT: formatting, reference to title
- JahWob 7y ago
  Where were you in my intro linear algebra courses?

by xxpor 7y ago

klodolph 7y ago

You might prefer the earlier post, https://news.ycombinator.com/item?id=21528425 https://news.ycombinator.com/item?id=21528425 Basically, this allows you to compute eigenvectors from eigenvalues of minor matrices. It is an interesting identity, but speculating on its applications is beyond my expertise.

te_platt 7y ago

It's something like an economist finding a $20 dollar bill on the ground and it's actually a real $20 bill that no one has picked up yet.

Confusion 7y ago
Finding a $20 bill on Times Square
- scottlocklin 7y ago
  More like a gold sovereign in Piccadilly. I only skimmed, but it's a sweet result, and something an insightful undergrad could have come up with, but never did. Linear algebra for large scale "muh big data" applications has had a mini renaissance in recent years. Haven't seen any this cute and basic though.

randomsearch 7y ago

Don’t know how simple you want me to go, so apologies if required. You’ve got a matrix A, ie a 2D array of numbers. You’ve got a vector v, that is a 1D array of numbers. You can multiply A by v, written Av, to get a new vector. Matrices can therefore be viewed as devices for taking a vector and giving a new one, ie as linear transformations. You can design a matrix to rotate vectors, stretch them etc. An eigenvector of a matrix is a vector that changes only by a constant factor c, when you apply (multiply by) the matrix. So Av = kv where k is a number. For example, if k=2 then applying A just doubles every number in v. Eigenvectors are stretched or squashed by the matrix, no funny business like shearing or rotating. An eigenvalue is the “k” mentioned above, ie there’s at least one eigenvector such that Av=kv. There could be multiple eigenvectors all with the same k, ie all changed in the same simple way by applying the matrix. Ok? Slight complication: matrix A may contain complex numbers, not just your common garden variety real numbers. But the above all still applies. “Symmetric matrices” are matrices that have a symmetry across the top left to bottom right diagonal. So the number at A[i][j] is the same number as that at A[j][i]. “Hermitian” matrices are the equivalent of symmetric matrices when we’re dealing in complex numbers. Rather than A[i][j] being equal to A[j][i], if one entry is a complex number then the other entry is the “complex conjugate” of the first entry. (In case you’ve forgotten complex numbers: we extend the real numbers to including numbers of the form r + zi, where r is the “real part” (just a real number) and “zi” is a real number z multiplied by i, where i = sqrt(-1). Imaginary numbers were introduced to allow us to solve equations we couldn’t otherwise solve, but have turned out to be super useful everywhere. The “complex conjugate” of an imaginary number is obtained by flipping the sign of z, eg (2 + 3i) -> (2 - 3i).) Anyway, so Hermitian matrices are “symmetric” in this way and turn out to be super useful in physics. They also have the property that when you multiply a Hermitian matrix H by a vector v, the possible eigenvalues are real numbers, despite the fact that H may contain complex numbers. What the paper states is a relationship between the eigenvalues and eigenvectors of a Hermitian matrix H and the eigenvalues of a smaller “submatrix” matrix H’, where H’ is just the same as H but with a column and row removed, where the index of the row and column is the same. This is neat, because it can be used to speed up the calculation of eigenvectors (as important as say array sorting in CS) in some specific situations. Commenting further is beyond me.

akie 7y ago
Thanks! It's been 15 years since I did any linear algebra or had any use for eigenvectors or matrices, and I could follow this. Much appreciated.
MaximumYComb 7y ago
ELI(Bach of Comp Sci) went very well

FabHK 7y ago

So, you have some infinite space, and now you transform it with a linear transformation A - that could include mirroring, rotation, stretching (but not translation - one of the properties of linear transformations is that the origin, zero, stays at the origin). Now, there could be lines through the origin that map to themselves under this transformation. These lines are called eigenvectors of A, and they characterise the transformation A. (If you mirror something, a line in the mirror plane maps to itself. If you rotate something, the rotation axis maps to itself. If you stretch something, a line in the direction you stretch in might map to itself. And so on.) Now, these lines map onto themselves, but they might be stretched or shrunk in the process - that's given by the Eigenvalue. The famous equation is A x = lambda x: You transform eigenvector x by A, and you get back x itself, but stretched by a factor lambda (the Eigenvalue). So, if you have some mapping of 5d space to itself, for example, it can be characterised by 5 eigenvectors (lines that map unto themselves), and 5 eigenvalues (the stretch factor for each of these lines). Now, "traditionally", you compute the eigenvector by solving a 5d linear system for each of the eigenvalues. (5 eigenvalues, 5 slightly modified linear systems, each gives you an eigenvector of 5 coefficients, for a grand total of 25 eigenvector coefficients). Here, it is shown that you can compute the eigenvectors of the full system without even solving that traditional linear system, but by instead taking the eigenvalues of a slightly modified smaller system. (5 eigenvalues, 5 slightly modified smaller systems M (that you get from A by striking out the i'th column and row). Each of those has 4 Eigenvalues, so you have a total of 5 + 4x5 = 25 Eigenvalues. Now, you compute some differences and products and ratios of those numbers, and hey presto, you get your 25 Eigenvector coefficients (thus the title, "Eigenvectors from Eigenvalues"). Pretty neat, though it's unclear to me how the computational complexity really compares. EDIT: formatting, reference to title

JahWob 7y ago
Where were you in my intro linear algebra courses?