## Wonderful applications of the Vandermonde determinant

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

2
You should probably add the 'big-list' and 'example' tags, and set this as Community Wiki. – Mariano Suárez-Alvarez Oct 25 2010 at 16:20
The basic proof seems however more simple : take $x\in V_1 \setminus \bigcup_{i>1}V_i$ and $y\in V_2\setminus V_1$; then for some $\lambda \neq \mu$ in $F$, we have $x+\lambda y, x+\mu y \in V_j$ for some $j$, absurd. – Henri Oct 25 2010 at 16:27
yes, but here the set has an extra property: each subset with n elements is a base of $V$, which is a bit more interesting. – zhaoliang Oct 25 2010 at 16:35

2
I think the Vandermonde can also be used to compute the discriminant of a cyclotomic number field. Can an algebraic NTist step forward and elaborate on this? – darij grinberg Oct 26 2010 at 0:12

## 17 Answers

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.

-

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-

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.

-

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.

-

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$.

-

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

-

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

-

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.

-

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.

-

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.

-

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

-

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

-

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?

-

(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.

-

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

-

When I was typing this item, I had Lagrange interpolation in my mind :P  I think there should be some applications in combinatorics or symmetric function theory – zhaoliang Oct 25 2010 at 17:54

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.

-
this reminds me the Linderman-Weierstrass theorem on the transcendence of e. – zhaoliang Oct 25 2010 at 17:50

1
@zhaoliang: In fact, one uses the Vandermonde determinant in the standard proof of Baker's theorem. – Daniel Litt Oct 25 2010 at 23:02
The independence of $e^{c x}$ is a rather trivial fact. To prove it using Vandermond determinant, just differentiate any linear dependence multiple times and pack it into a matrix equality. – Keivan Karai Oct 26 2010 at 13:43

1
@Keivan. A beautiful application of this characterization of nilpotent matrices is Amitsur-Levitski's polynomial identity in $M_n(k)$. – Denis Serre Oct 26 2010 at 16:52
Another application is to prove that for any $0<\alpha_1<\cdots<\alpha_n$ the family $$\sin \alpha_1x,\cdots,\sin\alpha_nx$$ is linearly independent in $C^{4(n-1)}(\mathbb R)$. – Hany Oct 26 2010 at 19:20

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.

-

gigapedia.com/… – zhaoliang Oct 25 2010 at 17:18
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 95, "mathjax_display_tex": 10, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9163573980331421, "perplexity_flag": "head"}