What makes a linear system of equations "unsolvable"?

Solution 1:

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$.

Solution 2:

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.

Solution 3:

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.

Solution 4:

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.