I don't think the "+-, therefore 0" argument works. It requires that permuting the Si change the sign of the determinant. But the problem seems to require that the row ordering of Si is the same as the column ordering. If you swap two rows of the matrix, you must also swap two corresponding columns. The determinant changes by (-1)(-1), i.e. not at all. Any permutation can be built from swaps, so the ordering of Si doesn't matter. (Does the Putnam use trap questions?) I don't know if this matters for a proof, but M is symmetric. Rich ---- Quoting Dan Asimov <dasimov@earthlink.net>:
I never got a few things right in the statement of this problem, even on the second try. But now it's right:
----- A2 Let S_1, S_2, ..., S_(2^n?1) be the nonempty subsets of {1,2,...,n} in some order, and let M be the (2^n?1)×(2^n?1) matrix whose (i,j)th entry m(i,j) = 0 if S_i ? S_j is empty; m(i,j) = 1 otherwise.
Calculate the determinant of this matrix. -----
Allan's point that if the order doesn't matter, the determinant must be 0 also occurred to me. But maybe they're looking for an answer of the form
±[expression]
??? In any case, if the answer doesn't turn out to be too trivial, this is a very cool problem.
?Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun