# Matrix whose entries are given by polynomial $A_{ij} = p(\lambda_i, \lambda_j)$; when is it positive semidefinite?

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

• it is not even symmetric. How could it be positive semi-definite. Besides, why do you need that the entries be $\ge0$ ? – Denis Serre Apr 22 at 15:43
• 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. – Felix Huber Apr 22 at 15:47
• 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. – Igor Khavkine Apr 22 at 16:15
• 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$ ? – Denis Serre Apr 22 at 16:39
• Thanks! I didn't know about this trick, I will give it a try.. – Felix Huber Apr 22 at 16:52

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$$.
• 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. – Felix Huber Apr 23 at 21:49