Vandermonde and Discriminants (Graph Theoretic Proof) (14.6.27)

Dummit and Foote Abstract Algebra, section 14.6, exercise 27:

Let $f(x)$ be a monic polynomial with roots $α_1,...,α_n$.
(a) Show that the discriminant $D$ of $f(x)$ is equal to the square of the Vandermonde determinant. $$\begin{vmatrix} 1&α_1&α_1^2&\cdots&α_1^{n-1} \\ 1&α_2&α_2^2&\cdots&α_2^{n-1} \\ 1&α_3&α_3^2&\cdots&α_3^{n-1} \\ \vdots&\vdots&\vdots&\ddots&\vdots \\ 1&α_n&α_n^2&\cdots&α_n^{n-1} \end{vmatrix} = \prod_{i > j}(α_i-α_j)$$ (b) Taking the Vandermonde matrix above, multiplying on the left by its transpose, and taking the determinant, show that one obtains $$D = \begin{vmatrix} p_0&p_1&p_2&\cdots&p_{n-1} \\ p_1&p_2&p_3&\cdots&p_n \\ p_2&p_3&p_4&\cdots&p_{n+1} \\ \vdots&\vdots&\vdots&\ddots&\vdots \\ p_{n-1}&p_n&p_{n+1}&\cdots&p_{2n-2} \end{vmatrix}$$ where $p_k=∑α_i^k$, which can be computed in terms of the coefficients of $f(x)$ using Newton's Formulas from exercise 22. This gives an efficient procedure for calculating the discriminant of a polynomial.

Proof: (a) Expanding $\prod_{i > j}(α_i-α_j)$ into sums, one finds that the summands can be represented by the collection of graphs on $n$ points where for every point $α_i$ and $α_j$, a "choice" is made according to whether the element from the term $(α_i-α_j)$ is $α_i$ or (negative) $α_j$. Visually, this may be depicted by a regular $n$-gon with exactly one arrow from each vertex to another, with the vertices successively labeled $α_1,...,α_n$. Conversely, a sum may be obtained from a diagram of this type by examining how many arrows point to the vertex $α_i$ (notated $d(i)$) and retrieving $\pm ∏α_i^{d(i)}$, where the sign is negative if the number of arrows pointing from higher-ordered vertices to lower-ordered vertices is odd.

First, a lemma.

Lemma: Given such a diagram on $n$-points, if $d(i)=d(j)$ for any $i≠j$, then there exist points $a,b,c$ such that $a→b→c→a$.

Proof: The lemma is vacuously true for $n=2$. We shall prove it inductively for $n$: Given a counterexample, assume there does not exist $z$ such that $d(z)=n-1$. Then for every point, there is an arrow from that point to some other point. Starting from any point $x_1$, one may follow arrows without dead-ends to obtain a path $x_1→x_2→...→x_i→...→x_i$, so that the existence of a circuit $x_i→...→x_i$ is guaranteed. Observe a circuit $y_1→y_2→...→y_k→y_1$ of minimum distance $k$: if $k≠3$, then either $y_1$ points to $y_3$ or $y_3$ points to $y_1$. In the former case $y_1→y_3→...→y_k→y_1$ is a shorter circuit violating minimality, and in the latter case so too is $y_1→y_2→y_3→y_1$. Hence $k=3$ and the lemma's hypothesis is contradicted.

Therefore there is $z$ such that $d(z)=n-1$, i.e. all other points point to $α_z$. Note that in the equality $d(i)=d(j)$ assumed by a counterexample necessarily $i,j≠z$ as there cannot be two points toward which every point yields an arrow (since one of the two must yield an arrow to the other). As such, examine the diagram on $n-1$ points given by removing $α_z$ from the diagram and all the arrows pointing toward it ($α_z$ itself yields no arrows) to obtain a counterexample of the lemma on a smaller diagram, an inductive contradiction. This establishes the lemma.

Returning to the view of the diagrams as individual summands, establish a map between positive and negative diagrams of the type in the lemma ($d(i)=d(j)$ for some $i≠j$) given by reversing the directions of the arrows on the "first" triangle $a→b→c→a$ appearing in the diagram (triangle in order of labels $a_1,b_1,c_1$ is before triangle $a_2,b_2,c_2$ if the label of $a_1$ is smaller than the label of $a_2$, then compare $b_1$ with $b_2$ then $c_1$ with $c_2$). This map is a bijection as it is its own inverse. This ultimately implies the summands of the form $±α_1^{β_1}α_2^{β_2}...α_n^{β_n}$ where $β_i=β_j$ for some $i≠j$ cancel out in $∏_{i > j}(α_i-α_j)$, and the only ones remaining are those corresponding to diagrams where one point receives $0$ arrows, another $1$ arrow, $...$, and the last $n-1$ arrows, of which there are exactly $n!$; in fact, these are all point-permutations of the graph on $n$ points where point $α_i$ receives $i-1$ arrows. These permutations and negations correspond precisely to the definition of the determinant of the Vandermonde matrix above.

(b) If the $i,j$ entry of the Vandermonde matrix $V$ is $v_{ij}=α_i^{j-1}$, then we see the $i,j$ entry of $V^tV$ is, $$\sum_{k=1}^n v_{ki}v_{kj}=\sum_{k=1}^n α_k^{(i-1)+(j-1)}$$ which is the matrix written above. As described above, Newton's Formulas provide an efficient means of inductively calculating $p_i$ in terms of the symmetric functions which appear in the coefficients of $f(x)$, thus giving an efficient means of calculating the discriminant of $f(x)$.$~\square$