How to Solve The System of Linear Equations

Equivalence of the system of linear equations

Definition 1. Two systems of linear equations are called equivalent if they have the same solution set.

Theroem 1

Theorem 1. Let $Ax = b$ be a system of $m$ linear equations in $n$ unknowns, and let $C$ be an invertible $m \times m$ matrix. Then the system $(CA)x = Cb$ is equivalent to $Ax = b$.

Proof. Denote $K$ and $K_C$ the solution set to $Ax = b$ and $(CA)x = Cb$, respectively.
$\forall s \in K, As = b \Longrightarrow (CA)s = Cb \Longrightarrow s \in K_C$.
$\forall l \in K_C, CAl = Cb \Longrightarrow C^{-1}CAl = Al = b = C^{-1}Cb \Longrightarrow l \in K$. Thus $K = K_C.$ $\blacksquare$

Corollary

Corollary. Let $Ax = b$ be a system of linear equations. If $(A' \,|\, b')$ is obtained from $(A \,|\, b)$ by a finite number of elementary row operation, then the system $A'x = b'$ is equivalent to the original system.

Proof. Denote that $(A' \,|\, b') = R_p \cdots R_1(A \,|\, b) = R_p(I) \cdots R_1(I) (A \,|\, b) = C (A \,|\, b)$, where $C := R_p(I) \cdots R_1(I)$. Then $A' = CA$ and $b' = Cb$. By Theorem 1, $A'x = b$ is equivalent to $Ax = b$. $\blacksquare$

    이 따름정리는 주어진 선형연립방정식을 RREF로 바꾸어도 해집합은 같다는, 즉 equivalent하다는 것을 보장해준다. 주어진 방정식을 RREF로 바꾸면 해를 쉽게 구할 수 있다.

Example

$$2x_1 + 3x_2 + x_3 + 4x_4 - 9x_5 = 17 \\ x_1 + x_2 + x_3 + x_4 -3x_5 = 6 \\ x_1 + x_2 + x_3 + 2x_4 -5x_5 = 8 \\ 2x_1 + 2x_2 + 2x_3 + 3x_4 - 8x_5 = 14$$

다음과 같이 연립방정식이 주어졌다고 하자. 가우스 소거법을 적용하여 RREF로 변환하면 다음과 같다.

$$(A \,|\, b) = \left( \begin{array}{ccccc|c} 2&3&1&4&-9&17 \\ 1&1&1&1&-3&6 \\ 1&1&1&2&-5&8 \\ 2&2&2&3&-8&14 \end{array} \right) \sim \left( \begin{array}{ccccc|c} 1&0&2&0&-2&3 \\ 0&1&-1&0&1&1 \\ 0&0&0&1&-2&2 \\ 0&0&0&0&0&0 \end{array} \right) = (A' \,|\, b')$$

이때 rank($A'$) = rank($A' \,|\, b'$)이므로 주어진 방정식은 해가 존재한다. 변환한 방정식을 새로 쓰면 다음과 같다.

$$x_1 + 2x_3 - 2x_5 = 3 \\ x_2 - x_3 + x_5 = 1 \\ x_4 - 2x_5 = 2$$ 각 줄의 가장 왼쪽에 있는 변수들을 제외한 나머지, 즉 $x_3, x_5$에 매개변수 $t_1, t_2$를 부여하고 정리하면 다음과 같다.

$$x_1 = -2t_1 + 2t_2 + 3 \\ x_2 = t_1 - t_2 + 1 \\ x_4 = 2t_2 + 2$$ 따라서 방정식의 일반해는 다음과 같이 얻어진다. $$\begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{pmatrix} = \begin{pmatrix} -2t_1 + 2t_2 + 3 \\ t_1 - t_2 + 1 \\ t_1 \\ 2t_2 + 2 \\ t_2 \end{pmatrix} = \begin{pmatrix} 3 \\ 1 \\ 0 \\2 \\0 \end{pmatrix} + t_1 \begin{pmatrix} -2 \\ 1 \\ 1 \\ 0 \\ 0 \end{pmatrix} + t_2 \begin{pmatrix} 2 \\ -1 \\ 0 \\ 2 \\1 \end{pmatrix},$$ where $t_1, t_2 \in \mathbb{R}$.

How to solve the system of linear equations

지금까지의 과정을 요약하면 다음과 같다.

1. Applying Gaussian elimination to the augmented matrix of the system to obtain RREF.
2. Determine whether the system is consistent.
3. If it does, then discard any zero rows from RREF and write the corresponding system.
4. Divide the variables into two sets: 1) The leftmost variables, 2) The remaining variables
5. Assign parametric values $t_1, t_2, ...$ to each variables in 2) set.
6. Solve for the variables of the 1) set in terms of the 2) set.
7. Then the solution $s$ to the system is of the form $$s = s_0 + t_1u_1 + \cdots + t_{n-r}u_{n-r},$$ where $r$ is the number of nonzero rows in RREF.

이렇게 얻은 해 $s$를 주어진 연립방정식의 일반해라고 부른다. 위와 같은 과정을 통해서 주어진 선형연립방정식이 해가 존재한다면 항상 구할 수 있다. 

한편, 시스템의 해집합이 어떻게 생겨먹었는지를 기억한다면 위에서 구한 일반해 $s$의 형태는 자명하다. 이때 각 $u_1, ..., u_{n-r}$은 대응하는 homogeneous system의 해집합의 기저가 된다는 것을 다음의 정리가 보여준다.

Theorem 2

Theorem 2. Let $Ax = b$ be a system of $r$ nonzero equations in $n$ unknowns. Suppose that rank($A$) = rank($A \,|\, b$) and that $(A \,|\, b)$ is in RREF. Then the followings hold:
(a) rank($A$) = $r$,
(b) If the general solution obtained by the procedure above is of the form $s = s_0 + t_1u_1 + \cdots + t_{n-r}u_{n-r},$ then $\{u_1, ..., u_{n-r}\}$ is a basis for the solution set of $Ax = \mathbf{0}$, and $s_0$ is a solution to $Ax = b$.

Proof. (a) By the definition of RREF, it is clear.
(b) Let $K$ and $K_H$ be the solution set of $Ax = b$ and $Ax = \mathbf{0}$, respectively.
If we set $t_1 = \cdots = t_{n-r} = 0$, then $s = s_0 \in K$. Note that $K = \{s_0\} + K_H$ by Theorem 1. Thus we have $K_H = \{-s_0\} + K$. Since $-s_0 + s = t_1u_1 + \cdots + t_{n-r}u_{n-r}$ and we can choose any value of t_i arbitrarily, $K_H = <\{u_1, ..., u_{n-r}\}>$. 
Note that dim($K_H$) = $n - r$ by the dimension theorem. Thus $\{u_1, ..., u_{n-r}\}$ is a basis for $K_H$ by the replacement theorem.