## Formal Power Series and Determinants

It seems that wherever you go in mathematics linear algebra comes chasing you. Here is one such example where you are simply dealing with subsets and nothing more. You are probably aware that subsets of {1, …, n} can be represented formally using the power series

1 ≤ i1 < i2 < … < ik ≤ nxi1xi2xik

The above expression can be more succintly written as the following product.

(1 + x1)(1 + x2)…(1 + xn)

The sign alternating version of this is given below where subsets of even size have  + 1 as their coefficient and subsets of odd size have  − 1 as their coefficient.

(1 − x1)(1 − x2)…(1 − xn)

Surprisingly, this can be computed as a determinant! Recall, that a determinant of a square matrix is

det(A)1 ≤ i, j ≤ n = ∑w ∈ Snsgn(w)A1w(1)Anw(n)

Now, construct a matrix A as follows 1) Aij = xj if i ≤ j, 2) Aij = 1 if i = j + 1, and 3) Aij = 0 otherwise.

Convince yourself that the determinant of A is (1 − x1)(1 − x2)…(1 − xn).

This entry was posted in Combinatorics and tagged , . Bookmark the permalink.