# What makes a linear system of equations “unsolvable”?

I've been studying simple systems of equations, so I came up with this example off the top of my head: \begin{cases} x + y + z = 1 \\[4px] x + y + 2z = 3 \\[4px] x + y + 3z = -1 \end{cases}

Combining the first two equations yields \begin{gather} z = 2 \\ x + y = -1. \end{gather}

But substituting $z = 2$ in the third equation implies $$x + y = -7,$$ while substituting $x + y = -1$ in the third equation implies $$z = 0.$$

I notice that $x + y$ appears in all three equations, so if we define $w = x + y$ then this essentially becomes three equations in two variables, which explains why I could solve for a variable using only the first two equations, and why the third equation doesn't agree.

So here is my question: What is the distinguishing feature of systems of equations that determines whether or not they have a solution? Perhaps put another way: in general, is there a "check" one can do on a system (aside from actually trying to solve it) to determine if there will be a solution?

Edit: Thanks for all the input everyone. I'm satisfied knowing that in general, there is no way to simply inspect such a linear system to determine if it has a solution - rather, some work is required. The geometric interpretations of linear systems of equations given in several answers were very helpful. Specifically: the interpretation of trying to find a vector $x$ in $Ax = b$ so that that the matrix $A$ represents a linear transformation mapping the vector $x$ to the vector $b$ (which may not be possible if $A$ maps $n$-dimensions to $n-1$ dimensions).

• Questions like these are (one of the reasons) why linear algebra exists :P – Kaj Hansen Jul 2 '18 at 2:56
• To determine if a general system has a solution is asymptotically as expensive as trying to solve it. – user569098 Jul 2 '18 at 3:00
• There’s already a few good answers using linear algebra so I’ll leave my addition as a comment. If your vector b (which consists of all the entries to the RIGHT of the equals sign) is not in the column space of A (which is a matrix consisting of all of the coefficients of x, y, and z in this example), the system is unsolvable. To determine if this is indeed the case, you can use methods described in a few other answers. Specifically if the n equations are not independent (we can derive one of them from a combination of the other two), it is not solvable. – Hanzy Jul 2 '18 at 3:02
• However, you may run in to two scenarios. One is the system is dependent and thus can’t be solved uniquely. The other is that the system is overdetermined and can’t be solved AT ALL. If you have more equations than variables, then you are probably dealing with an overdetermined system of equations that can’t be solved. If you are dealing with more unknowns than equations, or at least one of the equations can be derived from the other equations, the system does not have a unique solution. – Hanzy Jul 2 '18 at 3:09
• When you have an equal number of equations and unknowns, put the coefficients on the variables into a matrix and take the determinant of the matrix. If the determinant does NOT equal zero, the system is solvable. If it DOES equal zero, it is not uniquely solvable. – Hanzy Jul 2 '18 at 3:17

That's one of the main reasons why linear algebra was invented!

First we translate the problem into matrices: if $$\mathbf{A}=\begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 2 \\ 1 & 1 & 3 \end{bmatrix} \qquad \mathbf{x}=\begin{bmatrix} x \\ y \\ z \end{bmatrix} \qquad \mathbf{b}=\begin{bmatrix} 1 \\ 3 \\ -1 \end{bmatrix}$$ then the system can be rewritten as $\mathbf{A}\mathbf{x}=\mathbf{b}$. This is not really a great simplification, but allows using the unknowns as a “single object”.

A big advance is obtained by interpreting this in terms of linear maps. The matrix $\mathbf{A}$ induces a linear map $f_{\mathbf{A}}\colon\mathbb{R}^3\to\mathbb{R}^3$ defined by $$f_{\mathbf{A}}(\mathbf{v})=\mathbf{A}\mathbf{v}$$ and now solvability of the linear system becomes the question

does the vector $\mathbf{b}$ belong to the image of $f_{\mathbf{A}}$?

The image $\operatorname{Im}(f_{\mathbf{A}})$ is a vector subspace of $\mathbb{R}^3$; if it has dimension $3$, then clearly the system is solvable. But what if the dimension is less than $3$?

This is the “obstruction” for the solvability: when the dimension of the image (the rank of the linear map and of the matrix $\mathbf{A}$) is less than the dimension of the codomain (in your case $3$) the system can be solvable or not, depending on whether $\mathbf{b}$ belongs to the image or not.

There is no “general answer” that allows just looking at $\mathbf{A}$ and $\mathbf{b}$ and tell whether the system is solvable. Rather, there are efficient techniques that show whether the system has a solution without actually solving it. A very good one is doing elementary row operations, because these correspond to multiplying both sides of the system by an invertible matrix. In the present case, we do \begin{align} \left[\begin{array}{ccc|c} 1 & 1 & 1 & 1 \\ 1 & 1 & 2 & 3\\ 1 & 1 & 3 & -1 \end{array}\right] &\to \left[\begin{array}{ccc|c} 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 2\\ 0 & 0 & 2 & -2 \end{array}\right] &&\begin{aligned} R_2&\gets R_2-R_1 \\ R_3&\gets R_3-R_1 \end{aligned} \\&\to \left[\begin{array}{ccc|c} 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 2\\ 0 & 0 & 0 & -6 \end{array}\right] &&R_3\gets R_3-2R_2 \end{align} At this stage we know that the system is not solvable. We also know that the rank of $\mathbf{A}$ is $2$ and even that the image is spanned by the vectors $$\begin{bmatrix}1\\1\\1\end{bmatrix} \qquad \begin{bmatrix}1\\2\\3\end{bmatrix}$$ This is easy for the present situation, but the method can be applied to systems of any size, not necessarily with as many equations as unknowns.

The same row elimination shows that if the vector $\mathbf{b}$ had been \begin{bmatrix} 1 \\ 3 \\ 5 \end{bmatrix} then the system would be solvable.

Seen in a different way, the system is solvable if and only if $$\mathbf{b}=\alpha\begin{bmatrix}1\\1\\1\end{bmatrix} +\beta\begin{bmatrix}1\\2\\3\end{bmatrix}$$ for some $\alpha$ and $\beta$.

• Great answer! Shouldn't you have said, 'The matrix $\mathbf A$ induces a linear map...defined by $$\mathbf{f_A(x)=Ax}$$...' instead? – Allawonder Jul 3 '18 at 12:00
• @Allawonder That's the same, but I preferred to leave the “unknown vector” aside for systems. – egreg Jul 3 '18 at 12:45
• Yes, technically the same, but considering that $\mathbf A$ denotes a specific operator here acting on a space whose points are denoted by $\mathbf x,$ isn't it in the interest of consistency to continue using $\mathbf x$? – Allawonder Jul 3 '18 at 12:56
• @Allawonder I use to denote vectors by $\mathbf{v}$. ;-) – egreg Jul 3 '18 at 12:57
• I see. Then perhaps it would be more consistent to denote the vector $\begin{bmatrix} x \\ y \\ z \end{bmatrix}$ by $\mathbf v$ instead of $\mathbf x.$ – Allawonder Jul 3 '18 at 13:08

I'd like to add a geometric interpretation for a little added intuition. First, I'll try to set up the visual landscape, then describe how it relates to the problem. Then I'll quickly discuss why the determinant trick works in this context.

The visual

Your $x$, $y$, and $z$ represent the coordinates of a point in 3-dimensional space. The coefficients of the system of equations translate into the matrix that appears in other answers, which represents a particular linear transformation.

Visually, I like to think of linear transformations as moving around and/or stretching the axes of your coordinate system (without bending them). Normally, we think of a grid with three perpendicular axes, all with tick marks of unit length, but who says they need to be perpendicular, and why can't the tick marks be longer or shorter than one?

For instance, picture a basic 2d grid (it's a little easier to visualize in 2 dimensions). Now rotate the x-axis counter clockwise about 20 degrees, and let all of the horizontal lines that were parallel to the x-axis shift with it so they stay parallel at the end of the transformation. This is a simple linear transformation of 2d space. The intersections of the grid lines are points, and the points moved as the intersections moved. That's how changing the axes can describe the movement of points in a space, or mapping points to points. (It's also why matrices are used for a change of basis).

All the points in get moved around in such a way that a bunch of evenly spaced points on a straight line are still evenly spaced ad in a straight line after the transformation. The line may be angled differently and the points may be spaced out on the line differently, but it's still an even line (hence the term "linear" to describe the transformation).

I keep saying point when I technically mean vector. Instead of a points, they're really position vectors, which you can visualize as an arrow starting at the origin with the arrow head at the point. When I say vector, that's most likely what I'm referring to.

The explanation

Linear transformations can also compress spaces into lower dimensions. They can map planes into lines, or 3d space into a plane, or 3d space into a line. For instance, visualize rotating the x and y axis until they completely overlap. You've just pushed all the points on the plane into a single line. Obviously, some information was lost.

So say you have a matrix $A$ which corresponds to a linear transformation that compresses 3d space into a particular plane (the matrix $A$ in Mateus Rocha's answer and others, which corresponds to the system of equations, is such a matrix). Also, you have a vector $b$, which corresponds to a particular point in 3d space not on that plane (in your system, that vector's components are the right side of the equation, vector $b$ in egreg's answer).

When You have the equation $Ax = b$, you're asking this question: what vector, when transformed under the linear transformation $A$, gives me the vector $b$? What point gets moved to the point described by vector $b$ when I move all the points as described by matrix $A$?

However, $A$ maps all the points in 3d space to a plane and $b$ is not in that plane. So what vector gets mapped to $b$ under $A$? None! Therefore, the equation has no solution.

Visually, that's the primary feature of the system that determines if it has a solution.

Note: if the vector $b$ is in the plane (or line, or whatever lower dimension your higher dimensional space gets mapped to), then there are solutions. Infinitely many in fact, because you're compressing infinitely many points down into that lower dimension.

The determinant

The determinant of a matrix corresponds to the area of the parallelograms formed by the transformed squares of the new axes. So in the original coordinate system, we have a grid of a bunch of squares with area 1. The new axes transform those squares into parallelograms, and the area of one of those is the determinant of the matrix describing that transformation.

(In 3d, we're looking at the volume of a parallelepiped, the 3d equivalent. In n dimensions, we're looking at the n dimensional volume of an n dimensional parallelotope.)

If the determinant is $0$, that indicates we've compressed the space into a lower dimension. In the 2d case, if the transformation maps every point in the plane to a line, the area of the parallelogram formed by the new grid lines is $0$, because there is no parallelogram. Just a line.

That's why the determinant being $0$ is a good check to see if the system may have no solution. If it's $0$, you've compressed your space, and you end up with the scenarios we discussed above.

I hope this answer is clear and adds to the discussion. Personally, this is what made linear algebra click for me. For more on this perspective, I recommend checking out 3blue1brown's youtube series on linear algebra. You can see the visualizations I'm talking about animated in front of you.

• Your explanation of the geometric interpretation is the clearest I've ever heard it. Thanks! – JSmith Jul 3 '18 at 5:42
• This is the best answer in this post – cladelpino Jul 3 '18 at 14:41

You can try this by using gauss elimination method \begin{align} & \begin{bmatrix}1 & 1 & 1 & 1 \\ 1 & 1 & 2 & 3 \\ 1 & 1 & 3 & -1 \end{bmatrix} _{R_2\rightarrow R_2-R_1} \\ & \begin{bmatrix}1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 2 \\ 1 & 1 & 3 & -1 \end{bmatrix} _{R_3\rightarrow R_3-R_1} \\ & \begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 2 & -2 \end{bmatrix} _{R_3\rightarrow R_3-2R_2} \\ & \begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & -6 \end{bmatrix} \end{align}

Since the first three columns of last row of the matrix has all $0$'s the system of equation is inconsistent and has no solutions.

As @Arthur mentioned in the comments, if the first $3$ columns of the last row has $0'$s $\begin{bmatrix} 0 & 0 & 0 &r\end{bmatrix},r\ne0$ then the system of equations has no solution.

But, if the last row contains all $0'$s $\begin{bmatrix} 0 & 0 & 0 &0\end{bmatrix}$ then it means that there is a "free variable", and infinitely many solutions to the system, because that "free variable" can be assigned any value. The other variables can be expressed as free unknown variable and their values will often rely on the unknown value, depending on how much reduced the matrix is.

• I think you mean it is inconsistent if the last row of the matrix has three zeroes followed by a non-zero. If you change the last equation to x+y+3z=5, it makes the system solvable and produces [0, 0, 0, 0] for the last row. – Fax Jul 2 '18 at 11:03
• @KeyFlex If the last row is $[0\,0\,0\,r]$ with $r\neq 0$, then the system has no solutions. If the last row is $[0\,0\,0\,0]$, then the system has infinitely many solutions (assuming the other rows behave nicely). – Arthur Jul 2 '18 at 13:49
• @Arthur you are right. – Key Flex Jul 2 '18 at 13:57

You can look to the determinant of the coefficients. In your example, you need to calculate the determinant of $$A= \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 2 \\ 1 & 1 & 3 \\ \end{bmatrix}$$ If the determinant is not zero, your system has unique solution.

• Computing the determinant of the matrix of the system leaves unanswered the case of determinant equal to zero. In that case there might or might not be solutions. Moreover, it only works for systems with the same number of equations as unknowns. – user569098 Jul 2 '18 at 3:07
• @LB_O yes. If the determinant of any system equal to zero, we have no solutions or infinite solutions – Mateus Rocha Jul 2 '18 at 3:10
• Therefore, an additional decision procedure is needed to determine which one is the case. – user569098 Jul 2 '18 at 3:12
• Neither did I.$\phantom{ABC}$ – user569098 Jul 2 '18 at 3:17
• And in this specific case, the determinant is zero without a full calculation simply because the first and second columns of the matrix are the same (more generally, a linear combination of each other). That's a matricial formal equivalent to your $x+y=w$ observation. The first thing you want to do is visually checking for such obvious evidence of the determinant being zero. A lot of students rush to the mechanical approach without thinking first (citation needed). – Euro Micelli Jul 2 '18 at 13:53

Gaussian elimination or "row reduction" are the keywords you want to look up. Your question is in the context of systems of linear equations; more complicated contexts require more complicated techniques.

• It is important to note that this is basically saying: no, you just have to try to solve it and see what happens. – Steven Gubkin Jul 2 '18 at 16:46

But it requires you to have basic knowledge in Linear Algebra.

While the other answers are factually correct, I would like to add a geometric interpretation that might guide you in further thinking (and which I find a bit simpler than the intuition suggested by Cordello).

An equation of the form $$ax +by +cz +d=0$$ is called general form of the equation of a plane. That means that given the coefficients $a, b, c$ and $d$, all the points $(x,y,z)$ satisfying this equation form a particular plane in 3D.

You have a system of equations, which means that you are looking for points that satisfy all of the equations at the same time. In other words, you are looking for the intersection of the three planes. The intersection of three planes in 3D is one of the following sets:

1. A plane (this happens when all the three planes coincide).
2. A line (this happens when all the three planes intersect in the same line --- imagine an open book).
3. A point (this happens when each two planes intersect each other and these intersecting lines meet in one point).
4. Empty (this happens when either there are two of these planes that are parallel but distinct or if the pairwise-intersections do not meet in the same point).

The last case (empty intersection) is exactly the case when there is no solution to your system of equations (because there is no point that satisfies all the equations at the same time). It remains to connect it with the equations.

Recognizing two parallel planes is relatively easy: two planes are parallel when their normal vectors have the same direction. More precisely, two planes given by the equations $$a_1x+b_1y+c_1z+d_1=0$$ $$a_2x+b_2y+c_2z+d_2=0$$ are parallel if the vector $(a_1,b_1,c_1)$ is a multiple of the vector $(a_2,b_2,c_2)$.

As for the other possibility, I recommend thinking of Gaussian elimination in terms of intersecting planes. When you eliminate one of the equations, you also eliminate at least one of the variables. Supposing that the eliminated variable is $x$, you are left with two lines with equations $$p_1y+q_1z+r_1=0,$$ $$p_2y+q_2z+r_2=0.$$

• If $(p_1,q_1,r_1)=\alpha(p_2,q_2,r_2)$ for some $\alpha\in\mathbb{R}$, your two lines are identical and it is case 2.
• If $(p_1,q_1)=\alpha(p_2,q_2)$ but $r_1\neq\alpha r_2$, then your two lines are parallel, i.e., they do not intersect and it is case 4.
• Otherwise your two lines intersect in a point and it is case 3.
• I really hope that I did not forget any of the cases, because it is late in the evening. – Dominik Mokriš Jul 2 '18 at 23:03

A system of linear equations with $n$ variables is solvable if it has at least $n$ linear independent, non-contradicting equations.

Two equations a linear independent from each other if they are not constant multiples of each other.

Look at these two equations:

$$2x + 3y = 4 \\ 4x + 6y = 8$$

Note that they are practically the same (constant multiple by $2$ resp. by $\frac{1}{2}$), the second one is redundant (it does not add information to the equation system if you already have the first one). Also note, that if these were the only two equations, you had 2 variables with 1 useful equation - try to solve this and see how it fails! You cannot eliminate the one variable without the other one, you always get an arithmetic truth.

If the system has more than $n$ equations, then you have redundancy, they must not contradict, and they are reducible to $n$ equations without information loss.

$$x+y+z=1\\ x+y+2z=3\\ x+y+3z=−1\\$$

Without Gaussian elimination, you see that the right side of equation 2 is 3 times the right side of the right side of equation 1, but this does not hold for the left sides - hence linear independent. Also, equation 1 to equation three is factor $-1$ on right side, but not on left side, hence linear independent; equation 2 to equation 3 - try on your own (factor $-3$).

Until now, I only wrote about non-contradicting equations. Equations can be linear independent but contradicting, then the system is also unsolvable. E.g:

$$2x + 3y = 5\\ 2x + 3y = 10$$

The right sides are multiples by $2$ resp. $\frac{1}{2}$, but the left sides are not - so they are linear independent. But you cannot eliminate the one variable without the other, you get always an arithmetic fallacy.

Finding redundant equations can also be done by Gaussian elimination.

• Can you show how the equations from the actual question are not linearly independent? – ComicSansMS Jul 2 '18 at 7:05
• @F.Carette I had expanded my answer in the meanwhile. – rexkogitans Jul 2 '18 at 7:46
• Why downvote? Maybe I can improve... – rexkogitans Jul 4 '18 at 8:58

To complement other answers, let me mention that while determining whether $Ax = b$ has a solution may require some computational effort, there is always a very easy to verify certificate of whether a solution exists. I.e. if you already know whether $Ax = b$ has a solution, then you can easily convince someone else of the truth:

• If $Ax = b$ has a solution, then any solution $x$ is an easy to verify certificate of this fact.

• If $Ax = b$ has no solutions, then there exists a vector $z$ such that $z^\intercal b \neq 0$ but $z^\intercal A = 0$. So this vector $z$ is an easy to verify certificate that the system has no solution. In other words, if there is no solution, then you can find a linear combination of the equations, so that the left hand side coefficients are all zeros, while the right hand side is not zero.

Verifying these certificates takes time linear in the size of $A$, which is much faster than actually solving the system. Of course computing the certificates in the first place takes some effort.

Let me say how you get the second certificate $z$. You can use $z= b - A A^+ b$, where $A^+$ is the pesudoinverse of $A$. This is just the projection of $b$ to the space orthogonal to the span of columns of $A$. By definition, this $z$ is orthogonal to all columns of $A$, so $z^\intercal A = 0$. Also, $z^\intercal b = \|z\|_2$ which is nonzero if $b$ is not in the column span of $A$.

There is no such general method, and there is no way to tell (except perhaps in some simple cases, more anon) without actually attempting to solve the system (cf. Gaussian elimination).

There are three possibilities for a system of (linear) equations: either you have more equations than unknowns (we say the system is overdetermined) or you have more unknowns than equations (in which case the system is only weakly determined), or the system has exactly as many equations as unknowns. The last of these is what one usually sees in applications, so it has been widely studied (and this is a large part of linear algebra; also, that's the type previous answers have focused on), and in this case, as others have pointed out, one can often tell by computing a number which (if different from zero) tells us that the system has a unique solution -- it does not tell us more than this even in this case.

Anyway, the point of my answer is not to dwell on those aspects, but on a geometric interpretation of such systems that you apparently have not considered. First of all, usually, one often wants a unique solution for such systems. In any case, you can view this group of problems as trying to determine the intersection of $n-1$-dimensional euclidean spaces contained in some $n$-dimensional euclidean space -- this is because in rectangular coordinates such subspaces are defined by linear equations in (at most) $n$ variables. In this $n$-space, it is clear that one needs exactly $n$ of these $n-1$ subspaces in order to get them to intersect in a single point (two lines are necessary to meet in a point, two planes in a line, a line and a plane in a point, etc.). So our classification the other time into three possibilities can be interpreted geometrically as follows: the system is said to be overdetermined when it defines more $n-1$ subspaces than are strictly necessary to get their intersection to be a singleton; underdetermined when it defines less than the necessary number of $n-1$ subspaces, and just determined if it defines the necessary number.

It then becomes clear that in the underdetermined case, it is impossible to obtain a unique solution (however, one may have infinitely many solutions). When the system is overdetermined one may either have or not have a unique solution and there is no general way to tell other than studying the particular system further. It is the just determined case (which, luckily, one often encounters in practice) that one has a way to tell without immediately solving the system, whether it has a unique solution. To do this, one needs to change the picture a bit, and view the coefficients of the system as a matrix representing what is known as an operator (a kind of function between linear spaces) which acts on the $n$-space, taking every point of it to another point in the $n$-space (thus they are often called linear transformations). It turns out that that is not as bewildering as it might seem -- we need not track every point but what are known as the basis elements. The problem of solving this just determined system thus translates into finding the unique point (if it exists) that the operator carries to a given point (the point described by the constants of the system). It is now clear that the problem has been reduced to finding an inverse operator to tell us this unique point that is being sought for (if it exists, since a transformation need not be injective). However, we can even find out whether this point exists at all (IOW, whether the operator can be reversed) without trying to invert it directly. This is where the basis elements of the $n$-space which I mentioned before come into play. One need only track how the operator acts on these elements to see whether it is reversible. In general, these $n$ elements form an $n$-parallelotope, and it is a fact shown in linear algebra that a unique solution exists if and only if this $n$-parallelotope is transformed into another $n$-parallelotope by the operator -- that is, its $n$-volume does not disappear under the transformation, for in that case the space would have been folded on itself by the operator, as it were, so that there is no way to define an inverse transformation. Thus, just computing the $n$-volume of the image of this parallelotope tells us what we need to know -- this image volume is called the determinant of the mapping. There are many ways of defining and computing these determinants, but they all do the same job (this is a theorem in linear algebra). If the determinant does vanish, then either there is no solution (no point is mapped to the given point) or there are infinitely many. In either case (the system is said to be singular) things become complicated to analyse since we can no longer use the language of functions.

PS. As @LE ANH DUNG has mentioned above, all this is summarised in the powerful theorem of Rouché, which you should check out to understand this more.

## protected by Daniel FischerJul 3 '18 at 12:22

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).