Spaces of Vectors

Vector Space

유클리드 공간, 벡터 공간, 힐버트 공간 같은 집합적인 개념이다.

벡터공간은 그 원소간의 덧셈과 스칼라곱셈이 가능한 공간이다.

즉 Linear Combination 연산이 가능하고, 그것으로 이루어진 집합을 의미한다.

또한 벡터 공간은 늘 영벡터를 포함해야한다.

정의는 다음과 같다.

벡터 공간 내에 존재하는 임의의 벡터 v와 w는 그 둘을 더해도 (v+w) 그 결과가 반드시 같은 벡터 공간에 존재해야 한다.
벡터 공간 내에 존재하는 임의의 벡터 v에 임의의 상수 c를 곱해도 (cv) 그 결과가 반드시 같은 벡터 공간에 존재해야 한다.
벡터 공간 내에 존재하는 임의의 벡터 v,w와 임의의 상수 c,d에 대해 모든 경우의 cv+dw 조합(각 벡터에 임의의 상수를 곱한 뒤 더하는, 즉 선형 결합(Linear Combination)결과가 반드시 같은 벡터 공간에 존재해야 한다.)

Vector Space를 이루는 단위를 component라고 한다. \(R^3\)공간의 x,y,z축을 component라고 한다.

Subspace

벡터간의 덧셈에 대해 닫혀있는 공간.
그리고 벡터의 스칼라 곱셈에 대해 닫혀있는 공간을 의미한다.

즉, Linear Combination에 대해 닫혀있는 공간을 의미한다.

\(R^3\)공간을 기준으로 3차원 공간 그 자체, 원점을 지나는 직선, 원점을 지나는 평면, 원점 그자체.

이런 것이 Subspace가 된다.

서로 다른 P,L 의 subspace가 있을 때,
P와 L의 합집합은 subspace가 아니다.
P와 L의 교집합은 subspace이다.

Subspaces of Matrix

임의의 행렬 A에서, 모든 column들의 선형 결합(Linear Combination)은 부분 공간(subspace)을 형성한다.
이를 column space라 부르고 C(A)로 쓴다.

Column Space and Null Space

Column Space

행렬 A의 column이 정의하는 부분공간. column으로 span하는 공간.

새로운 차원을 만드는데 기여하는 Independent한 column들은 pivot column이라고 한다.

Null Space

선형 방정식 Ax=b에서 b가 zero vector(=Null vector)일 때, 이 식을 만족시키는 모든 가능한 해 x에 대한 집합이다. 즉 Ax=0의 해(Solutions)들이 이루는 공간, Null Space를 의미한다.

어떤 Null space든지 반드시 0벡터는 포함된다.

영벡터가 포함되지 않으면 벡터 공간을 정의할 수가 없다.

Null space의 임의의 해 v에 대한 상수배 cv는 Null space에 포함된다.

Null space의 임의의 해 v,w에 대한 덧셈 v+w는 Null space에 포함된다.

즉 Null space는 언제나 영벡터를 포함하는 subspace이다.

여기서 Ax=b 에 대해 임의의 b에 대해서도 solution에 대한 벡터공간이 존재할까?

당연히 아니다. 원점을 지나지 않는 해의 집합이 있을수 있기 때문이다.

Solving Ax=0

The Special Solution of Ax=0

먼저 dependent한 row를 제거하기 위해 소거를 한다. 소거를 하면 dependent한 column의 pivot은 사라진다.
그리고 남은 pivot의 갯수가 Rank와 일치한다

소거과정은 Null space를 변화시키지 않는다. 그러나 Column space는 변한다.

즉 Ax=0과 Ux=0의 해는 같은 Null space를 이룬다.

그럼 소거 후의 Ux=0에서 해는 어떻게 찾아낼까?
pivot이 존재하지 않는 column을 free column이라고 하고, pivot이 존재하는 column을 pivot column이라고 한다.
free column에 대응되는 미지수 변수를 free variable이라고 하고, free variable에는 우리가 원하는 임의의 값을 자유롭게 설정할 수 있다.

여기서 간단하게 한 free variable을 1로 두고 나머지 free variable을 0으로 두는 식으로 해들을 구할 수 있다.
이를 빠짐없이 넣고 back-substitution으로 pivot variable을 구하면 모든 Null space를 구성하기에 충분한 solution 벡터들을 구할 수 있게 된다.
이렇게 임의의 free variable을 설정하여 구한 solution을 special solution이라고 한다.

이 special solution들의 Linear combination을 통해 전체 Null space를 정의할 수 있다.
Null space를 정의할 때 special solution 벡터의 임의의 상수를 놓으면 되는데, 이 때 임의의 상수를 해당 special solution을 얻기 위해 1로 만든 free variable로 두기도 한다.

special solution은 그럼 얼마나 존재하는 걸까?
special solution은 각 free variable마다 존재한다.

free variable은 그럼 얼마나 존재하는 걸까?
free variable은 column의 수 - rank만큼 존재한다.

Reduced Row Echelon Form

REF를 더 간소화한 형태를 RREF라고 한다.

REF의 결과를 주로 U로 표기한다.
RREF의 결과는 주로 R로 표기한다.

Ax=0, Ux=0, Rx=0의 Null space는 모두 같다.

Rx=0에 대해서도 같은 방식으로 special solution을 구할 수 있다.

Solving Ax=b

Solvability Condition of Ax=b

Ax=b는 해가 존재할 수도 있고, 존재하지 않을 수도 있다.
(Ax=0은 항상 해가 존재한다. 영벡터를 무조건 포함하기 때문.)

Ax=b 해의 존재 여부는 소거법을 통하여 판별할 수 있다.
만약 해가 존재한다면 그 해를 알아내는 것도 가능하다.

해의 존재 조건이 제한되어 있다면, 먼저 좌변의 선형 결합이 0이 되는 linearly dependent한 row를 찾고, 해당 row의 우변에서도 동일한 선형 결합으로 0이 되어야 해가 존재한다.
이는 Augmented matrix를 만든 뒤 REF꼴로 만들어 좌변이 0인 row를 찾아 우변에서 해의 존재 조건을 구할 수 있다.

이렇게 구해진 해의 존재 조건을 가해 조건(Solvability Condition)이라고 한다.

정리하자면 다음과 같다.

b에 대한 가해조건(Solvability condition on b):

우변의 b벡터가 행렬 A이 column space안에 존재할 때, 선형바정식 Ax=b는 해가 존재한다.

다시 표현하자면,

행렬 A의 row의 어떤 선형 결합이 zero row를 만들어낸다면(dependent하다면), b에 대한 똑같은 선형 결합도 반드시 0이 되어야한다.

The Complete Solution of Ax=b

해를 구하는 알고리즘은 다음과 같다.

\(X_{particular}\): 특수해(particular solution) x를 찾는다. 모든 free variable을 0으로 설정한 뒤, pivot variable에 대해 Ax=b를 푼다.
\(X_{nullspace}\): Null space해(null space solution)를 찾은 뒤 특수해와 더해준다. 즉 \(x=x_p+x_n\)이다.

Particular Solution

REF로 만든 행렬 U에서 free variable을 모두 0으로 만든 다음 pivot variable에 대해서 구한 해를 의미한다.

Null Space Solution

Ax=0으로 두고, 여기서 special solution들을 구한 뒤, 이를 선형 결합하여 null space를 정의한다.

Complete Solution

Particular Solution에 Null Space Solution을 더하면 된다.

\[x=x_p+x_n\]

이것이 정말 가능할까? 아래 식을 보면 납득할 수 있다.
\(Ax_p=b\)
\(Ax_n=0\)
이 둘을 더하면,
\(A(x_p+x_n)=b\)

\(x_{complete}=x_{particular}+x_{nullspace}\)
\(x_{nullspace}=c_1x_{special1}+c_2x_{special2}+\cdots\)

결론적으로 Ax=b의 완전해는 particular solution과 Null space해인 subspace의 합으로 표현될 수 있다.

완전해는 Null space에서 shift된 형태이므로 원점을 지나지 않게 되고, 이는 더이상 subspace가 아니게 된다.

Rank

rank를 r,
row의 갯수를 m,
column의 갯수를 n 이라고 하자.

rank는 solution과 어떤 상관관계를 가지는가? 어떤 정보를 말해주는가?

Full column rank (r=n)

모든 column이 pivot을 가지므로 free variable이 없다.
즉 Null space에는 오직 영벡터만이 포함된다.

즉, Ax=0에 대해선 영벡터만을 유일한 해(unique solution)로 가지게 된다.
그러나 Ax=b에 대해선 해가 존재하지 않을 수 있다. 하지만 해가 존재한다면 유일한 해를 가진다.

Full row rank (r=m)

모든 row가 pivot을 가지므로 어떤 b에대해 항상 해를 가진다.
free variable은 n-r개 가진다.

즉, Ax=0에 대해서 Null space를 가진다.
Ax=b에 대해서도 늘 해가 존재한다.

pivot의 수는 rank인데, 솔루션이 존재하는 공간은 row 갯수의 차원이고, 여기서 rank차원만큼의 공간을 생성하기 때문에 rank가 b의 차원과 동일하면, 모든 b에 대해 항상 해를 가지는 것이다.
row의 갯수가 null space가 정의되는 차원 \(R^m\)과 관계있다는 것을 기억하자.
r = m 이면 \(R^m\)을 구성하는 basis를 가지는 것이고,
r < m 이면 공간 전체를 채우지 못하므로 특정 b에 대해서만 해를 가진다.

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

Square Matrix인 경우이다.
모든 column이 pivot을 가지므로 free variable이 없다.
그리고 모든 row가 pivot을 가지므로 b에 대해 항상 해를 가진다.

즉, Ax=0에 대해서 영벡터만을 해로 가진다.
Ax=b에 대해서도 늘 하나의 유일한 해를 가지게 된다.

r<m, r<n

이 경우는 해가 아예 없거나, 무수히 많은 해가 존재한다.

Ax=0는 항상 무수히 많은 해를 갖게 된다.
Ax=b는 조건에 따라 해가 없거나, 무수히 많은 해를 가진다.

Rank는 결국 해에 대해 모든 것을 말해준다.

Linear Independence, Span, Basis, Dimension

Linear Independence

어떤 column이 다른 column들의 linear combination으로 표현될 수 있으면, 이는 independence하지 않다.

벡터가 독립(independence)이라는 것은 다음과 같다.

벡터 x1, x2, …, xn에 대해, 모든 계수(coefficient)가 0인 경우를 제외하고 어떠한 Linear Combination으로도 0을 만들 수 없다면 이 벡터들은 Independent하다.

여기서 다음과 같은 성질을 밝힐 수 있다.
어떤 행렬 A의 크기가 m by n일 때, m < n이면 반드시 free variable을 갖게 되고, 이는 Null space를 존재하게 한다. 즉 Linearly Independent하지 않다

어떤 행렬 A의 column vector가 선형 독립(Linear independence)이기 위해선 A에 대한 Null space가 영벡터만을 포함해야 한다.
어떤 행렬 A에 대해 Ax=0식에 대한 Null space가 영벡터를 제외한 다른 경우가 존재한다면 A의 column vector는 종속이다.

즉 free varialbe이 없어야 하고, rank가 column의 수와 같아야 한다.

Span

벡터들의 가능한 모든 Linear Combination으로 공간을 형성하는 것.
결과는 항상 subspace가 된다.
모든 공간을 채울 수도 있다.

Basis

어떤 벡터를 통해 어떤 공간을 span할 수 있으면서도, 서로 독립이면 이 벡터를 Basis라고 한다.

Basis의 속성은 다음과 같다.

Basis들은 독립이다.
Basis들은 공간을 span한다.

또한 Basis들은 span하는 공간의 유일한 Basis가 아니다.

Basis를 통해 만들어진 행렬은 invertible하다.

주어진 벡터가 Basis가 될 수 있는지를 판단하기 위해선 행렬로 만든 뒤 소거를 실시하여 Full column rank를 갖는지 확인하면 된다. free variable이 있으면 안된다.

Dimension

Basis는 유일하지 않지만 차원은 유일하다.

차원은 그 공간을 이루는 Basis의 갯수와 같다.

주어진 공간(space)들에 대한 모든 기저(basis)는 같은 수의 벡터를 가지고, 그 벡터의 수가 그 공간의 차원을 의미한다.

\(R^3\)공간에서 두개의 기저 벡터가 어떠한 평면을 이룰 때, 이 평면은 3차원 공간이 아니라, 2개의 basis를 가지므로 2차원 공간이라고 할 수 있다.

Column space C(A)가 이루는 차원은 Rank와 같다.

Null space의 경우 free variable과 같은 수의 차원을 이룬다. 즉, n-r 차원이다.

Dimensions of the Four Fundamental Subspaces

Four Fundamental subspaces

Column space and Null space

Column space는 C(A)로 표기하며, column vector들의 Linear Combination을 통해 형성되는 공간이다.
Null space역시 Ax=0을 만족시키는 해(x)들의 LC로 형성되는 공간이다.

Row space

Row vector들은 row space를 span한다.
만약 행렬 A의 row vector들이 독립이면, row space의 기저가 된다.
이는 Transpose로 표현한다.

Row space = All combinations of columns of \(A^T\)
= \(C(A^T)\)

Left null space

Left null space = null space of \(A^T\)
=\(N(A^T)\)

Left null space라고 불리는 이유는 xA=0 형태일 때 x의 null space를 의미하기 때문이다.
하지만 이는 \(A^{T}x=0\)의 null space와 같으며, 이렇게 표기하는 것이 통일성이 있다.

Examples of 4 fundamental subspaces

A가 m x n의 크기라고 하면, 각 공간들은 몇 개의 component를 가진 전체공간에서 정의될까? 이는 각 subspace의 dimension과는 다르다.

Column space : \(C(A)\) in \(R^m\)
Null space : \(N(A)\) in \(R^n\)
Row space : \(C(A^T)\) in \(R^n\)
Left null space : \(N(A^T)\) in \(R^m\)

이는 잘 생각해보면 당연한 것들이다.
Column vector의 component수는 m과 같다. 그래서 Column space는 \(R^m\)에 속하는 것이다.
Null space는 Ax=0 해의 집합이므로 x의 component 수와 같다.

즉 Column space와 Left null space는 같은 Vector space 내에서 정의되고,
Row space와 Null space는 같은 Vector space 내에서 정의된다.

그러나 Column space의 dimension \(C(A)=r\)와 Left null space의 \(N(A^T)=m-r\)는 다르고,
Row space의 dimension \(C(A^T)=r\)와 Null space의 \(N(A)=n-r\)은 다르다.

Orthogonal subspaces

이 그림을 이해하면 LA의 절반을 이해한 것이라고 표현할 정도로 중요하다고 한다.

먼저 Row space와 Null space를 살펴보자.
\(Ax=0\)

\[\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ \end{bmatrix}\]

이 행렬 A를 예로 들면, row space와 null space는 \(R^3\)에서 정의된다.
row vector는 \(C(A^T)=2\)로 2차원 공간을 정의한다.
여기서 이 row vector와 직교하여 3차원 공간을 형성할 수 있도록 하는 것이 null space이다.
실제로 x의 solution은 영벡터를 포함하고, 각 row vector와의 dot product결과가 0이 된다.
즉, x의 solution은 row vector들과 orthogonal하다는 것이다.
(내적이 0이면 orthogonal, 영벡터는 모든 벡터와 orthogonal)
row space는 row vector들의 linear combination이므로, 결국 row space의 모든 벡터와 solution의 dot product는 0이 될 수 밖에 없다.
그러므로 row space와 null space는 orthogonal하다.

row space의 차원은 pivot variable의 개수인 rank가 되고,
null space의 차원은 free variable의 개수인 n-r이 된다.

column space와 left null space의 경우는 \(A^T\)를 통해 마찬가지로 이해할 수 있다.
\(A^Tx=0\)

\[\begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ \end{bmatrix}\]

Basis and Dimension of 4 fundamental subspaces

Column space and Null space

####C(A): Column space basis: pivot columns dimension: r

####N(A): Null space basis: special solutions dimension: n-r

Row space

Row space의 basis는 pivot rows와 같다.
차원은 r이다.

원시 행렬 A와 이의 RREF인 R의 column space는 다르지만,
row space는 같다.
A의 row들의 LC로 R의 row들을 만들어 낼 수 있고(실제로 그렇게 만들어내고), 그 반대도 가능하기 때문이다.

Left null space

이는 행렬 A의 row vector들에 대한 null space이다. 즉 \(A^Tx=0\)의 special solution이 Left null space의 basis이다.
차원은 m-r이다.

A를 transpose하지 않고 row space에 대한 solution을 찾는 법은 다음과 같다.

증강 행렬을 이용해,
rref[A I] -> [R E]
를 하여 E를 찾아내고, 이 E를 A의 좌측에 곱하여,
EA=R를 만든다.

EA=R에서,
꼴에서 R의 영벡터인 row에 해당하는 E의 row가 left null space를 이루는 벡터가 된다.
이 때 row vector들의 조합으로 다른 row vector를 만들 수 있다는 뜻이기 때문이다.
R이 영벡터인 row가 없다면? left null space는 영벡터만을 포함한다는 뜻이다.