Introduction
이번에 선형대수를 공부하면서 내용을 정리해보았습니다.
강의 영상 : https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/video_galleries/video-lectures/
Video Lectures | Linear Algebra | Mathematics | MIT OpenCourseWare
This section contains a complete set of video lectures on linear algebra along with transcripts and related resource files.
ocw.mit.edu
스터디 github : https://github.com/jwkweon/study-linear-algebra
GitHub - jwkweon/study-linear-algebra
Contribute to jwkweon/study-linear-algebra development by creating an account on GitHub.
github.com
참고한 블로그 :
Lecture 12: Graphs, networks, incidence matrices
Lecture 12: Graphs, networks, incidence matrices (5/18) - 이번은 강의 12번째이다. 좋아. 우리는 12...
blog.naver.com
[Linear Algebra] Lecture 12 그래프와 네트워크(Graph and Network), 근접 행렬(Incidence Matrices)
이번 포스팅에선 선형 대수의 응용에 대한 이야기를 할까 한다. 선형 대수를 공부하면서 한 번쯤은 "이것들이 어디에 사용될까?" 하는 의문을 가져본 적이 있을 것이다. 선형 대수는 실제로 너무
twlab.tistory.com
(주로 https://twlab.tistory.com/29블로그의 사진과 내용을 보면서 공부했고 추가로 나머지 블로그를 참고하였습니다.)
(저는 제가 이해하기 쉽게 요약해서 적었으므로 좀더 자세히 공부하고싶다면 위 블로그를 참고하시면 됩니다.)
그래프(Graph)
이산 수학(discrete mathematics)에서의 그래프는 어떤 네트워크 형태의 구조를 의미한다.
즉, 어떤 객체(object)들과 그들을 연결짓는 선(Line)을 통해 그들 사이의 관계를 나타내는 구조를 의미한다.
여기서, 각 객체를 노드(node)라 하고 각 노드들을 연결하는 선을 에지(edge)라 한다.
응용수학(Applied mathematics)에서 가장 중요한 모델 중 하나이며, 이산(discrete)적 형태를 띄고 있다.
그래프의 형태는 다음과 같다.
에지는 방향을 가지거나 방향을 가지지 않는 경우도 있다.
방향이 있는 에지로 구성된 그래프를 directed graph라 하며 위의 그래프와 같다.
방향이 없는 에지로 구성된 그래프를 undirected graph라 한다.
근접 행렬(Incidence Matrix)
위의 그래프의 노드와 그들을 연결한 에지들 간의 관계를 행렬로 나타낼 수 있다. 이러한 행렬을 근접행렬이라 한다.
위의 그림에서 노드의 개수가 4개이고 이것을 행으로, 에지의 개수가 5개이고 이것을 열로 정하면, 4x5의 근접행렬을 만들 수 있다. 이때, 에지는 방향을 가지고 있기 때문에, 에지에서 -1을 출발점, 1을 끝점으로 지정한다.
따라서, 근접행렬 A는 다음과 같다. (node1 = n1, node2 = n2, node3 = n3, node4= n4라 하겠다.)
$$ \begin{matrix} n1 & n2 & n3 & n4 \end{matrix}$$
$$A= \begin{bmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ 0 & 0 & -1 & 1 \end{bmatrix} \begin{matrix} edge1 \\ edge2 \\ edge3 \\ edge4 \\ edge5 \end{matrix} $$
row1을 해석해보면 edge1은 n1이 출발점, n2가 끝점이다. 따라서, 방향은 node1 -> node2를 가리킨다.
col1을 해석해보면 node1을 끝점으로 삼고있는 edge는 edge1, edge3, edge4이며, 이 3개의 edge가 node1과 연결되어있다.
또한, node들끼리 연결되다 보면 어떤 모양을 만들게 된다. 위의 그림은 3개의 n각형(작은 삼각형 2개, 큰 사각형 1개)을 만들게 되었다.
이러한, node들이 연결되어 만든 부분 그래프(subgraph)를 Loop라고 한다.
위의 그림에서는 3개의 n각형이 3개의 Loop라고 보면 된다.
즉, node1 - node2 - node3가 Loop1(왼쪽 삼각형)을 만들고, node1 - node3 - node4가 Loop2(오른쪽 삼각형)를 만들고, node1 - node2 - node3 - node4가 큰 Loop3(전체 큰 사각형)를 만든다.
(위의 그림에서 Loop3은 생략된거같다.. 똑같이 크게 Loop3를 그려주면됨)
이제, Loop를 고려하여 행렬A를 써보자. Loop가 행렬에서 어떤 특성을 가지는지 봐보자.
$$ \begin{matrix} n1 & n2 & n3 & n4 \end{matrix} \quad \quad \quad $$
$$A= \begin{bmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ 0 & 0 & -1 & 1 \end{bmatrix} \begin{matrix} edge1 & loop1 \\ edge2 & loop1 \\ edge3 & loop1\\ edge4 \\ edge5 \end{matrix} $$
loop1에 해당되는 node만 봐보자. loop1에 해당되는 row1, row2, row3은 종속(dependent)이다.
따라서, 어떤 그래프의 loop에 대한 근접행렬(Incident matrix)의 row들은 선형 종속(linearly dependent)의 특성를 갖는다.
전자회로의 그래프 모델링(Graph modeling of an electronic circuit)
솔직히 이부분이 갑자기 선형대수에 나와서 조금 놀랬다. 본인은 전자공학과여서 전자회로를 배웠기 때문에 이해가 잘되는 부분이여서 생략하면서 설명하지만, 잘모른다면 회로이론에 대해 검색해서 공부해보길 바란다.
만일, node가 100개이고 edge가 180개인 근접행렬을 생각해보자. 이 근접행렬에는 엄청나게 많은 0을 가지게 될 것이다.
왜냐하면, row 한개당 -1, 1 한개만을 값을 가지기 때문이다.
따라서, 이러한 행렬의 크기에 비해 원소가 적은 비율로 나타나는
즉, 희소(Sparse)한 원소를 가지게 되는 행렬을 희소행렬(Sparse matrix)이라 한다.
이러한 희소행렬은 내부적으로 어떤 구조(structure)가 형성된다. 즉, 위의 그래프처럼 구조가 나타날 것이고, 이러한 구조를 파악하기 위해 우리는 선형 대수적으로 행렬을 분석할 수 있다. 이에 대한 첫번째 방법이 근접행렬의 Null space를 찾는 것이다.
Null space라는 것은 어떤 행렬의 column vector들의 선형 조합을 통해 0을 만드는지 알려준다.
만약, column vector들이 독립이라면, Null space는 오직 영벡터만이 존재한다. 종속이라면, 해들의 집합이 발생한다.
따라서, Node를 나타내는 column들이 독립인지 종속인지 알 수 있게된다.
이제, Null space를 구해보자.
$$Ax= \begin{bmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ 0 & 0 & -1 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = \begin{bmatrix} x_2 - x_1 \\ x_3 - x_2 \\ x_3 - x_1 \\ x_4 - x_1 \\ x_4 - x_3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} $$
위의 행렬이 무엇이 나타내는지 해석해보자. 위의 그래프를 전자 회로라고 생각해보자.
이렇게 되면, 각 node들은 각 지점에서 전압(potentials)을 나타낼 것이다. 그리고 각 node에 대응하는 변수가 $x_1$, $x_2$, $x_3$, $x_4$이며 이것들이 실제 전압값이 될 것이다.
또한, 위의 식에서$x_2 - x_1$과 같이 각 node들의 차이는 전압의 차가 되고 이것을 우리는 전위차(potential differences)라고 한다.
이제, 우리가 구하려는 Null space는 모든 node들의 전위차가 0이되는지를 찾아야한다.
일단, x가 0이면 전위차가 당연히 다 0일 것이다. 이러한 경우는 그냥 회로에서 전류가 흐르지 않는다는 의미라 의미가 없다. 그러므로 회로에 전류가 흐른다고 가정하고 x의 값, Null space를 구해야 한다.
일단, A의 column이 종속이기 때문에(by loop) 해가 있을 것이다. 생각해보면, 각 row당 -1과 1이 한번씩 나온다.
그러면 row가 5개이므로 -1도 5개 1도 5개이다. 따라서, 그냥 모든 column들을 다 더하면 0이 될 것이다.
즉, $x_1=1$, $x_2=1$, $x_3=1$, $x_4=1$이 해가 될 것이다.
여기서 x가 1로만 이루어진 벡터라는 것은 각 node의 전압이 일정하다는 것을 의미한다.
각 node의 전압이 일정하기 때문에 전압차이가 없을 것이기 때문에 모든 node의 전위차는 0이 될 것이다.
이것이 Ax=0인 Null space의 해이다. 따라서, 위에서 구한 x에 상수 c를 곱한 형태가 Null space가 될 것이다.
결국, Null space는 4차원 공간상에 존재하는 1차원의 line이 될 것이다. 그리고, 이때의 Null space의 기저(basis)는 x=[1, 1, 1, 1]이 될 것이다.
$$ N(A) = x = c \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} $$
그렇다면, 위에서 Null space가 의미하는 것은 무엇인가?
전자회로를 공부한 입장에서 모든 node의 전압이 같다는 것은 전류가 흐르지 않는다는 뜻이다.
전자(electron)은 높은 전압에서 낮은 전압으로 이동하게되고 이때, 전류가 흐른다. 즉, 높은전압-낮은전압 = 전위차가 되고, 전위차가 0이면 전류가 흐르지않는다. 따라서, 전압이 다 같아버리면 전자는 자기자리에 그대로있게 되고 전류는 흐르지 않는다.
결국 위의 그래프 모델에서는 모든 node들의 전압을 올리거나 내릴 수 있는 단, 하나의 파라미터(parameter)만이 존재하는 것이다.
이러한 경우에 전류를 흐르게 하기위해, 전자회로에서는 접지(Ground)가 반드시 있으며, 전압이 0인 지점을 말한다.
이렇게 해야 전압을 5를 걸어주면 전압이 0인 접지는 무조건 낮은 전압이므로 전위차가 생기고 큰 전압에서 작은 전압으로 전자가 이동하여 전류가 흐르게 된다.
그렇다면, 아무대나 접지로 만들고 풀어보자. $x_4=0$으로 하여 node4를 접지로 만들자.(어디를 접지로 잡든 상관없다)
$$ Ax = x_1 \begin{bmatrix} -1 \\ 0 \\ -1 \\ -1 \\ 0 \end{bmatrix} + x_2 \begin{bmatrix} 1 \\ -1 \\ 0 \\ 0 \\ 0 \end{bmatrix} + x_3 \begin{bmatrix} 0 \\ 1 \\ 1 \\ 0 \\ -1 \end{bmatrix} + 0 \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \\ 1 \end{bmatrix} $$
이렇게 node 한개를 접지로 만들고 나머지 3개의 node를 이용해 해를 구하는 것이 가능한 이유는 근접 행렬의 Rank=3이기 때문이다. 앞서 우리는 행렬 A의 Null space를 구했고, Null space의 차원이 1임을 알았다.
따라서, Null space의 차원은 n-r이고, n=4이므로 4-r=1이므로, r=3임을 알 수 있다.
즉, Rank=3이란 뜻은 pivot column이 3개이고, free column이 1개이므로, free variable을 1이나 0으로 두고 풀어도 되기 때문이다. 그리고 이를 통해, col1, col2, col3가 독립(independent)임도 알 수 있다.
키르히호프의 전류 법칙 그리고 A의 전치행렬의 Null space
A의 전치(transpose)의 Null space를 계산하는게 의미가 있는 경우가 많다.
$N(A^T)$는 회로이론의 키르히호프의 전류 법칙(Kirchhoff's current law)와 관련이 있다.
일단, $A^T$의 Null space 즉, A의 Left Null space를 구해보자.
$$ A^T y = \underset{4 \times 5}{\begin{bmatrix} -1 & 0 & -1 & -1 & 0 \\ 1 & -1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & -1 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix}} \underset{5 \times 1}{\begin{bmatrix} y_1 \\ y_2 \\ y_3 \\ y_4 \\ y_5 \end{bmatrix}} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} = 0$$
일단, 앞에서 배웠듯이 Left Null space의 차원을 바로 알 수 있다.
A의 Rank=3이기 때문에, Left Null space의 차원은 m-r이므로 m=5여서 5-3=2라 Left Null space의 차원이 2차원임을 알 수 있다.
이제, 차원은 찾았으니 기저(basis)도 당연히 찾아야 할 것이다.
그전에 이러한 각 공간들이 전자회로에서 무엇을 의미하는지에 대한 관계는 다음과 같다.
일단, Column space와 Null space의 의미는 알았으니 넘어가겠다.
여기서, C행렬은 전위차와 전류 사이를 연결시켜주는 행렬이라고 하자. C행렬은 우리가 알고 있는 옴의 법칙으로 생각 할수 있다.
Row space에서 정의한 y는 회로에 흐르는, 그래프에서 edge에 흐르는 전류(current)를 나타낸다.
Left Null space는 키르히호프의 전류 법칙(Kirchoff's current law)를 의미한다.
키르히호프의 전류 법칙은 어떤 한노드를 기준으로 들어오고 나가는 전류의 합은 항상 같다.
예를들어 나가는 전류가 2개고 각각 a, b라하고 들어오는 전류가 3개고 각각, c, d, e라 하고, 들어오는 전류의 부호를 +, 나가는 전류의 부호를 -로 정하면 다음과 같이 키르히호프의 전류 법칙이 만족한다.
a + b = c + d + e 로 봐도 되고, 만약 좌변으로 전류의 값을 몰은다면 내가 정했던 부호에 의해 다음과 같이
- a - b + c + d + e = 0 으로 봐도 된다.
위의 그래프에서 Node 1에 키르히호프의 전류법칙을 적용시켜보자.
나가는 전류는 y1, y3, y4이다. 들어오는 전류는 없다.
따라서, y1 + y3 + y4 = 0 이다. 여기서, 의문이 들것이다 들어오는 전류가 없는데 왜 나가는 전류가 생기는것이냐..
이노드를 건전지라고 생각하자, 건전지는 전류를 보내는 역할, 즉, current soruce, 전류를 생산하는 Node라 생각하자.
따라서, 건전지가 자기가 가지고있는 전류를 모두 내보냈으니 가지고있는 전류가 0이 됬다고 생각하면 된다.
이제, Left Null space 식으로 한번 봐보자.
$$ A^T y = \begin{bmatrix} -1 & 0 & -1 & -1 & 0 \\ 1 & -1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & -1 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \\ y_4 \\ y_5 \end{bmatrix} = \begin{bmatrix} -y_1 -y_3 - y_4 \\ y_1 -y_2 \\ y_2 + y_3 - y_5 \\ y_4 + y_5 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} $$
위 식에서 보면 $-y_1 -y_3 -y_4 = 0$ 즉, 위에서 본 식이 나왔다. 여기서 부호가 +에서 -로 바뀌었는데 뭐가되든 상관없다. 내가 나가는 전류의 부호를 +로 하든 -로 하든 실제 전자회로에서는 일관성있게 풀면은 정답이 나오기 때문이다.
마찬가지로 $y_1 - y_2 =0 $ 이부분은 원래 A의 row2 즉, Node2의 키르히호프의 전류법칙이다. 들어오는 전류를 + 나가는 전류를 - 로 보면 된다. 나머지 Node도 마찬가지이다. 즉, Left Null space가 키르히호프의 전류법칙을 나타냄을 알 수 있다.
이제, Left Null space의 해를 구해보자.
우리가, 여태까지 배웠던 방식으로 해를 구하면 된다.
하지만, 다른 방법으로 풀어보자. 바로 Loop 단위로 node들 사이에 edge로 표현된 전류의 흐름을 따져서 기저를 구하는 방법이다. 일단, Left Null sapce의 차원은 m-r인 5-3이기 때문에 차원이 2이다. 따라서, 2개의 기저 special solution이 나올 것이다. 일단, Node1, Node2, Node3을 거치는 Loop1을 보자. 일단, Node1에서 y1을 나가는 전류로 보고 y1=1로 하자.
그러면, y2도 1이 될 것이다. 그다음, y3은 반드시 -1이되어야한다. 우리는 Loop1을 보기때문에 y4,y5=0 즉, 이쪽으로는 전류가 안흐른다고 생각하자. 그렇다면 키르히호프의 법칙에 의해서 Node1에서 나가는 전류가 y1에 1이 있으므로 y3은 반드시 들어오는 전류인 -1이 되어야한다. 따라서, Loop1을 통해 찾은 기저는 y=[1, 1, -1, 0, 0]이다.
Loop2에서도 마찬가지로 y1=0, y2=0으로 두고 풀면 다음과 같이 2개의 기저가 나온다.
(다시, 말하지만 내가 정한 기준을 일관성있게 적용하면 전자회로는 풀린다. y1을 들어오는 전류라 생각하고 y1=-1로 해도 다 일관성있게 풀면 똑같이 답이 나온다)
$$ \begin{bmatrix} 1 \\ 1 \\ -1 \\ 0 \\ 0 \end{bmatrix}, \quad \begin{bmatrix} 0 \\ 0 \\ 1 \\ -1 \\ 1 \end{bmatrix} $$
여기서, 큰 Loop3도 생각해볼 수 있지않을까? 대충 예상해보면 위의 두 기저에 종속일 것이다.
한번 구해보자, y3=0으로 설정하고 풀면 다음과 같은 y가 나온다.
$$ \begin{bmatrix} 1 \\ 1 \\ 0 \\ -1 \\ 1 \end{bmatrix} $$
위의 2개의 기저를 더하면 나오는 값이다. 따라서, 종속(dependent)이다.
마지막으로 다음 식을 Left Null space 식을 다시 봐보자.
$$ A^T y = \begin{bmatrix} -1 & 0 & -1 & -1 & 0 \\ 1 & -1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & -1 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \\ y_4 \\ y_5 \end{bmatrix} = \begin{bmatrix} -y_1 -y_3 - y_4 \\ y_1 -y_2 \\ y_2 + y_3 - y_5 \\ y_4 + y_5 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} $$
우리는 Left Null space가 Rank=3임을 안다. 그렇다면 pivot column이 3개 일 것이다.
그렇다면 처음 3개 col1, col2, col3가 pivot column일까? 아니다. 왜냐하면 col1+col2=col3이기 때문이다.
잘 보면 col1, col2, col3는 같은 Loop1에 있는 edge1, edge2, edge3이다.
따라서, pivot column은 col1, col2, col4이며, 이 3개는 서로 독립(independent)이다.
위 그림에서, pivot column인 edge만 녹색으로 표시했다.
서로 독립인 pivot column들만 보면, Loop가 만들어지지 않는다.
즉, 이렇게 Loop가 없는 형태의 그래프를 우리는 TREE라고 한다.
원래 그래프가 가지고 있던 모든 종속성질은 한 Loop로 부터 왔다. 그러나 Loop가 없어졌기 때문에 독립인 그래프인 TREE가 된 것이다.
결론
Loop의수 = edge의수 - (node의수 -1) 이다.
여기서, node의수 -1은 Rank를 의미하는데, 왜냐하면 그래프의 근접행렬에서 항상 Rank=n-1이기 때문이다. (node의 수 = n)
따라서, 위의 Loop의수 = m - r이 되고, 결국 Loop의 수는 Left Null space의 차원이 된다.
Left Null space의 차원 = m -r = Loop의수 = edge의수 - (node의수 -1)
그리고 위의 식을 약간 다르게 쓰면 오일러의 공식(Euler's Formula)이 된다.
node의수 - edge의수 + Loop의 수 = 1
위의 오일러의 공식은 어떠한 그래프에도 적용되는 위상기하학(topology)의 하나의 사실이다.
즉, 어떤 그래프에도 저 식이 만족하다는 것이다.
또한, 그래프에서 우리는 각 node의 전압을 x로 그다음 근접행렬 A를 곱해 전위차를 만들었다. 이렇게 만든 전위차를 e라하자.
x : 전압
↓
e = Ax : 전위차
그런 다음 전위차에 C를 곱해 전류를 만들었다.
↓
y= Ce : 전류
그런 다음 A의 전치를 전류에 곱해 키르히호프의 전류법칙을 만들었다.
↓
$A^T y = 0$ : 키르히호프의 전류법칙
참고로, 실제 배터리, 저항등이 edge에 생긴다면, 키르히호프의 전류법칙에서 우변은 0이 아닌 어떤 전류값 k가 생길 것이다. $A^T y =k $
이제, 위의 식을 한번에 다써보면,
$$ A^T C A x = k$$
즉, 위의 식이 어떤 실제 문제에 수학을 적용할 때 사용되는 응용 수학의 기본 공식이다. 마지막 식이 의미하는 것은 결국 평형방정식(balance equation)에 대한 내용이다.
솔직히, 잘이해가안되는 부분이긴하지만 문제로 한번 풀어봐야 완전히 이해가 될 거 같다. 왜냐하면 회로이론을 공부할 때는 voltage source(배터리, 직류전압공급장치), 저항, 커패시터, 인덕터를 고려하여 풀기 때문에 위의 그래프의 전자회로는 이러한 parameter가 없다는 가정으로 푸니깐, 물리적으로 이해가 안되긴한다.
