9
$\begingroup$

The entries of Gram matrix is defined by $ \langle x_i,x_j\rangle$ in the $(i,j)^{\text{th}}$ position. It is known that Gram matrix is positive semidefinite.

Is it still positive semidefinite if $ \langle x_i,x_j\rangle$ is replaced by $ |\langle x_i,x_j\rangle|$?

$\endgroup$
0

2 Answers 2

Reset to default
8
$\begingroup$

I believe this is true for three vectors, but here's a counterexample with four vectors:

$$x_1=\begin{pmatrix}-1\\-2\\-3\end{pmatrix},\;\;x_2=\begin{pmatrix}-3\\3\\-5\end{pmatrix},\;\;x_3=\begin{pmatrix}-4\\-3\\0\end{pmatrix},\;\;x_4=\begin{pmatrix}-1\\-1\\1\end{pmatrix}$$

I found this by looking for three vectors such that their scalar products are positive and at least one scalar product of two vectors in the dual basis of $\mathbb R^3$ is also positive, so that the difference of these two dual basis vectors is shorter than their sum.

A Hermitian matrix is positive semidefinite if and only if it is the Gram matrix of some set of vectors. Consider the Gram matrix $A$ of the three vectors and the sum of the two dual vectors and the Gram matrix $B$ of the three vectors and the difference of the two dual vectors. They are the same up to signs, except for the square of the sum or difference in the last entry. $A$ has only positive entries. For the component-wise absolute value of $B$ to be the Gram matrix of some set of vectors, the first three vectors would have to be the three basis vectors (up to orthogonal transformations), and the projection of the fourth vector onto the hyperplane of these three would have to be the sum of the dual basis vectors, but its length would have to be the length of the difference, which is impossible, since the difference is shorter than the sum.

This construction doesn't work for three vectors, since in $\mathbb R^2$ the scalar product of the dual basis vectors of a basis with positive scalar product of the basis vectors is always negative.

$\endgroup$
3
  • $\begingroup$ Thanks for your explanation. $\endgroup$
    – Sunni
    Sep 13, 2011 at 12:08
  • $\begingroup$ @joriki Can you provide a reference to the fact you cite about a matrix being positive definition iff it is a Gram matrix? $\endgroup$
    – ItsNotObvious
    Sep 13, 2011 at 12:32
  • 1
    $\begingroup$ @3Sphere: I made this a bit more precise now. (Some include "Hermitian" in the definition of positive-semidefiniteness, others don't.) This is just due to the fact that Hermitian matrices are diagonalizable and the eigenvalues of a positive semidefinite matrix are non-negative, so you can multiply the eigenvectors by the square roots of the eigenvalues to get a set of vectors whose Gram matrix is the given matrix. In the other direction, a Gram matrix is obviously Hermitian, and it is positive semidefinite because $G=X^\dagger X$, so $y^\dagger Gy=y^\dagger X^\dagger Xy=(Xy)^\dagger(Xy)\ge0$. $\endgroup$
    – joriki
    Sep 13, 2011 at 13:00
3
$\begingroup$

The positive semi-definiteness of the Gram matrix can be seen from the following:

$G_{ij} = \langle x_i, x_j \rangle$ is equivalent to write $$ G = \begin{pmatrix} - &x_1^* &-\\ - &x_2^* &-\\ - &\vdots &-\\ - &x_n^* &-\\ \end{pmatrix} \begin{pmatrix} | &| &| &|\\ x_1 &x_2 &\ldots&x_n\\ | &| &| &|\\ \end{pmatrix} = X^*X \succeq 0 $$ Modifiying this structure might or might not preserve the positive semidefinite structure as Joriki showed with a counterexample.

$\endgroup$
2
  • $\begingroup$ Well, this does not seem to answer the question :-) $\endgroup$
    – Srivatsan
    Sep 13, 2011 at 13:32
  • $\begingroup$ I see. I did not realize that the poster of the comments under Joriki's answer is not the OP. That's why I posted for further clarification. But I can remove if you wish. $\endgroup$
    – user13838
    Sep 13, 2011 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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