[백준 16224] Path Equality (Diamond III)

https://www.acmicpc.net/problem/16224

16224번: Path Equality

 

 선형대수학 D3 문제치고는 굉장히 어려웠다. 구현이 쉬워서 난이도가 약간 깎인 듯싶다.

 

 일단 결론은 $m\le n$이고 $\sqrt{mn}$이 자연수라는 조건이 필요충분조건이다. (<=) 방향 증명은 쉽다. adjacency matrix를 A라 했을 때, A의 각 원소가 0 또는 1이면서 A^2 = mJ가 되도록 하는 A를 찾아야 한다. J는 모든 성분이 1인 행렬이다. 이때 mJ의 eigenvalue가 $mn$ 1개, 0 n-1개라는 사실이 잘 알려져 있다. 증명은 쉬운데, 일단 rank(mJ) = 1이라는 사실로부터 n-1개의 eigenvalue가 0이라는 사실이 바로 튀어나오고, 나머지 1개의 eigenvalue는 tr(X) = sum of eig.vals of X 정리로부터 얻으면 된다.

 

 이로부터 A의 characteristic polynomial은 n-1개의 0과 1개의 $\sqrt{mn}$을 영점으로 갖는다는 결론을 얻는다. 따라서 $\mathrm{tr}(A)=\sqrt{mn}$이므로 $\sqrt{mn}$은 자연수여야 한다.

 

 (=>) 방향 증명은 어렵다. n = 9이고 m = 1인 경우로 사례연구를 해 보자. tr(A) = 3이므로 9개의 노드 중 3개는 자기 자신을 향하는 loop를 갖고, 나머지 6개는 그렇지 않다. 일단 자기 자신을 향하는 loop를 갖는 3개의 노드는 똑같이 loop를 갖는 다른 노드들과 연결되지 말아야 한다(이는 m = 1이라는 특수한 조건 때문이며, 항상 그런 것은 아니다). 나머지 6개 친구들에 대해서 자기 자신으로 돌아오는 길이 2의 경로가 있으려면, 노드를 2개씩 짝지어서 이들 사이에 양방향 길을 하나씩 놓아주어야 함을 알 수 있다. 따라서 A는 일단 이렇게 생겼다.

 

$$A=\left[\begin{array}{ccccccccc}1& 0& 0& ?& ?& ?& ?& ?& ?\\ 0& 1& 0& ?& ?& ?& ?& ?& ?\\ 0& 0& 1& ?& ?& ?& ?& ?& ?\\ ?& ?& ?& 0& 1& ?& ?& ?& ?\\ ?& ?& ?& 1& 0& ?& ?& ?& ?\\ ?& ?& ?& ?& ?& 0& 1& ?& ?\\ ?& ?& ?& ?& ?& 1& 0& ?& ?\\ ?& ?& ?& ?& ?& ?& ?& 0& 1\\ ?& ?& ?& ?& ?& ?& ?& 1& 0\end{array}\right]$$

 

 A가 만약 모든 node의 outdegree가 같은 regular graph라면, 또한 $e=n\sqrt{mn}$을 가정할 수 있다. 이는 길이가 2인 모든 경로의 수를

 

$$n\times indeg\times outdeg$$

 

 로 구해줄 수 있기 때문이다. 증명은 쉬운데, 길이가 2인 모든 경로는 경로를 양분하는 node를 하나 갖고 있고, 하나의 node를 양분점으로 가진 길이 2인 모든 경로의 수는 그 node의 indegree 값과 outdegree 값의 곱이기 때문이다. 따라서 A의 각 행벡터는 $\sqrt{mn}$개의 1을 갖고 나머지를 모두 0으로 가져야 한다. 이 성질은 A가 regular graph일 때만 성립하고, regular가 아닐 때는 어떤지 잘 모르겠다.

 

 여기서 뜬금없는 가정을 하나 해 줄 건데, rank(A) = 3이라는 가정이다. 사실 rank는 우리가 A에 대해서 얻을 수 있는 정보 중 상당히 가치가 높은 정보다. 왜냐하면 우리가 rank(A^2) = 1이라는 사실을 알고 있는데, 이 1이라는 값이 정말로 낮은 수치다. 모든 행렬 X에 대해서 X^2의 rank에 대해 다음이 성립함이 알려져 있다.

 

$$\mathrm{rank}(X^2)\ge n-2\times \mathrm{nullity}(X)$$

 

 이 사실은 대학생 수학경시대회에서 몇 번 출제된 적이 있다. 어쨌든 이 사실을 쓰면 우리는 rank(A) <= 5라는 사실을 증명할 수 있는데, 이 rank 값이 낮으면 낮을수록 rank(A^2) 값도 낮아질 거라는 직관이 있다. 그러므로 우리는 rank(A) = 3으로 놓는다. 이걸 굳이 3으로 놓는 이유는 ? 위치를 어떻게 채우더라도 저 값이 3보다 낮아질 수가 없다. 어쨌든 rank(A) = 3이고, A의 모든 성분이 0 또는 1이므로, 각 행벡터 중 서로 다른 것이 최대 3개까지라는 새로운 가정을 해 줄 수 있다. 이 가정 하에 주어진 행렬은 다음과 같이 채워진다.

 

$$A=\left[\begin{array}{ccccccccc}1& 0& 0& 0& 1& 1& 0& 0& 0\\ 0& 1& 0& 1& 0& 0& 0& 0& 1\\ 0& 0& 1& 0& 0& 0& 1& 1& 0\\ 1& 0& 0& 0& 1& 1& 0& 0& 0\\ 0& 1& 0& 1& 0& 0& 0& 0& 1\\ 0& 0& 1& 0& 0& 0& 1& 1& 0\\ 1& 0& 0& 0& 1& 1& 0& 0& 0\\ 0& 1& 0& 1& 0& 0& 0& 0& 1\\ 0& 0& 1& 0& 0& 0& 1& 1& 0\end{array}\right]$$

 

이것 말고도 여러 가지 방법이 있지만 일단 이렇게 적어줄 수가 있다. 이 행렬은 엄청나게 복잡하게 생겼지만, 적절한 좌표변환을 통해 이 행렬과

 

$$\left[\begin{array}{ccccccccc}1& 1& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 1& 1\\ 1& 1& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 1& 1\\ 1& 1& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 1& 1\end{array}\right]$$

 

 이 닮음이라는 결론을 얻어줄 수 있다. 이를 일반화하면 된다.