Systems of Linear Equations

Introduction

Linear algebra is a fundamental tool in mathematics and natural sciences. It begins by studying the systems of linear equations. The subject evolves by polishing the techniques for solving the systems and generalizing them into operator theory.

Many techniques of linear algebra are familiar to students even before they start studying the subject. Thus it is important to emphasize that in order to properly interiorize the concepts, one may be required to abandon his/her favorite methods of solving the systems. The old methods will be replaced by techniques that allow better generalizations in the future.

Let us, for one last time solve a system of two equations in non-linear-algebra-approved ways - using the method of guessing.

Example 1
 
\begin{eqnarray*} 3x-2y&=&1\\ 4x+3y&=&7. \end{eqnarray*}

  • (a) Is it possible to guess the solutions of this system?

  • (b) Is guessing a legitimate way of solving the system? What are disadvantages of the method of guessing?

  • (c) Can this system be solved in ways other than guessing?

Definitions

A real linear equation in variables \( x_1 \), \( \dots \), \( x_n \) is any equation of the form \[ a_1x_1+a_2x_2+\cdots+a_nx_n=b,\] where \( a_1 \), \( \dots \), \( a_n \), \( b \) are real numbers. It is called linear because the left side is a linear function of its variables, or in other words, variables are only multiplied by constants and added together. (For example, the function \( \varphi(x_1,x_2,\dots, x_n)=x_1\cdot x_2+7 \) is not a linear function since \( x_1 \) and \( x_2 \) are multiplied.)

A system of linear equations is several linear equations put together. A general form of the system is: \begin{eqnarray*} a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n&=&b_1\\ a_{21}x_1+a_{22}x_2+\cdots+a_{2n}n_x&=&b_2\\ &\vdots&\\ a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n&=&b_m, \end{eqnarray*} where \( a_{11} \), \( \dots \), \( a_{1n} \), \( \dots \), \( a_{m1} \), \( \dots \), \( a_{mn} \), \( b_1 \), \( \dots \), \( b_m \) are real numbers.

A solution to the system is any \( n \)-tuple \( (x_1, \dots, x_n) \) that satisfies each of the \( m \) equations.

Equivalent systems

Two systems of equations are called equivalent if they have the same solutions.

Theorem 1
 

Consider the system of equations: \begin{eqnarray*} a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n&=&b_1\\ a_{21}x_1+a_{22}x_2+\cdots+a_{2n}n_x&=&b_2\\ &\vdots&\\ a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n&=&b_m, \end{eqnarray*}

  • (a) Let \( i,j\in\{1,2,\dots, m\} \). If the \( i \)-th and the \( j \)-th equation change their positions, the obtained system is equivalent to the original one.

  • (b) Let \( i\in\{1,2,\dots, m\} \) and let \( \alpha\neq 0 \) be a real number. Consider the equation \[ \alpha\cdot a_{i1}x_1+\cdots+\alpha\cdot a_{in}x_n=\alpha b_i\quad\quad\quad\quad\quad\quad\quad\quad\quad (\ast_i)\] obtained by multiplying the \( i \)-th equation by \( \alpha \). If the \( i \)-th equation is replaced by \( (\ast_i) \) the obtained system is equivalent to the original one.

  • (c) Let \( \alpha \) be any real number and let \( i,j\in\{1,2,\dots, m\} \). Consider the equation \[ \alpha\cdot a_{i1}x_1+\cdots+\alpha\cdot a_{in}x_n=\alpha b_i\quad\quad\quad\quad\quad\quad\quad\quad\quad (\ast_i)\] obtained by multiplying the \( i \)-th equation by \( \alpha \). Consider the equation obtained by adding \( (\ast_i) \) to the \( j \)-th equation: \[ \left(a_{j1}+\alpha a_{i1}\right)x_1+\cdots + \left(a_{jn}+\alpha a_{in}\right)x_n=b_j+\alpha b_i. \quad\quad\quad\quad\quad (\ast\ast_j)\] If the \( j \)-th equation is replaced by \( (\ast\ast_j) \) the obtained system is equivalent to the original one.

Gaussian elimination

The previous theorem is the cornerstone of majority of methods for solving systems of linear equations. In each step a system is transformed to an equivalent one that is in some way simpler than the original. After several steps one hopes to obtain the trivial system.

Let us first start from explaining the meaning of the expression trivial system. This is one such system: \begin{eqnarray*} x&=&8\\ y&=&9\\ z&=&21.\end{eqnarray*} Looking at the definition, this is indeed a system of equations. It has all the ingredients: variables and equations. This is a trivial system, or solved system. A little bit more complicated system is the following: \begin{eqnarray*} 2x-y+z&=&28\\ y+z&=&30\\ z&=&21. \end{eqnarray*} This system is easy to solve if we go backwards. From the last equation we have \( z=21 \), and this is sufficient to determine \( y \) from the second, giving us \( y=9 \). Now we can figure out \( x \) from the first equation: \( x=8 \). The last system is called a system in a row echelon form, or a system in an upper triangular form. Word echelon comes from French and means ladder or staircase.

The method of Gaussian elimination aims to reduce the system in the row-echelon form. The goal is for the last equation to have only one variable, thus making it trivial to solve. Then once we have the variable from the last equation, the preceding equation would ideally have only one more variable allowing us to find it if we know the last one.

In order to put the system in the row-echelon form we will first fix one variable in one of the equations, and using the transformations from Theorem 1 obtain an equivalent system in which that variable is removed from every other equation.

As an outline of the method we will consider the following system of three equations with three variables: \begin{eqnarray*} 2x-2y+8z&=&6\\ 6x+7y-9z&=&11\\ -4x+11y-3z&=&15. \end{eqnarray*}

Let us consider the variable \( x \) in the first equation. We will put the box around it and eliminate it from the other two equations: Here is how the system looks with a box: \begin{eqnarray*} 2\begin{array}{|c|}\hline x\\\hline\end{array}-2y+8z&=&6\\ 6x+7y-9z&=&11\\ -4x+11y-3z&=&15. \end{eqnarray*} We multiply the first equation by \( -3 \), add it to the second, and use the obtained equation to replace the second in the system. This will give us an equivalent system. As a part of the same step, we will multiply the first equation by \( 2 \), add it to the third, and use the obtained equation to replace the third in the system. We arrive to the following system that is equivalent to the original one: \begin{eqnarray*} 2x-2y+8z&=&6\\ 13y-33z&=&-7\\ 7y+13z&=&27. \end{eqnarray*} We now concentrate on the last two equations that are forming a system with two variables. We will not write the first equation until the very end of the problem. A box in the equation also serves as a mark that the equation is going to be a part of any subsequent system. \begin{eqnarray*} 13y-33z&=&-7\\ 7y+13z&=&27. \end{eqnarray*} Let us now put the box around \( y \) variable in the first equation: \begin{eqnarray*} 13\begin{array}{|c|}\hline y\\\hline\end{array}-33z&=&-7\\ 7y+13z&=&27. \end{eqnarray*} We multiply the first equation by \( -\frac7{13} \) and add it to the second. We get: \begin{eqnarray*} \frac{400}{13}z&=&\frac{400}{13}. \end{eqnarray*} We put a box around \( z \): \begin{eqnarray*} \frac{400}{13}\begin{array}{|c|}\hline z\\\hline\end{array}&=&\frac{400}{13}. \end{eqnarray*} Solving for \( z \) yields \( z=1 \).

Now we look at the preceding equation with box and solve it for \( y \). We get \( y=2 \). Finally, the first equation with box gives us \( x=1 \).

Examples

Example 2
 

Find all triples \( (x,y,z) \) for which the following three equations are satisfied: \begin{eqnarray*} 3x-y-2z&=&7\\ 5x+4y-z&=&16\\ -2x+y+3z&=&-9 \end{eqnarray*}

Example 3
 

Find all sequences \( (x,y,z,t) \) for which the following two equations are satisfied: \begin{eqnarray*} 2x-3y+5z-2t&=&8\\ 5x+7y-2z-5t&=&49 \end{eqnarray*}

Matrix of the system

In this section we will introduce matrices as a way to represent systems of equations in a more compact form. We will study the matrices instead of systems, and we will be able to conclude wether systems are solvable just by looking at their matrices. It will turn out that there are operations on matrices that correspond to Gaussian elimination that we studied before.

We will start by the definition of the matrix of the system.

Definition 1 (Coefficent matrix and augmented matrix)
 

Consider the system of equations: \begin{eqnarray*} a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n&=&b_1\\ a_{21}x_1+a_{22}x_2+\cdots+a_{2n}n_x&=&b_2\\ &\vdots&\\ a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n&=&b_m, \end{eqnarray*} The coefficient matrix (or matrix of coefficients) \( M \) of the above system is the following two-dimensional array of numbers: \begin{eqnarray*} M&=&\left[\begin{array}{cccc}a_{11}&a_{12}&\cdots&a_{1n}\\ a_{21}&a_{22}&\cdots&a_{2n}\\ &&\vdots&\\ a_{m1}&a_{m2}&\cdots&a_{mn}\end{array}\right]. \end{eqnarray*} The augmented matrix \( M_A \) of the above system is the following two-dimensional array of numbers: \begin{eqnarray*} M_A&=&\left[\begin{array}{ccccc}a_{11}&a_{12}&\cdots&a_{1n}&b_1\\ a_{21}&a_{22}&\cdots&a_{2n}&b_2\\ &&\vdots&&\\ a_{m1}&a_{m2}&\cdots&a_{mn}&b_m\end{array}\right]. \end{eqnarray*}

We will now provide several examples of systems of equations and their corresponding coefficient matrices and augmented matrices.

Example 4
 
Consider the system of equations. \begin{eqnarray*} 3x-2y&=&1\\ 4x+3y&=&7. \end{eqnarray*}

  • (a) Determine its matrix of coefficients.

  • (b) Determine its augmented matrix.

Example 5
 
Consider the system of equations. \begin{eqnarray*} -2y+z&=&-5\\ -11x+17y&=&0. \end{eqnarray*}

  • (a) Determine its matrix of coefficients.

  • (b) Determine its augmented matrix.

Recall that we said that two systems of equations are equivalent, if they have the same solutions. We now extend that definition to matrices: Two matrices are said to be equivalent if they are augmented matrices of two equivalent systems.

Theorem 2
 

Consider the matrix \begin{eqnarray*} M_A&=&\left[\begin{array}{ccccc}a_{11}&a_{12}&\cdots&a_{1n}&b_1\\ a_{21}&a_{22}&\cdots&a_{2n}&b_2\\ &&\vdots&&\\ a_{m1}&a_{m2}&\cdots&a_{mn}&b_m\end{array}\right]. \end{eqnarray*}

  • (a) Let \( i,j\in\{1,2,\dots, m\} \). If the \( i \)-th and the \( j \)-th row change their positions, the obtained matrix is equivalent to the original one.

  • (b) Let \( i\in\{1,2,\dots, m\} \) and let \( \alpha\neq 0 \) be a real number. Consider the row \[ \mathbf{R_{i,\rightarrow}}=\left[\alpha\cdot a_{i1},\cdots,\alpha\cdot a_{in} , \alpha b_i\right]\] obtained by multiplying the \( i \)-th row of \( M_A \) by \( \alpha \). If the \( i \)-th row of \( M_A \) is replaced by \( \mathbf{R_{i,\rightarrow}} \) the obtained matrix is equivalent to the original one.

  • (c) Let \( \alpha \) be any real number and let \( i,j\in\{1,2,\dots, m\} \). Consider the row \[ \mathbf{R_{i,\rightarrow}}=\left[\alpha\cdot a_{i1},\cdots,\alpha\cdot a_{in},\alpha b_i\right]\ \] obtained by multiplying the \( i \)-th row of \( M_A \) \( \alpha \). Consider the following row obtained by adding \( \mathbf{R_{i,\rightarrow}} \) to the \( j \)-th row of \( M_A \): \[ \mathbf{R^{\prime}_{i,\rightarrow}}=\left[\left(a_{j1}+\alpha a_{i1}\right),\cdots,\left(a_{jn}+\alpha a_{in}\right),b_j+\alpha b_i\right] .\] If the \( j \)-th two is replaced by \( \mathbf{R^{\prime}_{j,\rightarrow}} \) the obtained matrix is equivalent to the original one.

Row reduction and echelon forms

Recall that the system of equation is in a row-echelon form if the last equation contains only \( x_n \) variable; the second-to last only \( x_n \) and \( x_{n-1} \); the third equation from the bottom only \( x_n \), \( x_{n-1} \), and \( x_{n-2} \); etc. Such system is as good as the solved one. The matrix corresponding to such a system is called a matrix in a row-echelon form. The precise definition is this:

Definition 2 (echelon form of a matrix)
 

A matrix is in echelon form (or row echelon form) if it satisfies the following two properties:

  • (i) Except for the first one, each row starts with consecutive zeroes.

  • (ii) Each row starts with more zeroes than the row above it.

Row echelon form is also called the upper triangular form. Few examples of matrices in row echelon forms can be visualized as follows: \begin{eqnarray*} \left[\begin{array}{ccccc} \star & \ast & \ast &\ast &\ast\\ 0&\star&\ast & \ast &\ast\\ 0&0&0&0&0\\ 0&0&0&0&0 \end{array}\right]\,, \quad \left[\begin{array}{cccccc} 0&\star & \ast & \ast &\ast &\ast\\ 0&0&\star&\ast & \ast &\ast\\ 0&0&0&0&\star&\ast\\ 0&0&0&0&0&\star \end{array}\right]\,, \quad \left[\begin{array}{cccccc} \star & \ast & \ast &\ast &\ast&\ast\\ 0&0&\star&\ast & \ast &\ast\\ 0&0&0&0&\star&\ast\\ 0&0&0&0&0&\star\\ \end{array}\right]\,. \end{eqnarray*}

Each symbol \( \ast \) above can be replaced by any number, while each occurrence of \( \star \) be replaced by any non-zero number.

We were solving the systems of linear equations by reducing the systems to the row echelon form. We will now see that in an analogous way we can reduce the matrix in a row echelon form.

Example 6
 

Find a row echelon form for the matrix: \begin{eqnarray*} M&=&\left[\begin{array}{cccc}2&-2&8&6\\ 6&7&-9&11\\ -4&11&3&15\end{array}\right]\,. \end{eqnarray*}

Reduced echelon form

Definition 3 (reduced echelon form)
 

A matrix is in a reduced echelon form if it is in the echelon form and satisfies the following condition:

In each row the first non-zero entry is equal to 1. All entries above it are equal to zero.

Examples of matrices in reduced echelon forms are given below. \begin{eqnarray*} \left[\begin{array}{ccccc} 1& 0 & \ast &\ast &\ast\\ 0&1&\ast & \ast &\ast\\ 0&0&0&0&0\\ 0&0&0&0&0 \end{array}\right]\,, \quad \left[\begin{array}{cccccc} 0 &1 &0 &\ast &0 &0\\ 0 &0 &1 &\ast &0 &0\\ 0 &0 &0 &0 &1 &0\\ 0 &0 &0 &0 &0 &1 \end{array}\right]\,, \quad \left[\begin{array}{cccccc} 1&\ast & 0 &\ast &0 &0\\ 0&0 &1 &\ast &0 &0\\ 0&0 &0 &0 &1 &0\\ 0&0 &0 &0 &0 &1 \end{array}\right]\,. \end{eqnarray*}

Example 7
 

Find a reduced row echelon form for the matrix: \begin{eqnarray*} M&=&\left[\begin{array}{cccc}2&-2&8&6\\ 6&7&-9&11\\ -4&11&3&15\end{array}\right]\,. \end{eqnarray*}


2005-2018 IMOmath.com | imomath"at"gmail.com | Math rendered by MathJax
Home | Olympiads | Book | Training | IMO Results | Forum | Links | About | Contact us