Linear algebra for GPS
Adapted from Dan Kalman’s article An Underdetermined Linear System for GPS in the November 2002 issue of the College Mathematics Journal.

Please email completed file to tleise@amherst.edu by 4pm Tuesday.

GPS calculations involve triangulation using at least 4 satellites to determine a point on the surface (location of the GPS receiver) and the time at which the GPS receiver receives the signals from the satellites. We will do a very simplified calculation in this lab, neglecting the issue of measurement error and physical complications (e.g., that the atmosphere impedes radio signals differently at different altitudes) and using only 4 satellites (while real systems use more than 4 to reduce the effects of noise and errors). Please note that real GPS calculations are much more complicated that the supersimplified problem we will examine. But this lab will show us the gist of how to carry out triangulation-type calculations.

Suppose our GPS receiver is onboard a ship at sea in an unknown location. The GPS receiver obtains simultaneous signals from four satellites in space. Each signal specifies its time of transmission and the position of the satellite at that time. From this information, the GPS receiver computes its position and the time. We want to work through this computation.

Imagine an xyz-coordinate system with the Earth centered at the origin, the positive z-axis running through the north pole and fixed along the Earth’s axis of rotation (so the xy-plane intersects the equator; the positive x-axis can be fixed to correspond to 0 degrees longitude if desired). The unknown position of the ship can be expressed as a point (x, y, z). To simplify things, work in units equal to the radius of the Earth and we’ll pretend that the Earth is a perfect sphere described by (x^2) + (y^2) + (z^2) = 1 in this system. Because radio signal travel at about the speed of light (0.047 Earth radii per millisecond), we will measure time in units of milliseconds. The GPS system determines distances by seeing how long it takes a radio signal to get from one point to another. 

Our ship is at an unknown position and has no clock. It receives simultaneous signals from four satellites, giving their positions and times as shown in the table below. (These numbers were made up for this example; in a real case the satellite coordinates would not involve simple integers and the time would not be such small numbers.)

({{Satellite, Position, Time}, {1, (1,2,0), 19.9}, {2, (2,0,2), 2.4}, {3, (1,1,1), 32.6}, {4, (2,1,0), 19.9}})

We want to deduce the position (x,y,z) of the ship and the time t at which the ship received the signals from the four satellites.

The distance traveled by the radio signal from Satellite 1 to the ship equals speed multiplied by the amount of time since the signal was sent: 

d = 0.047(t-19.9)

This distance also equals the distance between the points (x,y,z) and (1,2,0):

d = (Sqrt[(((x-1))^2) +((( y-2))^2) + (((z-0))^2)])

Square each of these expressions. The difference should equal zero:

(((x-1))^2) +((( y-2))^2) + (((z-0))^2) - (0.047^2)(((t-19.9))^2) == 0

Save the left hand side in Mathematica:

c=0.047;
Satellite1LHS=(x-1)^2+(y-2)^2+(z-0)^2-c^2(t-19.9)^2

Exercise 1. Find the corresponding expressions for Satellites 2, 3, and 4. Enter them into Mathematica as Satellite2LHS, Satellite3LHS, and Satellite4LHS.

Exercise 2. We need to get rid of the nonlinear terms, so subtract Satellite1LHS from each of the other expressions. Each expression equals zero, so the differences all equal zero, too. Press shift-enter on the code below to enter these 3 resulting equations into Mathematica.

eq1=Expand[Satellite2LHS-Satellite1LHS==0]
eq2=Expand[Satellite3LHS-Satellite1LHS==0]
eq3=Expand[Satellite4LHS-Satellite1LHS==0]

Exercise 3. Now we want to solve this linear system. Observe that we have 3 equations in 4 unknowns (x,y,z,t), so we expect at least one free variable. In fact, we will get exactly one free variable. Find the general solution for (x,y,z) in terms for the free variable t. (Move the constants to the right hand side.)

Exercise 4. To determine the correct value of t for the GPS problem, plug your solution for (x,y,z) from Exercise 3 into the original equation for Satellite 1 and solve for t. (It’s a quadratic equation, so we expect 2 solutions for t here.)

Exercise 5. Plug each value of t from Exercise 4 into the solution for (x,y,z) from Exercise 3 to determine the coordinates of the two solution points.

Exercise 6. Which set of coordinates is on the Earth’s surface? State your final solution for the ship’s coordinates (x,y,z) and the time t.