선형 대수학에서 가장 저평가된 단 하나의 사실: 행렬과 그래프의 연결성
The Single Most Undervalued Fact of Linear Algebra by The Palindrome
이 영상은 선형 대수학에서 음이 아닌 행렬(nonnegative matrices) 과 방향성 그래프(directed graphs) 사이의 강력한 연결성을 탐구합니다. 이 연결성은 복잡한 행렬의 성질을 그래프의 연결성(connectivity) 을 통해 시각적이고 직관적으로 이해할 수 있게 합니다.
- 행렬은 그래프이고, 그래프는 행렬입니다.
- 행렬을 그래프로 인코딩하는 것은 복잡한 동작을 단순하게 연구할 수 있는 치트 코드입니다.
행렬의 그래프 표현 규칙
- 행렬의 각 행은 그래프의 노드를 나타냅니다.
- 행렬의 각 요소는 방향이 있고 가중치가 부여된 엣지(edge) 를 나타냅니다.
예시 행렬(3x3) 분석:
- 첫 번째 행() 은 에서 나가는 엣지를 나타냅니다.
- (1, 1) 요소(0.5): 에서 로 돌아오는 루프 엣지이며 가중치는 0.5입니다.
- (1, 2) 요소(1): 에서 로 가는 엣지이며 가중치는 1입니다.
- (1, 3) 요소(0): 에서 로 가는 엣지는 없습니다.
- 첫 번째 열() 은 으로 들어오는 엣지를 나타냅니다.
- (1, 1) 요소(0.5): 에서 로 돌아오는 루프 엣지이며 가중치는 0.5입니다.
- (2, 1) 요소(0.2): 에서 로 오는 엣지이며 가중치는 0.2입니다.
- (3, 1) 요소(1.8): 에서 로 오는 엣지이며 가중치는 1.8입니다.
- 이는 행렬의 방향성 그래프 표현(directed graph representation) 이라고 불립니다.
그래프의 연결성
- 강하게 연결된 그래프(Strongly Connected Graph): 모든 노드가 다른 모든 노드로부터 도달 가능한 방향성 그래프입니다.
- 강하게 연결되지 않은 그래프: 모든 노드가 서로 도달 가능하지 않은 그래프입니다.
- 예시 그래프에서 노드 'b'에서 노드 'a'로 가는 경로가 없으므로 강하게 연결되지 않았습니다.
강하게 연결된 요소(Strongly Connected Components, SCC)
- 강하게 연결되지 않은 그래프의 경우에도, 노드들을 강하게 연결된 요소들로 분할(partition) 할 수 있습니다.
- 이는 전체 노드 집합을 서로소(disjoint)인 부분 집합 으로 그룹화하여, 각 부분 집합 내부에서는 노드들이 서로 강하게 연결되도록 하는 것입니다.
행렬 구조와 그래프 연결성의 관계
- 노드를 강하게 연결된 요소를 기준으로 적절히 라벨링하면, 행렬은 특별한 구조를 갖습니다.
- 강하게 연결되지 않은 그래프의 행렬 표현은 상부 블록 삼각형(upper block triangular) 형태를 가집니다.
- 대각선 블록(): 내부 엣지를 나타내며, 각 SCC에 해당합니다.
- 상부 비대각선 블록(): 요소 간 엣지를 나타냅니다.
- 하부 비대각선 블록(0): 모두 0입니다. 이는 라벨링 순서에 따라 아래쪽 요소에서 위쪽 요소로 가는 엣지가 없음을 의미합니다.
기약 행렬(Reducible Matrix)과 프로베니우스 정규형(Frobenius Normal Form)
- 기약 행렬: 상부 블록 삼각형 형태로 쓸 수 없는 음이 아닌 행렬입니다.
- 가약 행렬(Reducible Matrix): 상부 블록 삼각형 형태로 쓸 수 있는 음이 아닌 행렬입니다.
- 프로베니우스 정규형: 행렬을 대각선에 기약인 정사각형 블록() 을, 그 위에 가약 블록() 을 갖는 상부 블록 대각선 행렬로 나타내는 형태입니다.
- 중요 정리: 음이 아닌 정사각형 행렬 가 주어지면, 순열 행렬(permutation matrix) 가 존재하여 가 프로베니우스 정규형이 되도록 할 수 있습니다.
순열 행렬과 노드 재라벨링
- 순열 행렬과의 유사성 변환() 은 행렬의 행과 열을 동시에 교환하는 효과를 가집니다.
- 이는 그래프에서 노드의 라벨을 바꾸는 것과 동일하며, 그래프의 구조 자체는 불변으로 유지합니다.
- 치환 행렬(): 단위 행렬에서 번째와 번째 행을 교환한 행렬입니다.
- 는 자기 전치(transpose) 가 자기 역행렬(inverse) 인 성질을 가집니다.
- 는 행렬 의 행을 교환합니다.
- 는 행렬 의 열을 교환합니다.
- 는 그래프의 번째와 번째 노드의 라벨을 교환합니다.
프로베니우스 정규형으로의 변환 계획
프로베니우스 정규형으로 변환하는 과정은 그래프의 연결성을 활용합니다.
- 행렬에 대한 그래프를 구성합니다.
- 강하게 연결된 요소(SCC)를 찾습니다.
- 노드들을 영리하게 재라벨링합니다.
-
영리한 재라벨링 순서:
- 그래프의 SCC들을 하나의 노드로 골격화(skeletonize) 합니다.
- 외부에서 들어오는 엣지가 없는 컴포넌트를 **'0. 클래스 컴포넌트'**로 지정합니다.
- 다른 컴포넌트들이 '0. 클래스 컴포넌트'로부터 도달하는 가장 긴 경로를 기준으로 컴포넌트 순서를 정합니다. (일종의 ** 부분 순서**)
- 노드 라벨링 시, 더 높은 순서의 클래스에 속하는 노드부터 번호를 부여하고, 같은 컴포넌트 내에서는 연속적인 인덱스를 부여합니다.
-
결론: 이 영리한 재라벨링은 순열 행렬을 이용한 유사성 변환에 해당하며, 결과적으로 행렬 를 프로베니우스 정규형으로 변환하는 를 얻게 됩니다.