Tell me more ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.
up vote 7 down vote favorite
3

I'm trying to determine only if a solution to a linear system of equations exists. I have been using LinearSolve, which works fine, but it solves the system as well. Is there another more efficient method for only checking the existence of a solution?

share|improve this question
2  
For a one-off problem where nothing special is known about the system beforehand, actually solving the equation gives you access to the most efficient methods. In MMA, LinearSolve is very fast and (for general-purpose work involving non-square matrices) provides solutions an order of magnitude faster than other methods using (say) MatrixRank, RowReduce, or Minors. As an example of how extra info can help, if it's known the coefficient matrix is orthogonal, then you already know a solution exists. – whuber Sep 26 '12 at 19:07
There is some important discussion in the comments to my answer. – Vitaliy Kaurov Sep 27 '12 at 8:24

3 Answers

up vote 4 down vote accepted

==== Update ====

Please consider important discussion in the comments.

==== Original answer ====

If the matrix m has determinant zero, then there may be either no vector, or an infinite number of vectors x which satisfy m.x==b for a particular b. This occurs when the linear equations embodied in m are not independent. If you are interested only in well-defined systems, then, generally, confirming that you have a non-zero determinant is faster:

m = RandomReal[1, 1000 {1, 1}];
b = RandomReal[1, 1000];

Some timing tests:

Mean@Table[LinearSolve[m, b]; // AbsoluteTiming, {30}][[All, 1]]

0.0712654

Mean@Table[Det[m]; // AbsoluteTiming, {30}][[All, 1]]

0.0571327

share|improve this answer
2  
I suspect the performance trade may fall the other way depending on the size and character of the system. The most efficient methods for solving large systems usually do not involve directly computing the determinant. (LinearSolve automatically picks an efficient method..) – george2079 Sep 26 '12 at 17:47
@george2079 the benchmark i posted is pretty general and the system is pretty large. Of course, some specific systems may show a different result. – Vitaliy Kaurov Sep 26 '12 at 17:53
3  
This has two problems. For approximate matrices it is not numerically sound. Far safer is to check singular values for zeros below some tolerance. Else you can get a false positive, that is, a claim of solvability when the matrix is singular or nearly so. The other problem is that (to be cont'd) – Daniel Lichtblau Sep 27 '12 at 1:34
1  
... in the exact case, e.g. integers, Det computation can be slower than actual solving. Example:In[22]:= n = 2^10; mm = RandomInteger[{-1, 1}, {n, n}]; vec = RandomInteger[{-1, 1}, n]; In[27]:= AbsoluteTiming[sol = LinearSolve[mm, vec];] Out[27]= {11.3440000, Null} In[28]:= AbsoluteTiming[Det[mm] == 0] Out[28]= {53.7370000, False} – Daniel Lichtblau Sep 27 '12 at 1:34
1  
A third problem is that computing a determinant works only when there are exactly as many equations as variables. There is a generalization (implementable via Minors), but it is likely to be relatively inefficient (there can be a lot of minors to compute and store). – whuber Sep 27 '12 at 1:35
show 4 more comments
up vote 7 down vote

The upshot of Vitaliy's note to check for a zero determinant is that

  1. A matrix with inexact entries that is supposed to be singular (e.g. because it is rank-deficient) might not necessarily give a determinant that is exactly zero, due to roundoff.

  2. A tiny determinant does not necessarily imply that the matrix is "nearly" singular. (Conversely, just because a matrix does not have a tiny determinant doesn't mean that LinearSolve[] won't have a problem handling it.) See for instance this answer I wrote at scicomp.SE.

Thus, to safely determine if a matrix is singular, you can do any of two things:

  1. Check if the output of NullSpace[] is an empty list. If its output on your matrix is {}, the matrix is nonsingular; otherwise, the number of null vectors it produces (the nullity) gives an indication of how rank-deficient it is.

  2. Use the undocumented function LinearAlgebra`MatrixConditionNumber[]. Checking for singularity is as easy as seeing if its output on your matrix is $\infty$, in which case, your matrix is singular. As a bonus, if the value returned is huge, but not necessarily infinite, you still have a good warning sign that LinearSolve[] might treat your matrix as singular even if it isn't. See any good numerical linear algebra book (e.g. Golub/Van Loan) for details.

share|improve this answer
1  
P.S. The nice thing about NullSpace[] is that it can flexibly deal with both exact and inexact matrices; IIRC it uses Gaussian elimination in the exact case, and the (safer) singular value decomposition in the inexact case. – J. M.♦ Sep 26 '12 at 23:10
up vote 0 down vote

Odd. If you get a solution, you know that a solution exists, isn't it? Anyway, what you can do is suppress the output by adding a ; to your input. Then

LinearSolve[{{4, 8}, {9, 2}}, {x, y}];

returns nothing, while

LinearSolve[{{4, 8}, {9, 2}, {0, 0}}, {x, y, z}];

returns

LinearSolve::nosol: Linear equation encountered that has no solution.
share|improve this answer
LinearSolve carries out all of the steps of solving the system when all I need is a yes/no to whether or not a solution exists. So will LinearSolve be the most efficient way of doing this regardless? – A. R. S. Sep 26 '12 at 17:16
1  
@A.R.S. - My guess is that the steps to check if there's a solution are the same as calculating the solution. (disclaimer: I'm not a mathematician, so you may wish confirmation from the Real Guys :-)) – stevenvh Sep 26 '12 at 17:19
@A.R.S., what mathematical "magic" do you think might be done to determine whether a linear system has a solution that would be substantially different from actually attempting to find solution? Except in special cases, as others have noted, in each situation some sequence of transformations will need to be done (whether row reduction or something more sophisticated like a matrix decomposition). – murray Sep 27 '12 at 14:59
@murray - Maybe he's thinking about something like primality testing, where you can say a number is composite in a second, but may need a couple of months to find the factors. – stevenvh Sep 27 '12 at 15:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.