2018 대수경 2분야 5번 풀이

문제.

$1 \cdots n$의 순열 $a_{1}, a_{2}, \ldots a_{n}$과 $b_{1}, b_{2}, \ldots b_{n}$에 대해, 다음 행렬 $A$의 행렬식으로 가능한 값을 모두 구하여라.

$$A = (A_{ij}) = ((1+a_{i}b_{j})^{n-1})$$ 

$n = 2$일 때는 행렬을 다음의 꼴로 나타낼 수 있다.

$$A = \begin{pmatrix} 1 & a_{1} \\ 1 & a_{2} \end{pmatrix} \cdot \begin{pmatrix} 1 & 1 \\ b_{1} & b_{2} \end{pmatrix}$$

따라서 적당한 $k \in \{0,1\}$에 대해

$$\det (A) = (-1)^{k} \det \left[ \begin{pmatrix} 1 & 1 \\ 1 & 2\end{pmatrix} \right]^{2}$$

로 생각할 수 있다.

$n > 2$일 때는 관찰을 하나 더 섞으면 된다. 바로

$$(1+a_{i}b_{j})^{n-1} = \sum_{k = 0}^{n-1} \begin{pmatrix} n-1 \\ k \end{pmatrix} a_{i}^{k} \cdot b_{j}^{k}$$

이기 때문에, $A$를 다음과 같이 represent할 수 있다. $C(n,k)$는 $\begin{pmatrix} n \\ k \end{pmatrix}$이다.

$$A = \begin{pmatrix} 1 & a_{1} & a_{1}^2 & \cdots & a_{1}^{n-1} \\ 1 & a_{2} & a_{2}^{2} & \cdots & a_{2}^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & a_{n} & a_{n}^{2} & \cdots & a_{n}^{n-1} \end{pmatrix} \cdot \begin{pmatrix} C(n-1,0)1 & C(n-1, 1)b_{1} & C(n-1,2) b_{1}^2 & \cdots & C(n-1,n-1)b_{1}^{n-1} \\ C(n-1,0)1 & C(n-1,1)b_{2} & C(n-1,2)b_{2}^{2} & \cdots & C(n-1,n-1)b_{2}^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ C(n-1,0)1 & C(n-1,1)b_{n} & C(n-1,2)b_{n}^{2} & \cdots & C(n-1,n-1)b_{n}^{n-1} \end{pmatrix}^{T}$$ 

따라서 $\det(A)$는 다음의 꼴로 나타낼 수 있다.

$$\det (A) = (-1)^{k} \cdot \begin{pmatrix} n-1 \\ 0 \end{pmatrix} \begin{pmatrix} n-1 \\ 1 \end{pmatrix} \cdots \begin{pmatrix} n-1 \\ n-1 \end{pmatrix} \cdot \det \left[ \begin{pmatrix} 1^{0} & 1^{1} & \cdots &1^{n-1} \\ 2^{0} & 2^{1} & \cdots & 2^{n-1} \\ \vdots & \vdots & \ddots & \vdots \\ n^{0} & n^{1} & \cdots & n^{n-1} \end{pmatrix} \right] ^{2}$$

그런데 맨 오른쪽 항은 Vandermonde Matrix로, 이미 행렬식이 잘 알려져 있는 놈이다.

행렬식의 값을 계산하면 $(n-1)! (n-2)! \cdots 1!$이 나온다.

제곱해서 Combination 항들이랑 열심히 섞어주면, 결국 가능한 값은 $\pm \left( (n-1)! \right)^{n}$ 뿐이다. $\blacksquare$