You see nonlinear equations, they see linear algebra! (Harvard-MIT math tournament)
ฝัง
- เผยแพร่เมื่อ 29 มี.ค. 2024
- Get started with a 30-day free trial on Brilliant: 👉brilliant.org/blackpenredpen/ ( 20% off with this link!)
This system of nonlinear equations is from the general round of the 2023 Harvard-MIT math tournament. www.hmmt.org/www/archive/271 I will present the linear algebra method I learned from their official solution to solve this system because I thought it was fascinating. It's from Harvard and MIT, of course, it is awesome!
3 ways of finding the determinant of a 3x3 matrix: • How to find the determ...
Try "my first Harvard-MIT math tournament problem": • My First Harvard MIT M...
----------------------------------------
🛍 Shop my math t-shirt & hoodies: amzn.to/3qBeuw6
💪 Get my math notes by becoming a patron: / blackpenredpen
Get started with a 30-day free trial on Brilliant: 👉brilliant.org/blackpenredpen/ ( 20% off with this link!)
you are talking so much
i have another way
xy + z + xz + y = 40 + 51
x(y+z) + y + z = 91
(x+1)(y+z) = 91, we know that y+z = 19 - x, so :
(x+1)(19-x) = 91
19x - x^2 + 19 - x = 91
x^2 - 18x + 72 = 0
(x-12)(x-6) = 0
x = 12 or 6
then just plug x into the equation and we will get the same value of y and z like in the video, CMIIW :3
Yea. He said he would leave the substitute method for us to use. This was about using linear algebra to solve the problem
@@NarutoSSj6 okay
@@NarutoSSj6no way, did he really?
Я решил так же😄.
I've decided the same way
Same bro 😊
As they say, “linear algebra is limited to linearity property, but oftentimes, it is easy to fit your nonlinear problem in a linear form”
Who says that? The voices in the head?😂
Add 1st and second equation (y+z)(x+1)=91
x+1+y+z=20
Take x+1 as a and y+z as b
Then ab=91 and a+b=20
So (a,b)=(13,7),(7,13)
x is either 6 or 12
I started Gauss-Jordan elimination on the matrix at 5:18, got to [1 1 19-x] [0 x-1 x+32] [0 1-x x²-19x+40] and concluded that -(x+32) = x²-19+40 (to make row 2 + row 3 = 0), which gives x=6 and x=12.
Adding first two gives
(x+1)(y+z) = 91
Final gives
(x+1)+(y+z) = 20
Solving for x+1 and y+z gives the pair (7, 13), in either order.
Backsubstituting in the first eqns, et voila.
Yeah... also I did it in a very similar way but I then interpreted "x+1" and "y+z" as the zeroes of the equation z^2-20*z+91 = 0 and obtained so the two solutions suggested in the video, this problem can thus be solved quite quickly, maybe he simply wanted to intentionally apply concepts from linear algebra here, although that would not be necessary.
Only under the assumption that x+1 is an integer
@@Bayerwaldler Nope, why? Solving for x+1 and y+z allows them to be any real numbers (or complex or much more). That is a quadratic. It just turns out to be an an integer solution.
@@joseluishablutzelaceijas928 Yes, I agree.
I give a LinAlg course this quarter and thought of borrowing it as a different type of exercise when I saw the title, but I think it is a bit contrived given that easier approaches come to mind.
@@landsgevaer Aah - I see. You get a quadratic equation like -u^2 + 20u = 91 where u = x+1. Then the rest follows nicely. Very good!
I have another way
x + y + z = 19
xz + y = 51
xy + z = 40
y = 51 - xz
z = 40 - xy
x + 51 - xz + 40 - xy = 19
x - xz - xy = -72
-x (y + z - 1) = -72
x (y + z - 1) = 72
x + y + z = 19 then y + z - 1 = 18 - x
x (18 - x) = 72
18x - x² - 72 = 0
x² - 18 x + 72 = 0
(x - 6) (x - 12) = 0
x1 = 6 x2 = 12
Next:
y + z = 13
y + 6z = 51
6y + z = 40
6y + z = 40
3y + 3z = 39
3y + 18z = 153
(Substracting)
-20z = -152
z1 = 7,6 y1 = 5,4
y + z = 7
y + 12z = 51
12y + z = 40
12y + z = 40
6y + 6z = 42
6y + 72 z = 306
(Substracting)
-77z = -308
z2 = 4 y2 = 3
Solutions:
x1 = 6
y1 = 5,4
z1 = 7,6
x2 = 12
y2 = 3
z2 = 4
Add the first 2 equations, factor and take 2 cases, you are done
If I understood correctly, that's the same way I did it. If you add the first two equations, you get x(y+z) + (y+z) = 91. After that, using the 3rd equation, you get y+z = 19 - x. So, you can easily find both values of x. Then, using the first two equations again (this time, as a linear system of order 2), you find y and z for both cases.
Only under the assumption that x+1 is an integer
@danieldepaula6930 genuinely asking as I'm not 100% sure, when you add the first two equations together don't you need to do X×Z?
@@ZackBlackwood97 I didn't understand exactly what you mean, but this is it (step by step):
xy + z + xz + y = 40 + 51
xy + xz + y + z = 91
x*(y+z) + (y+z) = 91
And as you have that y+z = 19-x by the third equation, you can find x.
@@danieldepaula6930but that has complex roots
Adding the first two equations, you get (y + z)(1 + x) = 91.
From the second equation: y + z = 19 - x.
Substitute and get (19 - x)(1 + x) = 91.
Solving for x with Bhaskara's Formula, you obtain x = 12 or x = 6, and so on.
2:43 I love how these 3 equations actually do still have a valid real number solution
Love the way u solve it. Thx. ❤
I combined the first two equations, did some algebra to get (x+1)(y+z)=91, used the third to replace (y+z) with (19-x), and arrived at that same quadratic. After which I promptly made a sequence of arithmetic errors solving the quadratic and then subsequently even more arithmetic errors solving the resulting system of equations. It turns out that if you fail at basic arithmetic, math is hard. :)
I love how the math you do is simple and understandable, but used creatively.
Linear algebra is one thevmost useful math tools i never used unless forced to in my undergrad
What applications do you use it for now
@@darcash1738 nothing, couldn't get a job with my math degree.
Really useful in physics and especially computer science
2:32 was is a coincidence because 5y+2z=10,y+z=3 and 2y-z=1 has a solution which is (y,z)=(4/3,5/3)
I was doing this method of eigenvalues to solve systems of differential equations at my differential equations class today. Good lecture professor!
More of these please 🙏🙏
Loved this approach, thinking out of the box
Proud to have been able to solve this problem
I haven't heard about any of those things but it sounds cool.
In the example at 2:30, the 3rd equation is actually the 1st minus 3 times the 2nd, meaning it is also redundant
You don't need to solve the cubic, you can just say that it's easy to see that the first two rows of the 3x3 system of equations are linearly independent, therefore the third row must be expressible as a linear combination of the first two. Then looking at the left hand side, the respective coefficients must be 1/(1+x) and 1/(1+x), which yields 91/(1+x) = 19-x, x=6 or x=12.
Your digression about the 0 determinant not always giving solutions also applies in reverse. If you look at where the first two equations are linearly dependant, that must give 0 for the determinant, which gives you a root of the cubic (x=1) without needing to notice anything about the coefficients.
What happens if you equate phytagoras Therom to the quadratic formula or is that not possible
6:16 determinant of a determinant ?
Beautyfull. Thank you very much because you helped me to solver this exercise of Lineal Algebra.
Time for cheap tricks;
Computing L1+L2-L3- x L3
on the left hand side... we have
(xy+z)+(xz+y)-(x+y+z)-x(x+y+z)
carefully cancelling...we are left with
-x-x²
The right hand side is 40+51-19-19x=72-19x
-x-x²=72-19x
Then I got lazy... but we arrive at the same polynomial of x(up to a non-zero scalar multiple) so it should arrive at the same solution
How much would you bet that whoever came up with this problem started with the functions x*y+z, x*z+y, and x+y+z, picked some values for x, y, and z, and plugged them in to get the values x*y + z = 40, x*z + y = 51, and x+y+z = 19, only to be surprised later when it had multiple solutions?
quadratic equations are expected to have two solutions; because the numbers are real, both roots must be either real or complex conjugate
2:42 y = 4/3, z = 5/3. The third equation works just fine....
THANK YOU for this idea, can't believe is was that simple to fix x as a constant and take determinants - since x is non-zero!
Ignore all of the comments talking about the trivial way to solve this with gauss-elim, they don't understand the power this method has
Can you make a video on how to use Weierstrass factorization theorem?
When I was in school these were called "Simultaneous Equations". Not sure when the term "Systems of Equations" became the preferred term. I only heard for the first time about a year ago.
Extremely interchangeable but system usually refers to 3+ variables in my experience
‘simultaneous equations’ is commonly used in school mathematics
‘system of equations’ is commonly used in the field of linear algebra, from high school to university
Yess I asked for more last video and got more 😂
This question is to be answered until 11:59 am, for those who have the last digit of their DNI 5: What is the letter you like the most among A, B, C, I, N , The m?
wow, i like how you using matrix as part of solving
Another way is let w = y + z and it can form an quadratic equation
Hey I am an high schooler, I didn’t know most of the determinant formulas you used , but your video was fascinating. Thank you.
The way I had solved this I got values which when added and multiplied givens answers close to 40,51,19. The set of answers was (x,y,z)=(7.3,4.6,6.2) and this is the only set I got.
This is a beautiful problem.
Any closed contour integral videos?
It was great seeing an extraneous solution that didn't solve the systems of those nonlinear equations by trying to turn a 3x2 matrix multiplied by a 2x1 matrix to form a 3x1 matrix of solutions. We saw extraneous x=1 that didn't work with x=6 and x=12 that both do work as solutions in what was taught. Sometimes looking at a problem creating polynomial solutions both extraneous and good solutions get intermixed to allow us to see potentials that fail but can inter result. 👍
hi, thanks for the video, it's interesting as always, do you have a video where you detail more the method you're using at 10:00 for finding the factors of the cubic equation ?
also I tend to have the issue in maths that I try to brute-force a lot of calculations without thinking to use methods that would be easier, like in this case using substitutions and big annoying calculations instead of just thinking to use the determinant like you did, so do you have any method beyond just habit, training and exercises to have some idea of what methods to use whenever you see a new math problem ? is there anywhere you might check online if you're not sure what to do ? I'd love to see how your thought process goes from the moment you discover the problem
For the factors part, as he said in the video, he inspect the equation and saw that if you replace 1 in X then you will get 0=0 meaning that the cubic equation is divisible in (x-1) then you do so using ruffini method, sorry for the bad english, but I hope you understood
Got 'em both!
Before looking at BPRP's solution: I was able to factor the information in the equations into a quadratic in terms of x, yielding two results. One case yielded a solution in the Rationals while the other yielded a solution in the Naturals, so depending on the set the variables are meant to be from, there are either one or two solutions.
After watching BPRP's solution: the quadratic I obtained was the same, but the factor of (x - 1) in the cubic was a redundant solution because of the matrix multiplication. I eliminated that solution because I had used a linear transformation while I was manipulating the original equations to extract the quadratic in x. Always worth checking solutions with the original equations as well as any obtained through linear algebra manipulation to ensure they are true solutions rather than redundant (i.e contradictory) solutions.
det(x 1, 1 x)=x^2-1 detψ(40 1,51 x ) =40x-51 detz(χ 40,1 51)=51χ-40 ψ=detψ /det z=detz/det we substitute into third equation x^3-19x^2 +90x-72=0 x1 x=6 ψ=5.4 z=7.6 x=12 ψ=3 z=4 x>=1 x
we can solve by adding the equations
xy+z=40 eq1
xz+y=51 eq2
x+y+z=19 eq3
on adding eq. 1,2,3
x+xy+xz+2y+2z=110
adding 2 on both the sides
x(y+z+1) 2(y+z+1)=112
(x+2) (y+z+1)=112 -------equation 4
from equation 3
y+z=19-x
substituting y+z=19-x in eq. 4.
(x+2) (-x+20)=112
-x^2+18x-72=0
(x-6)(-x+12)=0--------equation 5
from equation 5 x=6, x=12
substituting x=6 in equations 1,2,3 we get
6y+z=40--eq6
6z+y=51---eq7
6+y+z=19 --eq8
from equation 8
y+z=13
from equation 6
z=40-6y
substituting z=40-6y in eq. 8
-5y=-27
y=5.4
substituting y=5.4 in equation 8
z=7.6
Just watch Gilbert strang course too
11:55 that transition
We can also solve it without using determinant. For example, let us arrange these equations as xz + y = 51 ...(1), xy + z = 40 ...(2) and x + y + z = 19 ...(3). Adding (1) and (2) and factorizing, we get (x + 1)(z + y ) = 91 ... (4). Again subtracting (2) from (1), we get , on factorizing, (z - y)(x - 1) = 11 ...(5). From (3), (z + y) = 19 - x ...(6). Putting (z + x ) value in (4) , we get (x + 1)(19 - x) = 91 ... (7) solving this , we get ( x - 6)(x -12) =0, so that we have x = 6 or x = 12. Case - I, when x = 6, in (3), we we get z + y = 13 ... (7) and again putting x =6 in (5), we get (z - y) = 11/5 ... (8). From (7) and (8) we get z = (1/2)(13+11/5) = 7.6 and y = (1/2)(13 - 11/5) = 5.4. Therefore, the first solution set {x, y, z) = {6, 5.4, 7.6}. Case - II when x =12: putting this in (3) z + y = 7 ...(9). Again putting x = 12 in (5) we get z -y = 1 ...(10). From (9) and (10), we get z = (1/2)( 7 + 1) = 4 and y = (1/2)( 7 - 1) = 3. Therefore, the 2nd solution set {x, y, z) = {12, 3, 4}.
3, 4, and 12
This is a simpleproblem for an Harvard MIT math tournament
xy+ z =40 equation 1
xz + y =51 equation 2
x+ y+z = 19 equation 3
Let's add the first two equations : xy + z =40 and xz + y =51, Hence
xy + xz + y + z =91
x(y+z) + 1(y+z) =91 factor out y +z Equation 5
y + z = 19- x (solving for y+ z , using equation 3)
x(19-x) + 1 (19-x) = 91 (substituting 19-x into equation 5)
(x+1)(19-x) =91
(x+1)(-x+19)=91
- x^2 + 19- x + 19x =91
0 = x^2 -18x +72
0= (x -6)(x-12)
x =6 and x =12
Let try x=12 first using equation 1 and equation 2
12y + z=40
y + 12z=51
y = 3, and z=4
Hence x=12 , y=3 and z= 4
The next step is to solve when x =6
and using equation 1 and equation 2 again
6y + z =40 equation 9
y + 6z= 51 equation 10
36y + 6z = 240 mulltiply equation 9 by 6
y + 6z = 51
35y = 189
y= 189/35 y=5.4
z=266/35 z=7.6
x =6, y=5.4 , and z=7.6 answer as well This also satisfy the equation when x= 6, Hence x=12
Hence the answer is x=12, y=3 and z=4
I multiplied the 3rd by x, and then substituted xy and xz with the first 2 equations and then substituted y+z with the 3rd equation to get a quadratic equation with only x.
7:43 You can immediately see there's a X-1 factor in the determinant and factor it right away before expanding the 19-X.
X²(19-X)+51+40-(19-X)-51X-40X
= (X²-1)(19-X)+51(1-X)+40(1-X)
= (X-1)(X+1)(19-X)-91(X-1)
= (X-1)((X+1)(19-X)-91)
= (X-1)(-X²+18X-72)
i was thinking of row reduction while treating x as const
It is a really good question
Set up the equation x(Eq3) + (Eq3), and simplify using (Eq1) and (Eq2), you get x^2 -18x +72 = 0, then solve for x.
Next, multiply (Eq1) by x, simplify using (Eq2), solve for y to get y=(40x-51)/(x^2-1) and solve for y.
Lastly use (Eq3) to solve for z
Nice. I didn't know that trick.
Is there a better way to check if the solutions are valid? Or is the only alternative to testing?
What questiined me is why did value 1 appeared?
After a thought, beacuse it makes matrix singular not with row 3 being linear combination of rows 1 and 2, but columns 1,2 became collinear.
Subtracting Eq 3 from Eq 1 and adding 1:
xy-x-y+1=(x-1)(y-1)=22
Subtracting Eq 2 from Eq 1 and adding 1:
xz-x-z+1=(x-1)(z-1)=33
Substituting X=x-1,etc., we get:
XYZ=22Z=33Y
Or
Z=3Y/2
X+Y+Z=16.
So
2X+5Y=32
Subtracting Eq 1 from Eq 2:
zX-yX=(Z-Y)X=11.
So XY=22
Now we get:
(2X-5Y)^2 = (2X+5Y)^2 - 40XY = 1024 - 880 = 144
So
2X-5Y=+/- 12
4X = 44,20.
We then get X, Y, Z, and finally get the two solutions:
x=12,y=3,z=4
or
x=6,y=27/5,z=38/5
Pretty interesting PROF 👍
Ever heard of the Moore Penrose inverse
First eq take last eq:
xy - x - y = 21 (IV)
Rearrange third
z = 19-x-y
Sub this into second
x(19-x-y) + y = 51 (V)
Expand this and add to (IV)
19x - x^2 -xy +y +xy -x -y = 21+51
Simplify to
x^2 -18x +72 =0
(x-6)(x-12)=0
x=6, or x=12
Then sub into (IV) to get y and then into third eq to get z.
(6,5.4,7.6) and (12,3,4)
I guess I over-complicated this:
xz + y - (x - y - z) = 32 => xz - x - z +1 = 33 => (x-1)(z-1) = 33 (1)
xz + y - xy - z = 11 => (x-1)(z-y) = 11 (2)
1/2 => z - 1 = 3(z - y) => z = (3y - 1)/2 => x = (39 - 5y)/2
xy + z = 40 => 5y^2 - 42y + 81 = 0; y = 3 or y = 27/5
(x,y,z) = (6, 27/5, 38/5) or (12, 3, 4)
Just subtract eq.3 from eq.2 = eq.4
Subtract eq.4 from eq.1=eq.5
Substitute the value of x from eq.3 in eq.5
Factorise eq.5 and you get value of x
Substitute value of x and y in eq.1 to get y and z
Nice and very easy
What is this sorcery dividing by x-1 can you explain that technique????
just add equation first and second and factorise
I haven't seen Ruffini in ages!
12,3,4
(40 + 51) / (x + 1) = 19 - x
You could have just added equations 1 and 2 and factorise as (x+1)(y+z) = 91. Then substitute from equation 3 y+z = 19-x…..
12,4,3
Basically, we assume that this system is solvable, and from that assumption we solving simpler system, avoiding undefined behaviour, like setting variable to zero.
Truely useful method that gave me new insights about using the traditional Gaussian Elimination
However, If I were to be in that tournament, i would use the traditional Substitution method, because it seems specifically easier and faster in this question
xy+(19-x-y)=40
x(19-x-y)+y=51
adding both eq to get
18x-x^2+19=91
so x^2-18x+72=0
then x=6, x=12
solve for y and z
and get 2 solutions
12,3,4 and 6,27/5,38/5
Esta pregunta es para que me respondan hasta las 11:59 am, para los que tienen el último dígito de su DNI 5 : ¿Cuál es la letra que les gusta más entre la A, la B, la C, la I, la N, la M?
Could also use multivariable Newton method
I have a question, Let A B C, and k are Real numbers. If 2k^2k = ((A+B+C)^(A+B+C))/2, find k in terms of A, B, and C.
I assumed that x had to control the rank of the system. I determined that the rank had to be 2, so I did Converted the equation to augmented matrix system (4 x 3) and determined the x value to ensure that one of the rows go to 0’s for rank 2.
I got I think 2 values for x (I have to check I did this a long time ago) that trip this equation to a rank 2. Then solved for y a and x using cramers rule.
Anyways moral of the story: I don’t think you have to get the characteristic polynomial to trip this into a diminished rank anyways.
Solved this in the real test! :)
Did it in my head, 12,4,3
Me using Newton’s method to approximate the solutions 😢
I just think of an easy way which high school can solve this.
Since x +y +z = 19,
z = 19 -x -y ;
xy +z = 40,
so xy + 19 -x -y = 40,
then xy -x -y =21 … (1)
xz + y = 51,
so x (19 -x -y) +y = 51,
then 19x -x^2 -xy +y = 51 …(2)
Put (2) into (1),
-x^2 +19x -xy +x +y -x =51,
so -x^2 +18x -21 =51,
x^2 -18x +72 = 0.
We can get x = 6 or 12
This man is a genius
The method above makes absolutely no sense to me. I solved the bottom equation for y:
y=19-x-z
Then I substituted it into the first two equations which yields the following two equations in terms of x and z:
-x^2+19x-xz+z=40
-x+xz-z=32
When you add these two equations together, the z and xz terms cancel out and you're left with the quadratic: x^2-18x+72=0, so x=6 or 12. From there, it is easy to solve for y and z. (x,y,z) = (6, 27/5, 38/5) or (12, 3, 4).
The part you kinda zipped through was that cube root part? You said assume 1 is a sol. and then proceeded with that approach I’m not familiar with
The coefficients add up to 0, so x=1 is a solution.
He used the remainder theorem.
Remainder theorem says that if a polynomial (say p(x)) is divided by another linear polynomial(say (x-a)), then the remainder is given by p(a).
If p(x) is divided by (x-1), then remainder is given by p(1).
But, p(1) means x=1, so if the coefficients all add up to zero, then (x-1) should be a factor of p(x)
Guessing solutions and using the remainder theorem is a common method of solving higher-order equations :)
add all eqns , we get
xy + z + xz + y + x + y + z = 110
xy + xz + x + 2y + 2z = 112 - 2
x(y + z + 1) + 2y + 2z + 2 = 112
x(y + z + 1) + 2(y + z + 1) = 112
(y + z + 1)(x + 2) = 112
(y + z + 1)(x + 2) = 8 * 14
x + 2 = 14, y + z + 1 = 8
x = 12..........(a), y + z = 7.........(b)
given xy + z = 40
from eq(a),
12y + z = 40
11y + (y + z) = 40
from eq(b),
11y = 40 - 7
11y = 33
y= 3.........(c)
also given,
x + y + z = 19
from eq(a) and (c),
12 + 3 + z = 19
z = 4
(x,y,z) = (12,3,4) integer soln
I have a type of equation I'm curious about
x!=a
how can we easily solve this for any given value of a
I couldn't find anyone even mention factorialic equations like this
I'm sure there is a solution since we can just guess it by insertion or solve it graphically but that's lame so is there a better way?
Mit never disappoints 🗿
0:27 I did pause and try and it quickly became overwhelming when x, y, and z have to be the same in all three equations.... So, I gave up and erased my original comment.
[I will be like you sir (Mathematician)]
I wonder if solving geometrically in 3d is any better
(x+1)*(y+z)=91 - add the first two. x+1 + y+z = 20 Solve the quadratic.
I'd stop at the matrix.... then the cubic 😅 [edit] then for sure the 7.6.... lol
Add first two equations and put y+z = 19-x
I forgot that you could do the determinant of a non-square matrix
Could you explain why cos(sin(1/e)) ≈ 1? (In degrees)
It's because when x ≈ 0 ,
sin(x) ≈ x
and
cos(x) ≈ 1
I looked at it as an eigenvalue problem in disguise. You want the eigenvalue (-x) of the matrix {{0, 1, -40},{1,0,-51},{1,1,-19}}, where the eigenvector is (y,z,1). The eigenvalues are x = 1,6,12 and the reason 1 doesn't work as a solution is that the corresponding eigenvector is (1,-1,0) which doesn't have a 1 in the third position, contradicting the form (y,z,1).
So, we're basically treating the X as a parameter and using the standard method for linear system? Well, pretty genious move; good job americans
Very nice method, but i have a confusion like why this method work ? You get the value of x such that it make 1 equation redundant and i got that , but this doesn’t explain why such X value will be a value that satisfies the original equation with the other variables?
It won't be, but the solutions to the original problem will be in the set of the solutions of the cubic equation. So you just check the latter ones one by one. It's like when you square both sides of an equation.
Yes here is the problem, that this x value will be in the set of solutions, is there a proof for that , does this mean that this method will work for any 3*3 non linear systems such that this 3*3 systems have a unique solution in the first place ?
Its okay i watched the video again and got it