§ Discriminant and Resultant
I had always seen the definition of a discriminant of a polynomial $p(x)$ as:
$Disc(p(x)) \equiv a_n^{(2n - n)} \prod_{i< j} (r_i - r_j)^2$
While it is clear why this tracks if a polynomial has repeated roots
or not, I could never motivate to myself or remember this definition.
I learnt that in fact, this comes from a more general object, the resultant
of two polynomials $P(x), Q(x)$, which provides a new polynomial $Res(P(x), Q(x)$
which is zero iff $P, Q$ share a common root. Then, the discriminant is
defined as the resultant of a polynomial and its derivative. This makes far more
sense:
- If a polynomial has a repeated root $r$, then its factorization willbe of the form $p(x) = (x - r)^2 q(x)$. The derivative of the polynomial will have an $(x-r)$ term that can be factored out.
- On the contrary, if a polynomial only has a root of degree 1, then thefactorization will be $p(x) = (x - r) q(x)$, where $q(x)$ is not divisible by $(x-r)$.Then, the derivative will be $p'(x) = 1 \cdot q(x) + (x - r) q'(x)$. We cannot take $(x - r)$ commonfrom this, since $q(x)$ is not divisible by $(x-r)$.
This cleared up a lot of the mystery for me.
§ How did I run into this? Elimination theory.
I was trying to learn how elimination theory works: Given a variety
$V = \{ (x, y) : Z(x, y) = 0 \}$, how does one find a rational parametrization
$(p(t), q(t))$ such that $Z(p(t), q(t)) = 0$, and $p(t), q(t)$ are
rational functions? That is, how do we find a rational parametrization of the
locus of a polynomial $Z(x, y)$? The answer is: use resultants!
- We have two univariate polynomials $p(a; x), p(b; x)$, where the notation $p(a; x)$ means that we have a polynomial $p(a; x) \equiv \sum_i a[i] x^i$.The resultant isa polynomial $Res(a; b)$ which is equal to $0$ when$p(a; x)$ and $p(b; x)$ share a common root.
- We can use this to eliminate variables. We can treat a bivariate polynomial $p(x, y)$as a univariate polynomial $p'(y)$ over the ring $R[X]$. This way, given twobivariate polynomial $p(a; x, y)$, $q(b; x, y)$, we can compute their resultant,giving us conditions to detect for which values of $a, b, x$, there existsa common $y$ such that $p(a; x, y)$ and $(q, x, y)$ share a root. If $(a, b)$are constants, then we get a polynomial $Res(x)$ that tracks whether $p(a; x, y)$and $q(a; x, y)$ share a root.
- We can treat the implicit equation above as two equations, $x - p(t) = 0$, $y - q(t) = 0$. We can apply the method of resultants to project out $t$from the equations.
§ 5 minute intro to elimination theory.
Recall that when we have a linear system $Ax = 0$, the system has a non-trivial
solution iff $|A| = 0$. Formally: $x \neq 0 \iff |A| = 0$. Also, the
ratio of solutions is given by:
$x_i / x_j = (-1)^{i+j} |A_i|/|A_j|$
If we have two polynomials $p(a; x) = a_0 + a_1 x + a_2 x^2$, and
$q(b; x) = b_0 + b_1x + b_2 x^2$, then the system $p(a; x)$, $q(b; x)$ has
a simeltaneous zero iff:
$\begin{aligned}
&\begin{bmatrix}
a_2 & a_1 & a_0 & 0 \\
0 & a_2 & a_1 & a_0 \\
b_2 & b_1 & b_0 & 0\\
0 & b_2 & b_1 & b_0\\
\end{bmatrix}
\begin{bmatrix}
1 \\ x \\ x^2 \\ x^3
\end{bmatrix}
= 0 \\
&A x = 0
\end{aligned}$
§ Big idea
The matrix is setup in such a way that any solution vector $v$ such that
$Qv = 0$ will be of the form $v = (\alpha^3, \alpha^2, \alpha, 1)$. That is,
the solution vector is a polynomial, such that $Qv = 0$. Since $Qv = 0$,
we have that $a_2 \alpha^2 + a_1 \alpha + a_0 = 0$, and $b_2 \alpha^2 + b_1 \alpha + b_0 = 0$.
§ Proof
- Necessity is clear. If we have some non trivial vector $v \neq 0$ such that$Qv = 0$, then we need $|Q| = 0$.
- Sufficiency: Since $|Q| = 0$, there is some vector $v = (w, x, y, z)$such that $Qv = 0$. We need to show that this $v$ is non-trivial. If the polynomials $p(a;x)$,$q(b;x)$ are not equal, then we have that the rows which have coefficientsfrom $p$ and $q$ are linearly independent. So, the pair of rows $(1, 3)$,and the pair $(2, 4)$ are linearly independent. This means thatthe linear system:
$a_2 w + a_1 x + a_0 y = 0 \\
b_2 w + a_1 x + a_0 y = 0 \\$
Similarly:
$a_2 x + a_1 y + a_0 z = 0 \\
b_2 x + a_1 y + a_0 z = 0 \\$
Since the coefficients of the two systems are the same, we must have that
$(w, x, y)$ and $(x, y, z)$ are linearly dependent. That is:
$(w, x, y) = \alpha (x, y, z) \\
w = \alpha x = \alpha^2 y = \alpha^3 z \\$
We can take $z = 1$ arbitrarily, giving us a vector of the form
$(w, x, y, z) = (\alpha^3, \alpha^2, \alpha, 1)$, which is the structure
of the solution we are looking for!
§ References