This may be one of the most typical application of Matrix. You may still remember from high school math on how to solve a simultaneous equation. If the number of unknown variable is only 2 or 3 as you saw in the high school math class, it would be easier to solve it in the way you learned in the high school math class. But unfortunately most of real life problem is much more complicated than that. The number of unknown variables would be much more than 2 or 3 and in some cases they may amount to several dozens. In such a case, representing the problem in a matrix format and solve the problem with the technique you would learn in Linear Algebra class would be the best solution.
I don't want to turn this page into a Linear Algebra test book. The purpose of this section is just to show an example of the case for matrix representation.
- How is a simultaneous equation written as a matrix equation ?
- Why is the matrix form needed ?
- How is a 3 x 3 example solved ?
- When does Ax = b have a solution ?
How is a simultaneous equation written as a matrix equation ?
Let's start with the translation step, because everything else on this page depends on it. The idea is to collect all the numbers of the system into one matrix and two vectors. Once that is done, the system has the same short form whether it has 2 unknowns or 2000.
A set of simultaneous equation with n unknown variable can be represented as follows.
Figure 1. A system of m linear equations in n unknowns. Each equation is a weighted sum of the same unknowns x1 to xn.
Once you get this kind of simultaneous equation, you can extract coefficient parts, unknown variable and constants parts and can construct a Matrix and two vectors as follows. This is what you already learned from your Linear Algebra course.
Figure 2. The coefficient matrix A, the unknown vector x and the constant vector b. Every coefficient sits in the row of its equation and the column of its unknown.
Once you got a coefficient matrix and variable vectors, you can represent your original simultaneous equation as follows.
Figure 3. The whole system in matrix form. The same three symbols describe a system of any size.
- In Figure 1, aij is the coefficient of the unknown xj in equation i. The first index counts the equations, from 1 to m, and the second counts the unknowns, from 1 to n. The number of equations m does not have to equal the number of unknowns n.
- In Figure 2, A therefore has m rows and n columns. The vector x has n entries, one per unknown, and b has m entries, one per equation.
- In Figure 3, row i of A multiplied by x gives ai1x1 + ai2x2 + ... + ainxn, which is the left side of equation i. So Ax = b is the whole of Figure 1, written with the row-by-column rule of matrix multiplication.
One detail matters when you build A for a real problem. If an unknown does not appear in an equation, its coefficient is 0, and the 0 must still be written into A. For example, the equation 3x1 - x3 = 5 in a three-unknown system becomes the row [3 0 -1] with the entry 5 in b. Forgetting the 0 shifts the remaining coefficients into the wrong columns.
Rows are equations and columns are unknowns : aij is the coefficient of xj in equation i.A missing unknown is a 0 in A : every row must have exactly n entries in the same column order.Ax = b has the same form for any size : only the dimensions of A, x and b change.
Why is the matrix form needed ?
Now a question comes out. Why we need to do this ? After we finish a high school math, all of us would know how to find solutions for a simultaneous equations (I hope you are also a part of this group -:). As far as I remember, I start learning about Simultaneous equation from Junior High and early Senior High. and the learns about using the Matrix to solve a simultaneous equation in the second year in Senior High. At that time, using Matrix for this didn't seem easy to me. Especially finding the solution for the matrix equation using what we called 'Gaussian Elemenation Method' was so complicated to me. And I (also a lot of my friends) said "Why do we have to do this kind of akward things ?".
I think the answer to this question is very simple. The common method you learned to solve a simultaneous equation in lower grade of High school would be a good method to find the solution to the simultaneous equation with 2 or 3 variables. Just try to use the same method to solve a simultaneous equation with 10 variables. Then you would realize right away that the method would not be a practical method and you would need something new way to solve it.
In addition, most of the real life problem would have much more variables than 10. Some times a single problem would get involved with several hundred variables. In this case, you would realize that Matrix representation is more practical method. A better news is that you only have to convert your problem (a simultaneous equation in this case) into a matrix equation and you don't have to worry about finding solution for it. There are a lot of computer program (e.g, Matlab, Octave, Mathematica and even Microsoft Excel) can find the solution from the Matrix equation. In short, Converting a real life problem into a Matrix format is your job and doing mathemtical operation for solution finding is not your job. It's computer's job.
Let's put numbers on the growth that these paragraphs describe. Gaussian elimination solves an n x n system with about n3/3 multiplications. That is about 330 for n = 10, and about 3.3 x 108 for n = 1000, which a laptop finishes in well under a second. Cramer's rule, with each determinant expanded by cofactors, needs on the order of n! products per determinant, and 10! is already 3,628,800. So the choice of method matters much more than the speed of the computer.
There is a second reason for the matrix form. It separates the structure of the problem from its data. A describes how the unknowns are connected, and b holds the measured or required values. When b changes but A stays the same, a solver can reuse the elimination work already done on A. Each new b then costs only about n2 operations instead of n3/3.
Hand methods grow too fast : substitution by hand and Cramer's rule become impractical long before n = 10.Gaussian elimination costs about n3/3 multiplications : a computer solves systems with thousands of unknowns routinely.The matrix form lets a solver reuse its work : the same A with many different b vectors is cheap to solve.Your job is to build A and b : once the problem has the form Ax = b, the solution is one library call.
How is a 3 x 3 example solved ?
Let's see what the computer actually does, on a system small enough to follow by hand. The method is the Gaussian elimination mentioned above. It has two phases, forward elimination and back substitution, and both work only on the numbers in A and b.
Take the following three equations in three unknowns.
2x1 + x2 - x3 = 8 -3x1 - x2 + 2x3 = -11 -2x1 + x2 + 2x3 = -3
In the notation of Figure 2, A = [2 1 -1; -3 -1 2; -2 1 2] and b = [8; -11; -3]. The elimination works on the augmented matrix [A | b], which is A with b attached as an extra column. Each step adds a multiple of one row to another row. This does not change the solution, because it is the same as adding a multiple of one equation to another.
start [ 2 1 -1 | 8 ]
[ -3 -1 2 | -11 ]
[ -2 1 2 | -3 ]
row2 + (3/2) row1, row3 + row1 [ 2 1 -1 | 8 ]
[ 0 1/2 1/2 | 1 ]
[ 0 2 1 | 5 ]
row3 - 4 row2 [ 2 1 -1 | 8 ]
[ 0 1/2 1/2 | 1 ]
[ 0 0 -1 | 1 ]
The matrix is now upper triangular, so the last row holds a single unknown. Back substitution solves the rows from the bottom up. The third row says -x3 = 1, so x3 = -1. The second row says x2/2 + x3/2 = 1, so x2 = 3. The first row says 2x1 + 3 + 1 = 8, so x1 = 2. You can check the answer (2, 3, -1) in all three original equations.
In Matlab or Octave, the whole calculation is a single backslash operator.
A = [2 1 -1; -3 -1 2; -2 1 2]; b = [8; -11; -3]; x = A\b % returns [2; 3; -1]
The backslash operator runs the same elimination internally. It also swaps rows when needed, so that each pivot, the diagonal element used to clear the column below it, is as large as possible. A zero pivot would stop the elimination, and a very small one would magnify rounding errors. For this reason, x = A\b is preferred to x = inv(A)*b, which does more work and is less accurate.
Forward elimination makes A upper triangular : each step adds a multiple of one row to another and leaves the solution unchanged.Back substitution solves from the last row upward : each row then contains only one new unknown.Row swaps keep the pivots safe : solvers choose large pivots to avoid division by zero and to limit rounding errors.Use A\b rather than inv(A)*b : it gives the same answer with less work and better accuracy.
When does Ax = b have a solution ?
The example above has exactly one answer, but that is not guaranteed. A solver can only report the situation; it cannot repair a badly posed system. So before you trust a result, you should know which of three cases your system is in.
The tool that separates the cases is the rank, the number of independent rows of a matrix. Compare the rank of A with the rank of the augmented matrix [A | b], and with the number of unknowns n.
- rank(A) = rank([A | b]) = n : there is exactly one solution. For a square A, this is the same as det(A) is not 0. The 3 x 3 example has det(A) = -1, so its solution is unique.
- rank([A | b]) > rank(A) : there is no solution. The equations contradict each other. For example, x1 + 2x2 = 3 and 2x1 + 4x2 = 7 cannot both hold. The left side of the second equation is twice the first, but the right side is not.
- rank(A) = rank([A | b]) < n : there are infinitely many solutions. With 2x1 + 4x2 = 6 as the second equation, both equations say the same thing. Then x1 = 3 - 2x2 works for any x2, so one unknown stays free.
The shape of A gives a first hint. With more equations than unknowns, m > n, the system usually has no exact solution, because measured data rarely agree perfectly. The practical answer is then the least square solution, which makes the error as small as possible. With fewer equations than unknowns, m < n, there is either no solution or infinitely many, and n - rank(A) unknowns stay free. For a square but singular A, Matlab prints the warning "Matrix is singular to working precision". That warning means that the result of A\b cannot be trusted.
Rank decides the case : compare rank(A), rank([A | b]) and the number of unknowns n.A square system has one solution when det(A) is not zero : a zero determinant means no solution or infinitely many.Too many equations call for least square : an overdetermined system usually has no exact solution, only a best fit.Too few equations leave free unknowns : the solution set then has n - rank(A) free parameters.