Quite useful ... for performance computing and hardware development, always looking at how to keep integers until I have to use floating point ... Thank you ...
Before you start trying to reinvent how to do high-performance Gaussian elimination with integers only, I recommend doing a fair amount of research... this is a _very_ well-studied topic. And it's easy to design pathological matrices that exponentially blow up the precision you have to store unless you use a clever algorithm - see rjlipton.wordpress.com/2015/01/14/forgetting-results/
I typically like to do an extra step where I find the LCM between the two numbers I'm trying to get rid of (so 6 for 2 and 3) then in the 2nd step I eliminate them by subtracting rows. It's more steps but each step I'm less likely to make a mistake since the additions between rows will always be by a factor of 1 or -1 and the multiplications ought to always make the two numbers the same, so I can check if the other entries were not multiplied correctly. The trick is to break down the problem into steps that your brain has optimized like -6 + 6 = 0.
I believe that this is effectively the same method. It just hides the multiply step and doesn't change the pivot row. Actually, yours uses the LCM, whereas this one just straight multiplies.
I'm about to take Linear Algebra starting this Monday. I have no clue what all of this is just yet but I'm saving this so I can reference it later on this quarter. Thank you, and great work!
just like you, i love the forward aspect but have no intention of that backwards component! i intend to implement this in code for fun. very neat trick. i think i understand why it works too. glad my linear algebra still feels fresh thank you for the great content and enthusiastic math, you're awesome
This is an excellent method! I wish I could use it in my linear algebra course but my lecturer requires that at each step I indicate which Elementary Row Operation was performed.
The use of the determinant here seems like it might just be a coincidental shorthand. It will haunt me unless someone finds a generalization that uses determinants of higher order matrices. But I don't even have the slightest idea of what it would even have to generalize - Guassian Elimination itself?
I think the algorithm in the video is just doing some shenanigans with Cramer's rule or matrix minors. Gaussian elimination will be exponentially faster than that for larger matrices.
@@AaronRotenberg I don't think you understand the method. Each entry only requires the determinant of a 2×2 matrix regardless of the size of the original matrix. Here is an explanation of the method I gave elsewhere: So you have a pivot row and a row you want to "update"; first, simultaneously multiply the pivot row by the first number in the "update" row and the "update" row by the first number in the pivot row; then, do the usual Gaussian Elimination on those two rows. What you've done is the simplest way to ensure that you get only integers in the rows, because now the number you want to turn into a 0 in the "update" row is the same in absolute value as the first number in the pivot row, so Gaussian Elimination amounts to adding/subtracting integers. At the same time, if you look at what you've done term by term in the "update" row, it's exactly the determinant described in the video, because you are just multiplying the respective terms by the first numbers in the other row before subtracting. I believe it is equivalent to standard Gaussian elimination in terms of computation time. If there is a connection to Cramer's rule or matrix minors, I would appreciate an explanation.
It's just the Gaussian Elimination with a factor to eliminate the fractions. Let's suppose you have a 2 x 2 system: a11x + a12y = b1 a21x + a22y = b2 To get a 0 in place of a21, by normal Gaussian Elimination, you multiply row 2 by -(a11/a21) and sum it with row 1: (-a11/a21*a21 + a11)x + (-a11/a21*a22+a12)y = (-a11/a21*b2 + b1), You can rewrite that as: 0 x + (-1/a21)*(a11*a22-a12*a21)y = (-1/a21)*(a11*b2 - b1*a21) and you just multiply by (-a21): 0 x + (a11*a22-a12*a21)y = (a11*b2 - b1*a21), and you can see the determinants right there. I'm no mathematician, but I hope I could help you.
Interesting technique, but how about proof that this is works. I think it maybe not too hard to do, because it uses basic row-summing with common multipliers for rows, etc. Interesting, how they relates with determinant. Thank you.
It is just a regular Gaussian elimination, but by only doing multiplication. For example: (2 5 | 3) (6 15 | 9) (3 2 | 7) becomes (6 4 | 14) We multiplied the first row by 3 and the second one by 2. This way, you can just substract them. Dr. Peyam's method is exactly the same, just doing two steps at once, with a determinant. I don't know if I'm very understandable, do not hesitate if you have any question x)
This is very interesting! I am taking Linear Algebra next term. Thank you! I have a question, professor. Does this work well with larger matrices? Or only systems of 3 linear equations of 3 variables?
So you have a pivot row and a row you want to "update"; first, simultaneously multiply the pivot row by the first number in the "update" row and the "update" row by the first number in the pivot row; then, do the usual Gaussian Elimination on those two rows. What you've done is the simplest way to ensure that you get only integers in the rows, because now the number you want to turn into a 0 in the "update" row is the same in absolute value as the first number in the pivot row, so Gaussian Elimination amounts to adding/subtracting integers. At the same time, if you look at what you've done term by term in the "update" row, it's exactly the determinant described in the video, because you are just multiplying the respective terms by the first numbers in the other row before subtracting.
2 1 4 |5 3 -1 2 |2 to take the determinants of first 2 rows is the same as to multiply the 1st row by the 1st element of the 2nd row (i. e. ×3), multiply the 2nd row by the 1st element of the 1st row , i. e. ×2 and then do the subtraction to eliminate the 1st element of the 2nd row the rest is done in the same concept
@@LaerteBarbalho Close. I am in the applied math trade, but I teach engineers linear algebra and numerical analysis. It goes like this: A) Here's Gauss-Jordan, by hand. B) Here's LU factorization with pivoting, by computer. C) Forget what you know and use Matlab backslash. :)
Are you sure about that? Computationally, integers and floating point numbers have different blind spots where they have to round. If given a problem in integers, converting to floating point might lead to unnecessary rounding errors.
Dr Peyam spoils us too much with this amazing content
Quite useful ... for performance computing and hardware development, always looking at how to keep integers until I have to use floating point ... Thank you ...
Before you start trying to reinvent how to do high-performance Gaussian elimination with integers only, I recommend doing a fair amount of research... this is a _very_ well-studied topic. And it's easy to design pathological matrices that exponentially blow up the precision you have to store unless you use a clever algorithm - see rjlipton.wordpress.com/2015/01/14/forgetting-results/
This way too good to be true!
This both saves time AND reduces mistakes which are extremely essential for competitive exams!
It is a very good way to find the solutions of linear equations without getting fraction.Thank you sir
Just amazing. I did not know this technique, but you have made my teaching a lot more enjoyable. Those fractions made me and my students going crazy.
I typically like to do an extra step where I find the LCM between the two numbers I'm trying to get rid of (so 6 for 2 and 3) then in the 2nd step I eliminate them by subtracting rows. It's more steps but each step I'm less likely to make a mistake since the additions between rows will always be by a factor of 1 or -1 and the multiplications ought to always make the two numbers the same, so I can check if the other entries were not multiplied correctly. The trick is to break down the problem into steps that your brain has optimized like -6 + 6 = 0.
I believe that this is effectively the same method. It just hides the multiply step and doesn't change the pivot row. Actually, yours uses the LCM, whereas this one just straight multiplies.
Wow, this is so cool!
Yoooo now we need Dr K to be featured on this channel!!
We should!!!
I'm about to take Linear Algebra starting this Monday. I have no clue what all of this is just yet but I'm saving this so I can reference it later on this quarter. Thank you, and great work!
Gauss would really be proud, thank you for this amazing method !
that is beautiful. i wish i knew this when in mathematics class. thank you Dr Peyam.
Simple and clear presentation. Excellent ! DrRahul Rohtak Haryana India has
just like you, i love the forward aspect but have no intention of that backwards component!
i intend to implement this in code for fun. very neat trick. i think i understand why it works too. glad my linear algebra still feels fresh
thank you for the great content and enthusiastic math, you're awesome
Just after two days of following , you deserve subscribtion❤
I am astounded. A beautiful method.
Dr. You are doing a great job.
What name should we call this method?
Koster’s Method haha
@@drpeyam 😁 Named after his name😁 thank you Dr.
This is an excellent method! I wish I could use it in my linear algebra course but my lecturer requires that at each step I indicate which Elementary Row Operation was performed.
Hello Dr payam ! Any trick or shortcut to find inverse of matrix?
Does this method have a name? I feel like ive heard this referenced as montante's method?
The use of the determinant here seems like it might just be a coincidental shorthand. It will haunt me unless someone finds a generalization that uses determinants of higher order matrices. But I don't even have the slightest idea of what it would even have to generalize - Guassian Elimination itself?
I think the algorithm in the video is just doing some shenanigans with Cramer's rule or matrix minors. Gaussian elimination will be exponentially faster than that for larger matrices.
@@AaronRotenberg
I don't think you understand the method. Each entry only requires the determinant of a 2×2 matrix regardless of the size of the original matrix.
Here is an explanation of the method I gave elsewhere:
So you have a pivot row and a row you want to "update"; first, simultaneously multiply the pivot row by the first number in the "update" row and the "update" row by the first number in the pivot row; then, do the usual Gaussian Elimination on those two rows.
What you've done is the simplest way to ensure that you get only integers in the rows, because now the number you want to turn into a 0 in the "update" row is the same in absolute value as the first number in the pivot row, so Gaussian Elimination amounts to adding/subtracting integers.
At the same time, if you look at what you've done term by term in the "update" row, it's exactly the determinant described in the video, because you are just multiplying the respective terms by the first numbers in the other row before subtracting.
I believe it is equivalent to standard Gaussian elimination in terms of computation time. If there is a connection to Cramer's rule or matrix minors, I would appreciate an explanation.
this is awesome technique. I wish I knew it when in high school.
Wow thank you sir for this amazing technique....
Wow!!
When I first saw this, I was reminded of Cramer's Rule. I'll call it a hybrid between Gaussian Elimination and Cramer's Rule.
LOL, this was my first thought too. The proof is probably similar.
Really clever technique, does this work for all three by three matrice? What about the inconsist case or infinite solutions, how would this work?
I guess you would find at some point a line with all zeros : 0 0 0 | 0
And in the case of 0 solutions, something contradictory like : 0 0 0 | a (a≠0)
It works for any kind of matrices
I wonder if i can use this in my linear algebra finals
Sure!
Absolutely incredible!!
Does this method work with 4×4 systems as well ?
Yes it does!
Great sir❤️
Love from India
Will you ever explain why this works plz
It's just the Gaussian Elimination with a factor to eliminate the fractions.
Let's suppose you have a 2 x 2 system:
a11x + a12y = b1
a21x + a22y = b2
To get a 0 in place of a21, by normal Gaussian Elimination, you multiply row 2 by -(a11/a21) and sum it with row 1:
(-a11/a21*a21 + a11)x + (-a11/a21*a22+a12)y = (-a11/a21*b2 + b1),
You can rewrite that as:
0 x + (-1/a21)*(a11*a22-a12*a21)y = (-1/a21)*(a11*b2 - b1*a21)
and you just multiply by (-a21):
0 x + (a11*a22-a12*a21)y = (a11*b2 - b1*a21), and you can see the determinants right there.
I'm no mathematician, but I hope I could help you.
4:22 Magic!
Nice one
Now we need a proof presentation that this algorithm works!!!! :) - YAY hate making arithmetic mistakes with Gaussian Elimination!
The proof is easy, try it out
I like your line which i believe 😊😊
Impressionnant !
Interesting technique, but how about proof that this is works. I think it maybe not too hard to do, because it uses basic row-summing with common multipliers for rows, etc. Interesting, how they relates with determinant. Thank you.
No the proof is easy, try it out with a matrix
a b c
d e f
And first row reduce, and then try this trick, and you’ll see it’s the same
@@drpeyam does it have to be a square matrix (w/ augmented column)?
@nathanisbored No I don’t think so, it works for any matrix
Determinants are an interesting toolkit for solving linear algebra problems 😁
Why does this method work?
Amazing! But how does this method work?
It is just a regular Gaussian elimination, but by only doing multiplication. For example:
(2 5 | 3) (6 15 | 9)
(3 2 | 7) becomes (6 4 | 14)
We multiplied the first row by 3 and the second one by 2. This way, you can just substract them. Dr. Peyam's method is exactly the same, just doing two steps at once, with a determinant. I don't know if I'm very understandable, do not hesitate if you have any question x)
@@JoachimFavre Thank you I understand now.
This method is incredible but I am unsure as to how it works
awesome!!
Can we also use this method to find the inverse of a matrix?
Ok I came back here from the future and the answer is definitely yes
Lol you're a genius. I needed it, thanks!
Oh Master Gauss look is awesome!
Does this work for square matrices of higher dimensions?
Yes, and in fact for any matrix
This is very interesting! I am taking Linear Algebra next term. Thank you! I have a question, professor. Does this work well with larger matrices? Or only systems of 3 linear equations of 3 variables?
It works for any system
I like this method
Cool technique but How does it work?
Try it out for a general 2x3 matrix and you see the pattern :)
So you have a pivot row and a row you want to "update"; first, simultaneously multiply the pivot row by the first number in the "update" row and the "update" row by the first number in the pivot row; then, do the usual Gaussian Elimination on those two rows.
What you've done is the simplest way to ensure that you get only integers in the rows, because now the number you want to turn into a 0 in the "update" row is the same in absolute value as the first number in the pivot row, so Gaussian Elimination amounts to adding/subtracting integers.
At the same time, if you look at what you've done term by term in the "update" row, it's exactly the determinant described in the video, because you are just multiplying the respective terms by the first numbers in the other row before subtracting.
Great!
Hello
For me, calculating determinants is a tedious process because of having to remember minus signs.
Great 'trick'!
Smart handsome Guess 😂
69k not bad.
I use 3d geometry to solve linear equations in 3 variables, will the society accept me?
Great, but I fail to see WHY this works.
He just applied row operations if u see clearly in those determinants
2 1 4 |5
3 -1 2 |2
to take the determinants of first 2 rows
is the same as to multiply the 1st row by the 1st element of the 2nd row (i. e. ×3), multiply the 2nd row by the 1st element of the 1st row , i. e. ×2
and then do the subtraction to eliminate the 1st element of the 2nd row
the rest is done in the same concept
@@jackiekwan Well explained. It’s essentially a fast way of multiplying the rows by the least common multiple.
Better: A\b
I've found the engineer...
@@LaerteBarbalho Close. I am in the applied math trade, but I teach engineers linear algebra and numerical analysis. It goes like this: A) Here's Gauss-Jordan, by hand. B) Here's LU factorization with pivoting, by computer. C) Forget what you know and use Matlab backslash. :)
Thumbnail 😎😎😎😎😎
Dr πM
Math made fun and easy
I will kepp using cramer's rule even after watching this video anyway😂
Check out the method of triangles.😉
Normal method is sufficient to do this question.
Are you sure about that? Computationally, integers and floating point numbers have different blind spots where they have to round. If given a problem in integers, converting to floating point might lead to unnecessary rounding errors.