2. Linear Equation and Linear System

1. 키워드

Linear Equation(선형방정식): 최고 차수의 항의 차수가 1을 넘지 않는 다항 방정식
Linear System(선형시스템): 동일한 변수를 포함하는 하나 이상의 선형방정식의 모음
Identity Matrix(단위 행렬): 대각선 항목이 모두 1이고 다른 모든 항목이 0인 정방 행렬
Inverse Matrix(역행렬): 어떤 행렬과 곱했을 때 곱셈에 대한 단위 행렬이 나오게 하는 행렬

2. Linear Equation

A linear equation in the variables $x_{1}, \dots, x_{n}$ is an equation that can be written in the form $a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n} = b$ , where $b$ and the coefficients $a_{1}, \dots, a_{n}$ are real or complex numbers that are usually known in advance.

The above equation can be written as $a^{T} x = b$ where $a = [\begin{matrix} a_{1} \\ a_{2} \\ ⋮ \\ a_{n} \end{matrix}]$ and $X = [\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}]$ .

3. Linear System: Set of Equations

A System of linear equations (or a linear system) is a collection of one or more linear equations involving the same variables - say, $x_{1}, \dots, x_{n}$ .

4. Linear System Example

Suppose we collected persons' weight, height, and life-span (e.g., how long s/he lived)

Person ID	Weight	Height	Is_smoking	Life-span
1	60kg	5.5ft	Yes (=1)	66
2	65kg	5.0ft	No (=0)	74
3	55kg	6.0ft	Yes (=1)	78

We want to set up the following linear system:

\begin{aligned} 60 x_{1} + 5.5 x_{2} + 1 \cdot x_{3} = 66 \\ 65 x_{1} + 5.0 x_{2} + 0 \cdot x_{3} = 74 \\ 55 x_{1} + 6.0 x_{2} + 1 \cdot x_{3} = 78 \end{aligned}

Once we solve for $x_{1}$ , $x_{2}$ , and $x_{3}$ , given a new person with his/her weight, height, and is_smoking, we can predict his/her life-span.

The essential information of a linear system can be written compactly using a matrix.

In the following set of equations:

\begin{aligned} 60 x_{1} + 5.5 x_{2} + 1 \cdot x_{3} = 66 \\ 65 x_{1} + 5.0 x_{2} + 0 \cdot x_{3} = 74 \\ 55 x_{1} + 6.0 x_{2} + 1 \cdot x_{3} = 78 \end{aligned}

Let’s collect all the coefficients on the left and form a matrix:

A = [\begin{array}{lll} 60 & 5.5 & 1 \\ 65 & 5.0 & 0 \\ 55 & 6.0 & 1 \end{array}]

Also, let’s form two vectors:

x = [\begin{array}{lll} x_{1} \\ x_{2} \\ x_{3} \end{array}], b = [\begin{array}{l} 66 \\ 74 \\ 78 \end{array}]

5. From Multiple Equations to Single Matrix Equation

Multiple equations can be converted into a single matrix equations:

\begin{aligned} 60 x_{1} + 5.5 x_{2} + 1 \cdot x_{3} = 66 \\ 65 x_{1} + 5.0 x_{2} + 0 \cdot x_{3} = 74 \\ 55 x_{1} + 6.0 x_{2} + 1 \cdot x_{3} = 78 \end{aligned} → [\begin{array}{lll} 60 & 5.5 & 1 \\ 65 & 5.0 & 0 \\ 55 & 6.0 & 1 \end{array}] [\begin{array}{l} x_{1} \\ x_{2} \\ x_{3} \end{array}] = [\begin{array}{l} 66 \\ 74 \\ 78 \end{array}] ← \begin{aligned} a_{1}^{T} x = 66 \\ a_{2}^{T} x = 74 \\ a_{2}^{T} x = 78 \end{aligned}

How can we solve for $x$ ?

6. Identity Matrix

Definition: An identity matrix is a square matrix whose diagonal entries are all 1's, and all the other entries are zeros. Often, we denote it as $I_{n} \in R^{n \times n}$ .

Example

I_{3} = [\begin{array}{lll} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}]

An identity matrix $I_{n}$ preserves any vector $x \in R^{n}$ after multiplying $x$ by $I_{n}$ :

\forall x \in R^{n}, I_{n} x = x

7. Inverse Matrix

Definition: For a square matrix $A \in R^{n \times n}$ , its inverse matrix $A^{- 1}$ is defined such that $A^{- 1} A = A A^{- 1} = I_{n}$ .

For a $2 \times 2$ matrix $A = [\begin{array}{ll} a & b \\ c & d \end{array}]$ , its inverse matrix $A^{- 1}$ is defined as $A^{- 1} = \frac{1}{a d - b c} [\begin{array}{cc} d & - b \\ - c & a \end{array}]$ .

8. Solving Linear System via Inverse Matrix

We can now solve $A x = b$ as follows:

\begin{matrix} A x = b \\ A^{- 1} A x = A^{- 1} b \\ I_{n} x = A^{- 1} b \\ x = A^{- 1} b \end{matrix}

Example

[\begin{array}{lll} 60 & 5.5 & 1 \\ 65 & 5.0 & 0 \\ 55 & 6.0 & 1 \end{array}] [\begin{array}{l} x_{1} \\ x_{2} \\ x_{3} \end{array}] = [\begin{array}{l} 66 \\ 74 \\ 78 \end{array}] → A^{- 1} = [\begin{array}{ccc} 0.0870 & 0.0087 & - 0.0870 \\ - 1.1304 & 0.0870 & 1.1314 \\ 2.0000 & - 1.0000 & - 1.0000 \end{array}]

One can verify $A^{- 1} A = A A^{- 1} = I_{n}$ .

$x = A^{- 1} b = [\begin{array}{ccc} 0.0870 & 0.0087 & - 0.0870 \\ - 1.1304 & 0.0870 & 1.1314 \\ 2.0000 & - 1.0000 & - 1.0000 \end{array}] [\begin{array}{l} 66 \\ 74 \\ 78 \end{array}] = [\begin{matrix} - 0.4 \\ 20 \\ - 20 \end{matrix}]$

Now, the life-span can be written as $(life-span) = - 0.4 \times (weight) + 20 \times (height) - 20 \times (is\_smoking)$ .

9. Non-Invertible Matrix $A$ for $A x = b$

Note that if $A$ is invertible, the solution is uniquely obtained as $x = A^{- 1} b$ .

What if $A$ is non-invertible, i.e., the inverse does not exist?

E.g., For $A = [\begin{array}{ll} 1 & 2 \\ 2 & 4 \end{array}]$ , in $A^{- 1} = \frac{1}{a d - b c} [\begin{array}{cc} d & - b \\ - c & a \end{array}]$ , the denominator $a d - b c = 0$ , so $A$ is not invertible.

For $A = [\begin{array}{ll} a & b \\ c & d \end{array}]$ , $a d - b c$ is called the determinant of $A$ , or $\det A$ .

10. Does a Matrix Have an Inverse Matrix?

$\det A$ determines whether $A$ is invertible (when $\det A \neq 0$ ) or not (when $\det A = 0$ ).

11. Non-Invertible Matrix $A$ for $A x = b$

Back to the linear system, if $A$ is non-invertible, $A x = b$ will have either no solution or infinitely many solutions.

12. Rectangular Matrix $A$ in $A x = b$

What if $A$ is a rectangular matrix, e.g., $A \in R^{m \times n}$ , where $m \neq n$ ?

$[\begin{array}{lll} 60 & 5.5 & 1 \\ 65 & 5.0 & 0 \\ 55 & 6.0 & 1 \end{array}] [\begin{array}{l} x_{1} \\ x_{2} \\ x_{3} \end{array}] = [\begin{array}{l} 66 \\ 74 \\ 78 \end{array}]$

Recall $m =$ #equations and $n =$ #variables.

$m < n$ : more variables than equations

Usually infinitely many solutions exist (under-determined system).

$m > n$ : more equations than variables

Usually no solution exists (over-determined system).

2. Linear Equation and Linear System

1. 키워드