[K-MOOC]  Introductory Mathematics for Artificial Intelligence

                Translated by

  Sang-Gu LEE with Youngju NIELSEN, Yoonmee HAM

         from the original Korean text written by

      Sang-Gu LEE with Jae Hwa LEE, Yoonmee HAM, Kyung-Eun PARK

    Part Ⅱ. AI and Matrix

4.  Solution Sets for System of Linear Equations

Linear algebra is known as a subject that can be used to solve most of our problems. Alan Tucker even said,

"Linear algebra is the model that mathematical theory pursues." A method to find the solution set of a given system of linear equations will be explained.

  4.1 System of linear equations

  4.2 Augmented matrices

  4.3 Gaussian elimination

  4.4 Solution Sets for System of Linear Equations

4.1 System of linear equations

Linear equations are the first-order equations. An equation is an example of a linear equation of two variables and .

The solutions of this linear equation have the ordered pairs that satisfy . These equations are defined for lines in the coordinate system.

A system of linear equations (or a linear system) is a collection of one or more linear equations involving the same set of variables.

One example of a system of linear equations involving variables , is as follows.

The solution of this system of linear equations is the value of x and y that satisfies the two linear equations at the same time.

Since one linear equation with two variables and represents a straight line in the coordinate plane, the above system of linear equations

means two straight lines. Thus, the solution becomes an ordered pair (or vector) that means the intersection of the two straight lines.

There are three types of systems of linear equations in two variables and three types of solutions. A given linear system belongs to

‘one and only one case of the following 3 cases’: 

   (1) A Unique solution

   (2) Infinitely many solutions

   (3) No solution

■ The following figures show ‘all three types of systems of linear equations with two variables’.

(1)         (2)        (3)

We can easily check that (1) has a ‘Unique solution’ (2) has ‘infinitely many solutions’ (3) and has ‘No solution’ as we see in the figures.

Furthermore, the above properties are also held for any system of linear equations with variables. In general, any system of linear equations

either has a unique solution, or infinitely many solutions, or no solution.

     Case of no solutions [Source]  Author’s Linear Algebra Bigbook

4.2 Augmented matrices

Any system of linear equations can be expressed in the form of matrices.

     (1)              

It is possible to express the above linear equations with variables (1) using vectors as follows:

     (2)              

This vector form of (1) can be written using a matrix product as follows:

     (3)              

Letting 

               , ,

the above equations (1)-(3) can be written as

The matrix is called the coefficient matrix of the given system of linear equations . In linear algebra, an augmented matrix is

a matrix obtained by appending the columns of two given matrices, Given the matrices and where the augmented matrix of (1)

is written as

                .

  Find the augmented matrix of the following linear system of equations.

  An invertible matrix is a square matrix defined as invertible if the product of the matrix and its inverse is the identity matrix.

If there exists an matrix such that where denotes the identity matrix, an matrix is called invertible.

If this is the case, then the matrix is uniquely determined by and is called the (multiplicative) inverse of . It is denoted by .

* If a square matrix is invertible, the linear system of equations has the unique solution .

 Find a solution to the following system of linear equations , using . (See the following codes)

This means the solution of is ,, and .           ■

☞ Note  But most of the coefficient matrix in a given system of linear equations has no inverse matrix, so we need to know

a general method to find a solution set for .

◩ Open Problem 12

Find a system of linear equations from other textbooks. Find a solution to that by using the code that you learned.

[Hint: http://matrix.skku.ac.kr/2018-album/LA-Sec-3-5-lab.html ]

4.3 Gauss-Jordan elimination

Let's take a look at Gaussian elimination (Gauss-Jordan elimination). Gaussian elimination is an algorithm for solving systems of linear equations.

When we solve a system of linear equations using Gaussian elimination, the final form (of the augmented matrix) on the left side of the equation

becomes the identity matrix.

We use three operations of the Gaussian elimination in the above example. These three operations are called ‘Elementary Row Operations.’

  Type (1) Exchange two equations.

  Type (2) Multiply an equation by a non-zero real number.

  Type (3) Add a non-zero multiple of an equation to another equation.

In the above example, the first type of elementary row operation was not used. However, (1) the exchange  of two equations is often used

to apply the elimination method to a system of linear equations, especially when there are many variables and equations.

The idea of Elementary Row Operations for a system of linear equations can be used the same for an augmented matrix as well.

Let's define Elementary Row Operations for a matrix.

 The following operations do not change the solution set.

  (1) Exchange two equations.                               

  (2) Multiply a row by a nonzero real number.               

  (3) Add a nonzero multiple of a row to another row.     

These are called the 1st, 2nd and 3rd type Elementary Row Operations (ERO).

After using ERO, you can obtain the solution easily from the simplified form as below.

The right-hand side matrix is in Reduced Row Echelon Form (RREF). The RREF of a given matrix can be obtained using the following command.

Gaussian elimination is the process of simplifying the augmented matrix as shown above to find the RREF of

by changing(simplifying or replacing) the coefficient matrix to RREF(), diagonal matrix, or identity matrix.

  Find a solution to the given system of linear equations using Gaussian elimination (by hand). And compare the solution

with the solution that you find using the following code. (A case of the unique solution)

(1)    [After the elimination: ]

It means that ,,.                                   ■

We can do the same job with the following Sage built-in command.

 It means we could find the same solution ,, using the code A.solve_right(b).       ■

(2)

4.4 Solution Set for System of Linear Equations

Find the solution to the system of linear equations given below.  (Case of infinitely many solutions)

It means

          and   

Let , where , can be any real numbers. Then we have

This can be written as a vector form:

All these are solutions for any real numbers and . So the system has infinitely many solutions.                                       ■

In Example 4, the variables , after changing in RREF are called ‘free variables’. The remaining variables can be specified

 with those free variables. Once the values of and are specified, for example, and , then the values of and are also decided.

The solution obtained from the specified values of and is called ‘a particular solution’.

[Details in http://matrix.skku.ac.kr/K-MOOC-LA/cla-week-4.html.]

How to get the whole set of solutions:

1) Find a particular solution of using the code 'solve_right.'

2) Find the general solution set of , say

3) The whole set of solutions for is the solution set + .

Find the solution set of the following system. (No solution case)

                   (즉,  )

It means that . From the RREF of the augmented matrix RREF( [ : ] ), we have 0*z=1 in the fourth equation.

It is contradictory. So we can conclude that this system has no solution.  ■

If we use code 'solve_right' instead of 'RREF', we will have the answer  “ValueError: ... has no solutions” for the system with no solution.

Find the RREF of an augmented matrix of .                                                 REF  (or RREF)   (1) If , has no solution.   (2) If , ( is # of leading variables, is # of unknowns)       ① If , then has a unique solution.       ② If , then has infinitely many solutions.

We have studied the notion of a system of linear equations and how to find the solution set. Solving a system of linear equations is an essential tool

to have an appropriate model for artificial intelligence. In many cases of a linear system of equations, they do not have solutions.

In the next section III-5, we will see how to find an optimal solution(least squares solution) when a linear system does not have any solution.

◩ Open Problem 13

Explain how and what we can determine for a given linear system of equations with a unique solution or infinitely many solutions,

or no solutions. Use an RREF of to do this. Explain to others what you understand.

 Reference Solution Sets http://matrix.skku.ac.kr/K-MOOC-LA/cla-week-4.html

Copyright @ 2021 SKKU Matrix Lab. All rights reserved.
Made by Manager: Prof. Sang-Gu Lee and Dr. Jae Hwa Lee