Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

[edited after Alexandre's answer]

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}$.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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
3  
"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}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.