Solving linear equations

1 Solving one equation: review

Given a system of linear equations Ax = b, we can solve this equation by Gauß-Jordan elimination. By solve we mean:

• determine if a solution exists

• if so, find all possible solutions, which effectively is:

– find the kernel of A (solve the homogeneous equation Ax = 0)

– find a particular solution

We do this by reducing the augmented matrix [A|b] to a row-reduced echelon matrix [A′|b′] (note that b changes to b′ in the process), from which we can read off the answer.

Suppose A′ has k rows (that is, A has rank k), and the pivots are in columns c_{1}, …, c_{k}. Then:

• a solution exists iff b′ vanishes after the kth entry:

i.e., it’s b′ = (b′_{1}, b′_{2}, …, b′_{k}, 0, …, 0) – this is because otherwise we have a 0 = 1 row.

• to find all possible solutions

– the kernel of A is exactly “the pivot equals minus the later terms in that row”

– a particular solution is “put the b′_{i} coordinate in the c_{i}th entry of x (formally, x_{c_{i}} = b′_{i}).

The above notation is confusing, but the idea is simple – let’s illustrate. For instance, if [A′|b′] is

[\begin{matrix}1 & 2 \\ & & 1 \end{matrix}| \begin{matrix}4 \\ 7 \\ 0 \end{matrix}]

(I’ve left spaces for zeros, for readability), then:

The pivots^{1} (the leading 1s in some rows) are x_{1} and x_{3}, while x_{2} is the free variable: we can set it to whatever we want (b/c the pivots can be adjusted to compensate).

The solution is:

• the system is consistent (meaning it has a solution), as we have zeros opposite the zero rows

• the solution is given by:

– the kernel is the subspace of R^{3} such that x_{1} + 2x_{2} = 0 (so x_{1} = −2x_{2}) and x_{3} = 0; in general we’d have more equations, but they’d all be of this form: some pivot equals negative the later coordinates in that row (or zero if there aren’t any). So ker A is

[\begin{matrix}−2x_{2} \\ x_{2} \\ 0 \end{matrix}]

For clarity, one often writes r, s, t for the free variables, so

ker A = [\begin{matrix}−2r \\ r \\ 0 \end{matrix}]

– A specific solution in x_{0} = (4, 0, 7) (i.e., x_{1} = 4, x_{2} = 0, x_{3} = 7): the pivots tell us where to put the numbers so they’ll end up in the right place.

Thus the general solution is:

x_{0} + ker A = [\begin{matrix}4 \\ 0 \\ 7 \end{matrix}] + [\begin{matrix}−2r \\ r \\ 0 \end{matrix}] = [\begin{matrix}4 − 2r \\ r \\ 7 \end{matrix}]

1I don’t know if this usage is correct: the point is that these are the “unfree” variables.

2 Solving many equations

The above shows how you can solve one particular equation, but what if you want to solve many, like Ax = b_{i}. Maybe every day your boss comes by and gives you a b_{i} to solve, and you really don’t want to have to do everything again.

What’s the solution? Well, every time you row reduce [A|b], you’ll get the same A′, but maybe a different b′ – so all you need to do is record the sequence of row moves and apply this to each b_{i}.

Recall that a row operation is just left-multiplication by an elementary matrix, so multiplying these together yields a matrix such that leftmultiplication by it does all of the row operations. Call this matrix R, so RA = A′, and thus R[A|b] = [A′|b′].

So given A, compute R (and in the process A′) and you’re set! Now given b, just compute b′ = Rb and you can read the solutions to A′x = b′ straight off the matrix as above.

How can you compute R? Concretely, you can do this by looking at the augmented matrix [A|I] – then Gauß-Jordan yields [A′|R]: each row operation you do on the A part gets recorded on the I part.

3 Special cases

3.1 Span

Given a collection of vectors ⟨v_{1}, …, v_{l}⟩ where v_{i} ∈ R^{n}, asking “is w in the span of ⟨v_{i}⟩, and if so, express it” is exactly the same as solving the equation Ax = b where A is the column matrix of the v_{i} and b = w.

If we want to solve this for any w that’s handed to us, just find A′ and R (as above), and run the machine.

3.2 Invertible Matrices

A particularly interesting case is when the rref matrix A′ is the identity matrix I_{n} (just 1s on the diagonal); note that this can only possible occur if A is square, i.e., a map A: R^{n} ) R^{n} between spaces of the same dimension.

In that case there’s no kernel (the kernel is x_{i} = 0 for all i), and the image is the whole space – the solution is exactly x = b′.

In that case RA = I_{n}, and R = A^{−1}. For instance, for A = ( \begin{matrix}5 & 6 \\ 4 & 5 \end{matrix}), we get A^{−1} = ( \begin{matrix}5 & −6 \\ −4 & 5 \end{matrix} ); in equations, Ax = b

is solved by applying A^{−1} to both sides and getting A^{−1}Ax = A^{−1}b so x = A^{−1}b (which we’ve also called b′).