Systems of Linear Equations

Let's start by taking a look at a problem that may seem a bit boring, but in terms of practical applications is perhaps the most common use of matrices: the solution of systems of linear equations. Following is a typical problem (although real-world problems may have hundreds of variables).

Solve the following system of equations:

$\displaystyle x + 4y + 3z$ $\displaystyle =$ $\displaystyle 7$  
$\displaystyle 2x + 5y + 4z$ $\displaystyle =$ $\displaystyle 11$  
$\displaystyle x - 3y - 2z$ $\displaystyle =$ $\displaystyle 5.$  

The key observation is this: the problem above can be converted to matrix notation as follows:

$\displaystyle \begin{pmatrix}1 & 4 & 3\\ 2 & 5 & 4 \\ 1 & -3 & -2\end{pmatrix} \begin{pmatrix}x\\ y\\ z\end{pmatrix} = \begin{pmatrix}7\\ 11\\ 5\end{pmatrix}.$ (1)

The numbers in the square matrix are just the coefficients of $ x$, $ y$, and $ z$ in the system of equations. Check to see that the two forms--the matrix form and the system of equations form--represent exactly the same problem.

Ignoring all the difficult details, here is how such systems can be solved. Let $ M$ be the $ 3\times 3$ square matrix in equation (1) above, so the equation looks like this:

$\displaystyle M \begin{pmatrix}x\\ y\\ z\end{pmatrix} = \begin{pmatrix}7\\ 11\\ 5\end{pmatrix}.$ (2)

Suppose we can somehow find another matrix $ N$ such that $ NM=I$. If we can, we can multiply both sides of equation (2) by $ N$ to obtain:

$\displaystyle NM \begin{pmatrix}x\\ y\\ z\end{pmatrix}= I\begin{pmatrix}x\\ y\\... ...begin{pmatrix}x\\ y\\ z\end{pmatrix}= N\begin{pmatrix}7\\ 11\\ 5\end{pmatrix}, $

so we can simply multiply our matrix $ N$ by the column matrix containing the numbers 7, 11, and 5 to get our solution.

Without explaining where we got it, the matrix on the left below is just such a matrix $ N$. Check that the multiplication below does yield the identity matrix:

$\displaystyle \begin{pmatrix}2 & -1 & 1\\ 8 & -5 & 2 \\ -11 & 7 & -3\end{pmatri... ...\ 1 & -3 & -2\end{pmatrix}= \begin{pmatrix}1&0&0\\ 0&1&0\\ 0&0&1\end{pmatrix}. $

So we just need to multiply that matrix $ N$ by the column vector containing 7, 11, and 5 to get our solution:

$\displaystyle \begin{pmatrix}2 & -1 & 1\\ 8 & -5 & 2 \\ -11 & 7 & -3\end{pmatri... ...gin{pmatrix}8\\ 11\\ -15\end{pmatrix} = \begin{pmatrix}x\\ y\\ y\end{pmatrix}. $

From this last equation we conclude that $ x=8$, $ y=11$, and $ z=-15$ is a solution to the original system of equations. You can plug them in to check that they do indeed form a solution.

Although it doesn't happen all that often, somtimes the same system of equations needs to be solved for a variety of column vectors on the right--not just one. In that case, the solution to every one can be obtained by a single multiplication by the matrix $ N$.

The matrix $ N$ is usually written as $ M^{-1}$, called ``$ M$-inverse''. It is a multiplicative inverse in just the same way that $ 1/3$ is the inverse of $ 3$: $ 3\cdot(1/3)=1$, and $ 1$ is the multiplicative identity, just as $ I$ is in matrix multiplication. Entire books are written that describe methods of finding the inverse of a matrix, so we won't go into that here.

Remember that for numbers, zero has no inverse; for matrices, it is much worse--many, many matrices do not have an inverse. Matrices without inverses are called ``singular''. Those with an inverse are called ``non-singular''.

Just as an example, the matrix on the left of the multiplication below can't possibly have an inverse, as we can see from the matrix on the right. No matter what the values are of $ a, b, \ldots, i$, it is impossible to get anything but zeroes in certain spots in the diagonal, and we need ones in all the diagonal spots:

$\displaystyle \begin{pmatrix}1&0&0\\ 0&0&0\\ 0&0&0\end{pmatrix}\begin{pmatrix}a... ...d&e&f\\ g&h&i\end{pmatrix}= \begin{pmatrix}a&b&c\\ 0&0&0\\ 0&0&0\end{pmatrix}. $

If the set of linear equations has no solution, then it will be impossible to invert the associated matrix. For example, the following system of equations cannot possibly have a solution, since $ x+y+z$ cannot possibly add to two different numbers (7 and 11) as would be required by the first two equations:

$\displaystyle x + y + z$ $\displaystyle =$ $\displaystyle 7$  
$\displaystyle x + y + z$ $\displaystyle =$ $\displaystyle 11$  
$\displaystyle x - 3y - 2z$ $\displaystyle =$ $\displaystyle 5.$  

So obviously the associated matrix below cannot be inverted:

$\displaystyle \begin{pmatrix}1&1&1\\ 1&1&1\\ 1&-3&-2\end{pmatrix}. $