연결 강의: MIT 18.06 Linear Algebra - Lecture 11: Matrix spaces; rank 1; small world graphs 연결 강의: MIT 18.06 Linear Algebra - Lecture 12: Graphs, networks, incidence matrices

1. 4대 부분공간의 정의와 차원 (The Big Picture)

$m \times n$ 행렬 $A$는 입력 공간 $\mathbb{R}^n$과 출력 공간 $\mathbb{R}^m$ 내에 4개의 핵심적인 부분공간(Subspace)을 정의한다.
이를 이해하는 것이 선형대수학의 기본 정리(Fundamental Theorem of Linear Algebra)의 핵심이다.

• 열공간과 좌영공간이 서로 직교
  • 열공간의 벡터(A의 한 열)과 좌영공간의 벡터 $y \in N(A^T)$ 의 직교: $A^Ty=0$
  • 열공간이므로, $A^T$ 로 표기. ($A^T$ 의 한 행 = $A$ 의 한 열)

$$\mathbb{R}^m = C(A) \oplus N(A^T)$$

• 행공간과 영공간이 서로 직교
  • 행공간의 한 벡터(행)는 $Ax=0$의 해와 내적이 0

$$\mathbb{R}^n = C(A^T) \oplus N(A)$$

1) 열공간 (Column Space, $C(A)$)

• 정의: 행렬 $A$의 열벡터들의 선형 결합(Linear Combination)으로 생성되는 공간.

• 위치: $\mathbb{R}^m$의 부분공간.

• 차원: $r$ (랭크, Rank).

• 의미: $Ax=b$가 해를 가질 수 있는 $b$의 집합.

2) 영공간 (Null Space, $N(A)$)

• 정의: $Ax=0$을 만족하는 모든 해 $x$의 집합.

• 위치: $\mathbb{R}^n$의 부분공간.

• 차원: $n - r$ (변수의 개수 - 랭크).

• 의미: $Ax=0$의 해공간. 행공간과 수직(Orthogonal)이다.

3) 행공간 (Row Space, $C(A^T)$)

• 정의: 행렬 $A$의 행벡터들의 선형 결합으로 생성되는 공간. 벡터 표기의 통일성을 위해 $A^T$의 열공간으로 취급한다.

• 위치: $\mathbb{R}^n$의 부분공간.

• 차원: $r$ (랭크).

• 핵심 성질: 행공간의 차원과 열공간의 차원은 항상 같다 (Row Rank = Column Rank).

4) 좌영공간 (Left Null Space, $N(A^T)$)

• 정의: $A^T y = 0$을 만족하는 모든 $y$의 집합.

  • 식을 전치하면 $y^T A = 0^T$가 되며, 벡터 $y$가 $A$의 왼쪽(Left)에서 곱해지므로 ‘좌영공간’이라 부른다.

• 위치: $\mathbb{R}^m$의 부분공간.

• 차원: $m - r$ (행의 개수 - 랭크).

• 의미: 열공간과 수직(Orthogonal)이다.

---

2. 각 공간의 기저(Basis) 구하는 법

행렬 $A$를 가우스 소거법을 통해 기약 행사다리꼴(RREF) $R$로 만들면, 4대 공간의 기저를 명확히 찾을 수 있다.

$A \xrightarrow{\text{Gauss-Jordan}} R$

1) 행공간 $C(A^T)$의 기저

• 방법: $R$의 0이 아닌 행(Nonzero rows)들을 선택한다.

• 이유: 기본 행 연산(Row operation)은 행들의 선형 결합이므로, $A$의 행공간을 보존한다. 즉, $C(A^T) = C(R^T)$이다. $R$의 행들은 가장 간단하고 독립적인 형태이다.

2) 열공간 $C(A)$의 기저

• 방법: $A$의 피벗 열(Pivot columns)들을 선택한다.

• 주의: $R$의 피벗 열을 선택하면 안 된다. $C(A) \neq C(R)$이기 때문이다. $R$에서 피벗이 있는 열의 인덱스(위치) 를 확인하고, 반드시 원래 행렬 $A$ 의 해당 열을 가져와야 한다.

3) 영공간 $N(A)$의 기저

• 방법: $Ax=0$ (혹은 $Rx=0$)의 특수 해(Special solutions)들을 선택한다.

• 과정: $n-r$개의 자유 변수(Free variable)에 대해, 하나는 1, 나머지는 0을 순차적으로 대입하여 구한다.

4) 좌영공간 $N(A^T)$의 기저

• 방법: 가우스-조르단 소거법을 확장하여 찾는다.

  $[A \ | \ I] \xrightarrow{\text{Elimination}} [R \ | \ E]$

  • 여기서 $E$는 $A$를 $R$로 만드는 기록 행렬이다 ($EA=R$).

  • $R$의 아래쪽 $m-r$개 행은 모두 0이다 (Zero rows).

  • 즉, $E$의 아래쪽 행들이 $A$와 곱해져서 0을 만든 것이다.

• 결론: $E$의 마지막 $m-r$개의 행이 좌영공간의 기저이다.

---

3. 주요 예시 및 응용

예시 1: 랭크-1 행렬 (Rank One Matrices)

모든 랭크 1 행렬은 하나의 열 벡터 $u$와 하나의 행 벡터 $v^T$의 곱으로 표현된다.

$A = uv^T = \begin{bmatrix} u_1 \\ \vdots \\ u_m \end{bmatrix} \begin{bmatrix} v_1 & \dots & v_n \end{bmatrix}$

• 행공간: $v$ 벡터 1개가 기저가 된다. (차원 = 1)

• 열공간: $u$ 벡터 1개가 기저가 된다. (차원 = 1)

• 의미: 행렬의 모든 행은 $v^T$의 배수이며, 모든 열은 $u$의 배수이다.

예시 2: 그래프와 접속 행렬 (Incidence Matrix)

그래프 이론에서 노드(Node)와 엣지(Edge)의 관계를 나타내는 행렬 $A$는 4대 부분공간의 물리적 의미를 잘 보여준다.

• 행($m$): 엣지(Edge)의 개수

• 열($n$): 노드(Node)의 개수

• 성분: 엣지가 노드 $i$에서 $j$로 연결되면, 해당 행의 $i$열은 -1, $j$열은 +1.

(1) 영공간 ($Ax=0$)의 물리적 의미: 등전위

• $Ax=0$은 각 엣지 양 끝의 차이가 0이라는 의미 ($x_j - x_i = 0$).

• 이는 모든 노드의 **전위(Potential)**가 동일함을 뜻한다 ($x_1 = x_2 = \dots = c$).

• 연결된 그래프라면 영공간의 차원은 1이다 (상수 벡터 $c[1, 1, \dots, 1]^T$).

(2) 좌영공간 ($A^T y = 0$)의 물리적 의미: 키르히호프 전류 법칙 (KCL)

• $A^T y = 0$은 각 노드에서 들어오고 나가는 값의 합이 0이라는 의미.

• 이는 회로 이론의 **키르히호프 전류 법칙(KCL)**과 같다. (유입 전류 = 유출 전류).

• 좌영공간의 기저는 그래프 내의 **독립적인 루프(Loop)**를 따라 흐르는 순환 전류가 된다.

• 차원: $m - r = \text{Edges} - (\text{Nodes} - 1) = \text{Loops}$ (오일러의 공식과 연결됨).

---

4. 벡터 공간의 확장 (New Vector Spaces)

벡터 공간은 $\mathbb{R}^n$에 국한되지 않으며, 벡터의 정의(덧셈과 스칼라배에 닫혀있음)를 만족하는 모든 집합으로 확장될 수 있다.

• 행렬 공간 (Matrix Space, $M$): 모든 $3 \times 3$ 행렬의 집합도 벡터 공간이다.

  • 차원: $3 \times 3 = 9$.

• 부분공간 (Subspaces of $M$):

  • 상삼각행렬 (Upper Triangular): 대각선 아래가 0인 행렬. (차원 6)

  • 대칭행렬 (Symmetric): $A^T = A$인 행렬. (차원 6)

  • 대각행렬 (Diagonal): 상삼각행렬 $\cap$ 대칭행렬. (차원 3)

• 이러한 공간들에서도 기저(Basis)와 차원(Dimension)의 개념은 동일하게 적용된다.

---

5. 그래프와 네트워크: 실제 문제에서 나오는 행렬

12강은 그래프(Graph), 네트워크(Network), 접속 행렬(Incidence Matrix)을 통해 선형대수학이 실제 응용 문제에서 어떻게 등장하는지를 보여주는 강의이다.

앞에서 배운 영공간, 행공간, 열공간, 좌영공간은 임의로 만든 작은 행렬에서만 의미가 있는 것이 아니다. 실제 응용에서 나오는 행렬들은 보통 어떤 구조를 가지고 있으며, 그 구조를 이해하면 행렬의 부분공간도 훨씬 자연스럽게 해석된다.

대표적인 예가 그래프에서 나오는 접속 행렬이다.

그래프는 다음 두 요소로 이루어진다.

• 노드(Node): 점 또는 위치
• 엣지(Edge): 노드와 노드를 연결하는 선

그래프는 전기 회로, 수도관 네트워크, 인터넷 링크, 도로망, 웹페이지 연결 구조, 사람 간 관계망 등 다양한 문제를 모델링하는 데 쓰인다.

이번 강의에서는 전기 회로를 예시로 사용한다. 각 노드에는 전위(Potential)가 있고, 각 엣지에는 전류(Current)가 흐른다고 생각한다.

---

6. 그래프 예시와 접속 행렬

다음과 같은 그래프를 생각하자.

노드는 4개이다.

$$n = 4$$

엣지는 5개이다.

$$m = 5$$

각 엣지는 방향을 가진다고 하자. 방향은 실제 물리적으로 반드시 정해진 방향이라기보다는, 부호를 정하기 위해 임의로 정한 기준 방향이다.

강의에서 사용한 그래프의 엣지는 다음과 같이 잡을 수 있다.

• edge 1: node 1에서 node 2로 향함
• edge 2: node 2에서 node 3으로 향함
• edge 3: node 1에서 node 3으로 향함
• edge 4: node 1에서 node 4로 향함
• edge 5: node 3에서 node 4로 향함

이때 접속 행렬 $A$는 다음과 같이 만든다.

• 행(row): 엣지
• 열(column): 노드
• 엣지가 어떤 노드에서 나가면 $-1$
• 엣지가 어떤 노드로 들어오면 $+1$
• 해당 엣지와 관련 없는 노드는 $0$

따라서 접속 행렬은 다음과 같다.

$$A = \begin{pmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ 0 & 0 & -1 & 1 \end{pmatrix}$$

이 행렬은 $5 \times 4$ 행렬이다. 엣지가 5개이므로 행이 5개이고, 노드가 4개이므로 열이 4개이다.

중요한 점은 이 행렬이 매우 sparse하다는 것이다. 각 행은 하나의 엣지를 나타내므로 $-1$ 하나와 $+1$ 하나만 가지고 나머지는 모두 $0$이다. 따라서 각 행에는 정확히 두 개의 nonzero entry만 있다.

실제 응용에서 나오는 행렬들은 이런 식으로 구조를 가진다. 무작위로 만들어진 행렬이 아니라, 문제의 형태가 행렬의 구조에 반영되는 것이다.

---

7. 접속 행렬이 하는 일: 전위 차이를 계산한다

각 노드의 전위를 다음 벡터로 나타내자.

$$x = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix}$$

여기서 $x_i$는 node $i$의 전위이다.

이제 접속 행렬 $A$를 $x$에 곱하면 어떻게 될까?

$$Ax = \begin{pmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ 0 & 0 & -1 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix}$$

계산하면 다음과 같다.

$$Ax = \begin{pmatrix} x_2 - x_1 \\ x_3 - x_2 \\ x_3 - x_1 \\ x_4 - x_1 \\ x_4 - x_3 \end{pmatrix}$$

즉 $A$는 각 엣지의 양 끝 노드 사이의 전위 차이를 계산한다.

이를 물리적으로 해석하면 다음과 같다.

• $x$: 노드의 전위
• $Ax$: 엣지에서의 전위 차이

전류가 흐르는 원인은 전위 자체가 아니라 전위 차이이다. 모든 노드의 전위가 같다면 전위 차이가 없으므로 아무 일도 일어나지 않는다.

---

8. 접속 행렬의 영공간 $N(A)$

이제 영공간을 보자.

$$Ax = 0$$

이라는 것은 모든 엣지에서 전위 차이가 $0$이라는 뜻이다.

위에서 계산한 $Ax$를 사용하면 다음 조건들이 나온다.

$$x_2 - x_1 = 0$$ $$x_3 - x_2 = 0$$ $$x_3 - x_1 = 0$$ $$x_4 - x_1 = 0$$ $$x_4 - x_3 = 0$$

즉 모든 노드의 전위가 같아야 한다.

$$x_1 = x_2 = x_3 = x_4$$

따라서 해는 다음과 같다.

$$x = c \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix}$$

여기서 $c$는 임의의 상수이다.

따라서 영공간은 다음과 같다.

$$N(A) = \operatorname{span} \left\{ \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} \right\}$$

영공간의 차원은 $1$이다.

$$\dim N(A) = 1$$

이것은 물리적으로 “전위는 상수만큼 올리거나 내려도 전위 차이는 변하지 않는다”는 뜻이다.

예를 들어 모든 전위를 $10$만큼 올리면 각 노드의 전위값은 달라지지만, 두 노드 사이의 차이는 그대로이다. 전류는 전위 차이에 의해 결정되므로, 전체 전위에 상수를 더하는 것은 물리적으로 같은 상태를 나타낸다.

이것은 미적분에서 부정적분을 할 때 $+C$가 붙는 것과 비슷하다. 기준점을 정하지 않으면 절대적인 전위는 정해지지 않고, 차이만 정해진다.

---

9. Grounding: 기준 전위를 정하는 것

전위의 임의 상수를 없애려면 한 노드의 전위를 고정하면 된다. 이를 grounding이라고 한다.

예를 들어 node 4의 전위를 $0$으로 둔다.

$$x_4 = 0$$

그러면 전체 전위를 상수만큼 올리거나 내리는 자유도가 사라진다.

행렬 관점에서는 해당 노드의 전위를 더 이상 미지수로 취급하지 않으므로, 대응되는 열을 제거하는 것과 같다. 연결된 그래프에서는 하나의 노드를 ground하면 나머지 전위들이 유일하게 결정될 수 있다.

이 예시에서 원래 $A$는 $5 \times 4$ 행렬이고 영공간 차원이 $1$이므로, 랭크는 다음과 같다.

$$\operatorname{rank}(A) + \dim N(A) = n$$

여기서 $n=4$이고 $\dim N(A)=1$이므로,

$$\operatorname{rank}(A) = 3$$

즉 이 접속 행렬의 랭크는 $3$이다.

$$r = 3$$

연결된 그래프에서는 일반적으로 다음이 성립한다.

$$\operatorname{rank}(A) = n - 1$$

여기서 $n$은 노드의 개수이다.

---

10. $A^T y = 0$과 키르히호프 전류 법칙

이제 좌영공간을 보자.

$$A^T y = 0$$

여기서 $y$는 엣지 위를 흐르는 전류 벡터이다.

$$y = \begin{pmatrix} y_1 \\ y_2 \\ y_3 \\ y_4 \\ y_5 \end{pmatrix}$$

각 $y_i$는 edge $i$를 흐르는 전류이다.

먼저 $A^T$는 다음과 같다.

$$A^T = \begin{pmatrix} -1 & 0 & -1 & -1 & 0 \\ 1 & -1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & -1 \\ 0 & 0 & 0 & 1 & 1 \end{pmatrix}$$

따라서

$$A^T y = 0$$

은 다음 연립방정식을 의미한다.

$$-y_1 - y_3 - y_4 = 0$$ $$y_1 - y_2 = 0$$ $$y_2 + y_3 - y_5 = 0$$ $$y_4 + y_5 = 0$$

이 식들은 각 노드에서 전류가 보존된다는 뜻이다.

즉 각 노드에서

$$\text{들어오는 전류} = \text{나가는 전류}$$

이어야 한다.

이것이 키르히호프 전류 법칙이다.

$$A^T y = 0$$

은 회로 이론에서 Kirchhoff’s Current Law, 줄여서 KCL이라고 부른다.

---

11. $A^T y = 0$의 물리적 의미

$A^T y = 0$은 각 노드에서 전류가 쌓이지 않는다는 뜻이다.

예를 들어 node 1을 보자.

node 1에서는 edge 1, edge 3, edge 4가 모두 node 1에서 나가는 방향으로 잡혀 있다. 따라서 node 1에 대한 방정식은

$$-y_1 - y_3 - y_4 = 0$$

이다.

부호를 바꾸면

$$y_1 + y_3 + y_4 = 0$$

이다.

이는 node 1에서 나가는 전류들의 합이 $0$이어야 한다는 뜻이다. 물론 실제 전류 방향이 화살표와 반대이면 해당 $y_i$ 값이 음수가 되므로, 이 식은 방향까지 포함한 전류 보존 법칙이다.

node 2에 대한 식은

$$y_1 - y_2 = 0$$

이다.

이는 edge 1을 통해 들어온 전류가 edge 2를 통해 나간다는 뜻이다.

$$y_1 = y_2$$

node 3에 대한 식은

$$y_2 + y_3 - y_5 = 0$$

이다.

이는 node 3으로 들어오고 나가는 전류의 총합이 균형을 이룬다는 뜻이다.

node 4에 대한 식은

$$y_4 + y_5 = 0$$

이다.

이처럼 $A^T y = 0$은 그래프 전체에서 전류의 보존을 표현한다.

---

12. 좌영공간 $N(A^T)$의 차원

앞에서 이 그래프의 접속 행렬은 $5 \times 4$ 행렬이고 랭크는 $3$이라고 했다.

$$m = 5, \quad n = 4, \quad r = 3$$

좌영공간 $N(A^T)$의 차원은 다음과 같다.

$$\dim N(A^T) = m - r$$

따라서

$$\dim N(A^T) = 5 - 3 = 2$$

즉 $A^T y = 0$을 만족하는 독립적인 전류 패턴은 2개이다.

이 2개는 그래프 안의 독립적인 루프(loop)에 대응된다.

---

13. 루프 전류와 좌영공간의 기저

그래프에서 전류가 한 루프를 따라 돌면 각 노드에서 들어오는 전류와 나가는 전류가 같아진다. 따라서 루프를 따라 흐르는 전류는 자동으로 $A^T y = 0$을 만족한다.

이 예시에서는 독립적인 루프가 2개 있다.

첫 번째 루프는 edge 1, edge 2, edge 3으로 이루어진 삼각형이다.

이 루프를 따라 전류를 흘리면 다음 벡터를 얻을 수 있다.

$$y^{(1)} = \begin{pmatrix} 1 \\ 1 \\ -1 \\ 0 \\ 0 \end{pmatrix}$$

이 벡터의 의미는 다음과 같다.

• edge 1 방향으로 전류 $1$
• edge 2 방향으로 전류 $1$
• edge 3의 반대 방향으로 전류 $1$
• edge 4에는 전류 없음
• edge 5에는 전류 없음

이 전류 패턴은 첫 번째 루프를 따라 순환하는 전류이다.

두 번째 루프는 edge 3, edge 4, edge 5와 관련된 루프이다.

강의에서는 다음 벡터를 두 번째 루프 전류로 잡는다.

$$y^{(2)} = \begin{pmatrix} 0 \\ 0 \\ 1 \\ -1 \\ 1 \end{pmatrix}$$

이 벡터 역시 각 노드에서 전류 보존을 만족한다.

따라서 좌영공간의 한 기저는 다음과 같다.

$$N(A^T) = \operatorname{span} \left\{ \begin{pmatrix} 1 \\ 1 \\ -1 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 1 \\ -1 \\ 1 \end{pmatrix} \right\}$$

좌영공간의 차원이 $2$이므로, 이 두 독립 벡터는 $N(A^T)$의 기저가 된다.

---

14. 큰 루프는 왜 새로운 기저가 아닌가

그래프에서 바깥쪽을 크게 도는 루프도 생각할 수 있다.

예를 들어 edge 1, edge 2, edge 5, edge 4를 따라 도는 전류 패턴은 다음과 같이 나타낼 수 있다.

$$y^{(3)} = \begin{pmatrix} 1 \\ 1 \\ 0 \\ -1 \\ 1 \end{pmatrix}$$

이 벡터도 $A^T y = 0$을 만족한다. 즉 좌영공간에 속한다.

하지만 이것은 새로운 독립 벡터가 아니다.

실제로

$$y^{(3)} = y^{(1)} + y^{(2)}$$

이다.

계산하면

$$\begin{pmatrix} 1 \\ 1 \\ -1 \\ 0 \\ 0 \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \\ 1 \\ -1 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 0 \\ -1 \\ 1 \end{pmatrix}$$

이다.

즉 큰 루프 전류는 두 작은 루프 전류의 합으로 만들어진다.

따라서 독립적인 루프의 개수는 3개가 아니라 2개이다.

이것이 좌영공간 차원 $m-r=2$와 일치한다.

---

15. 행공간과 트리(Tree)

접속 행렬 $A$의 행은 엣지에 대응된다.

앞에서 edge 1, edge 2, edge 3은 하나의 루프를 만들었다. 이때 대응되는 행들 사이에는 선형 종속 관계가 있다.

실제로 처음 세 행을 보면,

$$\begin{pmatrix} -1 & 1 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & -1 & 1 & 0 \end{pmatrix} = \begin{pmatrix} -1 & 0 & 1 & 0 \end{pmatrix}$$

이다.

즉

$$\text{row}_1 + \text{row}_2 = \text{row}_3$$

이다.

루프가 있으면 그 루프를 이루는 엣지들의 행 사이에 선형 종속 관계가 생긴다.

반대로 루프가 없는 엣지들의 집합은 독립적인 행들을 만든다.

그래프에서 루프가 없는 연결 부분그래프를 트리(Tree)라고 한다.

이 예시에서 pivot row 또는 독립적인 엣지를 고르면, 루프가 없는 그래프가 된다. 예를 들어 edge 1, edge 2, edge 4를 선택하면 네 노드를 모두 연결하면서 루프가 없는 그래프가 된다.

트리는 다음 특징을 가진다.

• 루프가 없다.
• 연결된 그래프에서 $n$개의 노드를 가지면 $n-1$개의 엣지를 가진다.
• 엣지를 하나 더 추가하면 루프가 생긴다.
• 접속 행렬 관점에서는 독립적인 행들에 대응된다.

이 예시에서는 노드가 4개이므로 트리의 엣지는 3개이다.

$$n - 1 = 4 - 1 = 3$$

이는 랭크 $r=3$과도 일치한다.

---

16. 오일러 공식과 선형대수

좌영공간의 차원은 독립적인 루프의 개수이다.

$$\dim N(A^T) = m - r$$

연결된 그래프에서는

$$r = n - 1$$

이므로,

$$\dim N(A^T) = m - (n-1)$$

정리하면 독립적인 루프의 개수는

$$\text{loops} = m - n + 1$$

이다.

이를 변형하면 다음과 같다.

$$n - m + \text{loops} = 1$$

여기서

• $n$: 노드의 개수
• $m$: 엣지의 개수
• $\text{loops}$: 독립적인 루프의 개수

이다.

이 식은 그래프에 대한 오일러 공식이다.

$$\text{nodes} - \text{edges} + \text{loops} = 1$$

예를 들어 어떤 그래프가 다음과 같은 수를 가진다고 하자.

$$\text{nodes} = 5$$ $$\text{edges} = 7$$ $$\text{loops} = 3$$

그러면

$$5 - 7 + 3 = 1$$

이다.

즉 선형대수의 차원 공식이 그래프 이론의 오일러 공식으로 연결된다.

이 점이 중요하다. 행렬의 랭크, 영공간, 좌영공간을 계산하는 것이 단순한 계산 연습이 아니라, 그래프의 구조를 설명하는 위상적 사실로 이어진다.

---

17. 응용수학의 기본 구조: $A^T C A x = f$

강의 마지막에서는 전기 회로 문제를 하나의 큰 방정식으로 정리한다.

먼저 각 노드의 전위를 $x$라고 하자.

$$x = \text{node potentials}$$

접속 행렬 $A$를 곱하면 엣지의 전위 차이가 나온다.

$$e = Ax$$

여기서 $e$는 각 엣지에서의 potential difference이다.

다음으로 오옴의 법칙을 적용한다.

전류는 전위 차이에 비례한다.

$$y = C e$$

여기서

• $y$: 엣지 위의 전류
• $C$: conductance matrix
• $e$: 엣지의 전위 차이

이다.

$C$는 보통 대각행렬이다. 각 엣지의 conductance, 즉 저항의 역수 $\frac{1}{R}$가 대각성분으로 들어간다.

$$C = \begin{pmatrix} c_1 & 0 & \cdots & 0 \\ 0 & c_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & c_m \end{pmatrix}$$

따라서

$$y = C Ax$$

이다.

마지막으로 키르히호프 전류 법칙을 적용한다.

외부에서 들어오는 전류가 없다면

$$A^T y = 0$$

이다.

외부 전류원(current source)이 있다면 오른쪽에 $f$가 들어간다.

$$A^T y = f$$

여기에 $y = C A x$를 대입하면

$$A^T C A x = f$$

가 된다.

이 식이 네트워크 문제에서 나오는 기본적인 선형 시스템이다.

---

18. 각 행렬의 의미

전체 흐름은 다음과 같다.

$$x \xrightarrow{A} e \xrightarrow{C} y \xrightarrow{A^T} f$$

각 단계의 의미는 다음과 같다.

1) $e = Ax$

노드의 전위 $x$로부터 엣지의 전위 차이 $e$를 계산한다.

$$e = Ax$$

$A$는 차이를 계산하는 행렬이다.

2) $y = Ce$

전위 차이 $e$로부터 전류 $y$를 계산한다.

$$y = Ce$$

이것은 오옴의 법칙이다.

3) $A^T y = f$

엣지의 전류 $y$를 각 노드에서 합산하여 외부 전류 $f$와 맞춘다.

$$A^T y = f$$

이것은 키르히호프 전류 법칙이다.

따라서 전체 방정식은

$$A^T C A x = f$$

이다.

이 식은 전기 회로뿐 아니라 여러 응용수학 문제에서 반복해서 등장하는 구조이다.

• 전기 네트워크
• 유체 흐름 네트워크
• 열전달 문제
• 스프링 구조
• 그래프 기반 최적화 문제

등에서 비슷한 형태가 나타난다.

---

19. $A^T A$와 $A^T C A$의 성질

강의 마지막에서 중요한 질문이 나온다.

$$A^T A$$

는 어떤 성질을 가지는가?

먼저 $A^T A$는 항상 대칭행렬이다.

왜냐하면 전치하면

$$(A^T A)^T = A^T (A^T)^T$$

이고,

$$(A^T)^T = A$$

이므로

$$(A^T A)^T = A^T A$$

이다.

따라서

$$A^T A$$

는 대칭행렬이다.

마찬가지로 $C$가 대칭행렬이면, 특히 $C$가 대각행렬이면 $A^T C A$도 대칭행렬이다.

$$(A^T C A)^T = A^T C^T A$$

이고, $C^T=C$이면

$$(A^T C A)^T = A^T C A$$

이다.

따라서

$$A^T C A$$

도 대칭행렬이다.

전기 네트워크에서 $C$는 conductance를 담은 대각행렬이므로 일반적으로 대칭이다. 그래서 네트워크 방정식

$$A^T C A x = f$$

의 계수행렬은 대칭행렬이다.

이런 형태는 수치선형대수에서 매우 중요하다. 실제 응용 문제에서 나오는 큰 선형시스템은 대칭성, 희소성, 양의 준정부호성 같은 구조를 가지는 경우가 많고, 이 구조를 이용해 효율적으로 푼다.

---

20. 12강 핵심 정리

이번 강의의 핵심은 접속 행렬을 통해 4대 부분공간이 실제 그래프 문제에서 어떤 의미를 가지는지 보는 것이다.

접속 행렬 $A$는 노드 전위 $x$를 엣지의 전위 차이 $Ax$로 바꾼다.

$$e = Ax$$

영공간 $N(A)$는 전위 차이를 만들지 않는 전위 분포이다.

$$N(A) = \operatorname{span} \left\{ \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} \right\}$$

즉 모든 노드의 전위가 같은 경우이다.

좌영공간 $N(A^T)$는 키르히호프 전류 법칙을 만족하는 순환 전류들의 공간이다.

$$A^T y = 0$$

이 공간의 차원은 독립적인 루프의 개수이다.

$$\dim N(A^T) = m - r$$

연결된 그래프에서는 $r=n-1$이므로,

$$\text{loops} = m - n + 1$$

이고, 이는 오일러 공식

$$\text{nodes} - \text{edges} + \text{loops} = 1$$

로 이어진다.

마지막으로 전기 네트워크의 기본 방정식은 다음과 같이 정리된다.

$$A^T C A x = f$$

이 식은 다음 세 단계를 합친 것이다.

$$x \xrightarrow{A} e \xrightarrow{C} y \xrightarrow{A^T} f$$

즉 선형대수의 행렬과 부분공간은 실제 네트워크에서 전위, 전위 차이, 전류, 보존 법칙을 표현하는 언어로 쓸 수 있다.