3
$\begingroup$

A linear system of equations is inconsistent (does not have a solution) if and only if there is a pivot in the last column of an echelon form of the augmented matrix.

I can understand the if part, that is because $0=1$ is impossible. But how do you prove the only if part? All of the posts I found on this site prove the if part only. My book says for only if part, "If we don’t have such a row, we just make the reduced echelon form and then read the solution off it." I don't think this is a proof to the only if part.

$\endgroup$
2
$\begingroup$

You want to prove that (a linear system of equtions is inconsistent) implies that (there is a pivot column in the last column of an echelon form of the augmented matrix).

This is equivalent to showing that

(there is no pivot column in the last column of the echelon form of the augmented matrix) implies that (the linear system is consistent).

Now suppose that there is no pivot column of the echelon form of the augmented system. Suppose that you already know that the solution space is not changed by elementary row operations. Also note that dropping the zero rows do not change the solution space as well and hence we can assume that there is no zero rows in our RREF. Remark: if the RREF is the zero matrix, any vector of the right size is a solution, we will assume that this is not the case here.

Let's construct a solution $x$ that satisfies the linear system. WLOG, we can write $x=(x_B, x_N)$ where $x_B$ are the entries of $x$ corresponds to pivot columns and $x_N$ corresponds to entries of $x$ corresponds to non-pivot columns.

We want to solve $$Rx=r$$

$$\begin{bmatrix} R_B & R_N \end{bmatrix}\begin{bmatrix} x_B \\ x_N \end{bmatrix}=r$$

where $R_B$ corresponds to the pivot columns and $R_N$ corresponds to the non-zero columns.

We set $x_N=0$ and we obtain $$R_Bx_B=r$$

As, $R_B$ is constructed from the pivot columns, the diagonal entries of $R_B$ are non-zero, hence it is non-singular and hence $x_B= R_B^{-1}r$.

Hence, we have found a solution.

$\endgroup$
2
  • $\begingroup$ I'm confused by the final step. Why do diagonal entries of 1 imply invertability? In fact, if I'm not mistaken, $R_B$ is not necessarily square. What does invertability even mean in the context of non-square matrices? $\endgroup$ – Serendipitous Epiphany Feb 5 '20 at 2:02
  • $\begingroup$ I made a mistake earlier, the diagonal need not be $1$ since it can be just a REF and need not be an RREF. The diagonals are non-zero. $R_B$ is an upper triangular square matrix and since the determiannt is just the product of diagonal for a triangular matrix, $R_B$ is invertible. $\endgroup$ – Siong Thye Goh Feb 5 '20 at 2:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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