Let $A$ be a matrix whose entries are given by a polynomial,

$$ A_{ij} = p(\lambda_i, \lambda_j) $$ where $p(\lambda_i,\lambda_j) = p(\lambda_j,\lambda_i)$ is symmetric.

Are there standard methods for showing that $A\geq 0$ is positive semidefinite, given a polynomial $p$?

I could imagine that there are some sum-of-squares methods, but I don't know exactly how to use these here. Also, I think these sort of matrices are known as polynomial matrix, usually they defined by a univariate polynomial however. I would be very happy for any pointers.

edit: In particular, I have the following polynomial as "kernel" $$ p(\lambda_i,\lambda_j) = x^4 \lambda_i \lambda_j + x^2 \lambda_i^2 \lambda_j^2 - 3x^2 \lambda_i \lambda_i + 1 $$ where $x\geq 0$ is some constant. Clearly, one has $p(\lambda_i,\lambda_j) \geq 0$ when $\lambda_i,\lambda_j\geq 0$.

I believe that $A\geq 0$ when $0 \leq x\leq 1$ and $0\leq\lambda_i\leq 1$ with $\sum_i \lambda_i = 1$.

Setting $y=\lambda_i=\lambda_j$, one retrieves the Motzkin polynomial $$ p(x,y) = x^4 y^2 + x^2 y^4 - 3x^2 y^2 + 1 $$

  • 1
    $\begingroup$ it is not even symmetric. How could it be positive semi-definite. Besides, why do you need that the entries be $\ge0$ ? $\endgroup$ Commented Apr 22, 2020 at 15:43
  • $\begingroup$ whops, I should add that p is indeed symmetric in its arguments. In my problem it happens that the entries are $\geq 0$, it doesn't necessarily need to be the case; I removed those extra conditions. I was hoping to write it in terms of a Gram matrix. $\endgroup$ Commented Apr 22, 2020 at 15:47
  • 2
    $\begingroup$ If your $p(x,y) = f(x-y)$ for some positive-definite function $f$, then $A_{ij}$ will be positive-definite for any number of $\lambda$'s. Pos.-def. functions a characterized by the positivity of their Fourier transform. More generally, there are also positive-definite kernels, but I don't know how they are characterized. $\endgroup$ Commented Apr 22, 2020 at 16:15
  • 1
    $\begingroup$ OK. Now you can write $P(x,y)$ as $Q(x+y,xy)$ for some polynomial $Q$. You should look for a condition over $Q$. For instance, here is a simpler question: for which $Q\in{\mathbb R}[X]$ is it true that ${\rm Mat}(Q(\lambda_i+\lambda_j)$ is positive semi-definite, for every $\vec\lambda$ ? $\endgroup$ Commented Apr 22, 2020 at 16:39
  • $\begingroup$ Thanks! I didn't know about this trick, I will give it a try.. $\endgroup$ Commented Apr 22, 2020 at 16:52

1 Answer 1


Here is an approach that might get you some insight. In particular, the matrix polynomial you have can be written as: $$ \left(x^4 \lambda_i \lambda_j + x^2 \lambda_i^2 \lambda_j^2 - 3x^2 \lambda_i \lambda_j + 1\right)_{i,j} = (x^4-3x^2) D_{\lambda}\boldsymbol{1}D_{\lambda} + x^2 D_{\lambda^2}\boldsymbol{1}D_{\lambda^2} + \boldsymbol{1}, $$ where (i) $D_{\lambda}$ and $D_{\lambda^2}$ are diagonal matrices with entries equal to $[\lambda_! \cdots \lambda_n]$ and $[\lambda_! \cdots \lambda_n]$, respectively and (ii) $\boldsymbol{1}$ is a rank-1 matrix with all 1's. The following points are in order:

(1) For $x\geq \sqrt{3}$, the matrix is always PSD for any $\lambda\geq 0$, as it is a positive linear combination of PSD matrices.

(2) For $\sqrt{2}\leq x< \sqrt{3}$, the matrix is PSD if $\lambda \in \{0,1\}^n$. Reason: in this case, $D_{\lambda^2}=D_{\lambda}$, and thus the matrix can be written as $(x^4-2x^2) D_{\lambda}+\boldsymbol{1}$. The PSD then follows.

(3) For $0\leq x< \sqrt{3}$, the matrix cannot be PSD for all $\lambda>0$. Reason: Note that the column spaces of $D_{\lambda}\boldsymbol{1}D_{\lambda}$, $D_{\lambda^2}\boldsymbol{1}D_{\lambda^2}$ and $\boldsymbol{1}$ are given by multiples of vectors $\lambda$, $\lambda^2$ and $\boldsymbol{1}^{n\times 1}$, respectively. Consider $\lambda=[1 \cdots 1~z_1 ~z_2 ~z_3]$. The for distinct non-zero $z_1, z_2, z_3$, the vector $\lambda=[1 \cdots 1~z_1 ~z_2 ~z_3]$ is not spanned by vectors $\lambda^2=[1 \cdots 1~z^2_1 ~z^2_2 ~z^2_3]$ and $\boldsymbol{1}^{n\times 1}$ (Vandermonde matrix has full rank for distinct values). This implies that choosing $v$ as the component of $[1 \cdots 1~z_1 ~z_2 ~z_3]$ perpendicular to $[1 \cdots 1~z^2_1 ~z^2_2 ~z^2_3]$ and $\boldsymbol{1}^{n\times 1}$ yields, $v^\top \left((x^4-3x^2) D_{\lambda}\boldsymbol{1}D_{\lambda} + x^2 D_{\lambda^2}\boldsymbol{1}D_{\lambda^2} + \boldsymbol{1}\right)v = v^\top \left((x^4-3x^2) D_{\lambda}\boldsymbol{1}D_{\lambda}\right)v<0$.

You can possibly find out more cases. Hope it helps.

  • $\begingroup$ Thanks a lot, point (3) is a very interesting approach, maybe I can use this sort of reasoning.. I am sorry that I didn't specify the ranges where I think this kernel is positive - initially I wanted to ask a more general question. The ranges are $0 \leq x \leq 1$ and $0\leq\lambda_i\leq 1$ with $\sum_i \lambda_i = 1$; I edited the question. I will try to think how the method in your point (3) can still be used. $\endgroup$ Commented Apr 23, 2020 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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