# Systems of simultaneous real quadratic equations

Starting from a problem in spectral graph theory, I got dragged into a problem in combinatorial matrix theory about constructing $n\times n$ real orthogonal matrices with a specified pattern of zero/non-zero entries. (I can expand on this if required.)

Anyway, I have a construction which appears to work (which I have tested in Maple for some small values of $n$), but to prove it in full generality would require showing that a certain system of simultaneous real quadratic equations has a real solution.

I know very little about algebraic geometry and, well, nothing at all about real algebraic geometry, but I was wondering if there were any existing results in the literature which may help with this---as it stands I'm not even sure where to start looking!

The aim (in the first instance) is to construct an orthogonal $n\times n$ matrix with zero diagonal entries and non-zero off-diagonal entries. The idea is to use the following matrix: $$A=\left[ \begin{array}{c|ccc} 0 & 1 & \cdots & 1 \\ \hline 1 & & & \\ \vdots && B & \\ 1 &&& \end{array} \right]$$ where the rows of $B$ are formed of the $n-1$ cyclic permutations of $v=(0,x_1,\ldots,x_{n-2})$. For this to be orthogonal (up to scaling by $\sqrt{n-1}$), the inner product of two distinct rows must be $0$, and the norm of each row must be $\sqrt{n-1}$. This gives the equations $\sum_{i=1}^{n-2} x_i = 0$, $\sum_{i=1}^{n-2} x_i^2 = n-2$, and $\lceil (n-2)/2\rceil$ other equations arising from inner products of rows containing cyclic permutations of $v$ (from adjacent rows, rows 2 apart, 3 apart, etc.). Also, we have the constraint that any solution for $x_1,\ldots.x_n$ may not contain a zero.

For example, when $n=5$, Maple finds the solution $x_2=1$, $x_1,x_3 = \frac{-1\pm \sqrt{3}}{2}$.

Existence of real solutions of systems of algebraic equation is a difficult problem and there is no general theory. You can get an impression of the modern state of it from the nice book:

MR2830310 Sottile, Frank, Real solutions to equations from geometry. American Mathematical Society, Providence, RI, 2011.

Also this one: MR1925796 Sturmfels, Bernd, Solving systems of polynomial equations. American Mathematical Society, Providence, RI, 2002.

Only some very special systems can be presently studied. That all equations are of degree 2 does not help much. But if you write your system, perhaps it is of the special kind about which something is known.

• Thanks for the suggestions of books to look at. I've expanded on my original question to describe the system of equations. – Robert Bailey Jan 18 '13 at 23:10
• "That all equations are of degree 2 does not help much." Indeed. By adding some additional variables, you can reduce any set of simultaneous polynomial equations one involving quadratic equations only. – Federico Poloni Jan 19 '13 at 14:19

This question is linked to the discrete Fourier transform. If $u=[1,\cdots,1]^T$, then $A=\begin{pmatrix}0&u^T\\u&B\end{pmatrix}$ and the equation $AA^T=(n-1)I_n$ is equivalent to $Bu=0,BB^T=(n-1)I_{n-1}-uu^T$. The spectrum of $BB^T$ is $0$ and $n-1$ ($n-2$ times). Let $F$ be the $(n-2)\times(n-2)$ matrix defined by $f_{j,k}=\exp(\dfrac{-2i\pi jk}{n-1})$ (the partial Fourier matrix associated to the non-zero eigenvalues of $B$). $B,B^T$ commute and they are simultaneously diagonalizable (using the complete Fourier matrix) and similar to $B'=diag(F[x_1,\cdots,x_{n-2}]^T)$ and to ${B'}^T=diag(F[x_{n-2},\cdots,x_1]^T)$. The eigenvalues of $BB^T$ are the $B'_{i,i}{B'}^T_{i,i}$. Finally our vector $X$ is solution of the quadratic system: for every $i\leq n-2$, $(\sum_{j=1}^{n-2}f_{i,j}x_j)(\sum_{j=1}^{n-2}f_{i,j}x_{n-1-j})=n-1$.

EDIT: Here $X$ is real; then the equations can be rewritten: for every $i\leq n-2$, $|\sum_{j=1}^{n-2}f_{i,j}x_j|=\sqrt{n-1}$.