선형 대수학에서 가장 저평가된 단 하나의 사실: 행렬과 그래프의 연결성

이 영상은 선형 대수학에서 음이 아닌 행렬(nonnegative matrices) 과 방향성 그래프(directed graphs) 사이의 강력한 연결성을 탐구합니다. 이 연결성은 복잡한 행렬의 성질을 그래프의 연결성(connectivity) 을 통해 시각적이고 직관적으로 이해할 수 있게 합니다.

• 행렬은 그래프이고, 그래프는 행렬입니다.
• 행렬을 그래프로 인코딩하는 것은 복잡한 동작을 단순하게 연구할 수 있는 치트 코드입니다.

행렬의 그래프 표현 규칙

• 행렬의 각 행은 그래프의 노드를 나타냅니다.
• 행렬의 각 요소는 방향이 있고 가중치가 부여된 엣지(edge) 를 나타냅니다.

예시 행렬(3x3) 분석:

• 첫 번째 행($v_1$) 은 $v_1$에서 나가는 엣지를 나타냅니다.
  • (1, 1) 요소(0.5): $v_1$에서 $v_1$로 돌아오는 루프 엣지이며 가중치는 0.5입니다.
  • (1, 2) 요소(1): $v_1$에서 $v_2$로 가는 엣지이며 가중치는 1입니다.
  • (1, 3) 요소(0): $v_1$에서 $v_3$로 가는 엣지는 없습니다.
• 첫 번째 열($v_1$) 은 $v_1$으로 들어오는 엣지를 나타냅니다.
  • (1, 1) 요소(0.5): $v_1$에서 $v_1$로 돌아오는 루프 엣지이며 가중치는 0.5입니다.
  • (2, 1) 요소(0.2): $v_2$에서 $v_1$로 오는 엣지이며 가중치는 0.2입니다.
  • (3, 1) 요소(1.8): $v_3$에서 $v_1$로 오는 엣지이며 가중치는 1.8입니다.
• 이는 행렬의 방향성 그래프 표현(directed graph representation) 이라고 불립니다.

그래프의 연결성

• 강하게 연결된 그래프(Strongly Connected Graph): 모든 노드가 다른 모든 노드로부터 도달 가능한 방향성 그래프입니다.
• 강하게 연결되지 않은 그래프: 모든 노드가 서로 도달 가능하지 않은 그래프입니다.
  • 예시 그래프에서 노드 'b'에서 노드 'a'로 가는 경로가 없으므로 강하게 연결되지 않았습니다.

강하게 연결된 요소(Strongly Connected Components, SCC)

• 강하게 연결되지 않은 그래프의 경우에도, 노드들을 강하게 연결된 요소들로 분할(partition) 할 수 있습니다.
• 이는 전체 노드 집합을 서로소(disjoint)인 부분 집합 으로 그룹화하여, 각 부분 집합 내부에서는 노드들이 서로 강하게 연결되도록 하는 것입니다.

행렬 구조와 그래프 연결성의 관계

• 노드를 강하게 연결된 요소를 기준으로 적절히 라벨링하면, 행렬은 특별한 구조를 갖습니다.
• 강하게 연결되지 않은 그래프의 행렬 표현은 상부 블록 삼각형(upper block triangular) 형태를 가집니다.
  • 대각선 블록($A_i$): 내부 엣지를 나타내며, 각 SCC에 해당합니다.
  • 상부 비대각선 블록($A_{i,j}$): 요소 간 엣지를 나타냅니다.
  • 하부 비대각선 블록(0): 모두 0입니다. 이는 라벨링 순서에 따라 아래쪽 요소에서 위쪽 요소로 가는 엣지가 없음을 의미합니다.

기약 행렬(Reducible Matrix)과 프로베니우스 정규형(Frobenius Normal Form)

• 기약 행렬: 상부 블록 삼각형 형태로 쓸 수 없는 음이 아닌 행렬입니다.
• 가약 행렬(Reducible Matrix): 상부 블록 삼각형 형태로 쓸 수 있는 음이 아닌 행렬입니다.
• 프로베니우스 정규형: 행렬을 대각선에 기약인 정사각형 블록($A_i$) 을, 그 위에 가약 블록($A_{i,j}$) 을 갖는 상부 블록 대각선 행렬로 나타내는 형태입니다.
• 중요 정리: 음이 아닌 정사각형 행렬 $A$가 주어지면, 순열 행렬(permutation matrix) $P$가 존재하여 $P^T A P$가 프로베니우스 정규형이 되도록 할 수 있습니다.

순열 행렬과 노드 재라벨링

• 순열 행렬과의 유사성 변환($P^T A P$) 은 행렬의 행과 열을 동시에 교환하는 효과를 가집니다.
  • 이는 그래프에서 노드의 라벨을 바꾸는 것과 동일하며, 그래프의 구조 자체는 불변으로 유지합니다.
• 치환 행렬($P_{i,j}$): 단위 행렬에서 $i$번째와 $j$번째 행을 교환한 행렬입니다.
  • $P_{i,j}$는 자기 전치(transpose) 가 자기 역행렬(inverse) 인 성질을 가집니다.
  • $P_{i,j} A$는 행렬 $A$의 행을 교환합니다.
  • $A P_{i,j}$는 행렬 $A$의 열을 교환합니다.
  • $P_{i,j}^T A P_{i,j}$는 그래프의 $i$번째와 $j$번째 노드의 라벨을 교환합니다.

프로베니우스 정규형으로의 변환 계획

프로베니우스 정규형으로 변환하는 과정은 그래프의 연결성을 활용합니다.

1. 행렬에 대한 그래프를 구성합니다.
2. 강하게 연결된 요소(SCC)를 찾습니다.
3. 노드들을 영리하게 재라벨링합니다.

• 영리한 재라벨링 순서:

  • 그래프의 SCC들을 하나의 노드로 골격화(skeletonize) 합니다.
  • 외부에서 들어오는 엣지가 없는 컴포넌트를 **'0. 클래스 컴포넌트'**로 지정합니다.
  • 다른 컴포넌트들이 '0. 클래스 컴포넌트'로부터 도달하는 가장 긴 경로를 기준으로 컴포넌트 순서를 정합니다. (일종의 ** 부분 순서**)
  • 노드 라벨링 시, 더 높은 순서의 클래스에 속하는 노드부터 번호를 부여하고, 같은 컴포넌트 내에서는 연속적인 인덱스를 부여합니다.

• 결론: 이 영리한 재라벨링은 순열 행렬을 이용한 유사성 변환에 해당하며, 결과적으로 행렬 $A$를 프로베니우스 정규형으로 변환하는 $P$를 얻게 됩니다.