[Optimization] Linear subspace, Affine subspace

 

최적화에서 가장 처음에 배우는 내용은 geometry의 정의이다.

 

정의를 보면 그렇구나, 싶지만 나중에 헷갈리게 되어서 정리를 한다. 이해를 위해서는 예시를 많이 알아두는 게 좋다.

Definition / Dimension / Bases / Independence / Examples 등에 대해 적는다.

 

1. Linear subspace

 

1-1. Definition

$L \subset R^{n} $ is a linear subspace iff it possesses the following three properties:

 - $L \neq \emptyset$

-[closedness with respect to additions] Whenever $x, y \in L$, we have $x + y \in L$

-[closedness w.r.t multiplications by reals] Whenever $x \in L$ and $\lambda \in R$, we have $\lambda x \in L$

 

공집합이 아니면서 덧셈과 곱셈에 대하여 close 되어있는 space

 

1-2. linear span (linear combination)

linear span $Lin(X)$은 내가 가지고 있는 set $X$에 대해서 Linear combination을 구해서 이것을 set으로 구성한 것이다.

$Lin(X)=\{x:x = \sum_i \lambda_i x_i\}$

linear span으로 만든 set이기 때문에 Linear subspace 성질을 만족해서 linear subspace라고 할 수 있다.

 

Linear span $Lin(X)$은 $X$를 포함하는 가장 작은 Linear subspace이다.

$Lin(X)$ = the set of all finite linear combination of the points $x_i \in X$

 

 

 

1-3. Independence

Recall that a collection \(x_1, \dots, x_k\) of vectors from \(\mathbb{R}^n\) is called \textit{linearly independent}, if the only linear combination of these vectors equal to 0 is the trivial one — all coefficients are equal to 0: \[ \sum_{i=1}^{k} \lambda_i x_i = 0 \implies \lambda_i = 0, \quad i = 1, \dots, k. \]

 

 

1-4. Dimension and Bases

Dimension은 basis의 숫자로 결정된다.

 

* Basis의 정의

 

There exist finite collections $x_1, ..., x_k$ which span L and are “minimal” in this respect (i.e., such that eliminating from the collection one or more elements, the remaining vectors do not span $L$). All minimal finite collections of vectors spaning L, when nonempty, are comprised of distinct from each other nonzero vectors and have the same cardinality, called the dimension of L (notation: dim L), and are called linear bases of $L$.

 

 

예시)

 

여러 Linear subapce를 보면서 dimension 

내가 있는 공간이 $R^n$이라고 하자.

$R^n$ dimension = $n$

$\{0\}$ dimension = $0$

The dimensions of all proper (distinct from $\{0\}$ and $R^n$) linear subspaces of $R^n$ are integers $\geq 1$ and $\leq n-1$

 

---

 

2. Affine subspace

 

2-1. Definition

 

Affine subspace는 linear subspace의 shift된 버전이라고 볼 수 있다. 따라서 affine subspace를 볼 때는 linear subspace를 미리 식별하는 게 편하다.

 

A set \(M \subset \mathbb{R}^m\) is called an affine subspace, if it can be represented as a shift of a linear subspace: for properly chosen linear subspace \(L \subset \mathbb{R}^n\) and point \(a \in \mathbb{R}^n\) we have \[ M = a + L := \{x = a + y, y \in L\} = \{x : x - a \in L\}. \]

 

 

2-2. Affine combination

 

$x= \{x: \sum \lambda_i x_i \text{ s.t. }\sum_i \lambda_i = 1 \}$

 

2-3. Affine hull

 

$Aff(X)$ = the set of all finite affine combinations of elements of $X$

 

임의의 set $X$의 dimension은 affine hull of $X$의 dimension으로 계산한다.

 

2-4. Independence

 

linear independence와 유사하게 결국 독립이라는 것은 affine subspace에서 어떤 affine combination을 하더라도 동일한 결과를 얻을 수 없다는 것을 의미한다.

 

$$\sum_{i=0}^{k} \lambda_i x_i = \sum_{i=0}^{k} \mu_i x_i, \quad \sum_i \lambda_i = \sum_i \mu_i = 1 \implies \lambda_i = \mu_i, \quad 0 \leq i \leq k.$$

 

또는 다음과 같이 표현할 수 있다.

 

\[ \sum_{i=0}^{k} \lambda_i x_i = 0, \quad \sum_{i=0}^{k} \lambda_i = 0 \implies \lambda_i = 0, \quad 0 \leq i \leq k. \]

 

2-5. Dimension and Bases

 

Affine dimension을 알기 위해서는 다음 lemma를 참고한다.

 

$\textbf{Lemma. }$ Let \(k \geq 0\), and let \(x_0, \dots, x_k\) be a collection of \(k+1\) vectors from \(\mathbb{R}^n\). This collection is affinely independent if and only if the collection \(x_1 - x_0, x_2 - x_0, \dots, x_k - x_0\) is linearly independent.

 

A collection $x_0,\ldots, x_k$가 있다고 하자. 다음 proposition을 참고하면서 affine bases와 dimension을 살펴본다.

 

 

The minimal w.r.t inclusion collections $x_0,x_1,\ldots,x_k$ of vectors from an affine subspace $M$ which affinely span $M$ are affine bases of the affine subspace $M$.

$\textbf{Proposition }$
An affine subspace \(M = a + L\) is affinely spanned by a finite set \(X = \{x_0, \dots, x_k\}\) if and only if \(x_0 \in M\) and the \(k\) vectors \(x_1 - x_0, x_2 - x_0, \dots, x_k - x_0\) linearly span \(L\). In particular, the minimal in cardinality subsets \(X = \{x_0, \dots, x_k\}\) which affinely span \(M\) are of cardinality \(k + 1 = \dim M + 1\) and are characterized by the inclusion \(x_0 \in M\) and the fact that \(x_1 - x_0, \dots, x_k - x_0\) is a linear basis in \(L\).

 

다음과 같이 linear independence를 만족하는 \(x_1 - x_0, \dots, x_k - x_0\)가 있을 때 \{x_0, \ldots, x_k\}는 affine subspace의 bases가 되고 $dim(X)=k$이다

 

따라서 Affine subspace는 linear subspace와 달리 bases가 dimension보다 1개 더 많다. $x_0$라는 shift를 위한 vector가 필요하기 때문에 an affine subspace $M= a+L$는 Linear subspace $L$과 동일한 dimension을 가졌지만 추가적인 bases가 필요한 것이다.

 

 

 

 

---

 

생각할 거리

 

1. 차원이 $R$일 때

 

이 경우에는 일직선 상의 좌표계를 생각하면 된다.

 

1-1. $X=\{0 \}$ 다음과 같은 원점만 가지고 있는 경우

- Linear subspace

- Affine subspace

 

둘 다 해당된다. dimension은 0

 

$Lin(X)=\{ 0 \}$

$Aff(X)=\{ 0 \}$

 

1-2. $X=\{ 1\}$ (Singleton) : Affine subspace

 

affine subspace는 $1+\{0\}$으로 표현할 수 있기 때문에 linear subspace $L=\{ 0 \}$의 dimension 0은 그대로 가져가고 bases는 0과 1이 된다.

 

$Lin(X)=R$

$Aff(X)=\{ 1 \}$ 

 

1-3. $X=\{ 1, 2 \}$

 

Not linear subspace

Not affine subspace

 

Linear subspace는 정의 상 맞지 않으므로 linear subspace가 될 수 없고, affine subspace의 경우에도 a translation of linear subspace로 해석할 수 없다.

 

 

$Lin(X)=R$

$Aff(X)=R$

two different points가 있는 경우 affine hull of $X$는 line이 된다. 

 

 

1-4. $X=\{ x: 1\leq x \leq 2 \}$

Not linear subspace

Not affine subspace

 

1-5. $X=R$

Linear subspace, Affine subspace이다.

$dim(X)=1$