Wonderful applications of the Vandermonde determinant - MathOverflow

Wonderful applications of the Vandermonde determinant

2010-10-25T16:17:58Z

This semester I am assisting my mentor teaching a first-year undergraduate course on linear algebra in Peking University, China. And now we have come to the famous Vandermonde determinant, which has many useful applications. I wonder if there are some applications of the Vandermonde determinant that are suitable for students without much math background.

For example, using the Vandermonde determinant, we can prove that a vector space $V$ over a field $F$ of characteristic 0 cannot be expressed as a finite union of its nontrivial subspaces, i.e., there do not exist subspaces $V_1,\ldots,V_m$ that satisfy $$ V_1\cup \cdots\cup V_m=V,$$ where $V_i\ne {0}$ and $V_i\ne V$ for all $i=1,2,\ldots,m$.

This can be proved as follows: choose $v_1,\ldots,v_n$ as a basis of $V$, and consider the infinite series $$ \alpha_i = v_1 + iv_2+\cdots+i^{n-1}v_n.$$ Using our knowledge of the Vandermonde determinant, one can show that every subset of the $\alpha$'s having $n$ vectors in it consists of a basis of $V$, hence each of the $V_i$'s can contain at most $n-1$ of the $\alpha$'s in it, so there must be infinitely many $\alpha$'s not contained in any of the $V_i$'s.

Answer by Jon Bannon for Wonderful applications of the Vandermonde determinant

2010-10-25T16:55:27Z

I loved encountering the following as a student:

The Vandermonde determinant plays a role in the proof of Hilbert's Theorem 90 in Section 9.6 of Schilling and Piper's Basic Abstract Algebra.

I certainly should take the time to type this argument in a bit. I just wanted to get the reference out there.

Answer by Keivan Karai for Wonderful applications of the Vandermonde determinant

2010-10-25T17:27:07Z

Of course, what is "wonderful" is quite subjective. One simple application that I like is showing that the functions $e^{cx}$ are linearly independent over ${\mathbb R}$. Another is that if $tr (A^n)=0$ for all $n$, then $A$ is nilpotent.

Answer by Terry Tao for Wonderful applications of the Vandermonde determinant

2010-10-25T17:42:39Z

Vandermonde determinants + Cramer's rule = Lagrange interpolation.

(EDIT: Also, there is a qualitative version of the above identity: just from knowing that the Vandermonde determinant is non-vanishing when the $x_i$ are distinct, one can already deduce that polynomial interpolation is theoretically possible, though to get the precise formula one still needs to go through the above identity.)

Answer by Richard Stanley for Wonderful applications of the Vandermonde determinant

2010-10-25T21:07:09Z

(1) Not really an application, but the paper by I. Gessel, Tournaments and Vandermonde's determinant, J. Graph Theory 3 (1979), 305-308, gives a nice connection with tournaments. See also Exercise 2.16 of my book Enumerative Combinatorics, vol. 1 (equivalent to Exercise 2.35 at http://math.mit.edu/~rstan/ec/ec1.pdf).

(2) Probably not suitable for an undergraduate course, but if $s_{(n-1,n-2,\dots,1)}$ denotes the Schur function of the staircase shape $(n-1,n-2,\dots,1)$, then the evaluation $$ s_{(n-1,n-2,\dots,1)}(x_1,\dots,x_n)=\prod_{1\leq i \lt j\leq n} (x_i+x_j) $$ follows immediately from the bialternant formula for Schur functions, since it reduces to the quotient of two Vandermonde's: $\prod (x_i^2-x_j^2)/\prod(x_i-x_j)$. See Exercise 7.30 of Enumerative Combinatorics, vol. 2.

Answer by darij grinberg for Wonderful applications of the Vandermonde determinant

2010-10-25T23:46:56Z

I wanted to put this online long ago but somehow never came to actually doing it. Now is a good occasion:

http://mit.edu/~darij/www/index.html#hyperfactorial

or, directly, the PDF file: http://mit.edu/~darij/www/hyperfactorialBRIEF.pdf

This is about a theorem by MacMahon stating that for any three nonnegative integers $a$, $b$, $c$, the number $\frac{H\left(a\right)H\left(b\right)H\left(c\right)H\left(a+b+c\right)}{H\left(b+c\right)H\left(c+a\right)H\left(a+b\right)}$ is an integer, where $H\left(m\right)$ means $0!\cdot 1!\cdot ...\cdot \left(m-1\right)!$. There are various proofs of this now, some of them combinatorial (see the references in the note), but the simplest one is probably the one I give using the Vandermonde determinant (I don't think it's new...).

The note is a bit long (10 pages), but the proof ends at page 6. Also note that I prove Vandermonde itself, which takes up some space as well. Another application of Vandermonde appears on page 9: If $a_1$, $a_2$, ..., $a_m$ are $m$ integers, then $\prod\limits_{1\leq i < j\leq m}\left(a_i-a_j\right)$ is divisible by $H\left(m\right)$. This is very well-known (and so is the proof).

Finally, a little question - slightly offtopic, I know. Back to the $\frac{H\left(a\right)H\left(b\right)H\left(c\right)H\left(a+b+c\right)}{H\left(b+c\right)H\left(c+a\right)H\left(a+b\right)}$ problem, one might try proving that this is an integer by showing that every prime $p$ divides $H\left(a\right)H\left(b\right)H\left(c\right)H\left(a+b+c\right)$ at least as often as it divides $H\left(b+c\right)H\left(c+a\right)H\left(a+b\right)$. This can be easily shown equivalent to the following: Any nonnegative integers $a$, $b$, $c$ satisfy

$\sum\limits_{k=0}^{a-1} \lfloor \frac{k}{p} \rfloor + \sum\limits_{k=0}^{b-1} \lfloor \frac{k}{p} \rfloor + \sum\limits_{k=0}^{c-1} \lfloor \frac{k}{p} \rfloor + \sum\limits_{k=0}^{a+b+c-1} \lfloor \frac{k}{p} \rfloor$ $\geq \sum\limits_{k=0}^{b+c-1} \lfloor \frac{k}{p} \rfloor + \sum\limits_{k=0}^{c+a-1} \lfloor \frac{k}{p} \rfloor + \sum\limits_{k=0}^{a+b-1} \lfloor \frac{k}{p} \rfloor$.

(Yes, it can be shown that the $p^2$, $p^3$, ... terms can be ignored.) Is there an easy way to see this? Or any way at all, without going back to the Vandermonde determinant?

Answer by darij grinberg for Wonderful applications of the Vandermonde determinant

2010-10-26T00:08:58Z

As for applications in symmetric function theory... well, open a book on symmetric function theory at a random page and stare at the formulas. Usually something looking like a Vandermonde determinant will stare back at you. For example: Crawley-Boevey, Lectures on Representation Theory uses it on page 18. Oh, and of course he uses the Cauchy determinant too. While he derives it from a geometric argument, it can also be proven purely algebraically, and the proof uses Vandermonde. (Again, I'm not claiming the proof is new. In fact I believe I have seen it somewhere, but I couldn't find it again...)

Answer by Timothy Chow for Wonderful applications of the Vandermonde determinant

2010-10-26T00:52:47Z

The Vandermonde determinant formula implies that Vandermonde matrices are maximum distance separable and can therefore be used to construct error-correcting codes with good properties (BCH codes in particular).

Answer by Federico Poloni for Wonderful applications of the Vandermonde determinant

2010-10-26T10:40:24Z

Maybe it is not really suitable to undergrads (unless they are really problem solving-oriented), but there is a nice proof that $$\prod_{1\leq i \lt j\leq n} \frac{x_j-x_i}{j-i}$$ is integer for all integer sequences $(x_k)_{k=1}^n$ using Vandermonde determinants. The idea is reducing the thesis to the fact that the matrix $$\begin{bmatrix}1 & 1 & \dots \newline \binom{x_1}{1} & \binom{x_2}{1} & \dots \newline \binom{x_1}{2} & \binom{x_2}{2} & \dots \newline \vdots & \vdots & \ddots \end{bmatrix}$$ has integer entries, and thus integer determinant. After clearing the denominators (which give the factor $\prod \frac{1}{j-i}$), one can transform the resulting determinant to a Vandermonde with basic row operations.

Answer by Wadim Zudilin for Wonderful applications of the Vandermonde determinant

2011-01-06T04:21:44Z

There is an elegant (and short!) application of the (generalized) Vandermonde determinant to the famous problem of D. H. Lehmer in the article [D.C. Cantor and E.G. Straus, Acta Arith. 42 (1982/83), no. 1, 97-–100]. I put here a scan of the article together with corrections given by the authors later.

Answer by Emilio Pisanty for Wonderful applications of the Vandermonde determinant

2012-06-21T13:35:27Z

The Discrete Fourier Transform, which sends a vector $x=\left(x_j\right)_{j=0}^{N-1}$ to $y=\mathrm{DFT}(x)$ such that $$y_k=\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}e^{2\pi i \times jk/N}x_j$$ has a matrix representation $$\mathrm{DFT}_{jk}=e^{2\pi i \times jk/N}=\left(e^{2\pi i /N}\right)^{j\times k},$$ which is in fact a doubly Vandermonde matrix: both it and its transpose are Vandermonde matrices. With this you can use the Vandermonde determinant to prove that $\mathrm{DFT}$ is nonsingular, and if you prove using other means that it is unitary (rather easy) then you will get, I think, a nontrivial expression for 1 as a product of differences of roots of unity.

Answer by Margaret Friedland for Wonderful applications of the Vandermonde determinant

2012-06-21T15:47:11Z

Maybe this should be a comment under Darij Grinberg's or Terry Tao's answer, but anyway: the discriminant of a monic polynomial is the square of the Vandermonde determinant evaluated at roots of the polynomial. Undergraduate students who advanced to a linear algebra course must have encountered at least the discriminant of a quadratic--although in this case the relation between the Vandermondian and the discriminant is not so wonderful...

This relation between Vandermondian and discriminant also determines the relation between Euler class and Pontryagin class: http://en.wikipedia.org/wiki/Splitting_principle

Answer by Jason Starr for Wonderful applications of the Vandermonde determinant

2012-06-21T17:56:25Z

The Vandermonde determinant plays a role in the proof by Kempf and Kleiman-Laksov of the existence portion of the famous Brill-Noether theorem (formulated, but not proved, by Brill and Noether): a general, genus $g$ projective curve has an algebraic line bundle of degree $d$ and $(r+1)$-dimensional space of global sections if and only if the "naive parameter count" for the dimension of such, $\rho(g,r,d) = g-(r+1)(g-r+d)$, is nonnegative. The point is that they set up the enumerative formula to count the number of such line bundles (satisfying some appropriate additional conditions). Miraculously the formula comes out to a Vandermonde determinant which can be explicitly evaluated as being nonzero (as opposed to many similar enumerative problems in algebraic geometry which have no such closed formula).

Answer by David Hansen for Wonderful applications of the Vandermonde determinant

2012-06-21T18:43:31Z

The vectors corresponding to any $n$ distinct points on the rational normal curve $x\to (x,x^2,\dots,x^n) \subset \mathbb{A}^n$ span $\mathbb{A}^n$.

Answer by Ryan Thorngren for Wonderful applications of the Vandermonde determinant

2012-06-21T18:55:22Z

Probably not an application for just any audience, but I thought I'd share...

The Vandermonde determinant shows up in matrix models of quantum field theories. Roughly speaking, in these we consider integrals of the form

$\int dM f(M)$,

over the space of Hermitian matrices, where $f$ is invariant under conjugation by unitary matrices, and $dM$ is the (also conjugation invariant) measure

$dM = (\prod_i dM_{ii})(\prod_{i\lt j} dM_{ij})$.

We want to calculate the integral by gauge fixing. In other words, to integrate over a judiciously chosen set of representatives of each $U(N)$ orbit. Usually the best set of representatives to take are the diagonal matrices. The procedure for evaluating the integral in that case is exactly that of the Weyl integration formula. In doing so we get what physicists call the Faddeev-Popov determinant, which turns out to be the Vandermonde determinant! In other words, we get an equivalent integral

$\int d\lambda_1 ... d\lambda_N \Delta(\lambda_1, ...,\lambda_N) f(diag(\lambda_1,...,\lambda_N))$,

where $\Delta$ is the Vandermonde determinant.

Answer by Patricia Hersh for Wonderful applications of the Vandermonde determinant

2012-07-31T12:33:47Z

The Vandermonde determinant is used to prove that cyclic polytopes maximize the number of $i$-dimensional faces for each $i$ among all triangulations of a $(d-1)$-dimensional sphere having exactly n vertices. The cyclic polytope $C(n,d)$ is the convex hull of any $n$ distinct points on the moment curve {$(t,t^2,\dots ,t^d) | t\in {\mathbf R} $} $ \subseteq {\mathbf R}^d$. I like the discussion of cyclic polytopes in G"unter Ziegler's book "Lectures on Polytopes". The wikipedia article en.wikipedia.org/wiki/Cyclic_polytope also seems to give a nice quick summary.

Answer by Jesko Hüttenhain for Wonderful applications of the Vandermonde determinant

2012-07-31T21:17:21Z

Especially for students with just very basic background, it might be a fun fact that companion matrices are diagonalized by the vandermonde matrix corresponding to the zeros of the characteristic polynomial they encode - provided, of course, that the roots are all distinct.

Answer by Yamaleev for Wonderful applications of the Vandermonde determinant

2012-09-21T06:53:21Z

I found some remarkable property of the Vandermonde determinant. Based on this property we are able to introduce a notion "difference between n>2 quantities". Below I give the abstract of this result.

The notion of difference between two quantities plays a basic role in mathematics, consequently in all branches of human activity where the mathematics is applied. However the long stand question is: what is {\it the difference between three (or more) quantities}? The binary operation $[a,b]=(a-b)$ possesses the following principal feature: with respect to the third quantity $c$ this operation is decomposed into a sum of the same operations between $a$ and $c$, and $c$ and $b$, i.e., $$ [a,b]=[a,c]+[c,b]. $$ Denote by $[a,b,c]$ difference between three quantities $a,b,c$. With respect to additional quantity $d$ this definition of the difference has to possess with the following property $$ [a,b,c]=[d,b,c]+[a,d,c]+[a,b,d]. $$ We prove that this property of difference between three (or $n\geq 2$) quantities is satisfied by one of the features of Vandermonde determinant.