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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s