[Linear Algebra] Lecture 12 그래프와 네트워크(Graph and Network), 근접 행렬(Incidence Matrices)

이번 포스팅에선 선형 대수의 응용에 대한 이야기를 할까 한다. 선형 대수를 공부하면서 한 번쯤은 "이것들이 어디에 사용될까?" 하는 의문을 가져본 적이 있을 것이다. 선형 대수는 실제로 너무나 다양한 곳에 응용되고 있다. 머신 러닝(Machine Learning), 로보틱스(Robotics), 컴퓨터 비전(Computer Vision), 그래픽스(Graphics), 영상 처리(Digital Image Processing), 게임(Game), 물리학(Physics), 생물학(Biology) 그리고 경제학(Economics)에 이르기까지 굉장히 방대한 분야에 걸쳐 사용되고 있다. 

 

필자의 경험을 예로 들자면, 실험실에서 보유하고 있던 다관절 형태의 산업용 로봇을 제어하기 위해 기구학을 풀었어야 했는데, 이때 선형대수를 이용하여 역기구학(Inverse Kinematics)을 풀고 이를 통해 로봇을 제어한 경험이 있다. 또한 물체 인식을 위한 카메라 캘리브레이션(Camera Calibration), 물체 자세추정을 위해 세그멘테이션(segmentation)된 바이너리 이미지의 Eigenvalue 및 Eigenvector등의 사용, 그리고 각종 머신 러닝 등을 사용할 때에도 선형대수를 이용하였다. 특히 컴퓨터 비전이나 그래픽스 분야에서는 선형 대수를 모르고서는 절대 공부할 수 없다. Multiple view geometry라는 컴퓨터 비전 분야의 전설적인 책이 있는데, 이 책은 선형 대수를 모르면 아예 읽을 수 조차 없다. 이렇듯 선형 대수는 특히 공학도라면 절대로 피할 수 없는 학문이다. 선형 대수의 중요함은 아무리 강조를 해도 지나치지 않는다. 

 

서론이 조금 길어졌는데 어쨋든 이번 포스팅에서 다룰 내용은 그래프(Graph)와 네트워크(Network)에 관련된 내용이다. 이 그래프 이론은 이후 확률/통계 기반의 머신 러닝 기법인 베이지안 네트워크(Bayesian Network)및 마코프 모델(Markov Model)의 기초가 되니 잘 이해하도록 하자. 또한 이를 우리가 잘 알고있는 법칙인 키르히호프의 법칙(Kirchhoff's Laws)과 연관지어 이해해보도록 하자. 

 

 

 

1. 그래프(Graph)

 

- Graph: Nodes and Edges

 

우리는 그래프(Graph)라고 하면 주가의 변동을 나타내는 2차원 평면상의 그래프와 같은 형태를 많이 떠올릴 것이다. 그러나 수학, 특히 이산 수학(discrete mathematics)에서의 그래프는 어떤 네트워크 형태의 구조를 의미한다. 즉 어떤 객체(object)들과 그들을 연결짓는 선(Line)을 통해 그들 사이의 관계를 나타내는 구조를 의미한다. 여기서 각 객체를 노드(node)(혹은 정점(vertex))라 하고 각 노드들을 연결하는 선을 에지(edge)라 한다. 그래프는 응용수학(Applied mathematics)에서 가장 중요한 모델 중 하나이며, 이산(discrete)적 형태를 띄고 있다. 그래프의 형태는 다음과 같다. 

 

 

위의 그림에 나와있듯이 그래프는 노드(node)와 에지(edge)로 구성되어 있다. 노드는 각각의 객체(object)를 의미하며 정점(vertex)이라고 부르기도 한다. 위 그림에서 색깔을 가지고있는 동그라미들이 바로 노드들이다. 

에지(edge)는 각 노드들을 연결시켜주는 역할을 한다. edge는 방향을 가지거나 방향을 가지지 않는 경우도 있다. 방향이 있는 edge로 구성된 그래프를 우리는 directed graph라 하며 위의 그림과 같다. 방향이 없는 edge로 구성된 그래프는 undirected graph라 한다. 

 

그래프 모델을 우리 실생활과 연결시켜보자. 각 노드를 어떤 하나의 웹사이트 혹은 우리 컴퓨터라고 생각해보자. node1은 네이버, node2는 다음, node 3는 우리집에 있는 컴퓨터와 같이 말이다. 각 웹사이트는 인터넷으로 연결되어 있는데, 우리는 네이버에 접속하기 위해서 가장 빠른 경로를 찾거나 가장 최적의 경로를 찾아야 할 때도 있다. 혹은 node들을 SNS의 계정이라고 생각해보자. 각 node들은 서로 연결되어 있고, 친구를 추천해주는 일 등을 할 때 이와 같은 그래프 모델을 사용해서 최적의 친구를 추천해 주거나 하는 일들을 할 수 있다. 

이밖에도 어떤 도시의 수도관 공사에서 물의 흐름을 나타내는 모델, 도시의 다리를 설계하기 위한 모델, 전자회로에서 전류의 흐름에 대한 모델 등 다양한 곳에 응용이 가능하다. 이렇듯 그래프 모델은 우리 실생활에서 유용하게 사용될 수 있다. 

 

 

- Incidence Matrix:

 

다시 그래프의 내용으로 돌아가서, 위의 그래프는 node가 총 4개이고 edge가 총 5개이다. node끼리 연결된 방향은 화살표로 표현되어 있다. 이러한 그래프의 노드와 그들의 연결관계를 행렬(Matrix)로 나타낼 수 있다. 이러한 그래프의 연결 관계에 대한 그래프를 우리는 근접행렬(Incidence Matrix)이라 한다. 

 

위의 그래프에서 node의 개수를 n, edge의 개수를 m이라고 했을 때, n=4, m=5가 된다. node의 개수인 n을 column으로, edge의 개수인 m을 row로 하여 5x4 크기의 근접 행렬을 만들 수 있다. 이때 그래프의 edge는 방향을 가지고 있기 때문에 근접 행렬의 각 원소들은 방향을 나타내야한다. 근접 행렬에 방향을 나타내는 방법은 다음과 같다. edge1의 경우 node1에서 출발하여 node2로 향한다. node1이 출발점, node2가 끝점이 되는데, 출발점은 -1, 끝점은 1로 지정하는 것이다. 이렇게 하여 위의 그래프에 대한 근접 행렬을 만들면 아래와 같다. 

 

 

행렬 A의 row를 중심으로 생각해보면 각 node들 간의 관계를 -1과 1로 정의해 준다. 이 incidence matrix만 있으면 그래프를 모르더라도 그릴 수 있다. 예를 들면 column이 4개 이므로 종이에 점 4개를 먼저 그리고 번호를 부여한다음 row를 보면서 node끼리 연결하는 것이다. 가령 row3를 보면 node1에 -1, node3에 1의 원소가 있으므로 node1에서 node3로 연결되는 화살표를 그리면 된다. 

 

여기서 한 가지 눈여겨봐야 할 것이 있다. node1은 node2와 node3로 각각 연결되어 있다. 이때 node2는 다시 node3로 연결되어 있다. 이렇게 node들이 연결되어져 있는 부분 그래프(subgraph)를 Loop라고 한다. Loop를 찾는 방법은 연결되어있는 edge들을 따라가며 찾는 방법도 있으나, 좀 더 쉬운 방법은 그래프에서 부분 면적을 찾는 것이다. 이것은 마치 아래 그림에서 작은 삼각형들의 총 개수를 찾는 문제와 같다. 

 

위 그림에서 중복되지 않는 삼각형의 총 개수는 몇 개인가? 

이를 그래프로 생각하면 각각의 부분 삼각형의 총 개수는 loop의 총 개수와 같다. 

그림 출처: http://kwon-blog.tistory.com/1289

 

 

위 그림에서 각 삼각형들의 꼭짓점들을 node라 하고 삼각형을 이루는 line들을 edge라고 생각했을 때, 위 그림의 각각의 삼각형들이 바로 부분 그래프(subgraph)가 되는 것이고 Loop가 된다. 위 그림에선 총 8개의 Loop가 존재한다(숨어있는 삼각형을 모두 찾으면 25개가 나오지만 여기선 중복되지 않는 부분만 loop로 간주함). 꼭 삼각형 뿐만 아니라 임의의 다각형 형태의 그래프에서 각각의 면적을 찾으면 그것이 loop의 개수이다(겹치는 부분 제외). 

 

다시 우리의 그래프로 돌아와서, 그렇다면 우리의 그래프는 몇 개의 loop를 가지고 있을까? 결론부터 말하자면 아래 그림과 같이 총 3개의 loop를 가지고 있다. edge1, 2, 3에서 loop1,  edge3, 4, 5에서 loop2,  edge1, 2, 4, 5에서 loop3가 나온다. 이러한 loop와 loop들의 위치는 그래프에서 중요한 역할을 한다. 

 

 

 

사실 loop는 incidence matrix에서 재미있는 특성을 가지고 있다. incidence matrix를 loop를 고려하여 다시 써보자. 

 

 

식 (2)에서 edge1,2,3는 loop1이다. A의 row1, 2, 3에 해당하는 것들인데, 이 row들은 독립(independent)인가?를 한 번 생각해보자. 즉 행렬 A에서 loop에 해당하는 row들은 독립(independent)인가? 정답은 No다. loop1의 row들은 종속(dependent)이다. row1과 row2를 더했을 때 row3가 나오는 것을 보면 쉽게 알 수 있다. 여기서 알 수 있는 사실은 어떤 그래프의 loop에 대한 Incident matrix의 row들은 선형종속(linearly dependent)의 특성을 갖는다는 것이다. 

 

 

 

2. 전자회로의 그래프 모델링(Graph modeling of an electronic circuit)

 

- Potential difference and null space of A:

 

우리는 4개의 node와 5개의 edge로 구성된 그래프에 대한 5x4크기의 Incidence matrix를 만들었다. 그런데 만약 node가 100개이고 이들을 연결하는 edge가 180개라고 가정해보자. 이에 대한 Incidence matrix는 180x100의 크기를 가질 것이다. 그러나 이때 이 행렬은 굉장히 많은 0을 가지게 될 것이다. 왜냐하면 Incidence matrix에서는 하나의 row에서 오직 2개의 non-zero원소들만 나타나기 때문이다. 결국 그래프의 규모가 커질수록 Incidence matrix의 원소들은 행렬의 크기에 비해 적은 비율로 나타날 것이다. 즉 희소(sparse)한 원소를 가지게 되는 것이다. 이러한 형태의 행렬을 희소 행렬(sparse matrix)이라 한다. 

중요한 것은 이러한 희소 행렬은 내부적으로 어떤 구조(structure)가 형성된다. 만약 실제 문제에 대한 그래프라면, 가령 실제 어떤 전자회로에 대한 그래프라면 그 회로에 대한 구조가 Incidence matrix에 드러나게 될 것이다. 이러한 구조를 파악하기 위해 우리는 선형 대수적으로 행렬을 분석할 수 있다. 이에 대한 첫 번째 방법은 바로 Incidence matrix의 null space를 찾는 것이다. 

 

행렬 A의 null space를 구한다는 것은 어떤 의미를 가질까? node를 나타내는 column이 독립인지를 파악할 수 있다. Null space라는 것은 어떻게 행렬의 column벡터들의 선형 조합(Linear combination)을 통해 0을 만드는지를 알려준다. 만약 column 벡터들이 독립(independent)이라면, null space의 해는 오직 영벡터(zero vector)만이 존재한다. 만약 종속이라면, null space라는 말처럼 해들의 공간, 즉 해들의 집합이 발생한다. 

 

그렇다면 식(2)의 행렬 A의 column은 독립인가? 지금부터 알아보도록 하자. Null space를 계산하기 위해선 Ax=0를 풀면 된다. 식(2)를 아래와 같이 Ax=0의 꼴로 다시 써보자. 

 

 

위의 행렬은 무엇을 나타낼까? 이해를 돕기 위해 위의 그래프를 전자 회로(electronic circuit)라고 생각해보자. node들을 전자 회로에서 전압을 측정하는 임의의 지점이라 생각해보자(사실 전자회로에서 node는 두 개 이상의 branch들이 연결되는 지점). Incidence matrix와 연관지어 생각해보면 Ax=0에서 변수인 x=[x1, x2, x3, x4]들은 각 node에서의 전압(potentials)이다. 이때 행렬 A를 x에 곱하게 되면 우리는 각 node들의 전위차(potential differences)를 계산할 수 있게 된다. 

 

 

이제 우리가 찾아야 할 것은 언제 모든 node들의 전위차(potential differences)가 0이 되는지다. 즉 null space를 찾는 것이다. 물론 모든 x가 0인 경우에 당연히 전위차가 0일 것이다. 그러나 x가 모두 0이라는 것은 회로에 아예 전류가 흐르지 않는 다는 말이기 때문에 별 의미가 없다. 따라서 우리는 회로에 전류가 흐를 때를 가정하고 x의 값, null space를 구해야 하는 것이다. 물론 영벡터도 null space에 존재하긴 하지만, A의 column이 dependent이기 때문에 영벡터 이외의 해가 존재한다. 어떻게 column이 dependent인지를 바로 알 수 있을까? 이유는 영벡터 이외의 해를 바로 찾을 수 있기 때문이다. 행렬 A를 보면 하나의 row에 -1과 1이 딱 한 번씩만 나온다(하나의 row가 하나의 edge를 나타내므로 당연히...). 이 말은 column 끼리 다 더하면 반드시 0이 된다는 소리이고, 결국 x1=1, x2=1, x3=1, x4=1이면 column끼리 그대로 더한 것과 같기 때문에 이것이 해가 된다. 

 

x가 1로만 이루어진 벡터라는 것은 결국 각 node의 potential이 constant하다는 것을 의미한다. 즉 각 node의 전압(potential)이 constant하다면, node들의 전위차(potential difference)는 0이 된다. 이것이 Ax=0인 null space의 해(solution)이다. 

Null space는 Ax=0의 해의 공간을 의미하므로 x는 해의 집합을 가질 것이고, 어떤 1차원의 line이 해가 된다. x에 상수 c를 곱한 것이 4차원 공간에서 [1, 1, 1, 1]을 지나는 line이고 결국 우리가 찾는 최종적인 null space는 4차원 공간상에 존재하는 1차원의 line이 되는 것이다. 이때의 null space의 기저(basis)는 x=[1, 1, 1, 1]이 된다. 

 

 

그렇다면 위의 그래프를 전자회로라고 가정했을 때, 식 (5)의 null space가 물리적으로 의미하는 것은 무엇일까? 위의 회로에서 각 노드들의 전압(potentials)은 오직 임의의 상수 c에 의해 동일하게 결정된다는 것이다. 즉 식 (5)의 null space에 의하면, 임의의 상수값 c를 설정하면(ex: c=1, 3, 56, etc...) 모든 노드의 전압이 한 번에 동일하게 설정된다는 말이다. 이것이 의미하는 것은 각 노드들간에 전위차(potential differences)가 없다는 것이다. 전자 회로에서 전위차는 전류의 흐름을 만들어낸다. 그러나 전위차가 없다면 어떠한 전류의 흐름도 일어나지 않는다. 결국 위의 그래프 모델에서는 모든 노드들의 전압을 올리거나 내릴 수 있는 단 하나의 파라미터(parameter)만이 존재하는 것이다. 

 

이러한 경우에 우리는 전위차를 만들어주기 위해 node들 중 하나를 ground로 설정하고 나머지를 풀 수 있다. 이를 테면 x4=0으로 만든다음 나머지 x1, x2, x3를 푸는 것이다. 이렇게 하면 Incidence matrix A의 col4는 신경쓰지 않아도 된다. 나머지 column을 가지고 해(solution)를 구하면 된다. 

 

 

 

node들 중 하나를 0으로 설정한다는 것은 전압(potential)을 0으로 만든다는 것이고 다른 node들의 기준 전압(base voltage)이 된다는 것이다. 이제 나머지 3개의 node에 대한 전압값에 대해서 해를 구하면 된다. 지금 예에서는 x4=0로 설정했지만(ground), x1=0, 혹은 x3=0처럼 어떤 node를 ground로 만들어도 상관 없다. 이 행위가 결국 전위차(potential difference)를 만들게 되고 전류의 흐름을 만든다.  

 

이와 같이 하나의 node를 ground로 만들고 나머지 3개의 node를 이용해 해를 구하는 것은 Incidence matrix의 rank가 3이기 때문이다. 우리는 앞서 식 (5)와 같이 그래프 행렬 A의 null space를 구했고, null space의 차원(dimension)이 1임을 알았다. Lecture 10에서 배웠듯이 null space의 차원은 dim N(A)=n-r이다. 여기서 n=4이고 r은 가우스 소거를 통해 pivot을 살펴보면 알 수는 있지만 아직은 모르는 상태다. 그러나 소거를 하지 않아도 n-r = 4-r=1으로부터 r=3임을 알 수 있다. 따라서 A의 column space(or row space)의 차원(dimension)은 3이고 결국 col1, col2, col3가 독립(independent)이라는 뜻이다. x1이나 x2, x3를 ground로 설정해도 마찬가지이다. 

 

정리하자면 위에서 정의했던 전자회로 그래프 모델에서 A의 4개의 변수(node의 전압(potential)을 의미)중 어떤것이던 처음 3개는 독립(independent)이며 유의미하다(pivot variable을 의미). 그러나 마지막 4번 째 변수는 그렇지 못하기 때문에(free variable처럼..) 보통 이 독립인 변수를 제외한 마지막 변수를 0으로 설정하고 나머지 변수에 대해서 해를 계산한다. 

 

 

- Kirchoff's current law and null space of A transpose:

 

이번에는 A의 transpose의 null space를 구해보자. 응용수학에서는 A의 transpose의 null space를 계산하는 경우가 의미 있을 때가 많다. $N(A^T)$는 우리가 잘 알고 있는 키르히호프의 전류 법칙(Kirchhoff's current law)과 관련이 있다. 우선 아래와 같이 식을 써보자. 

 

 

먼저 위의 Left null space의 차원(dimension)에 대해 알아보자. Left null space의 차원인 $\text{dim} \; N(A^T)$을 알기위해선 행렬에 대한 3가지 성분을 알아야한다. 바로 row와 column의 수인 m과 n, 그리고 rank이다. Lecture 10에서 배웠듯이 Left null space의 차원은 m-r이다. 여기서 m=5이고 r=3이다. A transpose에서는 m은 여전히 5이지만 column의 수를 나타낸다. 어쨋든 계산하면 m-r=5-3=2가 Left null space의 차원이 된다. 사실 m-r=2라는 것은 A transpose 행렬에서 소거를 했을 때 free column으로 나타나는 부분들이다. free column이 2개이고 이것이 결국 Left null space의 차원이 되는 것이다. Left null space의 차원은 2차원이다. 

 

 

차원을 알았으니 그 다음에 찾아야 할 것은 Left null space의 기저(basis)이다. 기저를 구하기전에 먼저 식 (8)이 의미하는 것이 정확히 무엇인지, 어떤 것을 표현하고 있는지를 먼저 이해해보자. 본 전자회로에 대한 그래프 모델에 대한 관계는 아래 그림과 같다. 

 

 

그래프 모델과 선형대수의 부분 공간과의 관계도

 

 

우리는 가장 먼저 그래프를 그렸고 미지수 x=[x1, x2, x3, x4]를 정의했다. 이 x가 나타내는 것은 각 node에서의 potential을 나타낸다. 그 다음 그래프의 node사이의 연결 관계를 식(1)과 같이 Incidence matrix로 정의하였다. 미지수 x에 Incidence matrix A를 곱해줬을 때, 우리는 식 (4)와 같은 방정식을 얻을 수 있고 이것이 의미하는 것은 node들 간의 전위차(potential difference)이다. Incidence matrix A를 곱해서 node들의 전압(potential)에서 node들 간의 전위차(potential difference)에 대한 방정식 Ax=0을 만들어낸 것이다. 

 

그 다음으로 정의한 것은 y=[y1, y2, y3, y4, y5]이다. y는 회로에 흐르는, 즉 그래프에서 edge에 흐르는 전류(current)를 나타낸다. 어떤 행렬 C가 있다고 했을 때, 이 C행렬이 전위차와 전류 사이를 연결시켜주는 행렬이라고 하자. C를 통해 전위차에서 전류로 연결되는 관계를 우리가 잘 아는 옴의 법칙(Ohm's law)으로 생각할 수 있다. edge에 흐르는 전류는 전위차(potential difference)가 클 수록 커지는데, 이때 edge 자체가 가지고 있는 저항이 전류의 양에 영향을 준다. 저항이 크면 edge에 흐르는 전류의 양도 작아지고, 저항이 작으면, 즉 전도율(conductance)이 높아지면 전류의 양도 커지는 것이다. 옴의 법칙은 결국 얼마나 많은 영의 전류가 흐르는지에 대한 관계를 설명해 주는 것이다. 이러한 전위차와 전류의 관계를 우리는 C행렬을 통해 연결시킬 수 있다. 

 

마지막 단계는 A의 transpose의 null space, 즉 Left null space를 구하는 것이다. 이 Left null space가 의미하는 것이 바로 우리가 잘 알고 있는 법칙인 키르히호프의 전류 법칙(Kirchhoff's current law)이다. 

 

이렇게 전체 그림을 보니 뭔가 떠오르는 것이 있을 것이다. 바로 Lecture 10에서 배웠던 4개의 주요 부분 공간(four fundamental subspaces)이 보일 것이다. 4개의 주요 부분 공간이 우리가 지금껏 전자회로의 그래프 모델에서 찾고자 하는 것과 정확히 일치한다. 즉 어떤 실제 응용문제에 대한 사각 행렬을 정의했을 때, 우리가 찾고자 하는 구조나 관계가 A와 A transpose를 통해 설명되어진다. 4개의 주요 부분 공간을 잘 이해하는 것이 굉장이 중요하다. 

 

 

이제 A transpose의 null space인 Left null space를 구해보자. 앞서 언급했듯이 이 응용문제에서 left null space가 의미하는 것은 키르히호프의 전류 법칙이라고 했다. 이를 다시 상기시켜보면 "전자(전기)회로에서 어떤 분기점을 기준으로 들어온 전류의 양과 나간 전류의 양은 같다" 이다. 이것이 Left null space의 식과 어떻게 연관되는지 살펴보자. 비교해보기 좋기 위해 그래프와 식을 다시 써보자. 

 

 

 

 

식 (10)의 화살표 부분의 row1을 보자. -y1-y3-y4=0이다. 음의 부호(-)는 node에서 전류가 흘러나가는 것을 의미한다. 즉 node1에서 전류가 다른 곳으로 나가는 edge1, edge3, edge4를 각각 의미한다. row1이 의미하는 것은 node1에서 흘러나간 전류의 총 합은 0이다. 이 말은 물리학에서 알짜힘(net force)과도 같은 말인데, 정지하고 있는 물체가 계속 정지할 수 있는 것은 물체에 작용하는 알짜힘이 0이기 때문이다. 즉 물체에 작용하는 다양한 힘 벡터의 크기가 물체에 작용하는 것이 0이기 때문에 물체가 계속 정지해 있는 것이다. 마찬가지로 node1에 흐르는 알짜 전류(net current)가 0이라는 뜻이다. 쉽게 말하면 "들어온만큼 나간다"이다. 만약 node1이 커패시터라고 했을 때, 알짜 전류가 0이 아니라면, 예를 들어 들어온 전류보다 덜 나간다면 커패시터는 터지고 말 것이다. 그러나 회로에는 들어온만큼 나가는 법칙이 존재하기 때문에 커패시터가 터지지 않고 잘 작동하는 것이다. 전류는 node에 쌓이지않고 계속 흘러서 돌아다닌다. (물론 커패시터는 충/방전을 통해 잠시 쌓이긴 하지만 말이다..)

 

row2를 보면 y1-y2=0인데, y2를 이항하면 y1=y2이다. 즉 node2에 흘러들어온 전류 y1과 node2에서 흘러나가는 전류 y2는 같다. 

row3는 y2+y3-y5=0인데, 역시 이항하면 y2+y3=y5이다. node3로 흘러들어오는 전류y2와 y3의 합은 node3에서 흘러나가는 전류 y5와 같다. 

마지막 row4를 보면 node4로 흘러들어가는 y4와 y5의 총 합이 0이다. 이렇듯 Left null space의 식 (10)은 "들어온만큼 나간다"는 키르히호프의 전류의 법칙을 잘 설명해주고 있다. 이것은 결국 평형방정식(balance equation)이다. 

 

 

이제 Left null space의 해(solution)를 구해보자. 어떻게 구할 수 있을까? 물론 지난 강의에서 배운대로 소거(elimination)를 통해 row reduced echelon form을 만들고 pivot과 free variable을 구하면 special solution을 구할 수 있고 결국 null space를 계산할 수는 있을 것이다(Lecture 7참고). 그러나 이런 실제 예제에서 우리는 소거를 하지 않고도 null space의 해를 구할 수 있다. 키르히호프의 전류 법칙을 잘 이해하면 Left null space의 기저(basis)를 어렵지 않게 구할 수 있다. 바로 Loop 단위로 node들 사이에 edge로 표현된 전류의 흐름을 따져서 기저를 구하는 방법이다. 

 

우선 Left null space의 차원은 식 (9)에 따라 2이다. 따라서 기저는 두 개의 special solution이어야 한다. 

먼저 node1, node2, node3에 걸쳐 형성된 Loop1을 보자. 방향은 처음에 정하기 나름이므로 y1을 1로 정하자. 그 다음 y2는 1일까? -1일까? y2=1이어야 한다. 왜냐하면 node1에서 출발한 전류가 node2를 거쳐 node3로 흘러가는 것이기 때문이다. 또는 식 (10)의 row2에 의해 y1=y2 이기때문에 1로 설정해야 한다. 

y3는? -1이다. 왜일까? Loop1에서 보자면 node1에서는 1만큼의 전류가 흘러나갔다. 키르히호프의 전류법칙에 따르면 전류가 나간 만큼 들어와야 하기 때문에 y3로는 전류가 들어와야 한다. 또한 우리는 현재 node3에 와 있다. 그런데 y3는 node3 입장에서 들어오는 전류이다. 지금까지 node 입장에서 나가는 전류를 1로 설정했기 때문에 y3는 -1로 설정해야 한다. loop1을 기준으로 기저를 찾고 있기 때문에 y4와 y5는 0으로 만들어준다. 이렇게 해서 첫 번재 special solution인 Left null space는 y=[1, 1, -1, 0, 0] 이다. 식 (10)의 row1, 2, 3, 4를 통해 검산해보면 special solution이 맞는지 확인할 수 있다. 

 

두 번째 special solution은 loop2를 기준으로 구해보자. 이번엔 y3=1, y5=1, y4=-1이고 나머지는 y1=0, y2=0이다. 따라서 y=[0, 0, 1, -1, 1]이다. 역시 식 (10)을 통해 검산해보도록 하자. Left null space의 기저(basis)는 아래와 같다. 

 

 

 

그런데 loop1과 loop2말고 node1, node2, node3, node4에 이르는 큰 loop가 기저가 될 수 있지 않을까? 하는 생각을 할 수도 있다. 우선 해를 구해보자. y1=1, y2=1, y5=1와 같이 설정하고 y3=0이다. 마지막으로 y4=-1로 설정하면 아래와 같은 큰 loop에 대한 left null space의 해가 구해진다. 

 

 

그렇다면 (12)에 있는 해를 세 번째 기저로 쓸 순 없을까? 그럴 수 없다. (11)의 두 special solution을 더하면 (12)가 된다. 즉 dependent한 해이기 때문에 사용할 수 없다. 

 

이렇게 해서 A의 Left null space의 해를 구하였다. 비록 소거(elimination)를 이용하여 해를 구하진 않았지만 키르히호프의 전류 법칙(Kirchhoff's Current Law)을 이해하고 이를 이용하여 해를 구할 수 있었다. 

 

 

- Graph without a loop: TREE

 

A transpose의 column space인 row space를 한 번 살펴보자. 앞서 row space의 차원은 rank=3임을 알았다. 차원, 즉 rank=3이라는 것은 A transpose를 소거하여 row reduced echelon form을 만들었을 때 pivot column이 3개이고 free column이 2개라는 소리다. 그렇다면 처음 3개의 col1, col2, col3가 pivot column일까? 그렇지않다. 왜냐하면 col1+col2=col3이기 때문이다. 즉 처음 세 개의 column은 독립(independent)이 아니다. 이들은 loop(col1=edge1, col2=edge2, col3=edge3)에서 왔기 때문이다. 따라서 pivot column은 col1, col2, col4이다. 

 

 

 

 

서로 독립(independent)인 이들 pivot column에 해당되는 edge들만 초록색 line으로 굵게 표시하였다. 독립인 column에 대한 edge들만 연결하니 원래 있던 loop가 없어졌다. 이렇게 loop가 없는 형태의 그래프를 우리는 TREE라 한다. 원래 그래프가 가지고 있던 모든 종속(dependency)성질은 loop로부터 왔다. 그러나 loop가 없어졌기 때문에 독립인 그래프인 TREE가 된 것이다.

 

 

 

3. 마치며

 

모든 그래프들에 대해서 node와 edge, 그리고 loop의 관계에 대해서 하나의 식으로 정리하자면 다음과 같다. 

 

 

어떤 그래프에서 loop의 개수는 edge의 개수에서 node의 개수-1과 같다. 여기서 nodes-1은 rank를 의미하는데, 그래프의 Incidence matrix에서 항상 rank=n-1이기 때문이다. n은 column의 개수이고 1개의 column은 종속이므로 1을 빼주면 rank(=dimension)가 된다. 

edge의 수는 Incidence matrix에서 row의 수와 같다. 즉 #edge=m이다. 결국 이 식이 의미하는 것은 어떤 그래프에서 독립적인 loop의 개수는 그래프의 Incidence matrix의 left null space와 같다. 사실 이 공식을 약간 다르게 쓰면 오일러의 공식(Euler's Formula)이 된다. 

 

 

이 오일러의 공식은 어떠한 그래프에도 적용되는 위상기하학(topology)의 하나의 사실이다이다. 우리가 예를 들었던 그래프에 적용하여 확인해보면 4-5+2=1임을 확인할 수 있다. 어떠한 그래프를 그려서 확인해도 마찬가지이다. 이는 그래프의 node와 edge, 그리고 loop에 대한 관계를 이해함에 있어 유용하게 사용될 수 있는 공식이다. 

 

 

마지막으로 위에서 살펴봤던 그래프 모델과 선형대수의 부분 공간과의 관계도에 대한 그림을 다시 보자. 

 

 

 

최초에 각 node에서의 potential을 x로 정의하고 여기에 Incidence Matrix A를 곱해 potential difference를 만들었다. 이것을 e라고 하자. e=Ax

그 다음 potential difference에 C를 곱해 current y와의 관계를 정의했다. y=Ce

마지막으로 A의 transpose를 y에 곱하여 키르히호프의 전류 법칙을 정의했다. 이를 정리하면 아래와 같다. 

 

 

사실 이 과정이 어떤 공식으로 부터 나온 것들은 아니다. 전자 회로를 그래프 모델로 정의한 후 선형 대수 이론을 적용하여 키르히호프 법칙까지 유도해낸 과정이다. 이 과정에서 지난 시간에 배운 네 개의 주요 부분 공간에 대한 이론이 적용되었다. 어떤 실제 문제에 선형 대수 등의 수학 이론을 적용하는 응용 수학의 전반적인 과정이라고 보면 된다. 

 

사실 이 과정에 실제 전자 회로처럼 여러 branch(배터리, 저항 등)들을 추가할 수 있다. 배터리를 추가한다면 위의 과정에서 실제 potential difference가 생겨날 것이고, 마지막에 가서는 키르히호프 법칙에 대해서 0이 아닌 어떤 전류값 f가 우변에 위치할 것이다. 즉

 

 

 

위의 (16)과 (17)에 있는 식을 한 번에 써보자. 

 

 

이것이 어떤 실제 문제에 수학을 적용할 때 사용되는 응용 수학의 기본 공식이다. 마지막 식 (18)이 의미하는 것은 결국 평형방정식(balance equation)에 대한 내용이다. 

 

 

사실 강의에서 대략적인 내용은 이해했지만 마지막 부분을 완벽하게 이해하기는 조금 어렵다. 아무래도 물리학에 대한 공부를 좀 더 하면 이해가 될까 싶은데, 일단 이러한 것이 있다 정도만 알아두도록 하자. 자세한 내용이 궁금하신 분은 아래 링크에서 확인하시면 됩니다. 

Lecture 12 MIT Linear Algebra

 

전자회로에 대한 깊이 있는 이해가 없어서 고생을 많이 했네요 ㅠㅠ 이상으로 포스팅을 마칩니다.