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
지금까지의 과정을 요약하면 다음과 같다.
- Applying Gaussian elimination to the augmented matrix of the system to obtain RREF.
- Determine whether the system is consistent.
- If it does, then discard any zero rows from RREF and write the corresponding system.
- Divide the variables into two sets: 1) The leftmost variables, 2) The remaining variables
- Assign parametric values $t_1, t_2, ...$ to each variables in 2) set.
- Solve for the variables of the 1) set in terms of the 2) set.
- 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.
