1 System of Linear Equations, Row Echelon Form

Go to the MLX, M, PDF, or HTML version of this file. Go back to fan’s MEconTools Package, Matlab Code Examples Repository (bookdown site), or Math for Econ with Matlab Repository (bookdown site).

See also: System of Linear Equations

See also: Solving for Two Equations and Two Unknowns

See also: System of Linear Equations, Row Echelon Form

1.1 Two Equations and Two Unknowns

This is a general system of equations with 2 equations and 2 unknowns

\[\left\lbrack \begin{array}{cc} a & b\\ d & e \end{array}\right\rbrack \cdot \left\lbrack \begin{array}{c} x_1 \\ x_2 \end{array}\right\rbrack =\left\lbrack \begin{array}{cc} a\cdot x_1 +b\cdot x_2 \\ d\cdot x_1 +e\cdot x_2 \end{array}\right\rbrack =\left\lbrack \begin{array}{c} o\\ p \end{array}\right\rbrack\]

this is the augmented matrix:

\[\left\lbrack \begin{array}{ccl} a & b & |o\\ d & e & |p \end{array}\right\rbrack\]

We want to solve for the unknown \(x_1\) and \(x_2\). In matlab, we just use the linsolve function, and in practice we do not solve these by hand. But how is linsolve solving this?

1.2 Elementary Row Operations

There are three things we can do to rows of the augmented matrix that do not change the solution to the linear system, they are called elementary row operations, and are very intuitive:

  1. Switch two rows in the matrix: we can move a row up or down, the system is still the same

  2. Replace an existing row by the sum of the row and a multiple of another row:

  3. Multiply all column values of a row by the same non-zero constant:

Using rule 3, we can multiple a row from an augmented matrix by \(Z\)

  • \(\displaystyle \left\lbrack \begin{array}{cccc} Za & Zb & Zc & |Zo \end{array}\right\rbrack\)

Using rule 2, we can add up \(Z\) times a row from an augmented matrix and \(Y\) times another row:

  • \(\displaystyle \left\lbrack \begin{array}{cccc} Za+Yd & Zb+Ye & Zc+Yf & |Zo+Yp \end{array}\right\rbrack\)

1.3 Row Echelon Form

After using elementary row operations to create as many zeros as possible in the lower left side of the matrix, we end up with a matrix that is equivalent to the original matrix that is in the Row Echelon Form, more formally:

  • Leading Zero: A row of a matrix is said to have, \(k\) leading zero, if the first \(k\) elements of the row are all zeros and the subsequent elements of the row are not zero. (SB P131)

  • Row Echelon Form: a matrix is in row echelon form if each row has more leading than row preceding (above) it. (SB P131)

  • Pivot: the first non-zero element in each row of a matrix that is in row echelon form is called a pivot

1.4 Row Echelon Form with 2 Equations and 2 Unknowns

Let’s study our system with just 2 equations and 2 unkowns. We can arrive at the row-echelon form in two steps:

Starting with: \(\left\lbrack \begin{array}{ccl} a & b & |o\\ d & e & |p \end{array}\right\rbrack\):

  1. Multiply second row by \(\frac{a}{d}\): \(\left\lbrack \begin{array}{ccl} a & b & |o\\ d\cdot (\frac{a}{d}) & e\cdot (\frac{a}{d}) & |p\cdot (\frac{a}{d}) \end{array}\right\rbrack\)

  2. Subtract the first row from the second row: \(\left\lbrack \begin{array}{ccl} a & b & |o\\ 0 & e\cdot (\frac{a}{d})-b & |p\cdot (\frac{a}{d})-o \end{array}\right\rbrack\)

We now have the row-echelon form, because we have as many zeros as possible in the lower left side

1.5 Reduced Row Echelon Form

We can simplify the matrix more and get to the reduced row echelon form.

  • A row echelon matrix in which each pivot is a \(1\) and in which each column containing a pivot contains no other non-zero entries a is said to be in reduced row echelon form. (SB P133)

When we are solving a system of \(N\) equations with \(N\) unknowns, the reduced row echelon form gives the solution for the unknowns. With 2 dimensions, the solution is the intersection of 2 lines, and with 3 dimension, the solution is the point intersection of 3 surfaces.

1.6 Reduced Row Echelon Form with 2 Equations and 2 Unknowns

Starting with the row echelon form: \(\left\lbrack \begin{array}{ccl} a & b & |o\\ 0 & e\cdot (\frac{a}{d})-b & |p\cdot (\frac{a}{d})-o \end{array}\right\rbrack\):

  1. Divide second row by \(\frac{ea-bd}{d}\): \(\left\lbrack \begin{array}{ccl} a & b & |o\\ 0 & 1 & |\left(\frac{pa-od}{d}\right)\cdot \left(\frac{d}{ea-db}\right) \end{array}\right\rbrack\), which simplifies to: \(\left\lbrack \begin{array}{ccl} a & b & |o\\ 0 & 1 & |\frac{pa-od}{ea-db} \end{array}\right\rbrack\)

  2. Subtract from first row \(b\) times second row : \(\left\lbrack \begin{array}{ccl} a & 0 & |o-b\cdot \frac{pa-od}{ea-db}\\ 0 & 1 & |\frac{pa-od}{ea-db} \end{array}\right\rbrack\)

  3. Divide the first row by \(a\): \(\left\lbrack \begin{array}{ccl} 1 & 0 & |\frac{o}{a}-\left(\frac{b}{a}\cdot \frac{pa-od}{ea-db}\right)\\ 0 & 1 & |\frac{pa-od}{ea-db} \end{array}\right\rbrack\)

Now we have the reduced row echelon form, which tells us that:

  • \(\displaystyle x_1 =\frac{o}{a}-\left(\frac{b}{a}\cdot \frac{pa-od}{ea-db}\right)\)

and

  • \(\displaystyle x_2 =\frac{pa-od}{ea-db}\)