Hacker News new | past | comments | ask | show | jobs | submit login

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




Where were you in my intro linear algebra courses?




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: