What is Hard about Solving Linear Algebraic Equations?

A variety of difficulties arise in solving some systems of linear algebraic equations (also known as “matrix problems”.)  We will present several such difficulties here in the smallest possible size. These are in no particular order.

1.       A variable may not actually be involved in the solution.  For example,

1*x + 0*y = 1

2*x + 0*y  = 2

In this case, y simply isn’t involved, and can’t be solved for.  Solving for x is easy with either equation (x=1) but when you substitute x=1 into the other equation you just get 0 = 0, which is true (!) but not helpful. Of course, you can see that this could happen with a larger system of equation also. So, can this problem be solved? Yes, x=1, y=anything is a solution.  But there is no unique solution unless you specify some rule for picking one.

Autorej returns x=1, y=0.

2.       Just as one variable may not really be present, one or more equations may not really be present.  For example,

1*x + 1*y = 2

0*x + 0*y  = 0

In this case the second equation is completely useless.  On the other hand, any x and y we pick would satisfy this equation!  So we can come up with solutions for the set of equations easily: x=1 and y=1, for example.  Of course, such equations present (minor) problems to solvers such as the ones we offer here.  More on that later.

Autorej returns x=1, y=1.

3.       The equations may be dependent.  That is, one or more of the equations may just be combinations of the previous equations.  For example,

1*x + 1*y = 2

2*x + 2*y  = 4

In this case the second equation is just 2 times the first.  When you attempt to eliminate the x term in the second equation, by subtracting the first equation from it twice, look what you get:

1*x + 1*y = 2

0*x + 0*y  = 0

This last equation is, again, true, but useless.  You can’t solve it for x or for y.  (But as in the above case, any pair of values will satisfy it.)  So, can this problem be solved?  Yes, in fact, there are many solutions: x=1 and y=1; or x=2 and y=0; etc.  But there is no unique solution unless you specify some rule for picking one. Note that we usually say the equations are not independent, meaning that somewhere among a perhaps large set of equations is a group of equations what are dependent.

Autorej returns x=-2, y=4, which is one of the correct solutions. A better solution would be x=1,y=1, and this is what would be computed if autorej accepted a system of just ONE equation: x+y=2. But Autorej requires at least two rows and at least two columns.

Autorej with nonnegativity returns x=0, y=2. Nonnegativity is achieved by setting certain variables to zero, in an iterative fashion, so this is typical. Remember that Autorej’s algorithms were developed for larger, more realistic problems, and they always begin by compute the Singular Value Decomposition of the matrix, which is a very different representation of the equations. This can result in unintuitive answers, though correct ones.

4.       The equations may not be consistent.  In the case just above, the equations were dependent, but at least agreed.  What if the equations are dependent again, but also disagreed?  For example,

1*x + 1*y = 2

2*x + 2*y  = 6

When we subtract the first equation times 2 from the second, we get

1*x + 1*y = 2

0*x + 0*y  = 2

and the second equation is false.  This system cannot be solved exactly.  However, an approximate solution can be computed.

Autorej returns x=1.26, y=1.26, which produces too large a value on the right hand side of the first equation, and too small a value for the second equation. This is typical.

5.       The equations may be independent, and consistent, but result in an unreasonable answer.  Often this is due to what we call an ill-conditioned system of equations.  For example, consider these two:

1*x + 1*y = 2

1*x + 1.01*y  = 3

When we solve this by the usual elimination and substitution method, we get x= -98 and y=100.  The reason for this can be seen in that a tiny increase in the coefficient of y caused a change of 1 in the right hand side: this y must be fairly large. But this is a surprising answer since by looking at each equation alone we would have guessed that the solution values would be near 1.  And a negative answer such as -98 may be completely unacceptable.  For example, if x and y represent amounts of physical entities then a negative number is plain wrong.

Autorej returns x=1.122, y=1.122.

6.       Sometimes a system of equations is simply under-determined.  That is, there is not enough information present to compute a particular solution.  For example:

1x + 2y = 2

Yes, that is just one equation, with two unknowns.  Sometimes it really happens that we need to solve say 10 equations in 20 unknowns.  So what do we do?  We have to add some rule for picking an appropriate solution among all the possible solutions.  The usual way to do this is to pick the solution with the smallest sum of squares.  That is, the smallest possible value of x*x + y*y.  In this case that turns out to be x=0.4, y = 0.8.

This cannot equation be solved with Autorej due to the requirement for at least two rows and two columns. But If we add a second meaningless equation of

0*x + 0*y  = 0, then autoreg returns the expected x=0.4, y = 0.8.

7.       Sometimes a system of equations is  over-determined.  That is, there are more equations than need to determine a solution, and we have no reason to eliminate any particular equation.  We would like a solution that somehow “comes closest” to solving all of the equations.  For example,

1*x + 2 *y  = 15

2*x + 2*y = 16

-1*x + 1*y  = 6

The solution to this system is easy: x=1, y=7.  And, we are in luck: that solution satisfies all three equations exactly!  But that is not the typical case.  More typically, we would have something like

1*x + 2 *y  = 15.1

2*x + 2*y = 15.9

-1*x + 1*y  = 6.5

And if we try x=1, y=7 in this set of equation, we will not quite solve the equations.  Instead we will get 0.1 too little for the first equation, 0.1 too much for the first equation, and 0.5 too much for the last equation.  We can do better than that.  In particular, we can compute a solution which minimizes the sum of the square of these errors.

Autoreg returns the expected  x=1, y=7 for the first system of equations.

Autoreg returns the expected  x=0.727, y=7.207 for the second system of equations, which is the “Least Squares” answer.

When we have larger systems of equations we may have two or more of the above difficulties in the one set of equations. For example, it would not be surprising for a set of equations to be underdetermined (case 6), and not independent (case 3) and ill-conditioned (case 5).  That’s what makes developing solvers for these systems interesting.