Solution when number equations is less than than the number of variables

I am curious if there is some solution method in the case when we have the number of equation less the number of variables. For example, and X , Y are two variables. I would appreciate any guidance on this very basic querry.

[Walter Roberson]

Is it a linear system? If so then do you want the equations that define the (hyper-) plane of solutions, or do you want a particular solution, such as "closest point" ?

[Saifullah Khalid]

Yes the system is linear and I need to findout the nearest point.

Answer 1

[John D'Errico]

There is no unique solution in general. That is, infinitely many possible solutions.

In this case, you have TWO variables, and ONE equation. So you could pick any value for X, substitute it into the equation, and then the value for Y is known, as long as b is not equal to zero. That is, you would compute

Y = (c - a*X)/b

Likewise, you could pick any value for Y, and then solve for X, as a function of Y. Again, that requires only that a is non-zero.

X = (c - b*Y)/a

Either approach is equally valid. There are also ways you can write a solution in the form of one that minimizes the norm of the vector [X,Y]. That is just another way to choose one of the infinitely many solutions.

So does a solution exist? Well, no. And, yes. But just not "a" solution. Any solution you desire.

[Saifullah Khalid]

John, thank you very much for the insightful answer. Can you please give some further guidance on minimization of norm method? Also, I am looking for a closest point colution.

[Walter Roberson]

[a, b]\c

would give you a result that minimized the norm.

[John D'Errico]

I'm not sure what you are asking. Do you seriously have only one equation, with two unknowns? Or is that just a stand-in for your real problem with hundreds of unknowns, but fewer equations? :-)

The classical solution that yields a minimum norm uses pinv. But first, you need to understand what the solution looks like, when you have an underdetermined problem. I'll describe a simple case where the rank is one less then a full rank problem. (That is, you have one less equation than unknown.)

Consider the matrix A. We want to solve the linear algebraic problem

A*x = b

But A has fewer rows than columns, so there are fewer equations than there are unknowns to solve for. That means there are some vectors x0 we could choose, such that A*x0 will be identically zero. This is called the nullspace of A.

>> A = rand(3,4);
>> V = null(A)
V =
         0.413182200930486
        -0.609881989544909
        -0.414088352338926
         0.534654340784975
>> A*V
ans =
     -5.30779453221573e-17
     -1.82343962492352e-18
     -2.22652602203392e-17

I generated a random matrix A. See that V is the vector that kills off A. (A*V is essentially zero, except for floating point trash.) V is unique here, except for scaling. But if we have any solution vector x that solves the problem A*x==b, then it must be true that x+k*x0 will also solve the problem as well, and that will be true for ANY value of k.

This is the general idea when you have an underdetermined system of equations. It is also why the solution is not unique. You can write the general solution in the form of

x = xp + k1*V(:,1) + ... + km*V(:,m)

where m is the dimension of the null space of A. (So the number of columns in the result null(A).)

To continue the above example, I'll pick some random 3x1 vector b.

>> b = rand(3,1);
>> xp = A\b
xp =
         0.331668553237443
                         0
         0.447128362882993
         0.197543545392574
         
>> xp2 = pinv(A)*b
xp2 =
         0.307907928279391
        0.0350721236045826
         0.470941097355257
         0.166797493783918

>> xp3 = lsqminnorm(A,b)
xp3 =
         0.307907928279391
        0.0350721236045825
         0.470941097355257
         0.166797493783918

Either of those solutions is equally valid. But the pinv solution yields a minimum norm solution, as does lsqminnorm.

>> norm(xp)
ans =
         0.590720961560797
>> norm(xp2)
ans =
         0.587915187133494

As you can see, the norm of xp2 is smaller than the norm of xp. Since the solution is not unique, the backslash solution is just one whee some of the unknowns will be chosen to be exactly zero. But in general that won't be a solution that minimizes the norm. (Do I need to get into the derivation of why pinv yields a minimum norm solution? pinv is based on the singular value decomposition of A.)

So what is the fully general solution? Again, there are infinitely many such solutions, parameterized on some general parameter k.

>> syms k
>> vpa(xp + k*null(A),5)
ans =
 0.41318*k + 0.33167
          -0.60988*k
 0.44713 - 0.41409*k
 0.53465*k + 0.19754

Or I could have written it as

>> vpa(xp2 + k*null(A),5)
ans =
  0.41318*k + 0.30791
 0.035072 - 0.60988*k
  0.47094 - 0.41409*k
   0.53465*k + 0.1668

which would be equally valid. The latter form has the minimum norm solution as the particular solution.

If you really just want the solution of a problem with one equation in two unknowns, that is easy enough to write:

>> syms a b c
>> xp = pinv([a,b])*c
xp =
 (c*conj(a))/(a*conj(a) + b*conj(b))
 (c*conj(b))/(a*conj(a) + b*conj(b))

That is the particular solution. The null space vector is:

>> null([a,b])
ans =
 -b/a
    1

So then the fully general solution of the problem becomes:

>> xp + k*null([a,b])
ans =
 (c*conj(a))/(a*conj(a) + b*conj(b)) - (b*k)/a
       k + (c*conj(b))/(a*conj(a) + b*conj(b))

Where conj is just the complex conjugate, in case ony of those numbers were complex.

[Saifullah Khalid]

Walter thanks, this method gives an exact solution but coefficients are set to 0 except the last one.

A = [4,5,6];%[a b]
c = 3;
S = A\c
% gives out
S =

         0
         0
    0.5000

Instead can we use psuedo onverse method e.g.

A = [4,5,6];%[a b]
c = 3;
S = pinv(A)*c
% gives out
S =

    0.1558
    0.1948
    0.2338

[Saifullah Khalid]

Thank you very much for very detailed insight. I have many unknowns but one eqaution. Your e answers provided me the solution, I was looking for.