연립 일차 방정식

미지수의 최고차항이 1을 넘지 않는 다항방정식이다.

$\mathbb R^2$에서 직선의 일차방정식은 $ax+by=c, \mathbb R^3$에서 평면의 이차 방정식은 $ax+by+cz=d$ 이다.
$n$개의 미지수 $x_1, x_2,\cdots,x_n$에 대해
일차 방정식(linear equation) : $a_1x_1+a_2x_2+\cdots+a_nx_n=b$ 
계수 : $a_1, a_2,\cdots,a_n$
상수항 : $b$



일차방정식의 예

$\displaystyle 3x-4y=-1\\ r-\frac{1}{2}s-\frac{15}{3}t=9 \\ x_1-5x_2=3-x_3+2x_4 \\ \sqrt2x+\frac{\pi}{4}y-(\sin\frac{\pi}{5})z = 1 \\ 3.2x_1 - 0.01x_2=4.6$

즉, $a_1x_1+a_2x_2+\cdots+a_nx_n=b$의 형태로 나타낼 수 있어야 한다.



일차방정식이 아닌것들

$\displaystyle xy+2z=1 \\ x_1^2-x_2^3=3 \\ \frac{x}{y}+z=2 \\ \sqrt{2x}+\frac{\pi}{4}y-\sin(\frac{\pi}{5}z)=1 \\ \sin x_1-3x_2+2^{x_3}=0$ 

일차방정식 $a_1x_1+a_2x_2+\cdots+a_nx_n=b$의 해(solution)는 벡터 $\displaystyle \left[S_1,S_2,\cdots S_n\right]$인데, 이 성분은 $x_1=s_1, x_2=s_2,\cdots, x_n=s_n$을 대입할때 방정식을 만족해야한다.

즉, $\displaystyle \left[a_1,a_2,\cdots a_n\right] \begin{bmatrix}S_1\\S_2\\\vdots\\S_n \end{bmatrix}=b$이 성립해야한다.

 

 

실수 계수의 연립 일차 방정식은 다음 세가지 경우중 하나이다.

a) 유일한 해를 지닌다.

b) 무수히 많은 해를 가진다 (부정)

c)해가 없다 (불능)

■

 

 

연립 일차 방정식의 해법

두 연립 일차 방정식이 같은 해집합을 지닐때 동치(equivalent)라고 한다.

ex)$\displaystyle x-y=1\\x+y=3$과 $\displaystyle x-y=1\\y=1$ 은 동치이다.

같은 유일한 해 $[2,1]$을 가지기 때문이다.

연립방정식의 풀이방법은 이 동치를 이용하는것이다.

(행연산을 하더라도 이전과 이후의 식은 서로 동치이다.)

 

 

$\displaystyle \begin{align*} x-y-z=2& \\ y+3z=5& \\ 5z=10&\end{align*}$

정답 : z=3, y=-1, x=3 

후진대입법으로 쉽게 풀 수 있다.

.

 

 

연립일차 방정식의 직접 풀이법

행렬과 사다리꼴

계수행렬(coefficient matrix) : 미지수의 계수들로 이루어진 행렬

$$\begin{align*} 2&x&+&y&-z=3 \\ &x&&&+5z=1\\-&x&+3&y&-2z=0\end{align*} \rightarrow \begin{bmatrix}2&1&-1\\1&0&5\\-1&3&-2\end{bmatrix}$$

 

연립일차방정식의 계수행렬을 A로, 상수항의 열벡터를 b로 두면 첨가 계수 행렬(augmented coefficient matrix)의 형태는 [A|b]이다.

 

 

행 사다리꼴(row echelon form)

ex)

$$\begin{bmatrix} 2&4&1 \\0&-1&2\\0&0&0 \end{bmatrix}, 
\begin{bmatrix}1&0&1 \\0&1&5 \\0&0&4 \end{bmatrix}, 
\begin{bmatrix} 1&1&2&1 \\ 0&0&1&3\\0&0&0&0 \end{bmatrix}, 
\begin{bmatrix}0&2&0&1&-1&3\\0&0&-1&1&2&2 \\0&0&0&0&4&0 \\0&0&0&0&0&5 \end{bmatrix}$$

위와 같은 형태를 가진 연립 방정식의 해는 후진대입법으로 쉽게 구할 수 있다

 

기본 행변환(elementary row equation)

주어진 행렬을 행사다리꼴로 변형시키는 과정을 지칭한다.

연립일차방정식을 동치인 연립일차방정식으로 변형시키는 과정에 대응하는 연산이다.

행렬에 실행하는 다음의 연산을 기본 행변환이라 한다.
1. 두 행을 교환한다.($R_i\leftrightarrow R_j$ : $i$행과 $j$행을 교환한다.)
2. 한 행에 0이 아닌 상수배 한다.($kR_i$ : $i$행에 $k$배 한다.)
3. 한 행을 상수배하여 다른 행에 더한다.($R_i+kR_j$ : $j$행을 $k$배 하여 $i$행에 더한다.)

한 행렬을 행 사다리꼴로 변형시키기 위해 기본 행변환을 적용하는 과정을 행줄임(row reduction)이라 한다.

 

 

 

 

두 행렬 $A$와 $B$에 대하여, $A$를 $B$로 바꾸는 일련의 기본 행변환이 있으면, $A$와 $B$는 행동치(row equivalent)라 한다.

두 행렬 $A$와 $B$가 행동치일 필요충분조건은 두 행렬을 같은 행사다리꼴로 행줄임 할 수 있는 것이다.
즉, 행사다리꼴 형태의 행렬은 유일하지 않다.

증명

만약 $A$와 $B$가 행동치라면, 행변환으로 같은  행사다리꼴로 고칠 수 있다. 즉, $A$와 $B$를 같은 행사다리꼴 $R$로 행줄임 할 수 있다면, $R$을 $A$와 $B$로 각각 변환이 가능하다. 그러므로 $A \rightarrow R \rightarrow B$ 로 하는 일련의 행변환으로 $A$와 $B$는 행동치임을 알 수 있다.

 

 

가우스 소거법(Gauss Elimination)

연립일차방정식의 첨가 계수행렬에 행줄임을 적용하여 후진대입법으로 풀 수 있는 동치인 연립일차방정식을 만들 수 있으며 이러한 과정을 가우스 소거법이라 한다.

가우스 소거법을 하는법
1. 연립일차방정식의 첨가 계수행렬을 적는다.
2. 첨가 계수행렬을 행사다리꼴로 바꾸기 위하여 기본 행변환을 시행한다.
3. 후진대입법을 이용하여, 행사다리꼴 행렬에 대응되는 동치인 연립일차방정식을 푼다.

 

 

 

계수(rank)
행렬의 행사다리꼴에서 적어도 한 성분이 0이 아닌 행의 수를 그 행렬의 계수(rank)라 한다.
한 행렬 $A$의 계수를 $rank(A)$로 나타낸다.

계수 정리
$A$를 $n$개의 미지수를 갖는 연립일차방정식의 계수행렬이라 하면 이 연립일차 방정식이 해를 가질경우 자유변수의 수는 $n-rank(A)$이다.

첨가계수행렬을 행사다리꼴로 바꾸었을때 $i$번째 행의 원소가 모두 $0$이라면 $C_i$는 임의의 수가 될 수 있기 때문에 자유변수의 갯수는 $n-rank(A)$이다.

 

행사다리꼴로 바뀐 첨가계수행렬에서 특정 행의 원소가 모두 0이라는 것은 해당 미지수는 어떠한 값도 될 수 있음을 의미한다. 즉, 해가 부정이다. 그러므로 자유 변수의 수는 미지수의 갯수에 계수를 뺀 $n-rank(A)$는 자유변수의 갯수가 되는것은 직관적이다.

 

첨가계수행렬 $\left[\begin{matrix}0&2&3\\2&3&1\\1&-1&-2\end{matrix}\right|
\left.\begin{matrix}8\\5\\-5\end{matrix}\right]$을 행사다리꼴로 바꾸면 $\left[\begin{matrix}1&-1&-2\\0&1&1\\0&0&1\end{matrix}\right|
\left.\begin{matrix}-5\\3\\2\end{matrix}\right]$ 이 된다. 행렬의 계수는 $rank(A)=3$ 이고 미지수의 갯수는 $3$개 이므로 $3-3=0$ 으로 자유변수의 갯수는 $0$이다.

 

첨가계수행렬 $  \left[\begin{matrix}1&-1&-1&2\\2&-2&-1&3\\-1&1&-1&0\end{matrix}\right|
\left.\begin{matrix}1\\3\\-3\end{matrix}\right]$을 행사다리꼴로 바꾸면 $  \left[\begin{matrix}1&-1&-1&2 \\ 0&0&1&-1 \\ 0&0&0&0\end{matrix}\right|
\left.\begin{matrix}1\\1\\0\end{matrix}\right]$ 이 된다. 행렬의 계수는 $rank(A)=2$ 이고 미지수의 갯수는 $4$개이므로 $4-2=2$으로 자유변수의 갯수는 $2$ 이다.

 

 

 

 

■

 

기약 행 사다리꼴(reduced row echelon form)

다음의 성질을 만족하는 행렬을 기약 행 사다리꼴(reduced row echelon form) 행렬이라 한다. 1)행 사다리꼴 이다. 2)적어도 한 성분이 0이 아닌 행의 선행 성분은 1이다. 3)선행 성분 1을 포함하는 열에서 선행성분을 제외한 모든 성분은 0이다.

 

기약행사다리꼴의 예

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

 

2x2 행렬에 대해서는

$\displaystyle \begin{bmatrix}1&0\\0&1 \end{bmatrix},\begin{bmatrix}1&*\\0&0 \end{bmatrix},\begin{bmatrix}0&1\\0&0 \end{bmatrix},\begin{bmatrix}0&0\\0&0 \end{bmatrix}$

 

기약 행 사다리꼴에서는 단위벡터인 열들의 일차결합으로 나머지 비단위벡터들을 표현할 수 있다. 즉, 열벡터들 사이에 일차종속 관계를 이룬다. 그렇기 때문에 기약행사다리꼴을 행변환해서 나온 행렬 또한 본래의 행렬에서의 열벡터들 간의 종속관계가 유지된다.

 

가우스-조르당 소거법

개선된 가우스 소거법으로 연립일차방정식을 수기로 풀때 편리하다.

가우스-조르당 소거법 방법

1. 연립일차방정식의 첨가 계수행렬을 구한다.
2. 기본 행변환을 이용하여 첨가 계수행렬을 기약 행사다리꼴로 고친다.
3. 선행변수들에 대한 결과의 연립방정식이 해를 가지는 경우, 자유변수들에 대응하는 매개변수에 관하여 해를 나타낸다.

 

 

■

 

동차 연립일차방정식

모든 연립일차방정식의 해는 유일하거나 부정이거나 불능이다

동차 연립일차방정식은 항상 적어도 하나의 해를 가지는 연립일차방정식이 있다.

각 방정식의 상수항이 모두 0인 연립 일차 방정식을 동차(homogeneous) 라고 한다. 즉, 첨가계수행렬이 $[A|0]$ 의 형태를 지닌다. ex) $$\begin{matrix}2x+3y-z=0 \\ -x+5y+2z=0 \end{matrix}$$ 동차 연립 일차 방정식은 0 이라는 자명하면서도 유일한 해를 가진다.   $$\left[\begin{matrix}2&3&-1\\-1&5&2 \end{matrix} \right| \left.\begin{matrix}0\\0 \end{matrix} \right]$$ 첨가 계수 행렬을 확인하면 어떤 행 연산을 하더라도 상수항은 항상 0 이 되므로 0이 유일한 해임을 알 수 있다.

 

만약 $[A|0]$이 $n$개의 미지수를 가지고 $m$개의 일차 방정식으로 이루어진 동차 연립일차 방정식의 첨가 계수 행렬이고 $m<n$이면, 이 연립 일차 방정식은 무수히 많은 해를 가진다. 증명 동차연립방정식 이므로, 자명해를 가지고 $rank(A) \leq m$ 이다. 그래서 계수정리에 의해 $자유 변수의 수 = n - rank(A) \geq n-m > 0$ 이다. ($\because rank(A) \leq m$) -> 자유 변수의 수 > 0 따라서 적어도 하나의 자유변수가 존재하므로 무수히 많은 해를 가진다.

■

 

$\mathbb Z_p$ 위의 연립 일차 방정식

지금까지의 해는 $\mathbb R^n$으로 나타낼 수 있었다.

p가 소수일때 $\mathbb Z_p$는 실수와 유사하다.($\div, \times, +, -$가 가능)

그러므로 미지수와 계수가 $\mathbb Z_p$인 수 일때의 연립 일차 방정식을 풀 수 있다.
이런경우를 $\mathbb Z_p$ 위의 연립 일차 방정식 이라 한다.

 

 

생성원 집합과 일차 독립

벡터의 생성원 집합

한 벡터가 다른 벡터의 일차 결합인지 판별 할 수 있다.

 

첨가 계수 행렬 $[A|b]$인 연립 일차 방정식이
해를 가질 필요 충분 조건은 $b$가 $A$의 열들의 일차결합이다.

행렬 $A$를 열벡터들을 각 열마다 나열한 형태라 하면

$$A=\left[\begin{matrix} \uparrow & \uparrow  & & \uparrow \\
v_1 & v_2 & \cdots & v_m\\
\downarrow & \downarrow  & & \downarrow
\end{matrix}\right|
\left.\begin{matrix}\uparrow \\ 0 \\ \downarrow\end{matrix} \right]$$

의 형태가 되며 연립일차방정식의 각 해가 열벡터 $v$의 계수가 되는것을 확인 할 수 있다.

 

예와 함께 확인해보면 직관적으로 이해된다.

$$\begin{cases}
x-y=1\\x+y=3
\end{cases}$$

위와 같은 연립일차방정식이 주어질때 해는 $x=2, y=1$이다.

그러므로

$$2\begin{bmatrix}1\\1 \end{bmatrix} + \begin{bmatrix}-1\\1 \end{bmatrix} = \begin{bmatrix}1\\3 \end{bmatrix}$$

이다.

 

$S=\{V_1,V_2,\cdots,V_k\}$를 $\mathbb R^n$의 벡터들의 집합이라 하자. 이때, $V_1,V_2,\cdots,V_k$ 의 모든 일차결합들의 집합을 $V_1,V_2,\cdots,V_k$의 생성(Span) 이라 하고, $span(S)$ 또는 $span(v_1, v_2, \cdots, v_k)$ 으로 나타낸다. 만약 $span(S)=\mathbb R^n$이면, $S$를 $\mathbb R^n$에 대한 생성원 집합(spanning set)이라 한다.

 

■

 

일차독립(linear independent)

일차 독립(linear independent)) : 일차 결합으로 다른 벡터를 표현 할 수 없는 벡터집합

일차 종속(linear dependent) : 일차 결합으로 다른 벡터를 표현 할 수 있는 벡터집합

 

$$3 \begin{bmatrix}1\\0\\3 \end{bmatrix}+2 \begin{bmatrix}-1 \\1\\-3 \end{bmatrix}=\begin{bmatrix}1\\2\\3\end{bmatrix} 
\rightarrow3\overrightarrow u+2\overrightarrow v=\overrightarrow w$$

벡터 $\overrightarrow w$는 $\overrightarrow u$ 와 $\overrightarrow v$의 일차결합 이므로 $\overrightarrow u$와 $\overrightarrow v$에 종속된다.

벡터 $V_1,V_2,\cdots,V_n$ 에 대하여 만약 $C_1V_1+C_2V_2+\cdots+C_nV_n=0$ 이 성립하는 적어도 0이 아닌 스칼라 $C_1,C_2,\cdots,C_k$가 존재할때 이 집합을 일차종속(linear dependent)라 한다. 벡터들의 집합이 일차종속이 아닐때 즉, 자명해를 가질때 일차독립(linear independent)라 한다.   $C_1,C_2, \cdots, C_k$중 적어도 하나는 0이 아니어야 한다는것은 그 중 일부는 0이 될 수 있다는 것이다. $3u+2v=w$의 경우 $3u+2v-w=0$이므로 $u,v,w$ 는 일차종속이다. 즉, 일차종속인 벡터끼리는 벡터 하나를 나머지 벡터들의 일차결합으로 표현 가능하다.   $0V_1+0V_2+\cdots+0V_n=0$ 이므로 일차종속은 필수적으로 영벡터를 $V_1 ~ V_k$의 자명하지 않는 일차결합으로 표현할 수 있다. 즉, 일차독립은 영벡터를 $V_1~V_k$의 일차결합으로 나타내는 방법이 모든 계수 $C$가 $0$인 자명한 경우 뿐임을 의미한다.

 

$\mathbb R^n$의 벡터의 집합은 일차종속이다. $0, V_2, \cdots,V_m$이 $\mathbb R^n$의 벡터이면, $C_1=1$이고 $C_2=C_3=\cdots=C_m=0$ 이라 두어 $C_10+C_2V_2+\cdots+C_mV_m=0$인 자명하지 않은 일차결합을 구할수 있기 때문이다.

 

 

$V_1, V_2,\cdots,V_m$을 $\mathbb R^n$의 벡터라 하고 $A$가 이 벡터를 열로 가지는 $n \times m$ 행렬 $[V_1, V_2,\cdots,V_m]$이라 하자. $V_1, V_2,\cdots,V_m$이 일차종속일 필요충분 조건은 첨가 계수 행렬이 $[A|0]$인 동차 연립 일차 방정식이 자명하지 않은 해를 가진다.

증명

$\mathbb v_1,\mathbb v_2,\cdots, \mathbb v_m$ 이 일차종속일 필요충분 조건은 $c_1 \mathbb v_1 + c_2\mathbb v_2 + \cdots + c_m \mathbb v_m=0$ 이 되는 자명해 $c$가 존재하는것이다. 이는 영벡터가 아닌 벡터 $\begin{bmatrix}c_1 \\ c_2 \\ \vdots \\c_m \end{bmatrix}$ 이 첨가계수행렬을 $\begin{bmatrix} \mathbb v_1 & \mathbb v_2 & \cdots & \mathbb v_m & | & 0  \end{bmatrix}$로 가지는 동차 연립일차방정식의 해라는 의미와 동치이다.

 

 

$V_1, V_2,\cdots,V_m$ 을 $\mathbb R^n$의 (행)벡터라 하고 A가 이 벡터들을 행으로 가지는 $m \times n$ 행렬 $\displaystyle \begin{bmatrix} \leftarrow &V_1& \rightarrow \\\leftarrow & V_2 & \rightarrow\\ & \vdots & \\\leftarrow & V_m & \rightarrow \end{bmatrix}$ 라 하자. 그러면 $V_1, V_2,\cdots,V_m$ 이 일차종속일 필요충분 조건은 $rank(A)<m$ 이다. (즉, $rank(A)=m$ 이면 일차종속이 아니게 된다.)
$rank(A)=m$ 일 경우 $m$은 행렬 $A$를 이루는 차원수 즉, 열의 수가 된다.
$\displaystyle A= \begin{bmatrix} \uparrow & \uparrow & & \uparrow\\ V_1 & V_2 & \cdots & V_n \\ \downarrow & \downarrow & & \downarrow \end{bmatrix}$
$V_k \in \mathbb R^m$
$A$는 $m$행 $n$열의 행렬이 된다.

$rank(A) \leq m$ 이므로
$rank(A) < m$ (일차종속)
$rank(A) = m$ (일차독립)
이 2개 이외의 조건은 존재하지 않는다.

증명

$V_1,V_2,\cdots,V_m$이 일차종속이기 위해선 $C_1V_1+C_2V_2+\cdots+C_mV_m=0$ 을 만족하는 상수 $C_i$ 가 존재해야 한다. 즉, $C_1V_1+C_2V_2+\cdots=-C_mV_m$ 처럼 벡터 하나를 나머지 벡터의 일차결합으로 표현 가능해야한다. 이는 기본 행 변환을 통해서 임의의 행에 있는 벡터 하나의 모든 원소를 0으로 만들 수 있다는 뜻이며 그렇기 때문에 $rank(A)<m$ 이면 일차종속이 만족되는 것이다.

 

기본 행 변환을 통해 임의의 행에 있는 벡터를 하나라도 0으로 만들 수 없는 경우는 벡터 하나를 나머지 벡터의 일차결합으로 표현 할 수 없음을 상징하므로 $rank(A)=m$ 인경우이며 이는 일차독립이다.

 

 

 

행렬 $A$가 $v_1,v_2,\cdots,v_m$의 차원수가 $n$인 $m$개의 열벡터로 이루어진 $$A=\begin{bmatrix}\uparrow & \uparrow & & \uparrow \\ v_1 & v_2 & \cdots & v_m\\ \downarrow & \downarrow & & \downarrow \end{bmatrix}$$ 과 같은 $n \times m$의 행렬 일때, $m > n$ 이면, $m$ 개의 $\mathbb R^n$의 벡터는 일차종속이다.