Jump to content
  • Advertisement
Sign in to follow this  
Nicholas Kong

Understanding linear combinations with more unknowns than equations

This topic is 2074 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

All of the questions before the question I will post below can be solved in a trivial way to me because the amount of equations and unknowns were exactly the same.

 

Here is the linear algebra problem.

 

Use Gauss’s Method to solve each system or conclude ‘many solutions’ or ‘no
solutions’:

 

x - 3y + z = 1
x + y + 2z = 14

 

So this question surprised me because it had 2 equations and 3 unknowns and it was not so trivial now! It tested my brain and I struggled for an hour and I am still clueless. After that one hour, I decided to look at the answer key.

 

The textbook approach decided to multiply the first equation by a -1 which makes the first equation to become -x + 3y - z = -1 and then add that to the second equation which ends up knocking out the variable x thus being left with 4y + z = 13.

 

The first equation becomes the same: x - 3y + z = 1. The second equation is the new equation 4y + z = 13.

 

The textbook answer states "the variable z is not a leading variable in any row, that there are many solutions."

 

The answer in the textbook did not give me any closure. Why does the variable z not becoming a leading variable leads to the linear combination having many solutions? Why depend on variable z and not x or y? There seems to be something serious missing from this puzzle.

 

It seems I need to think differently about when a linear combinations have more unknowns than equations which right now is a challenge for me.

Edited by warnexus

Share this post


Link to post
Share on other sites
Advertisement

In Gaussian elimination you eliminate one variable at a time, and hopefully end up with a "triangular" system of equation.

4*x + 3*y - 2*z = 1
      6*y + 5*z = 2
              z = 3

That system is triangular. Each variable is the leading variable of one equation. You can easily deduce the values of x and y from this system.

 

In a system that is under-determined you might never end up with this nice triangular set of equations. In the problem you posted, you ended up with an equation where x was the leading variable, an equation where y was the leading variable, but no equation where z was the leading variable. Because you didn't end up with any equations that were obviously impossible (ie, nothing simplified to 0 = 1 or anything) then you must conclude that there were many solutions. If you had found a contradiction you would conclude that there were no solutions (the system is over-determined). 

 

It is important to know that there is nothing special about z. You could rearrange your equations and perform Gaussian elimination and find that you never got an equation with x as the leading variable, or rearrange them in a different way and discover that you never got y as a leading variable. 

Share this post


Link to post
Share on other sites
If you have more unknowns than equations, you'll either have multiple solutions or you'll have none.

The way I think about your example, each linear equation determines a plane in 3D space, and the solution of the system of equations is the intersection of the planes. The planes either intersect in one line (the general case), or they are parallel or they are coincidental (meaning they are the same). In the last two cases, the coefficients of x, y, and z in the two equations would be proportional. I just looked at the first two coefficients of each equation and I saw that they were not proportional, so you are in the general case and the solution is a line.

Share this post


Link to post
Share on other sites

In Gaussian elimination you eliminate one variable at a time, and hopefully end up with a "triangular" system of equation.

4*x + 3*y - 2*z = 1
      6*y + 5*z = 2
              z = 3

That system is triangular. Each variable is the leading variable of one equation. You can easily deduce the values of x and y from this system.

 

In a system that is under-determined you might never end up with this nice triangular set of equations. In the problem you posted, you ended up with an equation where x was the leading variable, an equation where y was the leading variable, but no equation where z was the leading variable. Because you didn't end up with any equations that were obviously impossible (ie, nothing simplified to 0 = 1 or anything) then you must conclude that there were many solutions. If you had found a contradiction you would conclude that there were no solutions (the system is over-determined). 

 

It is important to know that there is nothing special about z. You could rearrange your equations and perform Gaussian elimination and find that you never got an equation with x as the leading variable, or rearrange them in a different way and discover that you never got y as a leading variable. 

Does a linear system always have many solutions if one variable from the system is not a leading variable? Is that a given trivial fact all the time?

Share this post


Link to post
Share on other sites


Does a linear system always have many solutions if one variable from the system is not a leading variable? Is that a given trivial fact all the time?

 

Yes, unless your equations contradict one another. For example, consider this system:

4*x + 3*y - z = 1
8*x + 6*y - 2*z = 10

If you multiply the top equation by 2 and subtract it from the second equation you get:

4*x + 3*y - z = 1
            0 = 8 <-- contradiction!

So, in that system of equations you couldn't get  y or z to be leading variables, but you got a contradiction, so you conclude that the system has no solutions.

 

You sound like you're still fairly early in your linear algebra course. As you progress, things will start to make more sense and seem a bit less arbitrary.

Share this post


Link to post
Share on other sites

 


Does a linear system always have many solutions if one variable from the system is not a leading variable? Is that a given trivial fact all the time?

 

Yes, unless your equations contradict one another. For example, consider this system:

4*x + 3*y - z = 1
8*x + 6*y - 2*z = 10

If you multiply the top equation by 2 and subtract it from the second equation you get:

4*x + 3*y - z = 1
            0 = 8 <-- contradiction!

So, in that system of equations you couldn't get  y or z to be leading variables, but you got a contradiction, so you conclude that the system has no solutions.

 

You sound like you're still fairly early in your linear algebra course. As you progress, things will start to make more sense and seem a bit less arbitrary.

 

Oh thanks! I get it now! It definitely makes more sense!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!