Consistency

A linear system Ax = b is consistent if it has at least one solution and inconsistent if it has no solutions.

In general, a linear system Ax = b consistent for some b's but not for others. One way to think about consistency is to expand the left-hand side into a linear combination of the columns of A: if those columns are A1, A2, ..., An, then the equations is equivalent to

x1A1 + x2A2 + ... + xnAn = b.

In this form, the equation says that b is a linear combination of the columns of A. It holds only if there are x's that for which it is true, i.e. if and only if the equation has a solution for that b.

The linear system Ax = b is consistent if and only if b is a linear combination of the columns of A.

If A is square, we can relate the consistency of the system Ax = b to the invertibility of A.

If A is a square matrix, then the linear system Ax = b is consistent for all b if and only if A is invertible.

Proof: If A is invertible, then for any b, the system always has the solution x = A–1b.

Assume that A is not invertible. We'll find a b for which the system Ax = b is not consistent.

Suppose A has reduced row-echelon form R. Since A is not invertible, R cannot be the identity matrix, and so must have a row of zeroes at the bottom.

For some elementary matrices E1, E2, ..., Ek, we have that Ek...E2E1A = R. Set C = Ek...E2E1; then C is invertible and CA = R. Define b = C–1[0, 0, ..., 0, 1]T.

Suppose that Ax = b for some x. Then CAx = Cb = [0, 0, ..., 0, 1]T, so Rx = [0, 0, ... , 0, 1]T. But R has a row of zeroes at the bottom, so the matrix product Rx must also have a zero at the bottom. It clearly doesn't, so our assumption that Ax = b for some x was incorrect; there is no such x and the system is inconsistent for this b.