# 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)