0

I've a [8x4] matrix, 'A', and a [8x1] matrix, 'B'. How do I check if there exists a [4x1] matrix 'x' such that A * X = B?

This can be done using linprog in MATLAB, but I'm not sure how to give the constraints. I tried x = linprog([],[],[],A,B);, but this doesn't seem to work.

How to specify the condition x>=0 and optimize it for A*X-B so that, if it returns 0, we know there is X.

Update:

pinv in MATLAB doesn't work in all the cases. Consider the following example:

A= [1     0     0     0
     0     1    -1    -1
    -1    -1     1    -1
    -1    -1    -1     1
     0     0     0     0
     0     0     0     0
     0     0     0     0
     1     1     1     1]
B = [0
     0
     0
    -1
     0
     0
     0
     1]

using pinv gives the the value of X as:

X = [-2.7756e-017
    0.5000
    0.5000
         0]

but when linear programming is used I get x as:

X = [    0
    0.5000
    0.5000
         0]

This is the reason why I preferred linprog tool in MATLAB. I just used it the way I mentioned previously but it is throwing a lot of warnings. I still think there is a better way to use this function correctly. It did not throw for this matrix but in general when I loop through a lot of matrices my command window overflow with warnings.

Improve this question

3 Answers 3

Reset to default
2

Why use linear programming? You can just solve the system A*x=B directly:

A =[ 1    -1    -1    -1     1     0     0     1
    -1     1    -1     0     0     1     0     0
    -1    -1     1     0     1     0     0     0
    -1    -1    -1     1     1     1     0     0]'; %'# 

B = [-1    -1     0     0     0     0     1     1]'; %'#

x = A\B
x =
      0.16327
     0.097959
      0.46531
      0.11837

The problem you may face is that A can be rank deficient, but in that case, you'll get infinitely many solutions for x.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

That is the main problem. What I do now is if ( (A * pinv(A) * B) == B) then there exists a solution. where pinv is pseudo inverse function in matlab. I think linear programming handles this condition well. That's why I'm looking for a way to do that.
No, you don't know that is true. It is a rare case where such a test for EXACT equality will EVER be true when applied in floating point arithmetic! Use of linprog to try to do that test is silly.
2

But why use a code that will do MORE work than necessary to solve the problem? Just use the pseudo-inverse. If A is of full rank, then backslash will be entirely sufficient.

Compute the solution. If the norm of your residuals is less than some tolerance, then you have a solution. Note that essentially no solution is ever assured to give you truly zero residuals, so you must apply a tolerance. Thus

x = A\B;
if norm(B - A*x) < tol
  disp('Eureeka!')
end

Or use x=pinv(A)*B if you are worried about the rank of A.

Trying to throw linprog at the problem will surely not be more efficient than the direct solution itself.

Edit: Since non-negativity of the result has now been added as a requirement, use lsqnonneg instead. Just compare the norm of the residual vector to a tolerance. If the norm is too large, then no solution exists.

Improve this answer

4 Comments

I tried x=pinv(A)*B but it doesnt give me any solution but when I used linprog it gives me solution but throws in a exception at each iteration (I have many A's). the exception is: (1)Exiting due to infeasibility: an all-zero row in the constraint matrix does not have a zero in corresponding right-hand-side entry. (2) Exiting: One or more of the residuals, duality gap, or total relative error has stalled: the primal appears to be infeasible (and the dual unbounded).(The dual residual < TolFun=1.00e-008.)
You should also look at the condition X>=0 which is very important.
ARGH. You now change the problem as posed, adding in non-negativity of the result as a requirement.
Sorry for a late reply. The non-negative condition was always there in my original question. Wasn't it ?
0

Unfortunately, you can not use array division. This is not the same a matrix division. However, you could use the inverse of the Matrix A to multiply it with matrix B to get x x = (A-1)B, but I am not sure if an inverse is possible for non-square matrix A (8x4). Hence, you might not have been able to work that with linprog

Improve this answer

1 Comment

Pseudo inverse always exists and that's how I'm doing it now. Please see my comments to jonas about how I'm doing it now.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.