**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.