Wonderful applications of the Vandermonde determinant - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T23:46:10Z http://mathoverflow.net/feeds/question/43538 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/43538/wonderful-applications-of-the-vandermonde-determinant Wonderful applications of the Vandermonde determinant zhaoliang 2010-10-25T16:17:58Z 2012-09-21T06:53:21Z <p>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. </p> <p>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$.</p> <p>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.</p> http://mathoverflow.net/questions/43538/wonderful-applications-of-the-vandermonde-determinant/43543#43543 Answer by Jon Bannon for Wonderful applications of the Vandermonde determinant Jon Bannon 2010-10-25T16:55:27Z 2010-10-25T22:36:13Z <p>I loved encountering the following as a student:</p> <p>The Vandermonde determinant plays a role in the proof of Hilbert's Theorem 90 in Section 9.6 of Schilling and Piper's <em>Basic Abstract Algebra</em>. </p> <p>I certainly should take the time to type this argument in a bit. I just wanted to get the reference out there. </p> http://mathoverflow.net/questions/43538/wonderful-applications-of-the-vandermonde-determinant/43548#43548 Answer by Keivan Karai for Wonderful applications of the Vandermonde determinant Keivan Karai 2010-10-25T17:27:07Z 2010-10-25T17:27:07Z <p>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. </p> http://mathoverflow.net/questions/43538/wonderful-applications-of-the-vandermonde-determinant/43553#43553 Answer by Terry Tao for Wonderful applications of the Vandermonde determinant Terry Tao 2010-10-25T17:42:39Z 2010-10-25T17:48:32Z <p>Vandermonde determinants + Cramer's rule = Lagrange interpolation.</p> <p>(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 <em>theoretically possible</em>, though to get the precise <em>formula</em> one still needs to go through the above identity.) </p> http://mathoverflow.net/questions/43538/wonderful-applications-of-the-vandermonde-determinant/43578#43578 Answer by Richard Stanley for Wonderful applications of the Vandermonde determinant Richard Stanley 2010-10-25T21:07:09Z 2010-10-25T21:07:09Z <p>(1) Not really an application, but the paper by I. Gessel, Tournaments and Vandermonde's determinant, <em>J. Graph Theory</em> <strong>3</strong> (1979), 305-308, gives a nice connection with tournaments. See also Exercise 2.16 of my book <em>Enumerative Combinatorics</em>, vol. 1 (equivalent to Exercise 2.35 at <a href="http://math.mit.edu/~rstan/ec/ec1.pdf" rel="nofollow">http://math.mit.edu/~rstan/ec/ec1.pdf</a>).</p> <p>(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 <em>Enumerative Combinatorics</em>, vol. 2. </p> http://mathoverflow.net/questions/43538/wonderful-applications-of-the-vandermonde-determinant/43596#43596 Answer by darij grinberg for Wonderful applications of the Vandermonde determinant darij grinberg 2010-10-25T23:46:56Z 2012-03-11T19:38:12Z <p>I wanted to put this online long ago but somehow never came to actually doing it. Now is a good occasion:</p> <p><a href="http://mit.edu/~darij/www/index.html#hyperfactorial" rel="nofollow">http://mit.edu/~darij/www/index.html#hyperfactorial</a></p> <p>or, directly, the PDF file: <a href="http://mit.edu/~darij/www/hyperfactorialBRIEF.pdf" rel="nofollow">http://mit.edu/~darij/www/hyperfactorialBRIEF.pdf</a></p> <p>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...).</p> <p>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 &lt; 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).</p> <p>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</p> <p>$\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$.</p> <p>(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?</p> http://mathoverflow.net/questions/43538/wonderful-applications-of-the-vandermonde-determinant/43599#43599 Answer by darij grinberg for Wonderful applications of the Vandermonde determinant darij grinberg 2010-10-26T00:08:58Z 2012-03-11T19:37:54Z <p>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: <a href="http://www.amsta.leeds.ac.uk/~pmtwc/repinv.pdf" rel="nofollow">Crawley-Boevey, Lectures on Representation Theory</a> 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 <a href="http://mit.edu/~darij/www/19-9ML.pdf" rel="nofollow">purely algebraically</a>, 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...)</p> http://mathoverflow.net/questions/43538/wonderful-applications-of-the-vandermonde-determinant/43608#43608 Answer by Timothy Chow for Wonderful applications of the Vandermonde determinant Timothy Chow 2010-10-26T00:52:47Z 2010-10-26T00:52:47Z <p>The Vandermonde determinant formula implies that Vandermonde matrices are <a href="http://en.wikipedia.org/wiki/MDS_matrix" rel="nofollow">maximum distance separable</a> and can therefore be used to construct error-correcting codes with good properties (<a href="http://en.wikipedia.org/wiki/BCH_code" rel="nofollow">BCH codes</a> in particular).</p> http://mathoverflow.net/questions/43538/wonderful-applications-of-the-vandermonde-determinant/43656#43656 Answer by Federico Poloni for Wonderful applications of the Vandermonde determinant Federico Poloni 2010-10-26T10:40:24Z 2010-10-26T10:40:24Z <p>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 &amp; 1 &amp; \dots \newline \binom{x_1}{1} &amp; \binom{x_2}{1} &amp; \dots \newline \binom{x_1}{2} &amp; \binom{x_2}{2} &amp; \dots \newline \vdots &amp; \vdots &amp; \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.</p> http://mathoverflow.net/questions/43538/wonderful-applications-of-the-vandermonde-determinant/51279#51279 Answer by Wadim Zudilin for Wonderful applications of the Vandermonde determinant Wadim Zudilin 2011-01-06T04:21:44Z 2012-07-31T15:25:52Z <p>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, <em>Acta Arith.</em> <strong>42</strong> (1982/83), no. 1, 97-–100]. I put <a href="http://carma.newcastle.edu.au/wadim/MO/Cantor_Straus-AA1982.pdf" rel="nofollow">here</a> a scan of the article together with corrections given by the authors later.</p> http://mathoverflow.net/questions/43538/wonderful-applications-of-the-vandermonde-determinant/100243#100243 Answer by Emilio Pisanty for Wonderful applications of the Vandermonde determinant Emilio Pisanty 2012-06-21T13:35:27Z 2012-06-21T13:35:27Z <p>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 <em>doubly</em> 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.</p> http://mathoverflow.net/questions/43538/wonderful-applications-of-the-vandermonde-determinant/100255#100255 Answer by Margaret Friedland for Wonderful applications of the Vandermonde determinant Margaret Friedland 2012-06-21T15:47:11Z 2012-06-21T17:13:36Z <p>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...</p> <p>This relation between Vandermondian and discriminant also determines the relation between Euler class and Pontryagin class: <a href="http://en.wikipedia.org/wiki/Splitting_principle" rel="nofollow">http://en.wikipedia.org/wiki/Splitting_principle</a></p> http://mathoverflow.net/questions/43538/wonderful-applications-of-the-vandermonde-determinant/100262#100262 Answer by Jason Starr for Wonderful applications of the Vandermonde determinant Jason Starr 2012-06-21T17:56:25Z 2012-06-21T17:56:25Z <p>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).</p> http://mathoverflow.net/questions/43538/wonderful-applications-of-the-vandermonde-determinant/100267#100267 Answer by David Hansen for Wonderful applications of the Vandermonde determinant David Hansen 2012-06-21T18:43:31Z 2012-06-21T18:43:31Z <p>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$.</p> http://mathoverflow.net/questions/43538/wonderful-applications-of-the-vandermonde-determinant/100269#100269 Answer by Ryan Thorngren for Wonderful applications of the Vandermonde determinant Ryan Thorngren 2012-06-21T18:55:22Z 2012-06-21T18:55:22Z <p>Probably not an application for just any audience, but I thought I'd share... </p> <p>The Vandermonde determinant shows up in matrix models of quantum field theories. Roughly speaking, in these we consider integrals of the form</p> <p>$\int dM f(M)$,</p> <p>over the space of Hermitian matrices, where $f$ is invariant under conjugation by unitary matrices, and $dM$ is the (also conjugation invariant) measure</p> <p>$dM = (\prod_i dM_{ii})(\prod_{i\lt j} dM_{ij})$.</p> <p>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</p> <p>$\int d\lambda_1 ... d\lambda_N \Delta(\lambda_1, ...,\lambda_N) f(diag(\lambda_1,...,\lambda_N))$,</p> <p>where $\Delta$ is the Vandermonde determinant.</p> http://mathoverflow.net/questions/43538/wonderful-applications-of-the-vandermonde-determinant/103602#103602 Answer by Patricia Hersh for Wonderful applications of the Vandermonde determinant Patricia Hersh 2012-07-31T12:33:47Z 2012-07-31T13:36:43Z <p>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.</p> http://mathoverflow.net/questions/43538/wonderful-applications-of-the-vandermonde-determinant/103637#103637 Answer by Jesko Hüttenhain for Wonderful applications of the Vandermonde determinant Jesko Hüttenhain 2012-07-31T21:17:21Z 2012-07-31T21:17:21Z <p>Especially for students with just very basic background, it might be a fun fact that <a href="http://en.wikipedia.org/wiki/Companion_matrix#Diagonalizability" rel="nofollow">companion matrices</a> 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.</p> http://mathoverflow.net/questions/43538/wonderful-applications-of-the-vandermonde-determinant/107743#107743 Answer by Yamaleev for Wonderful applications of the Vandermonde determinant Yamaleev 2012-09-21T06:53:21Z 2012-09-21T06:53:21Z <p>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.</p> <p>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.</p>