Algorithm Khachiyan (Khachiyan) to build the minimum (by area) ellipse around a given set of points

Question

MATLAB

I'm trying to write a C++ program that calculates the minimum (by area) ellipse described around a given set of points. On stackoverflow, a matlab pseudocode was found that implements the optimal Hachiyan algorithm for solving this problem.
During the rewriting of the code in C ++, a couple of problems arose that I, with my little knowledge of linear algebra, could not find answers to.
Problem 1 - the second action in the while loop from the pseudocode given on the stackoverflow:
M = diag(Q' * inv(X) * Q); // Q' - transpose of Q
For some initial sets of points, such as {{1, 2}, {3, 4}, {5, 6}, {7, 8}}, this matrix is ​​obtained X for which there is no inverse, and all subsequent calculations are impossible.
Question: How should this be interpreted (the whole set of points should not lie on one line?)?
Problem 2 - interpretation of the final matrix form of the ellipse equation.
As I understand it, the final result is presented in the form of two matrices - a 2x1 matrix c that defines the center of the desired ellipse and a 2x2 matrix A that represents some coefficients from the ellipse equation as a second-order curve (?).
Question: How can I bring this matrix form to the canonical form (well, or to the form from which it will be more convenient to visualize it)?

Answer 1

Problem 1:
Matrix Q has the form:
Matrix X has the form:
Given the form of matrix Q, matrix X will take the form:
If all x or y are equal to zero, then all points lie on one straight line. This is a special uninteresting case. If x and y are non-zero, then we will not have null rows. If the determinant of the matrix X is equal to zero, then we can write (express the rows through each other; simpler cases are obvious):
Same thing: Multiply
the first row by a, the second by b, add : obviously for the case N = 2. Draw a circle with radius squared equal to 2 and a straight line x + y = 2. They will touch at the same point. After you draw, it will become obvious for any N.
So, we have proved that if the determinant of X is equal to zero, then the points lie on one straight line.
Found the right side from the matlab site:
Find the eigenvalues ​​and unit length eigenvectors (they must be orthogonal) for matrix A, after which, using the point
as the center, you need to draw the length eigenvector
(lambda corresponds to the eigenvector). Likewise for the other. These vectors will be the major and minor semiaxes for our ellipse. Further on the capabilities of the visualizer.
Somehow it all came together.