Groebner basis calculations in Sage: three examples
|
If you want to know what a Groebner basis actually is: "What is a Groebner Basis" (AMS Notices?)
Techniques to mention:
1) How to set up polynomial rings
2) Solving equations by changing term ordering or using elimination ideals
3) Reducing degrees of freedom by plugging in guesses
4) Breaking into cases with a complete primary decomposition
5) Generating a certificate via lifting
Under the hood of Sage
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Question 1: What are all the points of intersection between the circle $$(x - 1)^2 + (y - 1)^2 = 1$$ and the parabola $$y = x^2?$$
|
|
|
|
|
|
|
This Groebner basis is only slightly reduced from what we started with, and is not so helpful for solving the equations, since $x$ and $y$ are still mixed up together in both polynomials. (This is because the default term order for a polynomial ring in Sage, “degrevlex”, orders first by total degree, which is usually the fastest choice for calculations.)
|
Okay, so how do we actually solve it? Two approaches: Change the term order, or project down to an elimination ideal.
|
|
|
|
|
|
|
Question 2: Does $\mathcal{S}(C_4)$ contain a matrix $B$ with spectrum $(0, 0, 1, 1)$?
This is related to a question that came up during Shaun Fallat’s Combinatorial Matrix Theory session: For a tree $T$, $$q(T) \ge \mathrm{diam}(T) + 1.$$
For what other graphs is this true? Odd cycles? Even cycles?
It is not hard to show that $\mathrm{M}(C_k) = 2$ means that this inequality does hold for odd cycles $k = 3, 5, \dots$
So the first interesting case is $C_4$. For $B \in \mathcal{S}(C_4)$, can we have $q(B) = 2$?
Without loss of generality, can the spectrum of $B$ be $(0, 0, 1, 1)$?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Oops—that choice leads to imaginary values for $a$ and $c$. But maybe it is possible to break into simpler cases using a complete primary decomposition.
|
|
|
|
|
|
|
|
|
Question 3: For the graph $\mathrm{Circ} = $ CirculantGraph(11, [1, 3]), does $$\mathrm{M}(\mathrm{Circ}) = \mathrm{Z}(\mathrm{Circ})?$$
|
|
Useful fact: A zero forcing set of size $6$ guarantees a (non-principal) submatrix that is permutation equivalent to a necessarily invertible upper-triangular matrix of size $11 - 6 = 5$.
|
|
|
|
The question reduces to whether there exists any $B \in \mathcal{S}(\mathrm{Circ})$ whose rank is only $11 - \mathrm{Z}(\mathrm{Circ}) = 5$
Since we are only interested in rank rather than all of the spectrum, we can freely assume that all of the spanning tree edges have weight $1$.
For all other edges, and for the diagonal entries, we need variable names.
|
|
|
|
|
If $B$ is truly rank $5$, then any $6 \times 6$ submatrix must be singular. In fact, since our triangular submatrix is invertible, it suffices to check only those $6 \times 6$ which extend it by a single row and column.
|
|
We can just trust this answer, or we can ask Sage to provide us with a certificate that $1$ can be written as a combination of things all of which are supposed to equal $0$.
|
|
|