Matrix Tree theorem

G를 simple digraph on labeled n-set, 변이 m개 잇다고 하고

n by m 행렬 A을 G의 incidence matrix라고 하자

여기서 n번째 row를 제거한 것을 , 라 하자

그러면 Matrix Tree theorem이 말하는것은

the number of spanning trees of the underlying graph of G가 라는 것이다...

여기서 생각해 볼점은 왜 n번째 row를 빼는가이다

증명은 Cauchy Binet formula의 직접적인 도움을 받는다

굉장히 놀랍지 않은가.

이로써 꽤 대칭적으로 정의되는 그래프들의 spanning tree의 개수를 determinant로도 생각해볼수 잇게 되엇

예를 들어 이라 하고 각 선분의 방향은 임의로 주어졋다고 하자 그러면 spanning tree의 개수는

가 된다. 여기서 행렬의 size는 n-1 by n-1이 되겟다

이 행렬의 determinant는 무엇인가?

row operation으로도 어렵지 않게 구할수 잇으나 eigenvalue를 이용해 구해보자

이렇게 대칭적으로 정의된 matrix를 eigenvector와 eigenvalue로 분석하는 것은 자주 쓰이는 테크닉이다

먼저 n-1 by 1 column vector 는 eigenvalue를 1로 갖는 eigenvector이다 그리고 n-2개의 column vector는 eigenvalue를 n으로 가지고 서로 linearly independent하다 따라서 determinant는 가 나오고 Cayley`s formula가 증명이 된다