for textmining

Surjection vs Injection

|

이번 글에서는 전사함수(全射函數;surjection)와 단사함수(單射函數;injection)를 선형대수학의 선형변환 관점에서 살펴보도록 하겠습니다. 이번 글 역시 고려대 박성빈 교수님 강의를 참고로 했습니다. 그러면 시작하겠습니다.

선형변환과 표준행렬

$V$와 $W$를 벡터공간이라고 하고, 벡터공간 $V$의 원소 $A$, $B$와 실수 $k$에 대하여 아래 두 가지 성질을 모두 만족할 때 $T$를 $V$에서 $W$로의 선형변환(linear transformation)이라고 합니다.

$T(A+B) = T(A) + T(B)$

$T(kA) = kT(A)$, 즉 $k=0$일 때 $T(0)=0$

여기서 모든 선형변환은 행렬 곱의 형태로 나타낼 수 있는데요, 임의의 선형변환 $T$가 $n$차원 벡터공간에서 $m$차원으로 사상(mapping)한다고 할 때 선형변환 $T$는 위 정의에 의해 아래와 같이 다시 쓸 수 있습니다.

위 식에서 행렬 $A$를 선형변환 $T$를 나타내는 표준행렬(standard matrix)이라 부르고, $T$는 $A$에 의해서 표현된 선형변환이라고 부릅니다.

$T$에 대응하는 표준행렬은 유일합니다. 증명해보겠습니다. 만약 표준행렬이 $A$, $B$ 이렇게 두 개 있다고 가정해 보겠습니다. 선형변환 T에 임의의 기본벡터 $e_i$를 넣으면 아래와 같은 식이 됩니다.

여기에서 $Ae_i$는 행렬 $A$의 $i$번째 열벡터와 같고, $Be_i$는 행렬 $B$의 $i$번째 열벡터입니다. 위 식이 성립한다는 건 행렬 $A$, $B$의 열이 서로 같다는 의미이기 때문에 $A$와 $B$는 동일한 행렬이라 말할 수 있습니다. 따라서 $T$에 대응하는 표준행렬은 유일합니다.

전사함수

수학에서 전사함수 또는 위로의 함수(onto)공역(codomain)치역(range)이 일치하는 함수입니다. $n$차원 벡터공간의 벡터 $x$를 $m$차원 벡터공간의 벡터 $b$로 사상하는 선형변환 $T$를 $Ax=b$라고 둡시다.

전사함수는 $b$에 대응하는 $x$가 적어도 하나 존재하는 경우를 말합니다. 이를 그림으로 설명하면 아래와 같습니다.

위 그림의 왼쪽은 전사함수가 아닌 경우를 말합니다. 정육면체가 $m$차원 공간이라고 상상해 봅시다. 선형변환 $T$는 정의역(domain)에 있는 원소들을 정육면체를 둘로 가르는 하늘색 평면에 옮기고 있는 모습을 확인할 수 있습니다. 여기에서 $m$차원 벡터 $b$가 정육면체 안에 있으나 하늘색 평면 바깥에 존재한다고 가정해봅시다. 이 경우 $b$에 대응하는 $x$는 존재하지 않는다는 사실 또한 알 수 있습니다. (공역>치역)

반대로 오른쪽 그림의 경우 어떤 $b$를 상정하더라도 그에 대응하는 $x$가 존재합니다. 이게 바로 전사함수입니다. (공역=치역)

단사함수

그럼 단사함수 또는 일대일(one-to-one) 함수를 살펴볼까요? 전사함수 설명 때와 동일하게, $n$차원 벡터공간의 벡터 $x$를 $m$차원 벡터공간의 벡터 $b$로 사상하는 선형변환 $T$를 $Ax=b$라고 둡시다.

단사함수란 $b$에 대응하는 $x$가 최대 한 개 존재하는 경우를 일컫습니다. 이를 그림으로 도시하면 아래와 같습니다.

위 그림의 왼쪽은 단사함수가 아닌 경우를 말합니다. $m$차원 벡터 $b$에 대응하는 $n$차원 벡터 $x$가 여러개이기 때문입니다. 반대로 오른쪽 그림의 경우 $b$에 대응하는 $x$는 단 하나 존재합니다. 이 경우 단사함수라고 부릅니다.

전단사와 선형 연립방정식 (1)

4차원 벡터공간에서 3차원 공간으로 사상하는 선형변환 $T$에 대응하는 표준행렬 $A$는 다음과 같다고 둡시다.

우선 $T$가 전사함수인지를 살펴보겠습니다. 정의역(4차원) 벡터를 $x$, 공역(3차원) 벡터를 $b$라고 두면 $T$는 아래와 같이 쓸 수 있습니다.

$T$가 전사함수인가 아닌가라는 질문은 임의의 $b$에 대해 해가 적어도 하나 존재하는가라는 질문과 동일합니다. 이 문제를 풀기 위해 선형 연립방정식 관련 네 가지 명제를 소개합니다. 이들은 하나가 참이면 모두 참이고, 하나가 거짓이면 모두 거짓인 동치(equivalent) 관계입니다. 자세한 내용은 이곳을 참고하시기 바랍니다.

(1) $Ax=b$가 해를 갖는다.

(2) $b$는 계수행렬 $A$의 열벡터 간 선형결합으로 표시된다.

(3) 계수행렬 $A$의 열벡터는 $m$차원 벡터공간을 생성(span)한다.

(4) $A$는 모든 행에 pivot positon을 하나 가진다.

표준행렬 $A$는 가우스행렬(echelon form) 형태입니다. $A$의 행 개수는 3개인데, pivot position(선도 원소가 영이 아닌 행) 또한 3개(요소값 기준 : 1,2,5)이므로 위 네 가지 동치명제에 의해 해가 존재함을 알 수 있습니다. 따라서 $T$는 전사함수입니다.

$T$가 단사함수인지 가려볼까요? A의 세번째 열($[8,-1,0]^T$)은 추축열(pivot column;pivot position에 대응하는 열)이 아니군요. $A$를 선형 연립방정식의 계수행렬로 상정해 본다면 이 열에 대응하는 $x_3$은 어떤 값을 가지든 상관없는 자유변수(free variable)입니다. 바꿔 말하면 $b$에 대응하는 $x$가 유일하지 않다는 이야기입니다. 따라서 $T$는 단사함수가 아닙니다.

전단사와 선형 연립방정식 (2)

$n$차원 벡터를 $m$차원 벡터로 사상하는 임의의 선형변환 $T$에 관해 세 가지 정리를 하고 넘어가겠습니다.

(a) 표준행렬 $A$의 열벡터가 $m$차원 벡터공간을 생성(span)할 때 $T$는 전사함수이다.

(b) $T(x)$가 단사함수이면 $T(x)=0$은 자명해($x=0$)를 유일해로 갖는다. 그 역도 성립한다.

(c) 표준행렬 $A$의 열벡터가 서로 선형독립일 때 $T$는 단사함수이다. 그 역도 성립한다.

우선 (a)를 살펴보겠습니다. $T$를 $Ax=b$ 꼴로 둘 때 $b$는 $A$의 열벡터와 $x$의 선형결합인데요. $A$의 열벡터가 생성하는 벡터집합이 $m$차원 벡터공간을 모두 채우고 있다면(=$A$의 열벡터가 $m$차원 공간을 생성) $x$가 어떤 값을 갖더라도 $Ax=b$가 성립합니다. 다시 말해 임의의 $b$에 대응하는 $x$가 적어도 하나 존재합니다.

(b)와 관련해 $T$는 선형성(linearity) 조건을 만족하기 때문에 $T(0)=0$입니다. $T(x)$가 단사함수라면 $Ax=b$ 형식에서 단 하나의 해만 존재해야 합니다. 따라서 $T(x)$가 단사함수라면 $T(x)=0$은 자명해($x=0$)를 유일한 해로 갖습니다.

한편 $T$가 단사함수가 아니어서 임의의 $b$에 대응하는 $x$가 서로 다른 벡터 $u$, $v$가 존재한다고 가정해 봅시다. 즉, $T(u)=b, T(v)=b$가 성립한다는 이야기입니다. $T$는 선형성 조건을 만족하므로 $T(u-v)=T(u)-T(v)=b-b=0$입니다. 그런데 $u-v≠0$이므로 $T(x)=0$은 하나 이상의 비자명해를 갖습니다. 이 말은 $T(x)=0$이 자명해를 유일해로 갖는다면 $T(x)$가 단사함수이라는 명제와 동치입니다.

이번엔 (c)를 보겠습니다. $A$의 열벡터가 선형독립이라는 얘기는 $T$를 $Ax=b$ 꼴의 연립방정식으로 생각할 때 해가 영벡터뿐이라는 얘기와 같습니다. 따라서 (c)는 명제 (b)에 의해 참입니다.

이제 예를 들어보겠습니다. 선형변환 $T$가 아래와 같습니다.

우선 단사함수 여부를 가려보겠습니다. 표준행렬 $A$의 열벡터는 임의의 스칼라곱을 해서 비교해도 같아지지 않으므로 서로 선형독립임을 알 수 있습니다. (c)에 의해 $T$는 단사함수입니다.

하지만 $A$의 행 개수는 세 개 인데 열 개수는 두 개뿐이므로 모든 행에 pivot position이 있는 건 아닙니다. 전챕터 (1)~(4) 정리에 의해 $A$의 열벡터는 3차원 공간을 생성할 수 없습니다. $T$는 전사함수가 아닙니다.

이 문제를 가우스소거법에 의한 연립방정식($Ax=b$) 풀이로도 접근해서 풀어보겠습니다. 확대행렬(augmented matrix)로 나타내 기본행 연산을 한 결과는 아래와 같습니다.

$b_1-b_2+2b_3=0$이면 해가 있지만, 0이 아니면 해가 존재하지 않습니다. 따라서 전사함수가 아닙니다. $T$를 그림으로 나타내면 아래와 같습니다.

위 그림을 보시면 $T$에 의해 2차원 평면이 3차원으로 사상(mapping)되는 걸 확인할 수 있습니다. 변환 후 3차원 공간 전체를 채우지 못하는 것 또한 볼 수 있는데요, 여기서도 역시 우리는 이 변환이 전사함수가 아님을 알 수 있습니다. 다만 이렇게 그림으로 이해할 수 있는 건 3차원까지이고요, 그보다 높은 차원의 선형변환 $T$가 전사, 단사임을 확인하려면 지금까지 말씀드렸던 정리와 절차에 대해 확인하는 과정을 거쳐야 합니다.

마치며

지금까지 전사함수와 단사함수를 선형대수학의 선형변환 관점에서 살펴보았습니다. 임의의 선형변환이 전사이면서 단사함수이려면 사상 전후의 차원이 같아야 합니다(2차원=>2차원, 3차원=>3차원).

그런데 사상 후 차원이 커질 경우 단사함수 조건을 만족하지만 전사함수이진 않습니다. 바꿔 말해 일대일 대응 성질은 만족하지만 치역이 공역보다 작다는 이야기입니다.

반대로 차원을 줄일 경우 전사함수이지만 단사함수는 아닙니다. 공역을 빠짐없이 채우게 돼 치역과 일치하지만, 그에 대응하는 정의역 벡터 $x$가 여러 개가 될 수 있기 때문입니다.

이를 상식적으로 이해해보면 큰 공간을 작은 공간으로 줄일 때 빽빽해지고, 작은 공간을 큰 공간으로 늘릴 때 듬성듬성해진다고 이해하셔도 좋을 것 같다는 생각입니다.

선형변환은 선형 연립방정식의 해를 찾는 과정과 본질적으로 다르지 않기 때문에 선형대수학이라는 학문이 하나의 체계를 이루는 것 같다는 느낌도 듭니다. 질문이나 의견 있으시면 이메일이나 댓글로 알려주시면 감사하겠습니다. 여기까지 읽어주셔서 진심으로 감사드립니다.

Comments