# Is this induction proof of the Fundamental Theorem of Algebra rigorous?

I was trying to find a suitable proof of the Fundamental Theorem of Algebra at an undergraduate level which avoided abstract linear algebra, as I have not yet begun it. However, I came across this

http://www.math.washington.edu/~aloveles/ArchivedMaterials/Math300/FundamentalTheoremOfAlgebra.pdf

which is seemingly comprehensible and straightforward, and logical but I was wondering if it is rigourous or even valid?

• Yes, it contains a correct proof of the statement A polynomial of degree d has at most d real roots. But that's not what most people mean by the Fundamental Theorem of Algebra. – Zev Chonoles Jul 8 '15 at 22:51
• On the other hand, this statement can actually be considered both fundamental and of algebra, unlike the Fundamental Theorem of Algebra... – darij grinberg Jul 8 '15 at 23:10
• @Reinhild Van Rosenú: “This theorem is the more extraordinary that complex numbers were invented for attributing roots to the quadratic equations only” ....... “can not prove this theorem without recourse one or another way to own considerations in the analysis and not algebra” (Godement). – Piquito Jul 9 '15 at 0:00
• @Ataulfo I guess the name is a complete misnomer. – Reinhild Van Rosenú Jul 9 '15 at 0:03
• @Ataulfo Nooo, I meant the name of the theorem "The Fundamental Theorem Of Algebra", since it can't cosntructively be proved solely using algebra. – Reinhild Van Rosenú Jul 9 '15 at 9:03

I think the one of the more accessible proof of Fundamental Theorem of Algebra is the following argument (due to Lagrange). I learned it from Pierre Samuel's Algebraic Theory of Numbers. It uses induction on the highest power of $2$ dividing the degree of $f$.

Let $f(x)$ be a polynomial with coefficients in $\mathbb{C}$. We need to show that $f(x)$ has exactly $d=\deg(f)$ roots. It suffices to show that every polynomial has some root in $\mathbb{C}$. Because then we can factor $f(x)=(x-a_1) f_1(x)$ (where $a_1$ is a root of $f(x)$), and then apply the same argument to $f_1(x)$ to get $f_1(x)=(x-a_2)f_2(x)$. Doing this $d$ times (formally: we use induction) would give $f(x)=(x-a_1)\cdots (x-a_{d})$.

Okay, so let's show that $f(x)$ has some complex root. We might as well assume $f$ is monic, i.e. $f(x)=x^{d}+\mathsf{lower \ order \ terms}$. By replacing $f(x)$ by $f(x)\overline{f(\overline{x})}$ where $\overline{z}$ is the complex conjugation, it suffices to assume that $f(x)$ has real coefficients. This is because $f(x)$ and $f(x)\overline{f(\overline{x})}$ have same roots, but the latter polynomial has real coefficients! Indeed, if $f(x)=a_d x^{d}+\cdots + a_1 x + a_0$, then $\overline{f(\overline{x})} = \overline{a_d} x^{d}+\cdots + \overline{a_1} x + \overline{a_0}$, so their product will have real coefficients.

We write $d=\deg(f)=2^{n} m$ where $m$ is odd, and proceed by induction on $n$. When $n=0$, the degree $\deg(f)$ is odd. By intermediate value theorem, it is easy to see that $f$ has a real root. Indeed, $\displaystyle\lim_{x\to-\infty} f(x) =-\infty$ and $\displaystyle\lim_{x\to\infty} f(x)=\infty$. So $f$ must cross the real axis (thereby achieving a zero) at some point. Now we assume the induction hypothesis for the case $n-1$. A theorem from field theory tells us that $f$ has some splitting field, meaning that we can find some bigger field $K$ (containing $\mathbb{C}$) over which $f$ has $d=2^{n}m$ roots, say $x_1, x_2, …, x_d\in K$ (in reality, $K=\mathbb{C}$, and that's exactly what we are trying to prove!). Fix $c\in\mathbb{R}$ and consider the following polynomial: $$G_{c}(x) = \prod_{i<j} (x-(x_i+x_j+cx_ix_j))$$ The coefficients of $G_{c}(x)$ are symmetric polynomials in $\{x_i\}$ with real coefficients. By Fundamental Theorem of Symmetric Polynomials, any such symmetric polynomial can be written as a some polynomial (with real coefficients) in $\sum_{i} x_i$, $\sum_{i<j} x_i x_j$, $\sum_{i<j<k} x_i x_j x_k$, …, $x_1x_2\cdots x_d$. But these elementary symmetric functions are precisely the coefficients of $f$, which are real. To see this, expand $f(x)=(x-x_1)\cdots(x-x_d)$. So the conclusion is that $G_{c}(x)$ has real coefficients. Now, $\deg(G_{c})={d\choose 2}=d(d-1)/2=2^{n-1} (2^{n}m-1)$. Since $2^{n}m-1$ is odd, we can apply induction hypothesis to deduce that $G_{c}$ has a root $z_{c}\in\mathbb{C}$. So $z_{c}=x_i+x_j+cx_ix_j$ for some pair of index $(i, j)$ with $i<j$. But number of such indices is finite, while there are infinitely many choices for $c\in\mathbb{R}$. Hence, we can find distinct $c$ and $d$ in $\mathbb{R}$ such that $$z_{c}=x_i+x_j+cx_ix_j \ \ \ \ \ z_{d}=x_i+x_j+dx_ix_j$$ Since $c\neq d$, by using appropriate linear combination of these equations, it is easy to solve for $x_i+x_j$ and $x_ix_j$. In other words, find complex numbers $w_1, w_2$ such that $x_i+x_j=w_1$ and $x_ix_j = w_2$. These two equations can be combined to give a quadratic equation in $x_i$. The good old quadratic formula applies and shows $x_i\in\mathbb{C}$. So we have found a root of $f$ in $\mathbb{C}$! Whew!

• Wow! Thanks much for this. – Reinhild Van Rosenú Jul 9 '15 at 0:03
• My pleasure. I like this argument a lot, so writing it up was fun :) – Prism Jul 9 '15 at 0:04
• @Prism: Just a remark: “So we have found a root of $f$ in $\mathbb {C}$!” It is not strictly speaking the case the true story being “So we have proved there exists a root of $f$ in $\mathbb {C}$!". The most of several proofs of this theorem are not constructive (it was Weierstrass who asked about a constructive one of this important theorem). – Piquito Jul 9 '15 at 1:36
• In the beginning while constructing real coefficients you surely mean $f(x)·\bar f(x)=f(x)·\overline{f(\bar x)}$. – Dr. Lutz Lehmann Jul 10 '15 at 20:06
• By context, $x$ is a complex indeterminate. In your formulation, the product contains terms with factors $\bar x$ since $\overline{a_k·x^k}=\bar a_k·\bar x^k$. – Dr. Lutz Lehmann Jul 10 '15 at 20:22

This proves that polynomials of degree $d$ have at most $d$ roots, not that they have exactly $d$ roots with multiplicity, which what is usually referred to as the fundamental theorem of algebra.

• Would trying to continue it for the "exactly" statement involves complex analysis, Galois theory, abstract linear algebra or some other tool not normally frequented in the early years of an undergrad.? – Reinhild Van Rosenú Jul 8 '15 at 22:52
• Short answer: Basically. It's a deep fact and requires some machinery one way or another to prove it. – Spooky Jul 8 '15 at 22:54
• I think there is an `elementary' (in fact there are probably several) proof, but very intricate and clever due to Derksen, which appeared in the Bulletin of the AMS many years ago. This can be understood by a sophisticated undergraduate, avoids complex analysis, Galois theory etc. – Mohan Jul 8 '15 at 23:00
• There’s a proof using nothing but the fact that a polynomial of odd degree over $\Bbb R$ has at least one real root, but I no longer know it. – Lubin Jul 8 '15 at 23:23
• @Lubin: you may be thinking of Lagrange's proof jstor.org/stable/27642032?seq=1#page_scan_tab_contents – Rob Arthan Jul 8 '15 at 23:44