Equations and matrices

Systems of linear equations: System of linear equations and matrices

Equations and matrices

Now that we have discussed how to systems of linear equations can be represented with the aid of matrices, we formulate the elementary operations on systems of linear equations in terms of matrices.

Elementary row operations The elementary operations to systems of linear equations translate directly into elementary row operations on (or elementary operations on rows of) the augmented matrix. These operations can be briefly described by denoting the \(i\)-th row of the matrix by \(R_i\). The three elementary row operations on matrices are:

\(R_i\rightarrow c\cdot R_i\;(c\neq 0)\) : multiplying all the numbers in the \(i\) -th row with the number \(c\). \[\small\left(\begin{array}{ccc|c} a_{11} & \cdots & a_{1n} & b_1\\ \vdots && \vdots & \vdots \\ a_{i1} & \cdots & a_{in} & b_i \\ \vdots && \vdots & \vdots \\ a_{m1} & \cdots & a_{mn} & b_m\end{array}\right)\rightsquigarrow \left(\begin{array}{ccc|c} a_{11} & \cdots & a_{1n} & b_1\\ \vdots && \vdots & \vdots \\ c\cdot a_{i1} & \cdots & c\cdot a_{in} & c\cdot b_i \\ \vdots && \vdots & \vdots \\ a_{m1} & \cdots & a_{mn} & b_m\end{array}\right)\]
\(R_i\rightarrow R_i+c\cdot R_j\) : adding the \(c\) -voud of the \(j\) -th row to the \(i\) -th row. \[\small \left(\begin{array}{ccc|c} a_{11} & \cdots & a_{1n} & b_1\\ \vdots && \vdots & \vdots \\ a_{i1} & \cdots & a_{in} & b_i \\ \vdots && \vdots & \vdots \\ a_{j1} & \cdots & a_{jn} & b_j \\ \vdots && \vdots & \vdots\\ a_{m1} & \cdots & a_{mn} & b_m\end{array}\right)\rightsquigarrow \left(\begin{array}{ccc|c} a_{11} & \cdots & a_{1n} & b_1\\ \vdots && \vdots & \vdots \\ a_{i1}+c\, a_{j1} & \cdots & a_{in}+c\, a_{jn} & b_{i}+c\, b_j \\ \vdots&& \vdots & \vdots \\ a_{j1}& \cdots & a_{jn} & b_j \\ \vdots && \vdots & \vdots\\ a_{m1} & \cdots & a_{mn} & b_m\end{array}\right)\]
\(R_i\leftrightarrow R_j\) : changing the \(i\) -th and \(j\) -th row. \[\small\left(\begin{array}{ccc|c} a_{11} & \cdots & a_{1n} & b_1\\ \vdots && \vdots & \vdots \\ a_{i1} & \cdots & a_{in} & b_i \\ \vdots && \vdots & \vdots \\ a_{j1} & \cdots & a_{jn} & b_j \\ \vdots && \vdots & \vdots\\ a_{m1} & \cdots & a_{mn} & b_m\end{array}\right)\rightsquigarrow \left(\begin{array}{ccc|c} a_{11} & \cdots & a_{1n} & b_1\\ \vdots && \vdots & \vdots \\ a_{j1} & \cdots & a_{jn} & b_j \\ \vdots&& \vdots & \vdots \\ a_{i1}& \cdots & a_{in} & b_i \\ \vdots && \vdots & \vdots\\ a_{m1} & \cdots & a_{mn} & b_m\end{array}\right)\]

The arrow \(\rightarrow\) in the above row operations has the meaning of "is replaced by". This describes the row operation(s) we carried out to transform the matrix on the left of the symbol into the matrix on the right.

The symbol \(\rightsquigarrow\) has the meaning "is reduced to". We use the symbol \(\boldsymbol{\sim}\) to indicate that the matrices on the left and on the right of this symbol arose from one another by a series of elementary row operations. We then say that one matrix is obtained from the other by row reduction or briefly reduction.

A matrix obtained by reduction from the augmented matrix of a system of linear equations is the augmented matrix of a system of equations having the same solution as the original system.

Example To illustrate the matrix notation we look again at an earlier example, which dealt with the elementary operations. The system of linear equations \[\left\{\begin{array}{rrrrrrrrr}x&+&y&+&z&+&w&=&1\\ 2x&+&y&+&z&+&2w&=&4\end{array}\right.\] has as a corresponding augmented matrix \[\left(\,\begin{array}{rrrr|r} 1 & 1 &1 & 1 & 1\\ 2 & 1 &1 &2 & 4 \end{array}\,\right)\] At each step of the reduction, we describe the effect on the system, and which augmented matrix is obtained.

We subtract the first equation twice from the second equation, that is, we carry out the elementary row operation \(R_2\rightarrow R_2-2R_1\) to the augmented matrix; we get\[\left\{\begin{array}{rrrrrrrrr}x&+&y&+&z&+&w&=&1\\ &-&y&-&z&&&=&2\end{array}\right.\qquad\mathrm{and}\qquad \left(\,\begin{array}{rrrr|r} 1 & 1 & 1 & 1 & 1\\ 0 & -1 &-1 & 0& 2 \end{array}\,\right) \] Then we add the second equation to the first, that is, we apply the elementary row operation \(R_1\rightarrow R_1+R_2\): \[\left\{\begin{array}{rrrrrrrrr}x&&&&&+&w&=&3\\ &-&y&-&z&&&=&2\end{array}\right.\qquad\mathrm{and}\qquad \left(\,\begin{array}{rrrr|r} 1 & 0 & 0 & 1 & 3\\ 0 & -1 &-1 & 0& 2 \end{array}\,\right)\] Finally we multiply the second equation with #-1#, ie, we apply the basic rijoperatie \(R_2\rightarrow -1\cdot R_2\) to: \[\left\{\begin{array}{rrrrrrrrr}x&&&&&+&w&=&3\\&&y&+&z&&&=&-2\end{array}\right.\qquad\text{and}\qquad \left(\,\begin{array}{rrrr|r} 1 & 0 & 0 & 1 & 3\\ 0 & 1 & 1 & 0 & -2 \end{array}\,\right)\]

If we just perform the eliminations in matrix notation and indicate the steps explicitly, then we record the above reduction process as follows: \[\begin{array}{rcll} \left(\begin{array}{rrrr|r} \color{green}{1} & 1 & 1 & 1 & 1\\ 2 & 1 &1 & 2 & 4 \end{array}\right) & \rightsquigarrow & \left(\begin{array}{rrrr|r} \color{green}{1} & 1 & 1 & 1 & 1\\ \color{green}{0} & -1 &-1 & 0& 2 \end{array}\right) &\blue{\begin{array}{r} \phantom{x} \\ R_2-2R_1\end{array}}\\ \\ & \rightsquigarrow & \left(\begin{array}{rrrr|r} \color{green}{1} & \color{green}{0} & 0 & 1 & 3\\ \color{green}{0} & -1 & -1 & 0 & 2 \end{array}\right) &\blue{\begin{array}{r} R_1+R_2\\ \phantom{x}\end{array}} \\ \\ & \rightsquigarrow & \left(\,\begin{array}{rrrr|r} \color{green}{1} & \color{green}{0} & 0 & 1 & 3\\ \color{green}{0} & \color{green}{1} & 1 & 0 & -2 \end{array}\,\right) &\blue{\begin{array}{r}\phantom{x}\\ -R_2\end{array}} \end{array}\] At every stage, the above matrix elements that we are satisfied with and that will not be changed later during the process, are coloured green; the row operations mentioned in the reduction process are displayed in blue; in rows in which nothing happens, we add no comment.

The blue indications on the right make clear what row operation(s) we used to get from the matrix at the left to the matrix at the right.

The augmented matrix, the end result has a special form, the so-called row reduced echelon form, which will be discussed later.

homogeneous system In the case of a homogeneous system, we can work with the coefficient matrix in place of the augmented matrix.

Each effect of an elementary row operation can be undone by a similar operation. In the form of systems of equations it was found from the proof of the theorem hat arrays which can be reduced to each other by means of series of elementary operations, equivalent. This theorem underlines the main point of a row operation in the elimination method: at the transition from one augmented matrix to another augmented matrix by reduction, the corresponding systems of linear equations remain equivalent.

The symbol \(\sim\) is generally used to denote an equivalence. Previously we called two systems of linear equations equivalent if they have the same solution. Also, previously we stated that two systems are equivalent if and only if they can be transformed into each other by a sequence of elementary operations in which we allow rows of nulls to be omitted and added. This is an equivalence relation. Using the equivalence symbol is appropriate here, even though in #\sim#, we do not allow rows to be removed and/or added.

We will address the translation of the solving of a system of linear equations in terms of matrices. Below is the first step in this direction:

The goal

Each elementary operation of a matrix corresponds to an elementary operation on the associated system of linear equations. Therefore, systems of equations associated with matrices #A# and #B# such that \(A \rightsquigarrow B\) are equivalent.

The intention is to alter the augmented matrix by use of elementary operations in such a way that the associated system of equations will be solved.

For example, if the left-hand part of the coefficient matrix consisting of the elements from all #m# rows in the first #m# columns, has the form \[\matrix{1&0&0&\cdots&0 \\ 0&1&0&\cdots&0 \\ \vdots&\vdots&&\vdots&0 \\ 0&\cdots&\cdots&1&0 \\ 0&\cdots&\cdots&0&1 }\] then the solution of the system of equations can be read off from the augmented matrix: the unknowns #x_1,\ldots,x_m# are expressed in terms of the constants and the remaining unknowns #x_{m+1},\ldots,x_n# (which are begin used here as free parameters). The above matrix is called the identity matrix of dimension #m#, and is sometimes referred to as #I_m# or even #I# if the dimension is clear.

This goal cannot always be reached, that is: not every#(m\times m)#-matrix #A# satisfies \(A \rightsquigarrow B\).
A counterexample is #A=\matrix{1&1\\ 1&1}#.
But there is a more general method, the reduced echelon form, which always works. Later we come back to this.

In the case at hand, we assume that we have reached the following form by use of elementary operations:

\[ \matrix{1&0&0&\cdots&0&a_{1,m+1}&\cdots&a_{1,n}&b_1\\ 0&1&0&\cdots&0&a_{2,m+1}&\cdots&a_{2,n}&b_2\\ \vdots&\vdots&&\vdots&\vdots &\vdots&\vdots&\vdots&\vdots\\ 0&\cdots&\cdots&1&0&a_{m-1,m+1}&\cdots&a_{m-1,n}&b_{m-1} \\ 0&\cdots&\cdots&0&1&a_{m,m+1}&\cdots&a_{m,n}&b_m}\]

The solution of the corresponding system of linear equations then is

\[ \lineqs{x_1&=&b_1-a_{1,m+1}x_{m+1}-\cdots-a_{1,n}x_n\\ x_2&=&b_2-a_{2,m+1}x_{m+1}-\cdots-a_{2,n}x_n\\ \vdots\phantom{x} &=&\phantom{hoop geschrijf}\vdots\\ x_m&=&b_m-a_{m,m+1}x_{m+1}-\cdots-a_{m,n}x_n\\ }\]

In solving linear equations by Gaussian elimination we will discuss how the solution can be read off from the general reduced echelon form.

You are encouraged to consider some examples of systems with two or three unknowns for a taste of the elimination method by use of matrices.

Solve the following system of linear equations with unknowns \(x\) and \(y\) via row reduction of an augmented matrix. \[\lineqs{ x+4 y&=&4\cr 2 x+10 y&=&9 \cr}\]

\( x=2\quad\land\quad y={{1}\over{2}} \)

In order to see this, we begin with the original system of equations \[\lineqs{ x+4 y&=&4\cr 2 x+10 y&=&9 \cr}\] and write it down the corresponding augmented matrix. We will then perform elementary operations and continue the reduction process until we have a specific form that will be described in general in later theory, but that implies here that the coefficient matrix is the identity matrix \(\matrix{1&0\\ 0&1}\). Then the solution of the system of equations can be read off easily from the newly obtained augmented matrix. The matrix elements that have the desired value during the following reduction process are coloured green. We can work with different elementary operations in intermediate steps, but we will always arrive at the same result.
\[\begin{array}{rcll} \left(\begin{array}{rr|r}\color{green}{1} & 4 & 4 \\ 2 & 10 & 9 \end{array}\right) & \sim & \left(\begin{array}{rr|r} \color{green}{1} & 4 & 4 \\ \color{green}{0} & 2 & 1 \end{array}\right) &\blue{\begin{array}{l} \phantom{x} \\ R_{2}-2 R_{1}\end{array}}\\ \\ & \sim & \left(\begin{array}{rr|r} \color{green}{1} & \color{green}{0} & 2 \\ \color{green}{0} & 2 & 1 \end{array}\right) &\blue{\begin{array}{l} R_{1}-2 R_{2}\\ \phantom{x}\end{array}} \\ \\ & \sim & \left(\,\begin{array}{rr|r} \color{green}{1}& \color{green}{0} & 2 \\ \color{green}{0} & \color{green}{1} & {{1}\over{2}}\end{array}\,\right) &\blue{\begin{array}{r}\phantom{x}\\ \frac{1}{2}\!R_2\end{array}} \end{array}\] The solution of the system of equations is now easy to read off: \[x=2\quad\land\quad y={{1}\over{2}}\]

New example