Solve quadric equation system

Question

How to solve this analytically(not a numerical solution)?

For given real and symmetric matrices $A_1,A_2,A_3,A_4\in\mathbb{R}^{4\times4}$ find $0\neq x\in\mathbb{R}^4$

$$x^TA_1x=0$$ $$x^TA_2x=0$$ $$x^TA_3x=0$$ $$x^TA_4x=0$$

Example:

Solve the system:

\begin{align} a^2+b^2+c &=3.95 \\ ab+bc+c^2 &=4.57 \\ ac+b &=2.63 \\ \end{align} Denoting: \begin{equation} x = \begin{bmatrix}a & b & c & 1\end{bmatrix}^T \end{equation}

Then the matrices, $A_k$ can be build from the equations, for example to form $A_1$, we rewrite the first equation in matrix form $x^TB_1x=0$ where: \begin{equation} B_1 = \begin{bmatrix} 1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&0&-3.95\\ \end{bmatrix} \end{equation}

Then, since from $x^TB_1x=0$ transpose leads to $x^TB_1^Tx=0$, the sum is:
$x^T(B_1+B_1^T)x=0$ denoting the matrix as $A_1=(B_1+B_1^T)$, it is symmetric and $x^TA_1x=0$

Answer 1

Four equations, but since they are homogeneous there are just three degrees of freedom (say on the unit sphere). So you'll have to be lucky to get any nontrivial solutions at all. Try solving three of these together with $x_1^2 + x_2^2 + x_3^2 + x_4^2 = 1$, and then seeing if the solutions satisfy the fourth equation.

Answer 2

If you accept a numerical solution, then it is possible to make a convex (i.e. treatable) approximation of the problem. Introduce the matrix $X=xx^T$.

1. Rewrite the conditions $x^TA_kx=0$ equivalently as $\text{tr}\,A_k X=0$.
2. Add normalization $\text{tr}\,X=1$ to avoid the trivial solution.
3. Minimize rank of $X$.

Clearly, if there is a vector $x\in\mathbb{R}^4\setminus\{0\}$ that solves the original problem then the rank minimization gives you a rank one matrix, and you can easily find $x$ via factorization of the optimal $X$. Otherwise, if the optimal rank is two or more, then there is no solution to the original problem.

Rank minimization is quite hard (not convex), but there are numerous convex relaxations to it, e.g. using the nuclear norm. The nuclear norm is simply a sum of all singular values $\|X\|_*=\sum_{k=1}^N\sigma_k(X)$, and the minimal solution is known to be of very low rank in general. So a possible relaxation of the problem is the norm minimization with linear constraints $$ \min_{X}\|X\|_*\qquad\text{subject to}\quad \text{tr}\,X=1,\ \text{tr}\,A_k X=0,\ k=1,...,4. $$

UPDATE: You can also test your matrices first by a necessary condition for existence of a non-trivial solution. Obviously, there is no such solution if there exist $\tau_k\in\mathbb{R}$ such that the matrix $\sum_{k=1}^4\tau_kA_k$ is positive definite. Looking for $\tau_k$ is a semi-definite programming that can be solved efficiently.

Answer 3

@ Grigory Ilizirov , you spend your money my friend! Indeed, Robert gave (10 monthes ago !) a three lines solution that clearly shows that your problem has no non-zero solutions when the $(A_i)_i$ are generic matrices.

More precisely, consider the system (S) $x^TA_1x=x^TA_2x=x^TA_3x=x^Tx-1=0$. If $x$ is a solution of (S), then a vector $h$ of the tangent space in $x$ of the set of all solutions satisfies: $h^TA_1x=h^TA_2x=h^TA_3x=h^Tx=0$. Then $h$ is orthogonal to the $3$ vectors $A_1x,A_2x,A_3x$ which, in the generic case, generate a vector space of dimension $3$. then $h$ and $x$ are parallel vectors. Finally, the condition $h^Tx=0$ implies that $h=0$; we conclude that $x$ is an isolated solution and cannot, in the generic case, satisfies the last equation $x^TA_4x=0$ (otherwise $A_4$ would depend on $x$).

EDIT. There are no general formulae. Yet, if you know explicitly the matrice $(A_i)$, as in your example above, you can formally solve the system (S) $x^TA_1x=x^TA_2x=x^TA_3x=x^Tx-1=0$, using the Grobner basis theory (the software is included in Maple). You obtain all $16$ complex solutions in the form $P_{16}(x_1)=0,$for every $i>1, x_i=Q_i(x_1)$, where $P_{16}$ is an even polynomial of degree $16$ and the $(Q_i)$ are polynomial of degree $15$. It remains to keep the real solutions. You may assume $x_1>0$; then there are between $0$ and $8$ real solutions. Of course the effective calculation of the $(x_i)$ is impossible because $P_{16}$ is not solvable by radicals.

Answer 4

Writing the example as $$ \eqalign{a^2 + b^2 + c - \dfrac{395}{100} &= 0\cr a b + b c + c^2 - \dfrac{457}{100} &= 0\cr a c+b-\dfrac{263}{100} &= 0\cr}$$ and using Maple, I get the rational solution $$ a = \dfrac{11}{10},\ b = \dfrac{6}{5},\ c = \dfrac{13}{10} $$ as well as the more complicated $$ \eqalign{ a = &-{\frac {571155568\,{r}^{6}}{239293241139037}}-{\frac { 97836027296\,{r}^{5}}{5982331028475925}}+{\frac {6231586801884\,{r}^{4 }}{5982331028475925}}+{\frac {23593267878176\,{r}^{3}}{ 5982331028475925}}\cr &-{\frac {1202499156203509\,{r}^{2}}{5982331028475925 }}+{\frac {5383059078675992\,r}{5982331028475925}}+{\frac { 34070673499587139}{11964662056951850}}\cr b = & r/5\cr c = &-{\frac {4414166864\,{r }^{6}}{1196466205695185}}-{\frac {224758604064\,{r}^{5}}{ 5982331028475925}}+{\frac {8175883963396\,{r}^{4}}{5982331028475925}}+ {\frac {58329732068364\,{r}^{3}}{5982331028475925}}\cr & -{\frac { 1516933817840111\,{r}^{2}}{5982331028475925}}+{\frac {4604325789069518 \,r}{5982331028475925}}+{\frac {46730409611551821}{11964662056951850}} } $$ where $r$ is a root of the irreducible septic $$ 16\,{r}^{7}+176\,{r}^{6}-6188\,{r}^{5}-54928\,{r}^{4}+1095565\,{r}^{3} -1042350\,{r}^{2}-25308581\,r-29724296 $$ This has three real roots, approximately $-3.258533342, -1.369218643, 14.03972857$. Its Galois group is $S_7$, so no solutions in radicals.