Dr Peyam! I have my Linear Algebra exam this week! You've helped me revise a lot and understand many of the concepts! I'm so grateful for you and grateful you exist. You're a wonderful person and such an empathetic teacher! 💛
I have two questions... 1. What assures us that the others elements of D are less than 1? 2. What is the name of the theorem mentioned in 10:04? Pd: great video :)
Because were dealing with numbers thats are fractions they will always be 1/n and when you multiply n to infinity it will go to suuuuper close to 0, thus those numbers wont matter
Classic Markov chain problem!! For those who dont understand why 1 is always an eigenvalue of a Markov Matrix, consider Av=cv for some constant c and some markov vector v(and of course, the markov matrix A), take A to be a 2x2 matrix, for simplicity. Now multiply both sides by the row vector k= [1 1], so kAv =ckv, which gives c=1.
Building on this and explaining all the steps for anyone who is stuck. Notice that v is itself a probability distribution across states (websites in this case) and this is why transpose(k)*v = 1 (the sum of a probability distribution is 1 by definition). Therefore the right hand side reduces to 1*c = c. Now the left hand side transpose(k)Av, notice that A is a square matrix where each column is a probability distribution across states (by definition). Then transpose(k)*A = [1 1] (in this case, in the general case it is a 1 vector of length k). Then we have transpose(k)Av = transpose(k)v. We know from our argument for the right hand side that transpose(k)v = 1. Therefore there exists some v (which we call v_infinity also called the stationary distribution of the markov matrix A) for which it has an eigenvalue of 1.
I remember encountering your videos back in high school and understood only like 2% of it. I still don't understand lots, but I'm glad to know that you're still going strong educating people through internet
great video, all your videos in fact. It's good to see someone explaining in an easy way how this works, I've been following you on yt for years and you keep all the quality and motivation, keep it up. There is a book called Google's PageRank and Beyond: The Science of Search Engine Ranking. I read it a while back and the book discussed some methods to find eigenvalues faster and optimize algorithms etc. Sometimes we don't appreciate that, but it is important to study and develop it because it is our daily tool to work, at least in modern society. Un abrazo Doc y gracias por el video...;0
Love to see the math I learned applied! I study mech engineering not computer science but we also have some lin algebra. But in mech engineering, it feels like the only reason to study linear algebra for 2 semesters is to solve differential equation systems (except for statistics maybe). So seeing linear algebra being useful by itself is pretty cool!
Cool system, and even cooler video! As a physics student, as soon as you said transition matrix, I got flashbacks of hopping probabilities from quantum classes D: (also, go bears!!)
This is really cool but not having used algebra in a few years I can just barely remember "yeah, eigenproblem, we did that" but the details are murky. I didn't even remember matrix multiplication is associative :D I thought you have to do this from right to left
Love your energy! Btw what exactly do the connections between the states/ websites mean in the real world? You mentioned website can link to other websites, but that is very rare right?
I have a question, how does one prevent someone from abusing this algorithm by creating a bunch of dummy websites that link to your desired website and thus unfarily weighting the probabilities of landing in your desired website?
In reality, Google doesn't count how many websites link to your website, they count how many people actually visit your website coming from other sites. They can do this because have their analytics code on almost all websites today. Of course this can be (and sometimes is) abused by spamming links etc. but there's also countermeasures. In other words, this is much much more complicated than showed here.
I understand it is a Markonikov chain problem just like the weather prediction models. What I am curious about is the astounding similarity between this and the functionality of a moore type finite state machine. Instead of states we have probabilities here.
At the beginning of the video the ranking of website importance was 3>4>1>2 and then at the end the video the inferred ranking was 1>3>4>2. Am I missing something?
Nice; but do you have a rounding error. The sum 0.38 + 0.12 + 0.29 + 1.9 is just 0.98; and I believe it's necessary to have at least 5 values (rather than just 4) to fall that short of 1.00 under proper rounding. With 4 values the average error is 0.02/4 = 0.005, so at least 1 must round up; though with 5 values the average error is just 0.004 and so all can round down.
@@drpeyam All through middle school, and into high school, I was leaving careless errors in my wake like a cruise ship - until I determined after Grade 10 to stop doing so. Since then, it's become a bit of an OCD thing to search them out - just to keep in practice I guess. I hope you don't mind.
I checked last matrix more rigorously, than Dr. Peyam did and there is what I have found: First entry is 12/31 or ≈0.3870, correctly rounded value is 0.39. Second entry is 4/31 or ≈0.1290, correctly rounded value is 0.13. Third entry is 9/31 or ≈0.2903, rounded value is 0.29. Fourth entry is 6/31 or ≈0.1935, rounded value is 0.19. 0.39+0.13+0.29+0.19=1.00 If students aren't allowed to make faults in using of rule of correct numbers, why Doctor should morally allow himself do something that is morally and pedagogically unacceptable for students? Mr. Peyam, please, use rules of math correctly. Even if it touches not so significant rule like rule of correct numbers.
In this specific example the original matrix A has the trace equal to zero , therefore the sum of the eigenvalues in D has to be equal to zero as well. So with exception of the first one that is equal to 1, all the others eigenvalues can be negative and with absolute values less than 1. Correct?
@@drpeyam for finite dimensional spaces right or does it hold for all spaces? And even though they are equivalent, the “normalization” factor is still different, depending on what your measuring this scale factor can make things weird or what I’m saying is totally wrong?
@@drpeyam for finite dimensional spaces right or does it hold for all spaces? And even though they are equivalent, the “normalization” factor is still different, depending on what your measuring this scale factor can make things weird or what I’m saying is totally wrong?
Excellent! Very nice explanation, But I was wondering what if the matrix is not diagonalizable? Is it then the Jordan normal form?( generalized eigenvactors?)
In order for this algortihm to work, we absolutely need our matrix to behave in such a way that all its eigenvalues have absolute value at most 1 (otherwise it will diverge when raised to infinity), and at least one of the eigenvalues has to be exactly 1 (otherwise the matrix will converge to 0). So why can we guarantee these two properties of A?
Steve Strogatz did an oral explanation here: th-cam.com/video/AXk12z-NGPI/w-d-xo.html. It is nice to see some low level calculations. Page and Brin did well out of lineat algebra!!
Hey, why are the eigenvalues of the Matrix so small? Another thing that bothers me is that it is assumed that if a website has many links to other websites, it is relevant. But isn't it the case that these links also have to be clicked? I.e. there would still have to be a weighting for each connection that shows how often this connection is used.
Sorry to say but it is a truth 💔💔💔....I am from Asia where there is only theory not real life examples...I am a university student and today I know what exactly vector is .....In my past student career I hated vector a lot though I love mathematics 💔💔💔
"80% of mathematics is linear algebra"
-Raoul Bott
How can this be true?
What about non-linear algebra?
@@adamfattal468 it must be the 20% of mathematics, according to my calculations
@@thesenate8268 I wonder what rigorous methodology is behind this result
@@adamfattal468 linear algebra
Dr Peyam! I have my Linear Algebra exam this week! You've helped me revise a lot and understand many of the concepts! I'm so grateful for you and grateful you exist. You're a wonderful person and such an empathetic teacher! 💛
Thank you!!!
Learning about this in my data science classes. Truly exciting stuff!
this is awesome, I just finished linear algebra 1, and seeing how concepts like eigenvalues interact in the real world is super cool
I have two questions...
1. What assures us that the others elements of D are less than 1?
2. What is the name of the theorem mentioned in 10:04?
Pd: great video :)
Because were dealing with numbers thats are fractions they will always be 1/n and when you multiply n to infinity it will go to suuuuper close to 0, thus those numbers wont matter
Classic Markov chain problem!! For those who dont understand why 1 is always an eigenvalue of a Markov Matrix, consider Av=cv for some constant c and some markov vector v(and of course, the markov matrix A), take A to be a 2x2 matrix, for simplicity. Now multiply both sides by the row vector k= [1 1], so kAv =ckv, which gives c=1.
Building on this and explaining all the steps for anyone who is stuck. Notice that v is itself a probability distribution across states (websites in this case) and this is why transpose(k)*v = 1 (the sum of a probability distribution is 1 by definition). Therefore the right hand side reduces to 1*c = c. Now the left hand side transpose(k)Av, notice that A is a square matrix where each column is a probability distribution across states (by definition). Then transpose(k)*A = [1 1] (in this case, in the general case it is a 1 vector of length k). Then we have transpose(k)Av = transpose(k)v. We know from our argument for the right hand side that transpose(k)v = 1. Therefore there exists some v (which we call v_infinity also called the stationary distribution of the markov matrix A) for which it has an eigenvalue of 1.
Sir this is a wendys
I remember encountering your videos back in high school and understood only like 2% of it. I still don't understand lots, but I'm glad to know that you're still going strong educating people through internet
Thank you!!!
Abstractions are so cool! How they translate to real world ideas is even cooler!
Not too surprising since many abstractions originate as a special case of a "real world idea"
what a joy to see math so clearly explained. that was awesome! you basically capture the essence of it really well.
Good timing! I just gave my students a project on this topic!
We actually learned about this the last day of my linear algebra class! (Last year)
5:30 , and that's how power method works for dominant eigenvalue and corresponding eigenvector
4:31 memerable MAGIC
4:24 „… the same Spiel with….“. 🤗
great video, all your videos in fact. It's good to see someone explaining in an easy way how this works, I've been following you on yt for years and you keep all the quality and motivation, keep it up. There is a book called Google's PageRank and Beyond: The Science of Search Engine Ranking. I read it a while back and the book discussed some methods to find eigenvalues faster and optimize algorithms etc. Sometimes we don't appreciate that, but it is important to study and develop it because it is our daily tool to work, at least in modern society. Un abrazo Doc y gracias por el video...;0
You are the happiest mathematician of youtube!
This is awesome
Thank youuuu
is there a case where transition matrix is not diagonisable?
I've seen a similar analysis applied to the game of Monopoly. There was an article about that years ago in Scientific American.
I really like the linear algebra problems
Sameeee
Love to see the math I learned applied! I study mech engineering not computer science but we also have some lin algebra.
But in mech engineering, it feels like the only reason to study linear algebra for 2 semesters is to solve differential equation systems (except for statistics maybe).
So seeing linear algebra being useful by itself is pretty cool!
It’s used very frequently in multibody system dynamics when dealing with positions or forces of rigid bodies in different orientations
This is amazing !!!! . Please make more videos like this where you are explaining how these technologies are using Mathematics 🤩🤩🤩🤩🤩🤩
Cool system, and even cooler video! As a physics student, as soon as you said transition matrix, I got flashbacks of hopping probabilities from quantum classes D: (also, go bears!!)
This is really cool but not having used algebra in a few years I can just barely remember "yeah, eigenproblem, we did that" but the details are murky. I didn't even remember matrix multiplication is associative :D I thought you have to do this from right to left
Great video as always.
Love your energy!
Btw what exactly do the connections between the states/ websites mean in the real world? You mentioned website can link to other websites, but that is very rare right?
The count of Websites having link to others is what is used for , at least that was true in the initial days .
Websites commonly link others right ?
this is great!! how do we know the diagonalized matrix will have rapidly decaying eigenvalues?
Love Markov matrices...
I have a question, how does one prevent someone from abusing this algorithm by creating a bunch of dummy websites that link to your desired website and thus unfarily weighting the probabilities of landing in your desired website?
In reality, Google doesn't count how many websites link to your website, they count how many people actually visit your website coming from other sites. They can do this because have their analytics code on almost all websites today. Of course this can be (and sometimes is) abused by spamming links etc. but there's also countermeasures. In other words, this is much much more complicated than showed here.
@@l_szabi thanks!
Any explanation on why the largest eigenvalue is always 1 and the rest is less than 1 but not negative?
give this man a diamond medal...
Awwwww
As a CS major it's really cool seeing what seems to be a pointless class at the same being shown in real examples.
I understand it is a Markonikov chain problem just like the weather prediction models. What I am curious about is the astounding similarity between this and the functionality of a moore type finite state machine. Instead of states we have probabilities here.
At the beginning of the video the ranking of website importance was 3>4>1>2 and then at the end the video the inferred ranking was 1>3>4>2. Am I missing something?
Beautiful
Nice; but do you have a rounding error. The sum 0.38 + 0.12 + 0.29 + 1.9 is just 0.98; and I believe it's necessary to have at least 5 values (rather than just 4) to fall that short of 1.00 under proper rounding. With 4 values the average error is 0.02/4 = 0.005, so at least 1 must round up; though with 5 values the average error is just 0.004 and so all can round down.
Omg 😂
@@drpeyam All through middle school, and into high school, I was leaving careless errors in my wake like a cruise ship - until I determined after Grade 10 to stop doing so. Since then, it's become a bit of an OCD thing to search them out - just to keep in practice I guess. I hope you don't mind.
I checked last matrix more rigorously, than Dr. Peyam did and there is what I have found:
First entry is 12/31 or ≈0.3870, correctly rounded value is 0.39.
Second entry is 4/31 or ≈0.1290, correctly rounded value is 0.13.
Third entry is 9/31 or ≈0.2903, rounded value is 0.29.
Fourth entry is 6/31 or ≈0.1935, rounded value is 0.19.
0.39+0.13+0.29+0.19=1.00
If students aren't allowed to make faults in using of rule of correct numbers, why Doctor should morally allow himself do something that is morally and pedagogically unacceptable for students?
Mr. Peyam, please, use rules of math correctly.
Even if it touches not so significant rule like rule of correct numbers.
Great video, but why do the sum of the terms of the final probability vector not equal to 1?
It should, up to approximation
In this specific example the original matrix A has the trace equal to zero , therefore the sum of the eigenvalues in D has to be equal to zero as well. So with exception of the first one that is equal to 1, all the others eigenvalues can be negative and with absolute values less than 1. Correct?
It’s possible
I guess, Google can estimate the transition probabilities.
Why is the sum norm chosen and not the l^2 norm, or any other norm for that matter?
They’re all equivalent actually
@@drpeyam for finite dimensional spaces right or does it hold for all spaces? And even though they are equivalent, the “normalization” factor is still different, depending on what your measuring this scale factor can make things weird or what I’m saying is totally wrong?
@@drpeyam for finite dimensional spaces right or does it hold for all spaces? And even though they are equivalent, the “normalization” factor is still different, depending on what your measuring this scale factor can make things weird or what I’m saying is totally wrong?
I lost you at A equals PDP inverse .
Haven’t taken a linear algebra class officially. Any simple books or lectures?
Check out my playlists!
Excellent!
Very nice explanation,
But I was wondering what if the matrix is not diagonalizable? Is it then the Jordan normal form?( generalized eigenvactors?)
Yes you would use the Jordan normal form
As a fellow Golden Bear I can confirm that Cal shirts never fit 😆
😂😂
....no magic @ 3:02 ???
Thank you hahaha, I forgot to cut that part out
Changing two letters of an exceptionally copyrighted symbol to Lambda should keep you out of troubles. 😬
Brilliant idea although you skipped some ideas we are hopefully waiting see in your next videos
Check out my playlist
@@drpeyam thank you Dr
How is Vo computed in realistic settings?
The result is independent of v0 actually
In order for this algortihm to work, we absolutely need our matrix to behave in such a way that all its eigenvalues have absolute value at most 1 (otherwise it will diverge when raised to infinity), and at least one of the eigenvalues has to be exactly 1 (otherwise the matrix will converge to 0). So why can we guarantee these two properties of A?
I think it’s because the sums are 1, I think
You cannot always guarantee it. In general you need to adjust A using a dumping factor and then the two properties are guaranteed.
The relevant theorem is called the Perron-Frobenius Theorem.
I miss the "chenlu" tshirt.
Want that, but the sad its- hard to shipment to indonesia 😅
Just graduated and I don’t want to see any more of stochastic processes 😂
I was expecting the diagonal entries to be all ones and not zeros... You are already in the website so it's weird to have zeros
But it doesn’t link to itself though
you know our λ as loo, leeee, lemon, λέμον - smart
Steve Strogatz did an oral explanation here: th-cam.com/video/AXk12z-NGPI/w-d-xo.html. It is nice to see some low level calculations. Page and Brin did well out of lineat algebra!!
Hey, why are the eigenvalues of the Matrix so small?
Another thing that bothers me is that it is assumed that if a website has many links to other websites, it is relevant. But isn't it the case that these links also have to be clicked? I.e. there would still have to be a weighting for each connection that shows how often this connection is used.
They're 0 < x < 1, so raised to infinte power they go to zero.
this seems familiar...
Hahaha I wonder why 😉
i dont get how peanuts got into the equation
Markov chain...
Sorry to say but it is a truth 💔💔💔....I am from Asia where there is only theory not real life examples...I am a university student and today I know what exactly vector is .....In my past student career I hated vector a lot though I love mathematics 💔💔💔
Гугле-мугле
Now if only you could crack the TH-cam algorithm ... 🤔