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

Let $(a_{ij})$ be a $n\times n$ symmetric matrix such that $a_{ij}\geq 0$ for all $i,j$ and $a_{ii}=0$ for all $i$. Under which conditions on the $a_{ij}$'s can one find $n$ vectors $v_1,\ldots,v_n\in{\mathbb R}^n$ such that for all $i,j$ the area of the parallelogram spanned by $v_i$ and $v_j$ equals $a_{ij}$:

$\forall i,j:\quad\|v_i\|^2\|v_j\|^2-\langle v_i,v_j\rangle^2=a_{ij}^2$ ?

Here is the only and obvious necessary condition I know about: if $a_{ij}=0$ for some $i\neq j$, then $a_{ik}a_{jl}=a_{il}a_{jk}$ for all $k,l$.

What if $a_{ij}>0$ for all $i\neq j$ ?

Thank you.

Edit. As Noah Stein suggested, a useful reformulation of the question is: can one prescribe the $2\times2$ principal minors of a symmetric positive semidefinite matrix?

Edit 2. See also George Lowther comment. It is always possible (and easy!) to prescribe the $2\times 2$ principal minors of a symmetric $n\times n$ matrix. If the $a_{ij}$'s, $1 \leq i < j \leq n $, are to be those minors, we simply need to choose $n$ numbers $g_{ii}$ such that $g_{ii}g_{jj}\geq a_{ij}$ for all $i\neq j$. Then we are done with the symmetric matrix $G=(g_{ij})$ whose off diagonal entries are given by $g_{ij}=\epsilon_{ij}\sqrt{g_{ii}g_{jj}-a_{ij}}$, where $\epsilon_{ij}=\pm 1$.

So the initial question becomes : under what conditions on the $a_{ij}$'s, can one find $n$ real numbers $g_{ii}\geq 0$, and $\epsilon_{ij}=\pm 1$, so that the matrix $G$ defined above is positive semidefinite?

share|improve this question
    
Here is another obvious necessary condition: $a_{ij}+a_{jk}\leq a_{ik}$ (triangle inequality). That this is true in dimension 3 can be seen by projecting two of the three "side" faces of the tetrahedron with edges $v_i, v_j, v_k$ onto the remaining one; it is true in general because any 3 vectors span at most 3-dimensional subspace of $\mathbb{R}^n.$ Moreover, in case of equality $v_i, v_j, v_k$ are coplanar, which imposes a rank condition on the matrix similar to the one you gave for a pair of collinear vectors. –  Victor Protsak May 23 '12 at 16:40
3  
@Victor Protsak: I am not sure I understand what you mean. If $n=3$ the problem always has a solution. Assume for simplicity that $a_{12},a_{13},a_{23}$ are all $>0$. Then taking 3 orthogonal vectors $v_1,v_2,v_3\in{\mathbb R}^3$ such that $\|v_1\|^2=\frac{a_{12}a_{13}}{a_{23}}$, $\|v_2\|^2=\frac{a_{12}a_{23}}{a_{13}}$ and $\|v_3\|^2=\frac{a_{13}a_{23}}{a_{12}}$ does it –  Julien Maubon May 23 '12 at 18:00
    
Yes, you are right! I was thinking too quickly, and the diagram didn't work: the projection of the union of two faces is not the remaining face - in your construction, it even has zero area. –  Victor Protsak May 23 '12 at 18:31
6  
I don't have much to contribute except a slight reformulation. Since you have written everything in terms of the inner products $\langle v_i, v_j\rangle$ you can state the problem in terms of the Gram matrix of the $v_i$, the matrix with entries $G_{ij} = \langle v_i, v_j\rangle$. A square matrix $G$ is the Gram matrix of some list of vectors if and only if it is positive semidefinite, so your question becomes: does there exist a positive semidefinite matrix with prescribed $2\times 2$ principal minors? This seems like something someone must have studied. –  Noah Stein May 23 '12 at 20:47
4  
For the case with $a_{ij} > 0$, setting $\lambda_i=\Vert\nu_i\Vert^{-2}$ and $u_i=\nu_i/\Vert\nu_i\Vert$, then $1-\lambda_i\lambda_ja_{ij}=\langle u_iu_j\rangle^2$. So the question becomes whether there exists such $\lambda_i$ such that $1-\lambda_i\lambda_ja_{ij}$ are the elements of the componentwise square of a positive semidefinite matrix. But how do you tell if a matrix is the componentwise square of a positive semidefinite one? I don't know if there is a simple way. This question might be slightly relevant: mathoverflow.net/questions/52642 –  George Lowther May 23 '12 at 22:54

3 Answers 3

up vote 6 down vote accepted

In the case where the matrix $(a^2_{ij})\_{i,j=1,\ldots,n}$ is nonsingular, then the problem reduces to the condition that it has a single positive eigenvalue. In fact, we have the following for any $n\times n$ nonzero symmetric matrix $A$ with nonnegative components and zero diagonal (I'll remove the square from $a_{ij}$, as it doesn't seem to help).

If there exist $\nu_i\in \mathbb{R}^n$ such that $$ \begin{align} A_{ij}=\lVert\nu_i\rVert^2\lVert\nu_j\rVert^2-\langle\nu_i,\nu_j\rangle^2&&{\rm(1)} \end{align} $$ then $A$ has a single positive eigenvalue (counting multiplicities).

Conversely, if $A$ is nonsingular and has a single positive eigenvalue, then there exists $\nu_i\in\mathbb{R}^n$ satisfying (1).

First, suppose that (1) holds. Then, there exist nonnegative reals $\lambda_i$ and a positive semidefinite matrix $S$ such that $A_{ij}=\lambda_i\lambda_j(1-S_{ij}^2)$, simply by taking $\lambda_i=\lVert\nu_i\rVert^2$ and $S_{ij}=\langle\hat\nu_i,\hat\nu_j\rangle$, where $\hat\nu_i=1_{\lbrace\nu_i\not=0\rbrace}\nu_i/\lVert\nu_i\rVert$. Let $\lambda=(\lambda_i)\_{i=1,\ldots,n}\in\mathbb{R}^n$. Using the fact that the componentwise square of a positive semidefinite matrix is itself positive semidefinite, $$ x^{\rm T} A x= \langle x,\lambda\rangle^2-\sum_{ij}(\lambda_ix_i)S_{ij}^2(\lambda_jx_j)\le\langle x,\lambda\rangle^2. $$ In particular, $x^{\rm T}A x\le0$ for all vectors orthogonal to $\lambda$. So, the space generated by eigenvectors with positive eigenvalues cannot contain any nonzero members orthogonal to $\lambda$, and has dimension at most one. But, as the trace of $A$ is zero, it must have at least one positive eigenvalue.

Conversely, suppose that $A$ has a single positive eigenvalue and is nonsingular. Diagonalization gives $$ A=u u^{\rm T}-\sum_{\alpha=1}^{n-1} v_{\alpha}v_{\alpha}^{\rm T} $$ for nonzero orthogonal $u,\nu_\alpha\in\mathbb{R}^n$. As the diagonal of $A$ is zero, $$ u_i^2=\sum_\alpha\nu_{\alpha,i}^2. $$ Using Cauchy–Schwarz, $$ A_{ij}\le u_iu_j+\sqrt{\sum_\alpha v_{\alpha,i}^2\sum_\beta v_{\beta,j}^2} =u_iu_j+\vert u_iu_j\vert. $$ So, the $u_i$ are all nonzero, otherwise $A$ would have a row with no positive elements. Then, $u_iu_j > 0$.Writing $S=\lbrace i=1,2,\ldots,n\colon u_i > 0\rbrace$ we would have $A_{ij}=0$ for $i\in S$ and $j\not\in S$. Breaking $A$ down into two blocks on which the row and column indices are respectively in $S$ and not in $S$, we can break the problem down to the case where $u_i$ are all of the same sign. W.l.o.g., take $u_i > 0$. For $1 > \epsilon > 0$, define the matrix $$ \begin{align} S_{ij}&=\sqrt{1-\epsilon u_i^{-1}u_j^{-1} A_{ij}}\cr &=1-\frac12\epsilon u_i^{-1}u_j^{-1} A_{ij}+O(\epsilon^2)\cr &=1-\epsilon/2+\frac\epsilon2\sum_{\alpha}u_i^{-1}u_j^{-1}v_{\alpha,i}v_{\alpha,j}+O(\epsilon^2) \end{align} $$ As the vectors $u,v_{\alpha}$ are linearly independent, the same is true of the vectors $\tilde u=(1,1,\ldots,1)$ and $\tilde v_\alpha=(u_1^{-1}v_{\alpha,1},\ldots,u_n^{-1}v_{\alpha,n})$. Then, $$ x^{\rm T}Sx=(1-\epsilon)\langle\tilde u,x\rangle^2+\frac\epsilon2\left(\langle\tilde u,x\rangle^2+\sum_\alpha\langle\tilde v_\alpha,x\rangle^2\right)+O(\epsilon^2\lVert x\rVert^2) $$ is nonnegative for all $\epsilon$ small enough and $x\in\mathbb{R}^n$. In this case $S$ is positive definite and (by Gram-Schmidt, for example) there are $\hat\nu_i\in\mathbb{R}^n$ with $S_{ij}=\langle\hat\nu_i,\hat\nu_j\rangle$. Setting $\nu_i=\epsilon^{-1/4}u_i^{1/2}\hat\nu_i$ gives (1).


That concludes the case where $A$ is nonsingular. The singular case is, I think, considerably more complicated.

share|improve this answer
    
Thanks a lot! Very nice! –  Julien Maubon May 30 '12 at 17:04
    
No problem. The nonsingular case is rather simpler than the general case though. The $\epsilon_{ij}\in\lbrace-1,1\rbrace$ mentioned in the question can always be taken to be equal to 1. For singular matrices, you might need to make use of the flexibility to choose the sign of the square roots, which makes the question rather harder. –  George Lowther May 30 '12 at 20:53

I didn't check the paper by Oeding cited in Igor's answer, but i guess the following is in similar veins. You could compute a Groebner basis for the ideal generated by the $\binom{n}{2}$ equations you have (obviously working over $\mathbb{R}$). If all the variables corresponding to the $\{v_i=(v_{i1},\ldots,v_{in})\}$ are larger than those corresponding to $\{ a _{ij}\}$, then the polynomials in the Groebner basis having only $a$'s give you the algebraic relations which should be satisfied by the entries in the matrix.

Now, I wonder whether one can then find a pattern for generating such polynomials for arbitrary $n$.

share|improve this answer
1  
Thanks. I know essentially nothing about Groebner bases, unfortunately... Just one remark. In general there should be no algebraic relations that have to be satisfied by the $a_{ij}$'s. Indeed, using the notation of Edit 2 in the question, if for some set of $a_{ij}>0$ one can find $g_{ii}$'s and $\epsilon_{ij}$'s so that the matrix $G$ they define is positive definite, then there is an open neighborhood of the $a_{ij}$'s for which the same holds. It seems that algebraic relations should appear only "on the boundary" of the set of possible $a_{ij}$'s, whatever this means. –  Julien Maubon May 27 '12 at 14:07

This is studied in this very nice paper by Luke Oeding Oeding does not put in the positive semi definiteness conditions, but this makes the question only slightly more complicated.

share|improve this answer
1  
Thanks for the answer, this is indeed one of the paper I saw after reading Noah's comment. I may be missing something but I think Oeding addresses a different problem. He wants to prescribe all the principal minors of a symmetric matrix, whereas I want to prescribe only the 2x2 principal minors, but of a positive semidefinite matrix, as you pointed. If we drop the positive semidefinite condition then it's always possible to prescribe the 2x2 principal minors. See George Lowther comment and Edit 2 in the question. –  Julien Maubon May 24 '12 at 12:50

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.