# Revision history [back]

In this rather special case we can find a lift of $1$ quickly and efficiently using linear algebra.

Let $R$ be a polynomial ring over $\mathbb{C}$, $I \subset R$ a zero-dimensional radical ideal and $f \in R$. To show $\langle 1 \rangle = I + \langle f \rangle$ it suffices (by Hilbert's Nullstellensatz) to show $\varnothing = V(I + \langle f \rangle) = V(I) \cap V(f)$, i.e. that $f$ does not vanish on $V(I)$. Since $I$ is radical, the ideal of polynomials in $R$ vanishing on $V(I)$ is exactly $I$ (by the Nullstellensatz). By definition of zero-dimensional, the quotient $R/I$ is a finite-dimensional $\mathbb{C}$-vector space.

• Consider the $\mathbb{C}$-linear "multiplication by $f$" map $M_f: g \mapsto f \cdot g$ on $R/I$. Let $g$ be an eigenvector of $M_f$ with eigenvalue $\lambda$, so $f \cdot g = \lambda \cdot g$ or $(f-\lambda) g = 0$ holds in $R/I$, i.e. $(f-\lambda)g \in I$. The fact that $g \neq 0$ in $R/I$ means $g \not\in I$, hence there is a point $p \in V(I)$ with $g(p) \neq 0$. Now from $(f-\lambda)g \in I$ it follows that $\lambda = f(p)$ is the value of $f$ at the point $p$.

• Conversely, if $P$ is the minimum polynomial of $M_f$ then $P(M_f) = 0$ implies $P(f) = 0$ in $R/I$ (by evaluating at $1 \in R/I$), hence $P(f) \in I$ and it follows that $0 = P(f)(p) = P(f(p))$ for all $p \in V(I)$, i.e. all values $f(p)$ for $p \in V(I)$ are zeros of $P$, and hence they are eigenvalues of $M_f$.

So the values of $f$ on $V(I)$ are exactly the eigenvalues of $M_f$, and it suffices to show that $0$ is not one of them.

Given a Groebner basis $G$ of $I$, the multivariate polynomial division algorithm implies that set of of all monomials not divisible by any leading terms of $G$ is a basis of $R/I$ as a $\mathbb{C}$-vector space (called the normal basis). The matrix of $M_f$ with respect to this basis is easily computed:

def multiplication_matrix(f, I):
G = I.groebner_basis()
f = f.reduce(G)
NB = I.normal_basis()
M = Matrix(f.base_ring(), len(NB))
for (i, m1) in enumerate(NB):
g = (f*m1).reduce(G)
M.set_column(i, [g.monomial_coefficient(m2) for m2 in NB])
return M

We apply it to the problem at hand:

sage: f = 5*u0*z2 + 5*u1*z4 + 7*u2*z6 - u0 + 1/125
sage: I = R.ideal(C1 +  C2)
sage: M_f = multiplication_matrix(f, I)
sage: M_f.det() != 0
True

Hence $f$ does not attain the value $0$ on $V(I)$, so $\varnothing = V(I + \langle f \rangle)$ and $\langle 1 \rangle = I + \langle f \rangle$.

Since $M_f$ is invertible, we can find a polynomial representative of $f^{-1} + I$:

sage: NB = list(I.normal_basis())
sage: len(NB), NB.index(1)
(196, 195)
sage: finv_coeffs = M_f \ vector([0]*195 + [1])
sage: finv = sum(c*m for (c,m) in zip(C_finv, NB))
sage: (f*finv).reduce(I)
1

Then we have $1 = f^{-1} \cdot f$ in $R/I$, i.e. $1 = f^{-1} \cdot f + g$ for some $g \in I$, and we can express $g$ in terms of generators by applying the division algorithm to $1 - f^{-1} \cdot f$ (or finding a lift of it to $I$):

sage: lift_coeffs = [finv] + list((1 - finv*f).lift(I))
sage: sum(c*m for c,m in zip(lift_coeffs, [f] + I.gens()))
1

In this rather special case we can find a lift of $1$ quickly and efficiently using linear algebra.

Let $R$ be a polynomial ring over $\mathbb{C}$, $I \subset R$ a zero-dimensional radical ideal and $f \in R$. To show $\langle 1 \rangle = I + \langle f \rangle$ it suffices (by Hilbert's Nullstellensatz) to show $\varnothing = V(I + \langle f \rangle) = V(I) \cap V(f)$, i.e. that $f$ does not vanish on $V(I)$. Since $I$ is radical, the ideal of polynomials in $R$ vanishing on $V(I)$ is exactly $I$ (by the Nullstellensatz). By definition of zero-dimensional, the quotient $R/I$ is a finite-dimensional $\mathbb{C}$-vector space.

• Consider the $\mathbb{C}$-linear "multiplication by $f$" map $M_f: g \mapsto f \cdot g$ on $R/I$. Let $g$ be an eigenvector of $M_f$ with eigenvalue $\lambda$, so $f \cdot g = \lambda \cdot g$ or $(f-\lambda) g = 0$ holds in $R/I$, i.e. $(f-\lambda)g \in I$. The fact that $g \neq 0$ in $R/I$ means $g \not\in I$, hence there is a point $p \in V(I)$ with $g(p) \neq 0$. Now from $(f-\lambda)g \in I$ it follows that $\lambda = f(p)$ is the value of $f$ at the point $p$.

• Conversely, if $P$ is the minimum polynomial of $M_f$ then $P(M_f) = 0$ implies $P(f) = 0$ in $R/I$ (by evaluating at $1 \in R/I$), hence $P(f) \in I$ and it follows that $0 = P(f)(p) = P(f(p))$ for all $p \in V(I)$, i.e. all values $f(p)$ for $p \in V(I)$ are zeros of $P$, and hence they are eigenvalues of $M_f$.

So the values of $f$ on $V(I)$ are exactly the eigenvalues of $M_f$, and it suffices to show that $0$ is not one of them.

Given a Groebner basis $G$ of $I$, the multivariate polynomial division algorithm implies that the set of of all monomials not divisible by any leading terms of $G$ is a basis of $R/I$ as a $\mathbb{C}$-vector space (called the normal basis). The matrix of $M_f$ with respect to this basis is easily computed:

def multiplication_matrix(f, I):
G = I.groebner_basis()
f = f.reduce(G)
NB = I.normal_basis()
M = Matrix(f.base_ring(), len(NB))
for (i, m1) in enumerate(NB):
g = (f*m1).reduce(G)
M.set_column(i, [g.monomial_coefficient(m2) for m2 in NB])
return M

We apply it to the problem at hand:

sage: f = 5*u0*z2 + 5*u1*z4 + 7*u2*z6 - u0 + 1/125
sage: I = R.ideal(C1 +  C2)
sage: M_f = multiplication_matrix(f, I)
sage: M_f.det() != 0
True

Hence $f$ does not attain the value $0$ on $V(I)$, so $\varnothing = V(I + \langle f \rangle)$ and $\langle 1 \rangle = I + \langle f \rangle$.

Since $M_f$ is invertible, we can find a polynomial representative of $f^{-1} + I$:

sage: NB = list(I.normal_basis())
sage: len(NB), NB.index(1)
(196, 195)
sage: finv_coeffs = M_f \ vector([0]*195 + [1])
sage: finv = sum(c*m for (c,m) in zip(C_finv, zip(finv_coeffs, NB))
sage: (f*finv).reduce(I)
1

Then we have $1 = f^{-1} \cdot f$ in $R/I$, i.e. $1 = f^{-1} \cdot f + g$ for some $g \in I$, and we can express $g$ in terms of generators by applying the division algorithm to $1 - f^{-1} \cdot f$ (or finding a lift of it to $I$):

sage: lift_coeffs = [finv] + list((1 - finv*f).lift(I))
sage: sum(c*m for c,m in zip(lift_coeffs, [f] + I.gens()))
1