[2016.01.04] Dimension of Matrix Groups

차원(dimension)은 어떻게 정의되는가? 선형대수학 시간에 배우는 방법에 의하면, 차원은 벡터공간에서의 선형독립인 원소 개수의 최댓값으로 정의할 수 있겠다.

하지만, 차원이라는 개념은 벡터 공간 이외로도 확장될 수 있다. 예를 들어 실수 상의 3 \times 3 가역행렬의 군 \text{GL} _3 (\mathbb{R})의 차원은 얼마일까? 일반적으로 이는 임의의 행렬에서 행렬식이 0이 아닌 constraint를 주었기 때문에 차원이 줄어들지 않을 것이고, 모든 3 \times 3 행렬의 차원은 9임이 자명하므로 \text{GL} _3 (\mathbb{R})의 차원 역시 9일 것이라고 추측할 수 있다. 이러한 ‘추측’은 성립하는가?

결론부터 말하자면 처음부터 틀린 접근이다. 기본적으로 행렬군의 차원이라는 것을 정의하지 않았으며(사실 scalar가 \mathbb{R}인지 어쩐지도 정의하지 않았다!), 행렬군은 vector space가 아니므로 선형 독립인 원소를 기반으로 차원을 정의할 수 없다. 하지만 위의 접근이나 직관을 생각해 볼 때, \text{GL} _3 (\mathbb{R})의 차원은 9여야 할 것 같고, 만약 constraint가 더 주어질 경우 차원은 그에 비례하여 줄어들어야 할 것 같다. 이러한 성질을 가지게 차원을 정의할 수 있을까? 그러한 차원은 어디에 쓰이는 것일까?

이러한 문제들을 해결하기 위해, 우선 Lie Algebra를 정의한다.

정의 1. 주어진 field \mathbf{k}에 대해, \mathbf{k} -Lie Algebra\mathbf{k} -벡터공간 \mathfrak{a} 과 Lie Bracket이라 부르는 \mathbf{k}-bilinear map [ , ] : \mathfrak{a} \times \mathfrak{a} \rightarrow \mathfrak{a}가 존재해

  • [x,y]=-[y,x] (Skew symmetry)
  • [x,[y,z]]+[y,[x,z]]+[z,[x,y]] = 0 (Jacobi identity)

기본적으로 벡터공간이야 그렇다 치고, Lie Bracket에는 뭐가 있을까. 얼마 없을 것 같지만 의외로 있다.

예시. \mathfrak{a} = \mathbb{R}^3에서, 외적 (\mathbf{a} , \mathbf{b}) \rightarrow \mathbf{a} \times \mathbf{b}는 Lie Bracket이 된다.

예시. \mathfrak{a} = \text{Mat} _n (\mathbb{R})에서, commutator [A,B] = AB-BA는 Lie Bracket이 된다.

Lie Algebra도 일종의 Algebra이므로, algebra와 유사한 여러 정의 및 성질들을 정의할 수 있다. 후에 논의할 때 간단하게 정의하도록 하자.

본론으로 넘어가자. 당연히 Lie Algebra는 벡터공간이므로 차원을 정의할 수 있다. 하지만 이를 어떻게 group과 연관시키는가? 만약 group을 적당히 Lie Algebra와 연관시킬 수 있다면 좋을 것이다.

이를 위해 접선공간(Tangent Space)를 만든다: 주어진 행렬군 상에 있는 curve를 생각해, 그 도함수의 값을 살펴보자. 다시 말해,

정의. 행렬군 G와, U \in G에 대해, U에서의 G의 접선공간을

T_U G = \{ \gamma ' (0) \in \text{Mat} _n (\mathbf{k} ) | \gamma \gamma (0) = UG 상의 미분 가능한 curve\}

과 같이 정의한다.

이 경우, 아래를 보일 수 있다.

정리. T_I (G)는 $latex \text{Mat} _n (\mathbf{k})$의 \mathbf{k}-Lie subalgebra가 된다.

증명. T_I (G)가 덧셈, 스칼라곱 및 Lie Bracket에 대해 닫혀 있음을 보이면 된다.

  • 덧셈 : 주어진 두 curve \alpha, \beta에 대해, \gamma = \alpha \beta\gamma ' (0) = \alpha ' (0) + \beta ' (0)를 만족한다.
  • 스칼라곱 : 주어진 한 curve \alphac \in \mathbf{k} 에 대해, \gamma = c \alpha\gamma ' (0) = c \alpha ' (0)을 만족한다.
  • commutator : 주어진 두 curve \alpha, \beta에 대해, 2차원 함수 F(s,t) = \alpha (s) \beta (t) \alpha (s) ^{-1} 을 정의하자. 이 때, 고정된 s에 대해, dF(s,t)/dt |_{t=0} = \alpha (s) \beta ' (0) \alpha (s)^{-1} 가  T_I (G)의 원소이며 이 때, 접선공간은 닫힌 집합이므로 이에 상수곱 및 극한은 취해도 여전히 T_I (G)의 원소가 되며, 따라서d \alpha (s) \beta ' (0) \alpha (s) ^ {-1}/ds |_ {s = 0 } = \alpha ' (0) \beta ' (0) - \beta ' (0) \alpha ' (0) 역시 T_I (G)의 원소가 된다.

이로써, 행렬군으로부터 접선공간을 만들 수 있고, 이것이 위에서 정의한 Lie algebra가 됨을 확인할 수 있다. 이제 행렬군의 차원을 정의할 수 있다.

정의. 행렬군 G의 차원\text {dim} _{\mathbf{k}} G = \text{dim} _{\mathbf{k}} T_I G로 정의한다.

이제, 맨 위에서 보였던 \text {GL} _n (\mathbb{R} ) \text {SL} _n (\mathbb{R}) 의 차원을 구해보는 것으로 마치고자 한다.

예시.  A \in \text {Mat} _n (\mathbb{R} )에 대해, \text {GL} _n (\mathbb{R} )  상의 curve \gamma (t)\text {exp} (tA) = \sum_{i=0}^{\infty} (tA)^i / i!와 같이 정의하자. 실수의 그것과 같이 이것이 모든 t에 대해 정의되며, 이 때 \gamma는 미분 가능하며 \gamma '(0) = A 따라서 \text{GL} _n (\mathbb{R} ) 의 접선공간은  \text {Mat} _n (\mathbb{R} ) 가 되며, 따라서 차원은 n^2가 됨을 금방 확인할 수 있다.

예시. 위에서 거론한 \text {exp} (tA)에 대해, 그 행렬식이 e^{ \text {tr} (A) } 로 주어짐을 금방 확인할 수 있다. 따라서 \text {SL} _n (\mathbb{R}) 의 접선공간은 \{ A \in \text{Mat} _n (\mathbb{R} ) |\text{tr} (A) = 0 \}에 대응하며, 따라서 차원은 n^2 -1.

더욱 자세한 내용은 학부 행렬군론 시간에 좀더 자세히 배울 수 있다. 너무 길어질 것 같아 생략.

 

출처: Andrew Baker, Matrix Groups: An Introduction to Lie Group Theory, Springer, pp. 67~97

[2016.01.04] Dimension of Matrix Groups

[2016.01.01] Erdős distinct distances problem

평면 위의 n개의 점을 생각하자. n개의 점을 적당히 옮겨감으로써, 임의의 두 점 사이의 거리가 다르게 할 수 있음은 자명하다: 즉 서로 다른 거리의 개수는 최대 \binom{n}{2}개가 가능하다.

이 시점에서, 반대 방향을 생각해 볼 수 있다: 서로 다른 거리의 개수를 최소화하려고 하면, 어느 정도까지 가능할까. 아주 간단한 경우, 즉 n=3일 때를 생각해보자. 이를 정삼각형 형태로 배치할 경우, 점 사이의 거리의 개수는 1개로 충분하다. 하지만 좀더 많은 점이 있다면?

평면상의 문제에서 벗어나서, 쉬운 경우 – 선 위에 있을 경우를 생각해보자. 직관적으로 생각해 봤을 때 n개의 점을 등간격으로 둘 경우 거리의 개수는 n-1개로 정해진다. 따라서 평면에서는 n개보다 확실히 작게 만들 수 있으리라는 생각을 할 수 있다. 어느 정도로 작게 만들 수 있을까? 라는 질문이 Erdős distinct distances problem의 요지이다.

Paul Erdős 본인은 그의 1946년 논문 (PDF 링크)에서 다음을 증명하였다.

정리. 평면 상의 n개의 점 사이의 거리의 개수의 최소값 f(n)은 아래 부등식을 만족한다:

(n-3/4)^{1/2} - 1/2 \le f(n) \ge cn/( \log n)^{1/2} .

이 정리 자체는 쉽게 정리할 수 있다. 논문의 증명 방법을 인용한다.

증명: 우선 n개의 점으로 결정되는 볼록포(convex hull) 상에 있는 점을 잡아, P_1이라 부르고, P_1 P_i (i=2,3, \cdots, n)의 개수를 K라 하자. 이 중, 같은 거리가 최대 N회 나타난다고 할 경우, 당연히 KN \ge n-1.

이제 거리 r이 정확히 N번 나타나는 거리라고 할 때, 이제 P_1을 중심으로 하며 반지름 r인 원 위에는 N개의 점이 있고, 이 점들(Q_1 , Q_2 , \cdots , Q_N )은 한 반원 위에 존재하며 (아니면 P_1 이 convex hull 위에 있음에 모순이므로), 이 때 Q_1 Q_2 < Q_1 Q_3 < \cdots < Q_1 Q_{N-1} 이므로, N-1 개의 서로 다른 거리를 얻게 된다. 따라서, 다음을 얻는다;

f(n) \ge \max (N-1 , (n-1)/N )

이는 N(N-1)=n-1일 때 최소가 되며, 이는 정확히 첫번째 부등식이 된다.

“최대”를 증명하기 위해, 실제 경우의 예시를 들자: 아래와 같은 정사각형 격자를 생각하자.

square1

이 때, 격자점 사이의 거리는 (u^2 + v^2)^{1/2}, (0 \le u,v \le n^{1/2} )의 형태를 가지며,  두 정수의 제곱의 합으로 나타나지는 2n 이하의 자연수는 cn/(\log n )^{1/2} 개 이하임이 알려져 있으며, 이는 부등식의 우변이 된다.

이 방식을 그대로 응용해, 높은 차원의 경우 역시 보일 수 있다.

따름정리. k-차원 공간 위에 있는 n개의 점에 대해 f(n)을 다시 정의할 경우, 다음 부등식이 성립한다:

c_1 n^{1/k} <f(n) < c_2 n^{2/k }

더 나아가, Erdős는 다음을 주장하였다:

가설. 평면 위의 n개의 점 사이의 거리의 개수는 최소 n^{1- o(1) } 이다.

사실 이 가설은 상당히 오랫동안 open이었고, f(n)n^{c}꼴으로 정리하는 작업은 있었지만 위 가설에 접근하지는 못했다. 그렇지만 2010년, 본 가설이 증명되었고, 해당 논문은 2015년 Annals. of Math에 게재되었다.

정리. (Guth and Katz) 상수 c가 존재해, f(n)>cn/( \log n)가 만족한다.

위 정리를 정확히 이해하기는 사실 어렵지만, 중요한 아이디어들은 캐치할 수 있다(이하 내용은 Terrence Tao의 블로그에서 발췌).

Erdős의 하한 증명 과정에서, 한 점을 중심으로 한 원을 그림으로써 원하는 성질을 증명할 수 있었다. 유사하다면 유사하지만, Guth와 Katz는 명제를 증명하기 위해, 본 문제를 3차원 공간상의 에 관한 문제로 변환하였다.

길이가 같다라는 것은 사실은 도형으로써 두 선부이 합동임을 의미하고, 따라서 그에 따른 orient-preserving rigid motion이 유일하게 존재한다. 다시 말해, 두 길이가 같은 선분의 쌍 x_i x_j x_k x_l은 5개 원소의 쌍 (x_i, x_j, x_k, x_l, R)에 유일하게 대응된다. 뿐만 아니라, 이러한 선분의 쌍은, 특정 길이가 N번 언급될 경우 이러한 쌍은 \binom{N}{2}개 존재한다. \binom{n}{2}개의 선분이 f(n)개로 partition되는 케이스이므로, 이는 모두 길이가 같을 때 최소이다. 작은 항을 모두 제외할 경우 이는 n^4 /f(n) 이 되며, 따라서 만약 정리가 성립하지 않는다면 이것이 n^3 \log n보다 커져야만 한다. 이를 반증하자.

거꾸로, 이러한 Rx_ix_k로 보내며, x_jx_l으로 보내는 rigid motion이 되므로, xy로 보내는 모든 rigid motion의 집합 l_{x \rightarrow y}을 정의할 때 Rl_{x_i \rightarrow x_k }l_{x_j \rightarrow x_l }의 공통 원소가 된다. 한편 l_{x \rightarrow y}을 고려할 때, 이러한 rigid motion의 회전 중심은 x,y의 수직이등분선상의 점 중 하나가 되고, 이에 따른 회전각 역시 유일하게 주어진다. 따라서 (p, \cot ( \theta /2) ) 형태의 좌표를 주었을 때, l_{x \rightarrow y}R^3 상에서의 선으로 볼 수 있다. 사실 이렇게 좌표를 줄 경우, 이는 ‘직선’이 됨 역시 쉽게 확인할 수 있을 것이다. (코탄젠트의 값은 (중점에서의 변위)/선분 길이의 반) 으로 주어진다.)

아까도 언급했듯, 길이가 같은 선분의 쌍은  (x_i, x_j, x_k, x_l, R)에 대응되며, 이는 곡 두 선 l_{x_i \rightarrow x_k }l_{x_j \rightarrow x_l }이 교점을 가지게 된다. 즉 문제는 다음과 같아진다. 이러한 선은 대략 n^2개 존재하므로, 상수를 떼고 생각할 경우 아래와 같은 문제가 된다.

n^2개의 선 중, 만나는 선의 쌍은 몇 쌍이나 존재하는가?

위 문제의 답이 n^3 \log n이하라면 가정이 모순이므로 정리가 성립하게 될 것이다. 하지만 일반적으로 위 문제의 답은 당연히 n^4이다(모두 한 점을 지난다고 생각해보자)

Guth & Katz의 방법론을 통해 n개 점에 대한 문제를 ~n^2개의 직선 중 만나는 쌍에 대한 논의로 변환하였다. 우리의 목적은 이러한 쌍이 n^3 \log n 이하로 정해짐을 보이는 것이지만, 일반적으로 그렇게 되지는 않는다.

하지만 우리가 만든 이 ‘직선’은 임의로 결정된 것이 아니므로, 추가적인 제한 조건을 준다면 문제를 해결할 수도 있겠다. 관찰을 해보자.

  • 서 로 다른 점 x_i , x_j , x_k에 대해, l_{x_i \rightarrow x_j}l_{x_i \rightarrow x_k}는 만나지 않는다. 즉 같은 rigid motion은 같은 점을 다른 점으로 대응시킬 수 없다. 즉 만약 두 직선이 만난다면, 서로 다른 점에서 시작하는 직선이여야 한다. 따라서 한 점에서 만날 수 있는 직선의 수는 최대 n개.
  • 임의의 평면 \pi이 있을 때, l_{x_i \rightarrow x_j}\pi 상에 존재할 수 있는 (x_i , x_j )의 쌍은 O(n)개 존재한다.
  • 사실 이것은 평면이 아니라 일반적인 에 서도 성립한다. 증명 과정에서 필요한 것은 임의의 regulus(2차식으로 정해진 면) 역시 기껏해야 O(n)개 직선을 포함할 수 있다는 것이다. (사실 이는 Bezout’s Theorem에 의해 자명하며, 임의의 유한 차수 면에 대해서도 같은 성질이 성립한다.)

그렇게 될 경우, 본 문제는 다시 다음으로 회귀한다.

R^3 안의 ~ n^2 개 직선이

  • 한 점은 최대 n개 직선에서 만나며
  • 임의의 평면이나 regulus가 기껏해야 O(n)개의 직선을 포함할 경우

만나는 직선의 쌍은 최대 O(n^3 \log n)쌍 존재한다.

기초적인 더블 카운팅을 사용해보자. 어떤 점이 k개 직선에서 만날 경우, 그 점은 ~k^2개의 만나는 의 쌍을 만든다고 할 수 있다. 따라서, 여러 개 만나는 직선마다 만나는 횟수에 반비례하게 조금 만난다면, 결론에 조금 더 가까워질수 있을 것이다. 구체적으로는 다음과 같다.

정리. 3차원 실공간에서의 O(n^2)개 직선이, 임의의 평면이나 regulus가 기껏해야 O(n)개의 직선만을 포함한다고 하자. 이 때, 2 \le k \le n에 대해, k개 이상의 직선에서 만나는 점의 집합을 S라 하면, |S| = O(n^3 / k^2 ).

이 때, 정리가 성립할 경우 만나는 선의 개수는 최대

O(n^3 ( 1 + (n-1)^2 (1/(n-1)^2 -1/n^2) + \cdots + 4(1/4-1/9)) = O(n^3(1+1/2+\cdots+1/n))=O(n^3 \log n)

가 되어, 우리가 원하는 결론에 도달함을 알 수 있다.

이하 내용들은 다소 난해하므로, 기회가 된다면 다시 논의해보도록 하겠다.

참조:

[2016.01.01] Erdős distinct distances problem