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?
$\begingroup$
$\endgroup$
2
3 Answers
$\begingroup$
$\endgroup$
9
==== 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
answered Sep 26, 2012 at 17:37
-
2$\begingroup$ 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..) $\endgroup$ Commented Sep 26, 2012 at 17:47
-
$\begingroup$ @george2079 the benchmark i posted is pretty general and the system is pretty large. Of course, some specific systems may show a different result. $\endgroup$ Commented Sep 26, 2012 at 17:53
-
3$\begingroup$ 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) $\endgroup$ Commented Sep 27, 2012 at 1:34
-
1$\begingroup$ ... 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} $\endgroup$ Commented Sep 27, 2012 at 1:34
-
4$\begingroup$ 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). $\endgroup$– whuberCommented Sep 27, 2012 at 1:35
$\begingroup$
$\endgroup$
1
The upshot of Vitaliy's note to check for a zero determinant is that
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.
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:
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.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 thatLinearSolve[]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.
answered Sep 26, 2012 at 23:04
J. M.'s missing motivation♦J. M.'s missing motivation
125k11 gold badges407 silver badges581 bronze badges
-
2$\begingroup$ 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. $\endgroup$ Commented Sep 26, 2012 at 23:10
$\begingroup$
$\endgroup$
4
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.
-
$\begingroup$
LinearSolvecarries 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 willLinearSolvebe the most efficient way of doing this regardless? $\endgroup$– arshajiiCommented Sep 26, 2012 at 17:16 -
1$\begingroup$ @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 :-)) $\endgroup$– stevenvhCommented Sep 26, 2012 at 17:19
-
$\begingroup$ @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). $\endgroup$– murrayCommented Sep 27, 2012 at 14:59
-
$\begingroup$ @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. $\endgroup$– stevenvhCommented Sep 27, 2012 at 15:03
LinearSolveis 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, orMinors. 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. $\endgroup$