Solution: 2012-24 Determinant of a Huge Matrix

Consider all non-empty subsets \(S_1,S_2,\ldots,S_{2^n-1}\) of \(\{1,2,3,\ldots,n\}\). Let \(A=(a_{ij})\) be a \((2^n-1)\times(2^n-1)\) matrix such that \[a_{ij}=\begin{cases}1 & \text{if }S_i\cap S_j\ne \emptyset,\\0&\text{otherwise.}\end{cases}\] What is \(\lvert\det A\rvert\)?

The best solution was submitted by Kim, Taeho (김태호), 수리과학과 2011학번. Congratulations!

Here is his Solution of Problem 2012-24.

Alternative solutions were submitted by 이명재 (2012학번, +3), 임현진 (물리학과 2010학번, +3), 정종헌 (2012학번, +2),  어수강 (서울대학교 수리과학부 석사과정, +3).


GD Star Rating

2 thoughts on “Solution: 2012-24 Determinant of a Huge Matrix

  1. Jerome

    The given proof seems to be wrong: for n=2, the determinant should be (-1). I don’t understand the induction argument (how is defined the submatrix A_e?) so I cannot tell where is the mistake.

    Am I wrong somewhere?

  2. student

    First, problem wants to get the size of determinant(|det A|). Second, A_e is the matrix from row operation with A which subtract 1st row from 2nd, …2^kth row. (since it does not change the size of determinants)

Comments are closed.