Solving a quadratic equation problem with two variables

Question

This is a post of two three problems regarding the method to solve bivariate quadratic equations.

In brief,

1. How does the elimination happen here. Or, how is the elimination used? (Update, I know how this is done now. See update below)
2. Is the method below viable? If not, how to solve this problem in matrix format? (Update) Nope, this method below is not viable because rank 2 matrices cannot be factorized. And an alterative matrix method can be seen in chapter 11 of this book.
3. (Update) I also post a method. Is it valid and complete? In order to be complete, some measurements should be done to avoid the case where there are no solutions (i.e., conics don't intersect)

The very source of the problem is:

$\begin{cases} a_1x^2 + b_1y^2 + c_1xy + d_1x + e_1y + f_1 = 0 \\ a_2x^2 + b_2y^2 + c_2xy + d_2x + e_2y + f_2 = 0 \end{cases}$

(Problem 1) I find a method here, but it does not tell me how the elimination work. How did the elimination work?

(Backgrounds of problem 2) I heard that this problem also can be solved by matrices:

Say we convert the equations into

$\begin{cases} X^TAX = 0 \\ X^TBX = 0 \\ X = \begin{bmatrix}x &y &1\end{bmatrix}^T \end{cases}$

where $A$ and $B$ are symmetric and are obtained from the two equations respectively. And if $rank(A) = 3$ and $rank(B) =3$ (which happens most of the cases for randomly generated real symmetric matrices), to find the solution, one should find the eigenvalue of $A^{-1}B$, i.e.,

$[V, D] = eigs(A^{-1}B)$, where $V$ is the eigenvector matrix and $D$ is the eigenvalue matrix.

Then we can always find

$ X^T(\lambda{A} - B)X = 0$, where $\lambda$ is the diagonal value of matrix $D$.

($\lambda{A} - B$) is guaranteed to have a rank of lower than 3 since its determinant is $0$, and either it can be rank $1$ or rank $2$. Let's call it $C$. Then I do another diagonalization, such that

$X^TCX = X^TP^{-1} D_C PX = X^TP^T D_C PX = (PX)^TD_C(PX) = PX \cdot D_CPX$

, where $D_C$ is the diagonal matrix for $C$, and $P$ is its corresponding eigenvector matrix. Assume

$D_C = \begin{bmatrix} \lambda_{C1} & 0 & 0 \\ 0 & \lambda_{C2} & 0 \\ 0 & 0 & \lambda_{C3} \end{bmatrix}$, $P= \begin{bmatrix} p_1 & p_4 & p_7 \\ p_2 & p_5 & p_8 \\ p_3 & p_6 & p_9 \end{bmatrix}$, $\lambda_{C3} = 0$

Then the final result is something like:

$\lambda_{C1} (p_1 x + p_2 y + p_3)^2 + \lambda_{C2} (p_4 x + p_5 y + p_6)^2 = 0$

(Problem 2) is the following true? If yes, prove it and express the equation in a factorized format (You can use any notation if you want). If not, how to solve in matrix format?

The rank of matrix $C$, as I tested with Matlab scripts, can be either $1$ or $2$. In that post (I don't know where it is now), he says

each eigenvalue corresponds to a $C$, and $X^TCX=0$ corresponds to a factorized quadratic equation so that you can find $3$ equations that has the format of:

$\begin{cases} Eq_1 = (m_{11}x+m_{12}y+m_{13})(m_{14}x+m_{15}y+m_{16}) = 0 \\ Eq_2 = (m_{21}x+m_{22}y+m_{23})(m_{24}x+m_{25}y+m_{26}) = 0 \\ Eq_3 = (m_{31}x+m_{32}y+m_{33})(m_{34}x+m_{35}y+m_{36}) = 0 \\ \end{cases}$

And $Eq_3$ can be removed because "it is not telling anything new" and can be represented by $Eq_1$ and $Eq_2$. There are $4$ solutions in total by solving the systems of equations below:

Solve $(x_1, y_1)\begin{cases} m_{11}x+m_{12}y+m_{13} = 0 \\ m_{21}x+m_{22}y+m_{23} = 0 \end{cases}$

Solve $(x_2, y_2) \begin{cases} m_{11}x+m_{12}y+m_{13} = 0 \\ m_{24}x+m_{25}y+m_{26} = 0 \end{cases}$

Solve $(x_3, y_3) \begin{cases} m_{14}x+m_{15}y+m_{16} = 0 \\ m_{21}x+m_{22}y+m_{23} = 0 \end{cases}$

Solve $(x_4, y_4) \begin{cases} m_{14}x+m_{15}y+m_{16} = 0 \\ m_{24}x+m_{25}y+m_{26} = 0 \end{cases}$

(Edited for some grammatical problem)

Any $(m_{1}x+m_{2}y+m_{3})(m_{4}x+m_{5}y+m_{6})$ is not different from

$ = \begin{bmatrix} x &y & 1\end{bmatrix} \begin{bmatrix} m_1 \\ m_2 \\ m_3\end{bmatrix} \begin{bmatrix} m_4 & m_5 & m_6\end{bmatrix} \begin{bmatrix} x\\y\\1\end{bmatrix} = \begin{bmatrix} x &y & 1\end{bmatrix} \begin{bmatrix} m_1 m_4 & m_1 m_5 & m_1 m_6 \\ m_2 m_4 & m_2 m_5 & m_2 m_6 \\ m_3 m_4 & m_3 m_5 & m_3 m_6 \\ \end{bmatrix} \begin{bmatrix} x\\y\\1\end{bmatrix} $

The method is proved to be invalid. But can someone solve it with matrix form?

(Edited for proof)

I find a solution in Perspectives on Projective Geometry by Jurgen Richter-Gebert. The process is seen in chapter 11 of this book.

(Edited for finding one complete solution)

Okay, I am still not satisfied. So I want to make a method as well. It seems like we can always do the following step because eigenvalues of symmetric matrices are always real.

$C_{12} = \sqrt{\lambda_{C1}} (p_1 x + p_2 y + p_3) = \pm\sqrt{-\lambda_{C2}} (p_4 x + p_5 y + p_6)$

The $_{12}$ notation above means there are two equations ($C1$ and $C2$, plus and minus respectively) written into one. And with three eigenvalues we will have three groups of equations that look like this below (Shown two, but actually three). After some work, both equations can always be written as

$\begin{bmatrix}c_1 & c_2 & c_3\end{bmatrix}$ $\begin{bmatrix}x \\ y \\ 1\end{bmatrix}$ = 0, which represents a line. $C_1$ and $C_2$ represent two branches of solution.

Then, for a different eigenvalue, we will have $C_{34}$ ($C_3$ and $C_4$). Similarly, $C_3$ and $C_4$ represent two branches of solution. A set of solution can be obtained from, similar to the last method,

$\begin{cases} C_1 = 0 \\ C_3 = 0 \end{cases}\rightarrow (x_1, y_1)$

$\begin{cases} C_1 = 0 \\ C_4 = 0 \end{cases}\rightarrow (x_2, y_2)$

$\begin{cases} C_2 = 0 \\ C_3 = 0 \end{cases}\rightarrow (x_3, y_3)$

$\begin{cases} C_2 = 0 \\ C_4 = 0 \end{cases}\rightarrow (x_4, y_4)$

For combination of different ranks of matrices, the strategy is about finding two degenerate combinations ($\det(\lambda_1 A + \mu B)$) such that we have two groups of lines.

If both full rank (i.e., the combinations of $(\lambda , \mu)$ should not have a zero in it), we need to use two different eigenvalues of one matrix and establish two new degenerate cases.

If one is full rank and one is singular (i.e., one of the combination of $(\lambda , \mu)$ has a zero in it), then we only need one more degenerate case.

If both are singular, then we already have two degenerate cases. (In the combination, two of them should be $(something_1, 0)$ and $(0, something_2)$).

Question 3: Why can we just use two of the three will be fine for both full rank cases? I did not prove this yet, because I am new to this question (saw it 3 days ago).

But with some educated guess, just imagine the solutions are the lines that intersect on the intersection of conics (four points). You can draw three "kinds" of lines. Each two lines are parallel. The "three" here corresponds to three eigenvalues. The two parallel lines corresponds to the $\pm$ cases (two branches). If you pick any two combination of groups you can always find the four points and it is just up to you to use which two of them.

(Edited for posting an alternative method)

Allow me to make some stupid jokes, here's a not so detailed procedure on how to find the quartic equation.

First, treat $x$ as a constant in the function, then we can find y as a function of $x$, where there are two parts, one with square roots and one without. I'd like to write this as:

$y = notsoshit_{1}(x) \pm shit(x)$,

And let's consider

$notsoshit_{2}(x) = shit(x)^2$

because function without square roots are good elements in the bigger function. I want to avoid derive this myself and it is really... long. The $notsoshit$ functions contain elements that are not independent to what we have in the original functions, and then they can disappear (although it can be lengthy). Thus, substitute this into the original two equations, you will get something like

$\begin{cases} a_{3}x^2 + b_{3}shit(x)x + c_{3}x + d_{3}shit(x) + e_{3} = 0 \\ a_{4}x^2 + b_{4}shit(x)x + c_{4}x + d_{4}shit(x) + e_{4} = 0 \end{cases}$

Then we should eliminate the shit(x) element (Choose either one function to eliminate $d$). The next step is putting $shit(x)x$ to R.H.S., so that no square roots on L.H.S., and then make do a square for this function, so that no square roots on both sides.

It is something like:

$(a_{5}x^2+b_{5}x + c_{5})^2 = d_{5}(shit(x) x)^2 = d_{5}notsoshit_{2}(x)x^2$

After some work it will be in the beautiful format:

$a_{6}x^4+b_{6}x^3 + c_{6}x^2 + d_{6}x + e = 0$

I am not sure how wolfram did this process (Link in the very front), but then the mission is to eliminate $shit(x)$ by adding the two equations with some ratios.

(Edited for posting the method for elimination /Problem 1)

Answer 1

Property

$$X^TC_{3 \times 3}X = (ax + by + c)(dx + ey + f)$$

does not characterizes rank 2 matrices but rank 1 matrices.

Indeed, the RHS can be written under the form:

$$\begin{pmatrix}x&y&z\end{pmatrix}\underbrace{\begin{pmatrix}a\\b\\c\end{pmatrix}\begin{pmatrix}d&e&f\end{pmatrix}}_{\text{rank one matrix}}\begin{pmatrix}x\\y\\z\end{pmatrix}$$

Answer 2

Using the procedure described in Chapter 11 of the textbook suggested by the OP, I was able to write a computer program to find the four intersection points, and verified that it worked.

The reader is referred to that book for the details, which are summarized below for emphasis:

1. Start by describing both conics in homogenized coordinates by two $3 \times 3 $ symmetric matrices $C_1$ and $C_2$, where the each conic is the solution of $ r^T C_i r = 0 $, where $r = [x, y, 1]^T$.

2. Construct the matrix $C_0 = \alpha C_1 + \beta C_2 $ and determine the combination of $\alpha$ and $\beta$ that will result in $\det{C_0} = 0$. In my program, I first set $\alpha = 0, \beta = 1$, and checked the determinant, then I assumed that $\alpha \ne 0 $ and divided by it, resulting in $\alpha = 1$ and the determinant being a function of $\beta$ only. This results in a cubic polynomial in $\beta$ which can be solved in closed form (I have a procedure for that in my library).

3. For all the resulting combinations of $\alpha$ and $\beta$ from step 2, calculate the matrix $C_0$ which is now known to be rank deficient. Instead of following the procedure in the textbook, I used eigenvalue/eigenvector factorization, to write

$$ C_0 = R D R^T $$

And setup the system $ r^T R D R^T r = 0 $, define $r' = R^T r$, solved for $r'$ , then found the corresponding $r$, and this gave me two lines.

4. For each of the two lines, I intersected its equation which is basically, $ r = v_0 + t v_1 $ for two real vector $v_0 $ and $v_1$ , with the equation for the first conic (the second conic can be used just as well), so I plugged in

$(v_0 + t v_1)^T C_1 (v_0 + t v_1) = 0 $

And solved the quadratic for $t$, thus generating the intersections points.

In the following, I explain step $3$ in more detail. For the matrix $C_0$ obtained from step 2, we know that it is rank deficient, hence when diagonalizing it, we will have

$$ C_0 = R D R^T $$

where we can assume that $D_{33}= 0$, and that $D_{11} > 0 $ and $D_{22} < 0 $. If we now consider the degenrate conic $ r^T C_0 r = 0$, and define $r' = R^T r $, then we have $r'^T D r' = 0 $ which when expanded becomes,

$$ D_{11} (r'_x)^2 + D_{22} (r'_y)^2 = 0 $$

(Remember that $D_{11} \gt 0 , D_{22} \lt 0 $). Hence, this determines the two lines

$r' = (x', y', z') = t (1, \pm \sqrt{-\dfrac{D_{11}}{D_{22}}}, 0) + s (0, 0, 1) =: t v_t + s v_s $

for arbitrary parameters $t$ and $s$. Since $r = R r'$ then

$ r = t R v_t + s R v_s =: t w_t + s w_s \hspace{36pt} (*)$

To find the line in the $xy$ plane, we have to set $z = 1$ (so that $r$ represents homogenized coordinates). This means we have to intersect the plane given in equation $(*)$ with the plane $z = 1$, and this will give us the two lines that we're seeking. (Remember $v_t$ represents two vectors because of the $\pm$ in its definition).