Home > Algebra, Geometry, Linear Algebra, Python, sage, Scientific Computing, Teaching > An Automatic Geometric Proof

An Automatic Geometric Proof

July 9, 2013 Leave a comment Go to comments

We are familiar with that result that states that, on any given triangle, the circumcenter, centroid and orthocenter are always collinear. I would like to illustrate how to use Gröbner bases theory to prove that the incenter also belongs in the previous line, provided the triangle is isosceles.

We start, as usual, indicating that this property is independent of shifts, rotations or dilations, and therefore we may assume that the isosceles triangle has one vertex at A=(0,0), another vertex at B=(1,0) and the third vertex at C=(1/2, s) for some value s \neq 0. In that case, we will need to work on the polynomial ring R=\mathbb{R}[s,x_1,x_2,x_3,y_1,y_2,y_3,z], since we need the parameter s free, the variables x_1 and y_1 are used to input the conditions for the circumcenter of the triangle, the variables x_2 and y_2 for centroid, and the variables x_3 and y_3 for the incenter (note that we do not need to use the orthocenter in this case).

We may obtain all six conditions by using sympy, as follows:

>>> import sympy
>>> from sympy import *
>>> A=Point(0,0)
>>> B=Point(1,0)
>>> s=symbols("s",real=True,positive=True)
>>> C=Point(1/2.,s)
>>> T=Triangle(A,B,C)
>>> T.circumcenter
Point(1/2, (4*s**2 - 1)/(8*s))
>>> T.centroid
Point(1/2, s/3)
>>> T.incenter
Point(1/2, s/(sqrt(4*s**2 + 1) + 1))

This translates into the following polynomials

h_1=2x_1-1, h_2=8sy_1-4s^2+1 (for circumcenter)
h_3=2x_2-1, h_4=3y_2-s (for centroid)
h_5=2x_3-1, h_6=(4sy_3+1)^2-4s^2-1 (for incenter)

The hypothesis polynomial comes simply from asking whether the slope of the line through two of those centers is the same as the slope of the line through another choice of two centers; we could use then, for example, g=(x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1). It only remains to compute the Gröbner basis of the ideal I=(h_1, \dotsc, h_6, 1-zg) \subset \mathbb{R}[s,x_1,x_2,x_3,y_1,y_2,y_3,z]. Let us use SageMath for this task:

sage: R.<s,x1,x2,x3,y1,y2,y3,z>=PolynomialRing(QQ,8,order='lex')
sage: h=[2*x1-1,8*r*y1-4*r**2+1,2*x2-1,3*y2-r,2*x3-1,(4*r*y3+1)**2-4*r**2-1]
sage: g=(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)
sage: I=R.ideal(1-z*g,*h)
sage: I.groebner_basis()
[1]

This proves the result.

Categories: Algebra, Geometry, Linear Algebra, Python, sage, Scientific Computing, Teaching Tags: , , , , , , ,
  1. rrogers31
    July 9, 2013 at 9:38 am
    Reply

    Great! Would you be interested in a similar practical problem that might be solvable in a similar manner? When I did it, I “proved” it by calculating 360×360 trigonometric terms/points and saying “good enough”. Not very satisfying and it has nagged me for years. I have never thought of using Gröbner basis 🙂
    Ray

  2. rrogers31
    July 11, 2013 at 11:00 am
    Reply

    You have four microphones/sensors to be placed on a plane or sphere. The purpose is to detect and localize sounds from particular locations; say cracks in a bridge or nuclear/chemical containment vessel. This leaves only three readings; the time differences between one microphone to another as a function of the source (x,y).
    Simple part: prove that a square array does not provide a unique solution.
    More complicated: A triangular array with one sensor in the middle does produce a unique solution for both the plane and spherical cases.
    Still more complicated and unknown: What is the optimal sensor geometric placing in terms of sensitivity to misplacing the sensors?

    Although the equations involve sine/cos it would seem to me that replacing those terms could work into the Groebner schemes; say by asserting sin^2+cos^2=1 with s^2+c^2=1 or the more complicated parametrization from Algebraic Geometry.

    Just an idle problem from my past. As I said I have worked out partial solutions by algebra (and some exhaustive sampling) but never using Groebner decompostion techniques which might provide more powerful solutions; and generic techniques.

    • Francisco Blanco-Silva
      July 11, 2013 at 11:19 am
      Reply

      Fun project: I will show it to my students this afternoon, and see what comes out. Send us some of your equations, say for the simple question. LaTeX is fine.

      For the last part, you may want to read up on the theory of frames. Think for example the benefit of being able to represent vectors not in a basis, but on a system containing the elements of several different bases.

  1. No trackbacks yet.

Leave a comment