[impendia]

Here's a fun problem which can be solved by linear algebra.

You have a group of 20 people. Each of them rates how much they like everyone else, on a scale of 1 to 10. Your task is to figure out how popular everyone is, again on a scale from 1 to 10. Someone's "popularity" is based on how much the other kids like them, except the cool kids' opinion count more. You're popular if the popular people like you.

Can you mathematically compute how popular everyone is? Is the solution unique? Or might there be more than one solution? The problem seems hopelessly circular -- you have to figure out who is popular before you can figure out who is popular -- but actually it turns out to be a standard linear algebra problem.

[tcbasche]

Ooh that's cool - can you elaborate on the solution?

[impendia]

Suppose that the popularities of everyone are p_1, p_2, through p_20. Then, if you write "~" for "is proportional to", you get a bunch of equations like

0p_1 + 8p_2 + 4p_3 + ... + 4p_20 ~ p_1

7p_2 + 0p_2 + 7p_3 + ... + 9p_20 ~ p_2

...

if you assume that Person #1 is rated 8 by Person #2, 4 by Person #3, and so on, and that nobody rates themselves.

Anyway, you can combine these into a matrix equation

Mv = cv

where M is the matrix with all the popularity ratings that students give each other, v is a vector which says how popular everyone is, and c is a constant. M is known, and you have to solve it for v and c.

Anyway, v is an eigenvector of the matrix M, and finding them is a standard problem.

https://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors

The same idea shows up all over the place in linear algebra.

[BOOSTERHIDROGEN]

I still can't grasp the concept of eigenvalues and eigenvectors, any references that have good and intuitive explanations, thanks

[stadeschuldt]

The videos of 3blue1brown are very good:

https://www.youtube.com/watch?v=PFDu9oVAE-g