Solving the Most Ridiculous Systems of Equations (ft. a cool theorem)
Вставка
- Опубліковано 15 чер 2024
- Join us on an algebraic journey as we solve several crazy systems of equations, building up to formulating and proving the Fundamental Theorem of Symmetric Polynomials.
This video was a serious undertaking for us and is quite different from our previous video, so let us know what you think of it! We've got lots more ideas that we hope to post more frequently, but we're still figuring out our style and groove.
The video we made for SoME2: • What's So Natural Abou...
Living Mice Synthwave Remix: • C418 - Living Mice (Cy...
Special thanks to Talia S for the fish!
Timestamps
00:00 Intro
00:35 Solving the First System
06:13 Solving a Second System
16:21 The Fundamental Theorem of Symmetric Polynomials
27:14 Outro
idk how to explain it but I feel like I'm listening to an actual fish
Bro i was thinking the same thing
Yes, finally our prince is back. All hail Aquaman!!!
its kinda cute :3
There was a game called Fish Fillets where you controlled a big and a small fish to solve puzzles. The fish had some dialogue ...
On the internet, nobody knows you're a fish.
I love how you were able to use these problems as a vehicle to transition from one concept to another so smoothly! Not too mention how smooth the animation itself was! You've earned a sub from me
Glad you enjoyed!
@@diplomaticfish19:14 melted my brain send help
@@XanderAnimationsWe can cope together brother.
@@Ros2fi0 yh man
@@XanderAnimations yh
I was not expecting to watch one of the best math videos I've seen on this platform when I clicked on this video
I'm glad you enjoyed!
you guys always have the best production quality
We're back! We'll be doing a bit of upkeep on our channel in the next few days, so keep an eye out for that.
Also we totally forgot to put the timestamp for Challenge Question 5, but the claim in question is at 23:54 - 23:58.
I can tell this channel has a very bright future ahead
Note that this method can be generalized to also apply to non-symmetric polynomials, called Buchberger's algorithm. I usually resort to heuristic when solving this kind of problem, but I am shocked by the fact that it becomes very succinct when all polynomials in question are symmetric.
I just looked it up, very cool!
Great video! Proofs by descent always feel unreasonably powerful to me, and none more so than the proof in this video. It's just such beautiful logic
This video gave me that bad feeling of knowing ill have to do a bunch of calculations to maybe get somewhere, even tho it was not me doing them, and i knew that it would get somewhere.
The fact that result is all of sudden rational and not 4 is a crime.
4 is rational
@@B3Band well but 4 is integer too, which fraction definitely is not.
It doesn't generalize to the second system, but I think there is a different way for system 1 that doesn't find an explicit equation for one of the variables(and which I think avoids a lot of the computations). Notice that there are four ways to get x^4 + y^4 + z^4 somewhere in the expansion with what we already have:
(1): (x+y+z)^4 = 3
(2): (x^2+y^2+z^2)^2 = 4
(3):(x+y+z)(x^3+y^3+z^3) = 1
(4): (x^2+y^2+z^2)(x+y+z)^2 = 2
Let us denote:
S= x^4 + y^4 + z^4
A= yx^3 + xy^3 + zy^3 + yz^3 + xz^3 + zx^3
B=(xy)^2 + (zx)^2 + (yz)^2
C = x^2yz + y^2xz + z^2xy
By expanding (1) through 4 we get that:
(1) = S +B = 3
(2) = S + 2A = 4
(3) = S + 6A + 4B + 12X = 1
(4) = S + 2(A+B+C) = 2
Solving this linear system we get the correction answer: S=25/6 x^4 + y^4 + z^4 = 25/6
That's a great observation! This hints at another interesting fact: the so-called "power sums" x+y+z, x^2+y^2+z^2, and x^3+y^3+z^3 can also form any symmetric expression in 3 variables, just like the elementary symmetric polynomials can. In fact, when I was first writing the script for the video, I used your method to solve the first system, but I changed it later so it would lead more smoothly into the rest of the video.
Close to the most exciting mathematical journey I’ve had so far on yt!
Thank you very much for your work! Good luck in SoME3!
This is a really cool theorem, I think it would be pretty straightforward and fun to implement as a computer algorithm 😄
Great content guys, I wish you guys had 1000 more videos. They way you guys explain stuff is badass and really intuitive
Thank you! They are a ton of work but we will be making more
@diplomaticfish I bet, the math alone probably takes quite some time and then making the video animations and all that. And editing. Wish I could do stuff like that lol I'm only in Calc 2, striving to be like u guys
I wad actually shocked this video had so little views considering the production value and the great way you explained everything. Definitely subbing and hoping you get bigger in the future!
I was working with something related for years. This is a formula I got to:
If p_n is the sum of the variables to the n'th power then. s_n*n=sum of [s_(n-k)*p_k*(-1^(k+1)] from k=1 to k=n
Where s_0=1.
It's basically the inverse statement of the theorem, which I didn't know existed by the way😂
By the way that formula works when there are infinitely many variables (I don't remember if it works with finite) and it give a sequence of equalities such as. s_2=1/2*p_1^2-1/2*p_2
Which in turn gives q sequence of sets of coefficients (1/2,-1/2 in the example above) that remain a mistery to me, I couldn't find a close formula for those
Second video I’m excited
(After watching) That’s amazing! Before I watched how to solve it, I just tried to solve for x, y, etc. and stuck. I did know we can solve without doing that, but I didn’t know it was more efficient.
My mind was blown like twenty times and I haven't finished the video yet, I just finished watching the second system of equations. Beautiful stuff
Finally some good-ass motivation for learning conmutative ring theory...!!!! Well done man
Thank you so much. I learned about this during my first year of license and I never understood it deeply. I just knew vaguely that there was a link between the roots of polynomials and those very symmetrical systems of equations, but now I see clearly what there is in between. You have relieved me from an old frustration. Thank you ❤
I'm glad you found it so helpful!
incredibly useful method and you summed it up so, so neatly and so concisely that anyone with a basic understanding of algebra can grab it. amazing stuff, subbed
As an 11th grader in calc who is a super nerd when it comes to everything math and science and has really bad ocd this tickles my brain in all the right ways 😌
Don’t question my wording
I'll be honest, this video was pretty dry, having no fancy graphs or spinning animations. But I'll take this in a HEARTBEAT over a two hour lecture with all this madness filling six blackboards in a nearly illegible font.
Thank you for making this video. The video being dry isn't a criticism - I think it has to be by the nature of the subject. You guys made it so much easier to digest than a university lecture ever could.
reminds me of a roots of polynomials strategy that a markscheme once used and none of us could think of
Dude your production quality is so dang good bro
Good luck for a million subs
I like how the fact that the polynomial is symmetric is only used in showing that d1>=d2>=d3>=d4. Subtle hypothesis usage is always fun
agreed :)
I was quite confused about why d1>=…>=dn and ended up writing a whole comment asking about it at which point I deduced a statement that would need to be true in order for d1>=…>=dn to be true and only then was I able to see how that statement followed from symmetry
i have always wondered how to solve these THANKS
Absolutely fantastic content!!! You rocked my Sunday!
Interesting video. The elementary symmetric polynomials S1,S2,S3,... are seemingly playing the roles of basis vectors in the space of symmetric polynomials and procedure for writing the symmetric polynomials in terms of the elementary symmetric polynomials looks a lot like the Graham-Schmidt method for obtaining an orthogonal basis of a vector space.
That's a great observation! They aren't quite basis vectors because you need to take products of them with each other to get everything. But if you consider the set of all expressions of the form s1^a s2^b s3^c, where a, b, and c are nonnegative integers, this infinite set is exactly a basis for the space of symmetric polynomials.
In the video, we only proved that this set spans the space. To prove it's a basis, you need to prove uniqueness of the representation (which is one of the challenge problems we posed!)
I feel like the fact that the value increases as the powers do is a dead giveaway that it's not an easy equation.
Omg, this is legit one of the greatest videos I have seen in UA-cam, how tf does it not have 100k likes?!?
Glad you enjoyed!
This is so well done that I love it.
Congratulations.
Cool stuff! Feels really good to understand the whole thing.
your video qualities are just awesome, try to be more consistent tho
loved this concept and the way u explained it
Solving the original problem is much, much simpler than what is shown in the video. Since all of the equations involved are symmetric, an approach using only symmetric equations can get you there with no cubics, no roots and only a few simple fractions. Here's a sketch:
Call the three given equations I, II and III.
Square I and combine it with II to learn that xy+yz+xz= -(1/2) (call this IV)
Now, cube equation I and combine it with I, III and IV to get that xyz= 1/6 (it's slightly tricky but you can recombine and factor some things). Call this one V.
Then, square equation II. Call this equation VI. It says: x^4+y^4+z^4+2x^2y^2+2y^2z^2+2x^2z^2=4
Now take equation I to the 4th power. This involves some multinomial work, so it's a bit of a pain, but NO ROOTS are needed.
Simplify this monster--you need to use I and II and IV and V to do it. You can get
x^4+y^4+z^4+6x^2y^2+6y^2z^2+6x^2z^2=11/3
Finally, take 3 times equation VI minus equation VII and you get the result.
I did it in about 20 minutes. It took longer to type up this comment than to solve the problem. 🙂
But it's a very nice video. Good job.
Yep, this is a great way to do it! We're aware of simpler solutions, but we wanted to give this more complicated naive way to illustrate the benefit of taking advantage of the symmetry.
Before watching: I have no idea how to solve it, but I think the first three eqns probably pin the solutions to (x, y, z) to just six possibilities. Maybe all of them give the same result for the sum of the fourth powers.
My brain is so educated and fried at the same time that I'm going to put on a fish channel on the TV and watch it with my cat
I used basic algebraic identities to solve the first system. The second system though needed way more than that.
Amazing production
Loved the video, laughted at the outro 😂
I like that it's about a bit so well known topic and explains it well 😇
Method for solution of multiple algebraic equations is available by software using algorithm to find the Groebner basis.
You guys deserve more sub .
Keep up the good work .
You earned a sub❤
1:58 pueberty hit him like a bus
This is how I did this:
Squaring eq.1 and using eq.2, you get xy+xz+yz=-1/2. Then cube eq.1 to get cubes and mixed terms that are expressible in things you already have, and you get xyz=1/6. Last, multiply eq.1 and eq.3 to get 4th powers and mixed terms like x²(xy+xz) and their cyclical permutations. But x²(xy+xz) + two permutations = x²(-1/2 - yz) + two permutations. So now you can express x⁴+y⁴+z⁴ in terms of xyz, x+y+z, and x²+y²+z², all of which I already found numerical values for. So in the end I get 25/6.
This way I did not have to go through the horrible expressions in the video around 3:54, involving cubes of the outcomes of the quadratic solving formula. At around 5:54 in the video it comes nice again, but to get there was quite painful unless you are using a symbolic computer solver.
This is a good alternative method! We showed the hard way solving the first problem to emphasize the benefits of using the elementary symmetric polynomials.
this is really good!! lovely interesting topic, so beautiful and really well explained!!
Just as for your video on Euler's number e, I am again mesmerized by the way how you go through all the steps. Please go on like this. I am very curious about how this will go on.
Great video. Thank you
I kept waiting for quaternions to make their entrance.
It is amazing
❤
Thank you very much❤
well done, thanks for such an interesting video
Watched all the video this deserves a subscribe
Hopefully you’re still reading comments;
I was not able to follow the part in the proof that showed that the highest multi degree term has its variables in descending order. I can see how the rest of the proof would follow from that statement, but I don’t see why that’s true for each step of the descent to multi degree 0. After all, because the polynomial is symmetric there must be a term that does not have its exponents in descending order whenever there’s a term in which the exponents aren’t all the same. That term must get subtracted off at some point in the process but by the logic of the proof it can never be the term of highest multidegree. The only solution to this would be if every ordering of ax_1^(e_1)…x_n^(e_n) appears in the product as_1^(d_1-d_2)…s_(n-1)^(d_(n-1)-d_n)s_n^d_n where {e_1,…,e_2} = {d_1,…,d_n} and ax_1^(d_1)…x_n^(d_n) is the highest multidegree term AND no ordering of bx_1^(e_1)…x_n^(e_n) appears in any other subtracted term.
Now as I was typing this out I actually realized why it is true, but I haven’t formalized it and proving that statement above still feels like an important stage in the proof that got glossed over during the “exponents are always in descending order” Lemma
If I'm understanding your comment correctly, it sounds like you agree with the following fact: If a polynomial is symmetric and contains a monomial like ax1^d1....xn^dn, then it must contain all symmetric variants of that monomial as ax1^en...xn^en, where the e's are a rearrangement of the ds. Thus, at least for the symmetric polynomial we start with, the exponents on the highest multidegree term must be in decreasing order.
But the key fact is that at each step, we subtract off a product of the elementary symmetric polynomials, so we're subtracting off a symmetric polynomial from our symmetric polynomial. And the difference of two symmetric polynomials is again symmetric. Hence, the same logic we used to argue that the highest multidegree term of the initial polynomial must have exponents in decreasing order can also be used for any of the intermediary polynomials. We also know that the highest multidegree strictly decreases at each step, and any strictly decreasing sequence of nonnegative integers must eventually terminate at 0.
It sounds like you were initially confused how terms with exponents not in decreasing order could ever get subtracted off. But you realized that they could get subtracted off if the as1^(d1-d2)...sn^dn handled all symmetric variants at once. This is not something that needs to be proven, because we already have a complete proof of the theorem above. Rather, it is a necessary consequence of the fact that we already know we have to end up with a constant.
However, if you want a proof of that fact independent of the theorem, just note that as1^(d1-d2)...sn^dn is symmetric, so it will contain all symmetric variants of a particular monomial (all with the same coefficient). Hence, subtracting it will get rid of all the symmetric variants of the highest multidegree term all at once.
Let me know if this answered your question, or if you have further thoughts!
@@diplomaticfish this did indeed answer my question, thank you!
Great video! That's a monster of a method for determining the polynomial in terms of the elementary symmetryic sums though. Is there a computationally faster approach?
Not to my knowledge. If you go into the problem knowing about the elementary symmetric sums, I think finding the polynomial is pretty quick. The main difficulty would be finding w^3+x^3+y^3+z^3, which we needed to find the sum of fourth powers. There's a collection of formulas called Newton Sums ( en.wikipedia.org/wiki/Newton%27s_identities ) that helps find these power sums quickly.
honestly this is a great exercise, i doubt this is the most efficient method but:
i got 25/6 by expanding 1=(x+y+z)^4=x^{4}+4x^{3}y+4x^{3}z+6x^{2}y^{2}+12x^{2}yz+6x^{2}z^{2}+4xy^{3}+12xy^{2}z+12xyz^{2}+4xz^{3}+y^{4}+4y^{3}z+6y^{2}z^{2}+4yz^{3}+z^{4}
which i then split up by coefficients lets call those with a 1 A, 4 B, 6 C, 12 D
so the equation is now 1=A+4B+6C+12D where we're looking for A;
to find B =x^{3}y+x^{3}z+xy^{3}+xz^{3}+yz^{3}+y^{3}z by considering (x3+y3+z3)(x+y+z) we rewrite it as B=(x3+y3+z3)(x+y+z)-A=3-A
to find C = x^{2}y^{2}+x^{2}z^{2}+y^{2}z^{2} we consider (x2+y2+z2)^2 leading to C=((x2+y2+z2)^2-A)/2=2-A/2
to find D = x^{2}yz+xy^{2}z+xyz^{2} we can factor out an xyz leaving us with just, xyz
to find what xyz is im not sure if i did the best thing but if you cube 1=(x+y+z) you get x3+y3+z3+3(x2y+x2z+xy2+xz2)+6xyz where the thing in the brackets is just (x2+y2+z2)(x+y+z)-x3-y3-z3 which equals -1 so to find xyz you just have 1=3-3+6xyz, xyz=1/6 so D=1/6
we then plug that back into the beggining 1=A+4(3-A)+6(2-A/2)+12(1/6) which rearranges to A=25/6
I used the same method and got 61/12, so probably made a slight arithmetic error somewhere. I still like this way because you only need to know how to expand (or use wolframalpha to skip the grind) and then use some clever logic to group and factor the terms and substitute the given values whenever possible.
Yes this is a great method! It hints at the fact that the power sums x+y+z, x^2+y^2+z^2, and x^3+y^3+z^3 can also form any symmetric expression in x, y, and z, just like the elementary symmetric polynomials can.
For this type of symmetric polynomials there is Newton formulas
I used them to calculate coefficients of characteristic equation using trace and matrix multiplication
In case anyone was wondering, if you have a system of n equations of n variables [a_1…a_n] where the kth is
Sum { i=1,n} (a_i)^k=k
following this pattern, the general solution for the sum of (k+1)th powers is 5^(n-1)/(n!)
cool!
This is awesome!!
very neat and will use in comps :D
Great video! Subbed
I think you should change the channel picture, which is blue “d”, to the fish on 27:50
banger idea
roger that
What are you talking about? There's no fish at that time stamp
@@mrosskneIt was mistake it’s actually at 27:40
Incredible video! I'm so jealous of the animation. How did you make it?
Looks like they’re using manim, the 3blue1brown animation library
yep! here is the link to that if you want to try yourself ( www.manim.community/ )
i sincerely feel very intimidated by the second system, i dont even wanna try to solve it
Great stuff dudes
Awesome video!
What an amazing video
Wow excelente aporte
Very good. I presume that Lagrange had formulated this when he was trying to come with his method of getting formulae for solutions to polynomials.
Reminds me of how the trace powers can be used to find a matrix's determinant.
Incredible video
omg diplomatic fish!!
Newton worked on the symmetric functions 1665-1666 and published Newton's theorem on symmetric polynomials 1707 in his Arithmetica Universalis. This theorem is the foundation stone of Galois theory.
I can feel my 12th grade brain expanding while watching this super interesting video
happy to hear that you're getting an early start with these concepts. Symmetric polynomials are taught in a college level Abstract Algebra class. My school didn't cover them until Abstract Algebra 2. It's essentially the study of how all the roots of a polynomial behave similarly and exploiting that fact to compute values without giving any regard to what the actual value of those roots are.
With Newton's identity is very simple. Set S_n=x^n+y^n+z^n and s_1=x+y+z, s_2=x*y+x*z+y*z and s_3=x*y*z then , x,y,z are roots of polynomial (in t) t^3-s_1*t^2+s_2*t-s_3. Then if t=x,y or z t^3=s_1*t^2-s_2*t+s_3 and t^4=s_1*t^3-s_2*t^2+s_1*t.
Note that s_1^2=S_2+2*s_2. Therefore we obtain the system
s_1=S_1=1,S_2=2,S_3=3,
S_2=s_1^2-2*s_2, (s_2=?)
S_3=s_1*S_2-S_1*s_2+3*s_3 (s_3=?)
S_4=s_1*S_3-s_2*S_2+s_3*S_1.
It is simple, and fast
Respect to people who understood that video
Great Video ! quick question : what software did you use to produce this video ? maybe manim ?
Yep, we used ManimCE ( www.manim.community/ )
Very nice video! Can I ask what software you're using to make these animations? They were really well done.
We used ManimCE ( www.manim.community/ ). It's a community-maintained version of the python library that 3b1b uses to animate his videos!
Awesome explanation. Was wondering if the coefficients such as 3, 4 and 6 obtained can be further generalized in this theorem, using Binomial Coefficients, (i.e binomial theorem with values ³C¹, ⁴C¹, ⁴C²) based on number of variables and respective powers to which they are raised.
Yep! These are related to the so-called multinomial coefficients ( en.wikipedia.org/wiki/Multinomial_theorem )
25/6 is pretty close to 4 though, I think we should get at least half credit for accuracy ;)
Beautiful
damn it's been a year
can't wait for next video
When you already know everything the math teacher is saying, so you need something to pass the time.
Great video. I have one question though. If we find a polynome that has all the variables as roots (such as the one at 4:13), does every variable have to be different root (meaning that i have total number of solutions equal to the number of permutations of the roots)? I ask because it is important when i want to know the real solutions x,y,z for such system.
It depends on the system. Sometimes not all the roots of the polynomial will be distinct, so there will be less actual solutions than you'd expect. But there's a slick method for computing whether a polynomial has repeated roots or not without actually finding the roots: ( stackoverflow.com/questions/50546553/find-if-polynomial-has-multiple-roots )
They have a better way to find (sum root^n) = (sum root^(n-1))*s1 - (something). it have only N^2 term, rather than N^n term when you use (s1)^n
bravissimo! ❤
Thank you. I comment so UA-cam would recommend me similar channel.
4+ 1/6
ie 25/6??
bro i literally solved using transformation of roots taking 10 mins and u did it in 4 seconds
big hats off bro
where's the answer of the questions in the outro?
i got
(1) s1^2-2s2
(2) x^3-2x^2
(3) 8
is that correct?
very interesting vid btw
We didn't include answers to the problems, but I can give some feedback:
1) This produces x^2 + y^2 + z^2, but we wanted the sum of the cubes. Try starting by cubing s1, and then figuring out what you need to subtract off to leave only the sum of the cubes.
2) Correct.
3) I get something different. If you write the desired expression in terms of elementary symmetric polynomials, it should be s2^2 - 2s1 s3 - 4s4. Then if you write the polynomial as 2(t-w)(t-x)(t-y)(t-z) and expand like we did in the video, you get s1 = -1, s2 = 2, s3 = 1/2, and s4 = -1/2.
suggested resources to delve deeper into the topic?
I want to know how to solve for the complex numbers x,y, and z in the beginning of the video.
these equations look very similar to equations for the characteristic polynomials of matrices to different powers
I gave it a go first before seeing the method and did this to get the answer 25/6:
expanding (x + y + x)^2 = x^2 + y^2 + z^2 + 2(xy + xz + yz)
solve for xy + xz + yz = -1/2
expanding (x + y + z)^3 = x^3 + y^3 + z^3 + 3(x + y + z)(xy + xz + yz) - 3xyz
solve for xyz = 1/6
expanding (xy + xz + yz)^2 = (xy)^2 + (xz)^2 + (yz)^2 + 2xyz(x + y + z)
solve for (xy)^2 + (xz)^2 + (yz)^2 = -1/12 (hello complex numbers?)
then finally expanding...
(x + y + z)^4 = x^4 + y^4 + z^4 + 4(x^2 + y^2 + z^2)(xy + xz + yz) + 8xyz(x + y + z) + 6[(xy)^2 + (xz)^2 + (yz)^2]
and solve for x^4 + y^4 + z^4 = 25/6
think can modify this method by just expanding
(x + y + z)(x^2 + y^2 + z^2)...
(x + y + z)(x^3 + y^3 + z^3)...
but now i look at the systematic way of doing it and it's much easier and idk why i didnt see that initially
Yes this is a great alternative method! If you've heard of Newton's identities ( en.wikipedia.org/wiki/Newton%27s_identities ), they are a more systematic and general set of formulas for carrying out this method.
first time hearing about this method. can see how it's very similar to what i did here in a general form. i just remembered while i was in high school, i was solving one of the waterloo CMC questions in a book i have:
x + y + z = 0
xyz = -2
solve for x^3 + y^3 + z^3
and used a similar approach here in your problem to solve for it, remembering the strange factoring. but for the 2nd problem you present, it's way more confusing to look at. I could do the same approach probably for that one. Now I think about it, I did do a contest question long ago while in school which involved a polynomial which all x, y, z where all roots of, and wanted to find x^5 + y^5 + z^5 and used the same method by multiplying the variable and subbing it back into itself to find the next sums of powers. I just can't seem to remember where that question was.
I teach high school math and it's always great for me to be learning new things! thanks for sharing @@diplomaticfish
Lets see what you cook for the next some
what software do you use to make the visuals for these videos?
We use ManimCE ( www.manim.community/ ), a community-maintained python library
what a video
Is it sufficient to show that products of the symmetric basis polynomials are linearly independent to show the expansion is unique?
Yep, that's exactly the right idea!
at 23:45 If we only try to cancel the terms with highest multidegree then wouldn't that cause some terms with not decreasing left out ?
Good question! It turns out that since what we're subtracting is a symmetric polynomial, it not only cancels the term with highest multidegree, but also all "symmetric variants" of that term. If you try a small example you can see what I mean explicitly.
Ofc 4
Is there a way to systematically find the term with the biggest multidegree in every step without doing unholy amounts of algebra?
Yep, if you have a product of a bunch of polynomials, the term with highest multidegree is the product of the terms with highest multidegree in each factor. You can also use symmetric sum notation to greatly reduce the amount of writing you have to do when multiplying things out ( artofproblemsolving.com/wiki/index.php/Symmetric_sum ).
the editing feels a lot like 3blue1brown but i like it, you put a lot of effort into it
We use more or less his same python library :)
@@diplomaticfish there's a python library that does this?? what people can do with python never fails to amaze me lol, good job on the video regardless