7.1 - Introduction to Systems of Linear Equations

Background

A system has these properties: One example is a business organization. This system’s inputs are its capital, employees, raw materials and factories. Its outputs are its products. Management decides what the interactions among the inputs should be to give the maximum output (for example, how many factories should make which products, etc.)

A linear system is a system where the output is proportional to the input. For example, if the business organization is a linear system, then if we double the capital, employees, raw materials and factories (the inputs) then we expect to get double the production (the output).

We can describe mathematically how the parts of a linear system relate to one another and to the input using a system of linear equations. If a linear system has n parts (where n is some number), then we can describe it with a system of n linear equations in n unknowns or variables. The unknowns in these equations are the values of the inputs. If we did the analysis correctly then there will be a unique solution for the values of the inputs.

Here is an example of a system of two linear equations in the two unknowns x and y:
From the input-output point of view, the numbers 4 and 6 on the right-hand-sides are the output, and the unknowns x and y on the left-hand-sides are the input. The numbers 1, 1, 2 and −3 multiplying x and y express the relationships between the parts of the system.

We can verify that {x = 3.6, y = 0.4} is the solution of the system by substituting it into the system and getting the pair of equations 4 = 4 and 6 = 6. Now, suppose that we double the output (replace 4 and 6 by 8 and 12):
Then we can verify that the input is also doubled; the solution now is {x = 7.2, y = 0.8}. Thus the system is linear. The linearity can be traced back to the fact that the numbers 1, 1, 2 and −3 multiplying x and y are constants. If they were replaced by expressions involving x and y then the equations would be non-linear.



Definitions: A linear equation in one unknown is an equation of the form a x = b, where a and b are constants and x is an unknown that we wish to solve for. Similarly, a linear equation in n unknowns x1, x2, …, xn is an equation of the form:
a1 · x1 + a2 · x2 + … + an · xn = b,
where a1, a2, …, an and b are constants. The name linear comes from the fact that such an equation in two unknowns or variables represents a straight line. A set of such equations is called a system of linear equations.


Here is an example of a system of three linear equations in the three unknowns x, y and z:



Methods of solving systems of linear equations

There are many methods of solving systems of linear systems. Each one has its advantages and disadvantages. The graphical method is useful for introducing concepts such as the uniqueness of the solution or the meaning of inconsistent systems but is useless as a computational tool.

The substitution method is useful because it can be applied to non-linear as well as linear systems, but it bogs down for anything but small systems. The Algebra Coach can solve any system of linear equations using this method.

The elimination method is a good method for systems of medium size containing, say, 3 to 30 equations. It is easy to implement on a computer. The Algebra Coach can solve any system of linear equations using this method. Gauss elimination and Gauss-Jordan elimination are two variations of this method. Other methods such as the LU decomposition method are based on it.

Cramer's rule (also known as the determinant method) is nice for hand-calculation because it avoids fractions. However it is only practical for small systems (3 equations or less). The Algebra Coach does not explain this method.

And there are other methods that are useful under certain circumstances. For example, the problem of “predicting the weather” on a 100 × 100 grid leads to a system of 10,000 linear equations. Such large systems are solved by iterative improvement. In this method you start with any guess whatsoever for the solution. Then you iterate (recycle) this solution, improving it with each iteration. When the accuracy is good enough, you stop.

Another method, the tri-diagonal matrix method, is useful for systems that can be organized into well-defined stages, and where each stage depends directly only on the previous stage.




Some lessons to learn from graphing 2 equations in 2 unknowns

The graphical method is not very useful as a computational tool but it is useful for visualizing concepts such as the uniqueness of the solution and the meaning of inconsistent and redundant systems. Consider the following system of two linear equations in two unknowns:
In this method we simply draw graphs of the equations as we have done to the right. Notice that the graph of each equation is a straight line. (This is characteristic of a linear system. There are no curves, only straight lines.)

Any point on one line is a solution of one equation and any point on the other line is a solution of the other equation. The point where the lines cross {x = 3.6, y = 0.4} is the solution that satisfies both equations simultaneously. Notice that the solution is unique. This is because the lines are straight and there is only one point where they can cross. A system of linear equations with a unique solution is the “normal” situation.

However it is possible to have a system of equations with no solution or an infinite number of solutions. Such systems of equations are called inconsistent and redundant, respectively. They are the result of an inaccurate or incorrect analysis of the physical system being described by the system of equations.

Consider the following system of two equations in two unknowns:
This system of equations is inconsistent because there is no way that x + y can equal 2 and 4 at the same time. As shown to the right, the graph of this system consists of two parallel lines that never cross. Thus there is no solution.
Now consider the following system of equations:
This system is redundant because the second equation is equivalent to the first one. The graph consists of two lines that lie on top of one another. They “cross” at an infinite number of points, so there are an infinite number of solutions.
To summarize, a system of linear equations with 2 unknowns must have at least 2 equations to get a unique solution. Having 1 equation is not enough, because 1 equation in 2 unknowns is represented by an entire line. Having 2 equations is exactly enough, as long as they are not redundant or inconsistent. Having 3 (or more) equations is too many. The third equation must be either redundant or inconsistent.



Counting equations and unknowns

These results can be generalized to linear systems of equations with any number of equations and any number of unknowns:
  • A linear system of equations with n unknowns must have at least n equations to get a unique solution. Having any fewer equations is not enough; the solution will not be unique.

  • Having n equations is exactly enough, as long as they are not redundant or inconsistent.

  • Having any more than n equations is too many; the system will be either redundant or inconsistent.