Given a sufficient number of linearly independent points on an ellipsoid's surface....

Algebra Level pending

Given a sufficient number of linearly independent points on an ellipsoid's surface, compute the surface's equation in a specific style and normalized in specific manner. The answer is the sum of the equation's coefficients.

For three dimensions, nine linearly independent points are required. The reason will be explained in the solution, which will use matrix algebra for a more compact presentation. Now, the points, with each row being the coordiantes of a point: $\left( \begin{array}{ccc} -4 & 3 & \frac{125 \sqrt{49319}+57660}{19806} \\ -3 & -1 & \frac{125 \sqrt{115535}+39612}{19806} \\ -3 & 4 & \frac{63822-250 \sqrt{27515}}{19806} \\ -2 & 1 & \frac{50616-375 \sqrt{37167}}{19806} \\ -1 & 0 & \frac{250 \sqrt{88907}+47094}{19806} \\ 1 & 4 & \frac{69102-750 \sqrt{10979}}{19806} \\ 3 & -1 & \frac{125 \sqrt{202703}+47532}{19806} \\ 6 & 2 & \frac{2000 \sqrt{374}+66018}{19806} \\ 6 & 3 & \frac{70860-125 \sqrt{102119}}{19806} \\ \end{array} \right)$ .

In plain text: {{-4, 3, (57660 + 125 Sqrt[49319])/19806}, {-3, -1, (39612 + 125 Sqrt[115535])/19806}, {-3, 4, (63822 - 250 Sqrt[27515])/19806}, {-2, 1, (50616 - 375 Sqrt[37167])/19806}, {-1, 0, (47094 + 250 Sqrt[88907])/19806}, {1, 4, (69102 - 750 Sqrt[10979])/19806}, {3, -1, (47532 + 125 Sqrt[202703])/19806}, {6, 2, (66018 + 2000 Sqrt[374])/19806}, {6, 3, (70860 - 125 Sqrt[102119])/19806}}

Here is an image of the ellipsoid:

Here is a second, example ellipsoid's points: $\left( \begin{array}{ccc} 1 & 1 & \frac{37570 \sqrt{22562}+3217760}{6600723} \\ 1 & 3 & \frac{-2890 \sqrt{4219193}-1132768}{6600723} \\ 1 & 3 & \frac{2890 \sqrt{4219193}-1132768}{6600723} \\ 2 & 0 & \frac{2175264-43350 \sqrt{481206}}{6600723} \\ 2 & 1 & \frac{7225}{\sqrt{2200241}} \\ 2 & 2 & \frac{-43350 \sqrt{481206}-2175264}{6600723} \\ 2 & 3 & \frac{21675 \sqrt{1098573}-4350528}{6600723} \\ 3 & 1 & \frac{-37570 \sqrt{22562}-3217760}{6600723} \\ 3 & 1 & \frac{37570 \sqrt{22562}-3217760}{6600723} \\ \end{array} \right)$ .

The specific style is all terms on the left hand side of the equation, the right hand side is 0, and each term is a coefficient and a product of variables. The normalization is that fractions are cleared by multiplying both sides of the equation by the least common multiple of the denominators so that there are no longer any fractions. Then, the resultant coefficients are reduced by dividing both sides of the equation by the greatest common divisor . Finally, enter the absolute value of the sum. Note well, that the right hand side of the equation stays zero during the normalizations.

Here is an example of the style and normalizations using the second, example ellipsoid: $\frac{63673 x_1^2}{65025}+\frac{163072 x_2 x_1}{614125}+\frac{75712 x_3 x_1}{1842375}-\frac{23116468 x_1}{5527125}+\frac{6773209 x_2^2}{52200625}+\frac{2200241 x_3^2}{52200625}+\frac{1450176 x_2 x_3}{52200625}-\frac{41268658 x_2}{52200625}-\frac{17221568 x_3}{156601875}+\frac{1680803116}{469805625}=0$ .

The least common multiple of the absolute value of denominators of the left hand side of the equation is $469805625$ .

After multiplying both sides of the equation by $469805625$ , the equation becomes: $460037425 x_1^2+124750080 x_2 x_1+19306560 x_3 x_1-1964899780 x_1+60958881 x_2^2+19802169 x_3^2-371417922 x_2+13051584 x_2 x_3-51664704 x_3+1680803116=0$ .

Since no denominators became $-1$ , it is not necessary to clear that denominator by multiplying top and bottom of that term alone by $-1$ .

The greatest common divisor of the coefficents of the resultant equation's left hand side is $1$ . Therefore, that normalization does not need to be done explicitly.

Adding the coefficients of the terms (including the constant term, of course) and taking the absolute value gives $9272591$ . This is the answer for the for the second, example equation.

2020-10-08T13:19: Material copied from a problem report discussion.

The base problem is to find the equation of the ellipsoid described above. Because of limitations of the Brilliant answering system, the answer is given based on a computation of that equation written in a specific form. Much of the discussion in the problem description is just to get the equation into the necessary form to do the computation.

Here is the discussion from my answer to the problem report from someone who found the original discussion incomprehensible. Brilliant has resolved that report.

I am using homogenous coordinates and matrix algebra to get a more compact notation. The closest that I can get to your form would be "The equation of this ellipsoid can be expressed as $x_1^2 a_{1,1}+2 x_2 x_1 a_{1,2}+2 x_3 x_1 a_{1,3}+2 x_1 a_{1,4}+x_2^2 a_{2,2}+2 x_2 x_3 a_{2,3}+2 x_2 a_{2,4}+x_3^2 a_{3,3}+2 x_3 a_{3,4}+a_{4,4}=0$ , where the $a$ variables are integers and the greatest common divisor of the $a$ variables is $1$ . The answer is the absolute value of the sum of the coefficients of the $x$ variable terms."

A general quadratic polynomial can be written as: $\left( \begin{array}{cccc} x_1 & x_2 & x_3 & 1 \\ \end{array} \right) \left( \begin{array}{cccc} a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} \\ a_{1,2} & a_{2,2} & a_{2,3} & a_{2,4} \\ a_{1,3} & a_{2,3} & a_{3,3} & a_{3,4} \\ a_{1,4} & a_{2,4} & a_{3,4} & a_{4,4} \\ \end{array} \right) \left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \\ 1 \\ \end{array} \right)= \\ x_1^2 a_{1,1}+2 x_2 x_1 a_{1,2}+2 x_3 x_1 a_{1,3}+2 x_1 a_{1,4}+x_2^2 a_{2,2}+2 x_2 x_3 a_{2,3}+2 x_2 a_{2,4}+x_3^2 a_{3,3}+2 x_3 a_{3,4}+a_{4,4}=0$ .

The coefficients of the polynomial form are $a_{1,1},2 a_{1,2},2 a_{1,3},2 a_{1,4},a_{2,2},2 a_{2,3},2 a_{2,4},a_{3,3},2 a_{3,4},a_{4,4}$ .

You will need to make them be integers by multiplying by an appropriate integer and by dividing by the greatest common divisor of the resultant integers (which is the equivalent of the $p$ and $q$ of $\frac{p}{q}$ must be relatively prime).

I supplied a worked solution of the same problem with a different ellipsoid and therefore a different answer.

The answer is 1788975.

1 solution

A Former Brilliant Member
Oct 4, 2020

As warned, matrix algebra and in particular, affine transformations are being used.

Generate the following matrix equation and simplify it: $\left|\left( \begin{array}{cccccccccc} 1 & 2 x_1 & x_1^2 & 2 x_2 & 2 x_1 x_2 & x_2^2 & 2 x_3 & 2 x_1 x_3 & 2 x_2 x_3 & x_3^2 \\ 1 & -8 & 16 & 6 & -24 & 9 & \frac{125 \sqrt{49319}+57660}{9903} & -\frac{4 \left(125 \sqrt{49319}+57660\right)}{9903} & \frac{125 \sqrt{49319}+57660}{3301} & \frac{\left(125 \sqrt{49319}+57660\right)^2}{392277636} \\ 1 & -6 & 9 & -2 & 6 & 1 & \frac{125 \sqrt{115535}+39612}{9903} & \frac{-125 \sqrt{115535}-39612}{3301} & \frac{-125 \sqrt{115535}-39612}{9903} & \frac{\left(125 \sqrt{115535}+39612\right)^2}{392277636} \\ 1 & -6 & 9 & 8 & -24 & 16 & \frac{63822-250 \sqrt{27515}}{9903} & \frac{250 \sqrt{27515}-63822}{3301} & \frac{4 \left(63822-250 \sqrt{27515}\right)}{9903} & \frac{\left(63822-250 \sqrt{27515}\right)^2}{392277636} \\ 1 & -4 & 4 & 2 & -4 & 1 & \frac{50616-375 \sqrt{37167}}{9903} & -\frac{2 \left(50616-375 \sqrt{37167}\right)}{9903} & \frac{50616-375 \sqrt{37167}}{9903} & \frac{\left(50616-375 \sqrt{37167}\right)^2}{392277636} \\ 1 & -2 & 1 & 0 & 0 & 0 & \frac{250 \sqrt{88907}+47094}{9903} & \frac{-250 \sqrt{88907}-47094}{9903} & 0 & \frac{\left(250 \sqrt{88907}+47094\right)^2}{392277636} \\ 1 & 2 & 1 & 8 & 8 & 16 & \frac{69102-750 \sqrt{10979}}{9903} & \frac{69102-750 \sqrt{10979}}{9903} & \frac{4 \left(69102-750 \sqrt{10979}\right)}{9903} & \frac{\left(69102-750 \sqrt{10979}\right)^2}{392277636} \\ 1 & 6 & 9 & -2 & -6 & 1 & \frac{125 \sqrt{202703}+47532}{9903} & \frac{125 \sqrt{202703}+47532}{3301} & \frac{-125 \sqrt{202703}-47532}{9903} & \frac{\left(125 \sqrt{202703}+47532\right)^2}{392277636} \\ 1 & 12 & 36 & 4 & 24 & 4 & \frac{2000 \sqrt{374}+66018}{9903} & \frac{2 \left(2000 \sqrt{374}+66018\right)}{3301} & \frac{2 \left(2000 \sqrt{374}+66018\right)}{9903} & \frac{\left(2000 \sqrt{374}+66018\right)^2}{392277636} \\ 1 & 12 & 36 & 6 & 36 & 9 & \frac{70860-125 \sqrt{102119}}{9903} & \frac{2 \left(70860-125 \sqrt{102119}\right)}{3301} & \frac{70860-125 \sqrt{102119}}{3301} & \frac{\left(70860-125 \sqrt{102119}\right)^2}{392277636} \\ \end{array} \right)\right|=0$ .

The outer vertical bars $|$ request the determinant of the matrix.

The result with everything on the left hand side is: $72400 x_1^2-21120 x_2 x_1-15840 x_3 x_1-55040 x_1+101889 x_2^2+118836 x_3^2-212124 x_2-58104 x_2 x_3-580968 x_3-1138904=0$

That is an equation of the ellipsoid. Apply the normalizations and and add the coefficients. $\therefore$

Remember the $a$ matrix. The matrix is symmetrical. The number of distinct values in the matrix is therefore 10. But, one of the values can be forced to being a specific value, e.g., $a_{4,4}$ can be made to be $1$ . Therefore, in general, the number of needed points is $\frac{(\text{dimensions}+1)(\text{dimensions}+2)}{2}-1$ . That is also the rows that were added to make the matrix equation's matrix square so that the determinant could be computed.

Now how to extract the center of the ellipsoid and its semiradii.

Homogenous coordinates are used so that affine transformation methods can be used: $\left\{x_1,x_2,x_3,1\right\}$ .

For the ellipsoid on which we are working, by equating matching terms, the values in the $a$ matrix can be determined: $a_{1,1}\to 72400,a_{1,2}\to -10560,a_{1,3}\to -7920,a_{1,4}\to -27520,a_{2,2}\to 101889,a_{2,3}\to -29052,a_{2,4}\to -106062,a_{3,3}\to 118836,a_{3,4}\to -290484,a_{4,4}\to -1138904$ . $\left( \begin{array}{cccc} 72400 & -10560 & -7920 & -27520 \\ -10560 & 101889 & -29052 & -106062 \\ -7920 & -29052 & 118836 & -290484 \\ -27520 & -106062 & -290484 & -1138904 \\ \end{array} \right)$ .

The solution of this matrix equation gives the ellipsoid's center: $\left( \begin{array}{ccc} 72400 & -10560 & -7920 \\ -10560 & 101889 & -29052 \\ -7920 & -29052 & 118836 \\ \end{array} \right) \left( \begin{array}{c} -c_1 \\ -c_2 \\ -c_3 \\ \end{array} \right)= \left( \begin{array}{c} -27520 \\ -106062 \\ -290484 \\ \end{array} \right)\to \left( \begin{array}{c} 1 \\ 2 \\ 3 \\ \end{array} \right)$

Translating the ellipsoid's center to the origin gives this equation: $72400 x_1^2-21120 x_2 x_1-15840 x_3 x_1+101889 x_2^2+118836 x_3^2-58104 x_2 x_3-2250000=0$ .

Computing the eigenvalues and eigen vectors of the upper left square matrix of dimension $\text{dimensions}$ , in this case, 3 by 3, gives: $\text{eigenvalues}\to \{140625,90000,62500\}, \text{eigenvectors}\to \left( \begin{array}{ccc} 0 & -3 & 4 \\ -15 & 16 & 12 \\ 20 & 12 & 9 \\ \end{array} \right)$ .

The eigen vectors are read row-wise. When the vectors are normalized (adjusted so that their length is $1$ ) gives a rotation matrix, which may be improper (that is, contains a reflection). Unfortunately, the order of the eigen values and of the columns of rotation matrix is correct. The information about mapping back to the $x$ coordinates is lost though. Nonetheless, the values of the semi-radii can be extracted. The problem comes from the fact that there are $\text{dimensions}!\to 3!\to 6$ from a sphere's axes to the final ellipsoid coordinates, each with an appropriate rotation matrix. One does not which mapping the eigensystem will present. The sphere is first scaled by the semi-radii, in some order, then rotated by a rotation matrix whose orderings are dependent both how the sphere is scaled and how the ellipsoid's coordinates are assigned. Please, see the animated GIF below.

Applying the inverse of the rotation matrix to $q$ coordinates gives an equation: $140625 q_1^2+90000 q_2^2+62500 q_3^2-2250000=0$ . Dividing both sides by the constant term's abolute value $2250000$ gives an equation: $(\frac{q_1}{4})^2+(\frac{q_2^2}{5})^2+(\frac{q_3^2}{6})^2=1$ , from which the semi-radii can be read readily.

There are six frames, one for each possible transformation, the sets repeat five times. Each frame is oriented so that the final result is the same--showing one of each semi-radii in its final position and the one each of the original axes of the unit sphere (note, that the original sphere's axes do not start out in the same orientations in all cases) and the radii colors reflect the original sphere's radii:

Given a sufficient number of linearly independent points on an ellipsoid's surface....

The answer is 1788975.

1 solution

0 pending reports