19.1 Systems of linear equations
19.1.1 Gaussian elimination
A system of linear equations is something in the form
(19.1) | |||
(19.2) | |||
(19.3) | |||
(19.4) |
This is pretty abstract (it describes any system of linear equations). The rather obvious question is what’s what?
A concrete example will probably help
(19.6) | |||
(19.7) |
-
•
The
(for all integer and such that ) are the coefficients of the system of linear equations. In the case of the concrete example, , , and . The coefficients are constants and are fixed for the given system. -
•
The
are the \sayvariables. We do not know the values of these (we are trying to solve the system for them) and thus we denote them using letters, as we don’t know which values they are. In the case of the concrete values, and (don’t be confused by the fact that and look similar - they’re definitely different variables). -
•
The
are the \sayconstant terms. We are trying to solve for these. They are fixed for the system in question.
How do we solve a system of linear algebraic equations? Well, in the case of the
concrete example, we can just try using algebra. Of course,
The key idea behind Gaussian elimination is that a single equation in the form
If we have two equations, how can we turn them into one such equation? Take the
concrete example; currently there are two equations in two variables, and we’d
like one equation in one variable. From the system, we should pick one variable
(either
(19.9) | |||
(19.10) |
For this system (the concrete example system), we can eliminate
Then we can just subtract this equation from both sides of the other equation, which gives that
Therefore
So
The concrete example wasn’t too bad, so let’s try to think about a more general case, that of the system
(19.14) | |||
(19.15) |
If we proceed by using the previous method (of solving for
(19.16) |
Then by subtracting from the second equation we obtain a linear equation which
only involves
(19.17) | |||||
(19.18) |
It hopefully seems obvious that we already have a system in terms of
There’s another case which is a bit of a pain; if the two equations are
multiples of one another (e.g.
Therefore, we can solve a
How do we solve a
(19.19) | |||
(19.20) | |||
(19.21) |
Who doesn’t love a good spoiler? Here’s how we can decompose this
In the bottom right-hand corner, we have a
-
•
If
then we can just compute and and subtract the first equation multiplied by each value from the second equation and third equation (respectively). -
•
If
then we can’t eliminate the other s from the equations. What we can instead do, though, is swap two rows. If either of the coefficients is non-zero (i.e. or ), we just swap that row with the first row (which one doesn’t matter). In the case where , we already just have an equation in terms of and , so is a \sayfree variable (i.e. can be anything).
Then we have a
This is the easier case (from earlier), as we know
We can solve for arbitrarily large
It’s worth doing a few examples to really understand the method in full. As always, there are some great questions on https://madasmaths.com.
19.1.2 Elementary matrices
An \sayelementary matrix is a matrix which can be obtained by performing exactly one of the elementary row operations (last seen in Section 19.1.2), once on the identity matrix.
For example, let us consider the case of the
If we swap the two rows, we obtain a new matrix
Why the letter
We can codify the fact that elementary matrices and elementary row operations are kind of equivalent using this theorem.
Theorem 19.1.1
If
To prove this, we need to consider all the elementary matrices. The first
class (perhaps the easiest) to consider, is the elementary matrix which
we obtain by swapping two rows of the identity matrix. To prove that
multiplying this with another matrix,
Then, we can consider the result of multiplying
From here we can consider a set of exhaustive cases.
-
•
If
then we have that if and only if and in all other cases. This means that the sum is equal to , as this is the only non-zero member of the sum (i.e. the jth item of the yth row is now the jth item of the xth row - the positions have been swapped which is what we wanted to show). -
•
We now get the case where
for free, as we can apply the exact same logic as for the case by swapping and (i.e. this case is true by symmetry). -
•
In all other cases of
we know that if and only if , so when . Therefore, the only non-zero member of the sum is . That is, all the other rows in are equivalent to all the other rows in (they have remained unchanged, which is what would have happened had we just applied the elementary row operations to directly).
This means that the theorem is true for any
TODO: prove the other theorems (they can be shown analogously)
19.1.3 LU decomposition
In general, systems of linear equations which are triangular22
2
That is, all the elements in coefficient matrix either above or below
the diagonal are all equal to
Unfortunately, however, more often than not coefficient matrices do not come in triangular form33 3 As you’ve probably noticed, reality is messy.. It would, however, be nice if we could reduce them to triangular matrices (if you’re thinking \sayof course, we can just use Gaussian elimination (Section 19.1.1), then you are correct)! However, Gaussian elimination is useful for solving an equation in the form
It works very well when we only have one
And because matrix multiplication is associative, this is the same as
As
We can solve this system using forwards or backwards substitution (depending on
whether
Which gives us the value of
19.1.4 Performing LU decomposition
This is all very well, but how do we split
After Gaussian elimination, if we carried out steps represented by the matrix
(19.34) | |||||
As any matrix multiplied by its inverse is |
(19.35) | ||||
As matrix multiplication is associative | (19.36) |
Now we have an equation in the form
(19.37) |
Unfortunately,
(19.38) |
That is, we have
Where