Lecture 8: Solving Ax = b: row reduced form R

 

$A\mathbf{x} = \mathbf{b}$

 

$x_{1} + 2x_{2} + 2x_{3} + 2x_{4} = b_{1}$ 

$2x_{1} + 4x_{2} + 6x_{3} + 8x_{4} = b_{2}$ 

$3x_{1} + 6x_{2} + 8x_{3} + 10x_{4} = b_{3}$

 

Augmented matrix = $\begin{bmatrix} 
A &  \mathbf{b} 
\end{bmatrix}$

 

$\begin{bmatrix} 
1 & 2 & 2 & 2 & | & b_{1}\\  
2 & 4 & 6& 8  & | & b_{2}\\  
3 & 6 & 8 &10 & | & b_{3} 
\end{bmatrix}$

 

-> $\begin{bmatrix} 
1 & 2 & 2 & 2 & | & b_{1}\\  
0 & 0 & 2& 4  & | & b_{2} - 2b_{1}\\  
0 & 0 & 2 &4 & | & b_{3} - 3b_{1} 
\end{bmatrix}$

 

-> $\begin{bmatrix} 
1 & 2 & 2 & 2 & | & b_{1}\\  
0 & 0 & 2& 4  & | & b_{2} - 2b_{1}\\  
0 & 0 & 0 &0 & | & b_{3} - b_{2} - b_{1} 
\end{bmatrix} $

 

pivot columns는 1과 3 column입니다. 

 

$b_{3} - b_{2} - b_{1} = 0$

 

해가 존재하기 위해서는 위 식을 만족해야합니다. 

 

위와 같은 식을 가해 조건 (solvability condition)이라 합니다. 

 

$\mathbf{b} = \begin{bmatrix} 
1\\5  
\\6  
\end{bmatrix}$ 이면 가해 조건을 만족합니다. 

 

 

가해조건 (Solvability Condition)

 

$\mathbf{b}$가 C(A)에 존재할 때 $A\mathbf{x} = \mathbf{b}$의 해가 존재합니다.

 

행렬 A의 row의 선형결합이 zero row를 만든다면, b에 대한 같은 선형 결합도 반드시 0이 되어야합니다. 

 

 

$A\mathbf{x} = \mathbf{x}$ 완전해 구하기 

 

1. $\mathbf{x}_{particular}$ : free variables를 0으로 놓고, pivot variables에 대해 $A\mathbf{x} = \mathbf{b}$를 계산합니다. 

 

2. $\mathbf{x}_{nullspace}$

 

3. (1 + 2) $\mathbf{x} = \mathbf{x}_{p} + \mathbf{x}_{n}$

 

 

특수 해 (Particular Solution)

 

$\begin{bmatrix}  
1 & 2 & 2 & 2 & | & 1\\   
0 & 0 & 2& 4  & | & 3\\   
0 & 0 & 0 &0 & | & 0  
\end{bmatrix}$

 

free variable $x_{2}$, $x_{4}$를 0으로 놓습니다. 

 

$x_{1} + 2x_{3} = 1$ 
            $2x_{3} = 3$

 

후방대입법을 적용합니다. 

 

$x_{1} = -2$ 

$x_{3} = 3/2$

 

$\mathbf{x}_{p} = \begin{bmatrix} 
-2\\0  
\\3/2  
\\0 
\end{bmatrix}$

 

 

Null Space Solution

 

$\mathbf{x}_{n} = c_{1}\begin{bmatrix} 
-2\\1  
\\0  
\\0 
\end{bmatrix} + c_{2}\begin{bmatrix} 
2\\0  
\\-2  
\\1 
\end{bmatrix}$

 

 

완전 해 (Complete Solution)

 

완전 해는 특수 해와 영 공간의 해를 더해주면 됩니다.

 

$\mathbf{x} = \mathbf{x}_{p} + \mathbf{x}_{n}$

 

$A\mathbf{x}_{p} = \mathbf{b}$

 

$A\mathbf{x}_{n} = \mathbf{0} $

 

$A(\mathbf{x}_{p} + \mathbf{x}_{n}) = \mathbf{b} $

 

$\mathbf{x}_{complete} = \begin{bmatrix} 
-2\\0  
\\3/2  
\\0 
\end{bmatrix} + c_{1}\begin{bmatrix}  
-2\\1   
\\0   
\\0  
\end{bmatrix} + c_{2}\begin{bmatrix}  
2\\0   
\\-2   
\\1  
\end{bmatrix}$

 

특수 해는 상수가 곱해질 수 없습니다. 

 

$\mathbf{b}$가 특정 값으로 정해져 있기 때문입니다. 

 

 

랭크 (Rank)와 해의 관계

 

m by n 행렬 A는 rank r을 갖고 있습니다. ($r \leq m $, $r \leq n $)

 

Full column rank (r=n)

 

Rank와 column의 개수가 같고 모든 col이 pivot을 갖고 있습니다. 

 

따라서 free variables가 없습니다.

 

free variable이 없으므로 N(A)는 영벡터뿐입니다. 

 

$A\mathbf{x} = \mathbf{b}$의 해는 존재하지 않거나 또는 유일 해입니다. 

 

$A = \begin{bmatrix} 
1 & 3\\  
2 & 1\\  
6 & 1\\  
5 & 1 
\end{bmatrix}$

 

$R = \begin{bmatrix} 
1 & 0\\  
0 & 1\\  
0 & 0\\  
0 & 0 
\end{bmatrix}$

 

A를 R로 변환했습니다. 

 

$A\mathbf{x} = \mathbf{b}$의 해는 $\mathbf{x} = \mathbf{x}_{particular}$입니다. 

 

 

Full row rank (r=m)

 

$A\mathbf{x} = \mathbf{b}$는 모든 $\mathbf{b}$에 대해 해가 존재합니다. 

 

$A = \begin{bmatrix} 
1 & 2 &  6& 5\\  
3 & 1 & 1 & 1 
\end{bmatrix} $

 

$R = \begin{bmatrix} 
1 & 0 & \square  & \square\\  
0 & 1 & \square & \square 
\end{bmatrix} $

 

pivot, free variable이 2개씩 존재합니다. 

 

n - r (n - m) free variables

 

free variable이 2개 있기 때문에 항상 해가 존재하고 특수 해나 영 공간 해도 존재합니다.

 

 

Full row and column rank (r=m=n)

 

$A = \begin{bmatrix} 
1 & 2\\  
3 & 1 
\end{bmatrix}$

 

$R = \begin{bmatrix} 
1 & 0\\  
0 & 1 
\end{bmatrix}$

 

$R = I$

 

정방행렬이고 R은 단위 행렬과 같습니다. 

 

A는 역행렬을 가지고 유일해가 존재합니다. 

 

 

정리

 

1. r = m = n

 

$R = I$

 

$A\mathbf{x} = \mathbf{b}$에 대해 1 solution만 존재합니다. 

 

 

2. r = m < n

 

$R = \begin{bmatrix} 
I & F 
\end{bmatrix}$

 

무한대의 해가 존재합니다.

 

 

3. r = n < m

 

$R = \begin{bmatrix} 
I \\ 0 
\end{bmatrix}$

 

해가 아예 없거나 하나의 유일 해만 존재합니다.

 

 

4. r < m, r < n

 

$R = \begin{bmatrix} 
I & R 
\\ 0 & 0 
\end{bmatrix}$

 

해가 아예 없거나 무한대의 해가 존재합니다.