You are currently browsing the tag archive for the ‘Euclidean algorithm’ tag.

I had occasion recently to look up the proof of Hilbert’s nullstellensatz, which I haven’t studied since cramming for my algebra qualifying exam as a graduate student. I was a little unsatisfied with the proofs I was able to locate – they were fairly abstract and used a certain amount of algebraic machinery, which I was terribly rusty on – so, as an exercise, I tried to find a more computational proof that avoided as much abstract machinery as possible. I found a proof which used only the extended Euclidean algorithm and high school algebra, together with an induction on dimension and the obvious observation that any non-zero polynomial of one variable on an algebraically closed field has at least one non-root. It probably isn’t new (in particular, it might be related to the standard model-theoretic proof of the nullstellensatz, with the Euclidean algorithm and high school algebra taking the place of quantifier elimination), but I thought I’d share it here anyway.

Throughout this post, F is going to be a fixed algebraically closed field (e.g. the complex numbers ${\Bbb C}$). I’d like to phrase the nullstellensatz in a fairly concrete fashion, in terms of the problem of solving a set of simultaneous polynomial equations $P_1(x) = \ldots = P_m(x) = 0$ in several variables $x = (x_1,\ldots,x_d) \in F^d$ over F, thus $P_1,\ldots,P_m \in F[x]$ are polynomials in d variables. One obvious obstruction to solvability of this system is if the equations one is trying to solve are inconsistent in the sense that they can be used to imply 1=0. In particular, if one can find polynomials $Q_1,\ldots,Q_m \in F[x]$ such that $P_1 Q_1 + \ldots + P_m Q_m = 1$, then clearly one cannot solve $P_1(x)=\ldots=P_m(x)=0$. The weak nullstellensatz asserts that this is, in fact, the only obstruction:

Weak nullstellensatz. Let $P_1,\ldots,P_m \in F[x]$ be polynomials. Then exactly one of the following statements holds:

1. The system of equations $P_1(x)=\ldots=P_m(x)=0$ has a solution $x \in F^d$.
2. There exist polynomials $Q_1,\ldots,Q_m \in F[x]$ such that $P_1 Q_1 + \ldots + P_m Q_m = 1$.

Note that the hypothesis that F is algebraically closed is crucial; for instance, if F is the reals, then the equation $x^2+1=0$ has no solution, but there is no polynomial $Q(x)$ such that $(x^2+1) Q(x) = 1$.

Like many results of the “The only obstructions are the obvious obstructions” type, the power of the nullstellensatz lies in the ability to take a hypothesis about non-existence (in this case, non-existence of solutions to $P_1(x)=\ldots=P_m(x)=0$) and deduce a conclusion about existence (in this case, existence of $Q_1,\ldots,Q_m$ such that $P_1 Q_1 + \ldots + P_m Q_m = 1$). The ability to get “something from nothing” is clearly going to be both non-trivial and useful. In particular, the nullstellensatz offers an important correspondence between algebraic geometry (the conclusion 1 is an assertion that a certain algebraic variety is empty) and commutative algebra (the conclusion 2 is an assertion that a certain ideal is non-proper).

Now suppose one is trying to solve the more complicated system $P_1(x)=\ldots=P_d(x)=0; R(x) \neq 0$ for some polynomials $P_1,\ldots,P_d, R$. Again, any identity of the form $P_1 Q_1 + \ldots + P_m Q_m = 1$ will be an obstruction to solvability, but now more obstructions are possible: any identity of the form $P_1 Q_1 + \ldots + P_m Q_m = R^r$ for some non-negative integer r will also obstruct solvability. The strong nullstellensatz asserts that this is the only obstruction:

Strong nullstellensatz. Let $P_1,\ldots,P_m, R \in F[x]$ be polynomials. Then exactly one of the following statements holds:

1. The system of equations $P_1(x)=\ldots=P_m(x)=0$, $R(x) \neq 0$ has a solution $x \in F^d$.
2. There exist polynomials $Q_1,\ldots,Q_m \in F[x]$ and a non-negative integer r such that $P_1 Q_1 + \ldots + P_m Q_m = R^r$.

Of course, the weak nullstellensatz corresponds to the special case in which R=1. The strong nullstellensatz is usually phrased instead in terms of ideals and radicals, but the above formulation is easily shown to be equivalent to the usual version (modulo Hilbert’s basis theorem).

One could consider generalising the nullstellensatz a little further by considering systems of the form $P_1(x)=\ldots=P_m(x)=0, R_1(x),\ldots,R_n(x) \neq 0$, but this is not a significant generalisation, since all the inequations $R_1(x) \neq 0, \ldots, R_n(x) \neq 0$ can be concatenated into a single inequation $R_1(x) \ldots R_n(x) \neq 0$. The presence of the exponent r in conclusion (2) is a little annoying; to get rid of it, one needs to generalise the notion of an algebraic variety to that of a scheme (which is worth doing for several other reasons too, in particular one can now work over much more general objects than just algebraically closed fields), but that is a whole story in itself (and one that I am not really qualified to tell).

[Update, Nov 26: It turns out that my approach is more complicated than I first thought, and so I had to revise the proof quite a bit to fix a certain gap, in particular making it significantly messier than my first version. On the plus side, I was able to at least eliminate any appeal to Hilbert’s basis theorem, so in particular the proof is now manifestly effective (but with terrible bounds). In any case, I am keeping the argument here in case it has some interest.]

In one of my recent posts, I used the Jordan normal form for a matrix in order to justify a couple of arguments. As a student, I learned the derivation of this form twice: firstly (as an undergraduate) by using the minimal polynomial, and secondly (as a graduate) by using the structure theorem for finitely generated modules over a principal ideal domain. I found though that the former proof was too concrete and the latter proof too abstract, and so I never really got a good intuition on how the theorem really worked. So I went back and tried to synthesise a proof that I was happy with, by taking the best bits of both arguments that I knew. I ended up with something which wasn’t too different from the standard proofs (relying primarily on the (extended) Euclidean algorithm and the fundamental theorem of algebra), but seems to get at the heart of the matter fairly quickly, so I thought I’d put it up on this blog anyway.

Before we begin, though, let us recall what the Jordan normal form theorem is. For this post, I’ll take the perspective of abstract linear transformations rather than of concrete matrices. Let $T: V \to V$ be a linear transformation on a finite dimensional complex vector space V, with no preferred coordinate system. We are interested in asking what possible “kinds” of linear transformations V can support (more technically, we want to classify the conjugacy classes of $\hbox{End}(V)$, the ring of linear endomorphisms of V to itself). Here are some simple examples of linear transformations.

1. The right shift. Here, $V = {\Bbb R}^n$ is a standard vector space, and the right shift $U: V \to V$ is defined as $U(x_1,\ldots,x_n) = (0,x_1,\ldots,x_{n-1})$, thus all elements are shifted right by one position. (For instance, the 1-dimensional right shift is just the zero operator.)
2. The right shift plus a constant. Here we consider an operator $U + \lambda I$, where $U: V \to V$ is a right shift, I is the identity on V, and $\lambda \in {\Bbb C}$ is a complex number.
3. Direct sums. Given two linear transformations $T: V \to V$ and $S: W \to W$, we can form their direct sum $T \oplus S: V \oplus W \to V \oplus W$ by the formula $(T \oplus S)(v,w) := (Tv, Sw)$.

Our objective is then to prove the

Jordan normal form theorem. Every linear transformation $T: V \to V$ on a finite dimensional complex vector space V is similar to a direct sum of transformations, each of which is a right shift plus a constant.

(Of course, the same theorem also holds with left shifts instead of right shifts.)