semi definite representation of a polynomial

Question

Let $P\left( x \right) = {a_0} + {a_1}x + ..... + {a_n}{x^n}$ be a polynomial with degree $n$. How can I write the vector ${\bf{a}} = [{a_0},....{a_n}]$ in a semidefinite matrix form which yields $P\left( x \right)\ge 0 $ for $x \in R$? for example for quadratic polynomial $P\left( x \right) = {a_0} + {a_1}x +{a_2}x^2$ the semi definite representation for $P\left( x \right)\ge 0 $ can be written as $\left[ {\begin{array}{*{20}{c}} {{a_0}}&{a_1/2}\\ {a_1/2}&{{a_2}} \end{array}} \right]\ge{\bf{0}}$.

Answer 1

$ \newcommand{\x}{\vec{\mathbf{X}}} \newcommand{\xt}{\x^{T}\!} \newcommand{\a}{\mathbf{\mathcal{A}}\,} $ It is easy to come up with such representation for a polynomial of even degree.

Similar to your example of $n=2$ $$ \begin{bmatrix} {1} & {x} \end{bmatrix} \begin{bmatrix} {{c_0}}&{\frac{1}{2}c_1}\\ \frac{1}{2}c_1 & c_2 \end{bmatrix} \begin{bmatrix} {1} \\ {x} \end{bmatrix} = \begin{bmatrix} {1} & {x} \end{bmatrix} \begin{bmatrix} {{c_0} + \frac{1}{2}c_1x}\\ \frac{1}{2}c_1 + c_2 x\end{bmatrix} = \left(c_0 + \dfrac{c_1}{2}x \right) \!\cdot\!1 + \left(\dfrac{1}{2} c_1 + c_2x \right) \!\cdot\!x = \\ = c_0 + \dfrac{c_1}{2}x + \dfrac{c_1}{2}x + c_2 x^2 = c_0 + c_1x+ c_2 x^2 = P(x) $$

we can write the more general case for a $2n$-degree polynomial $P(x)$ of the form $$ P(x) = c_0 + c_1 x + c_2 x^2 + \dots + c_{2n-1}x^{2n-1} +c_{2n} x^{2n} = \sum_{i=0}^{2n} c_ix^i $$ Assume $\x$ is an $\left(n+1\right)$-dimentional vector, and $\a$ is $\left(n+1\right)\times \left(n+1\right)$ symmetric matrix $$ \x = \begin{bmatrix} {1} \\ {x} \\ \vdots \\ x^{n}\end{bmatrix}, \qquad \a = \begin{bmatrix} a_{0,0} & a_{0,1} & \dots & a_{0,n} \\ a_{1,0} & a_{1,1} & \dots & a_{1,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,0} & a_{n,1} & \dots & a_{n,n} \end{bmatrix}, $$ Then $P(x)$ can be represented as $\xt\a \x$ $$ \begin{aligned} P(x) &= c_0 + c_1 x + c_2 x^2 + \dots + c_{2n-1}x^{2n-1}+c_{2n}x^{2n} = \xt\a\x = \\& = \begin{bmatrix} {1} & {x} & \cdots & x^{n}\end{bmatrix}\cdot \begin{bmatrix} a_{0,0} & a_{0,1} & \dots & a_{0,n} \\ a_{1,0} & a_{1,1} & \dots & a_{1,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,0} & a_{n,1} & \dots & a_{n,n} \end{bmatrix}\cdot \begin{bmatrix} {1} \\ {x} \\ \vdots \\ x^{n}\end{bmatrix} \\ & = \begin{bmatrix} {1} & {x} & \cdots & x^{n}\end{bmatrix}\cdot \begin{bmatrix} a_{0,0} + a_{0,1}x + a_{0,2}x^2 + \dots + a_{0,n}x^{n} \\ a_{1,0} + a_{1,1}x + a_{1,2}x^2 + \dots + a_{1,n}x^{n} \\ \vdots \\ a_{n,0} + a_{n,1}x + a_{n,2}x^2 + \dots + a_{n,n}x^{n} \end{bmatrix} \\ & =\begin{bmatrix} {1} & {x} & \cdots & x^{n}\end{bmatrix}\cdot \begin{bmatrix} \displaystyle\sum_{k=0}^{n} a_{0,k} x^k \\ \displaystyle\sum_{k=0}^{n} a_{1,k} x^k \\ \displaystyle\vdots \\ \displaystyle \sum_{k=0}^{n} a_{n,k} x^k \end{bmatrix} = \begin{bmatrix} 1 \displaystyle\sum_{k=0}^{n} a_{0,k} x^k \\ x \displaystyle\sum_{k=0}^{n} a_{1,k} x^k \\ \displaystyle\vdots \\ \displaystyle x^{n}\sum_{k=0}^{n} a_{n,k} x^k \end{bmatrix} = \\ & = \sum_{k=0}^{n} a_{0,k} x^k + \sum_{k=0}^{n} a_{1,k} x^{k+1} + \sum_{k=0}^{n} a_{2,k} x^{k+2} + \cdots + \sum_{k=0}^{n} a_{n,k} x^{k+n} \\& = \sum_{k,l = 0}^{n} a_{l, k} x^{k + l}. \end{aligned} $$ Thus we conclude that $$ P(x) = \sum_{i=0}^{2n} c_i x^i = \sum_{k,l = 0}^{n} a_{l, k} x^{k + l}. $$ Collecting coefficients in front of different powers of $x$, we get the system $$ \begin{cases} c_0 = a_{0,0} \\ c_1 = a_{0,1} + a_{1,0} \\ c_2 = a_{0,2} + a_{1,1} + a_{2,0} \\ c_3 = a_{0,3} + a_{2,1} + a_{1,2} + a_{3,0} \\ c_4 = a_{0,4} + a_{3,1} + a_{2,2} + a_{1,3} + a_{4,0} \\ \vdots \\ c_{n-1} = a_{0,n-1} + a_{1,n-2} + \cdots + a_{n-2,1} + a_{n-1,0} \\ c_{n} = a_{0,n} + a_{1,n-1} + \cdots + a_{n-1,1} + a_{n,0} \\ c_{n+1} = a_{1,n} + a_{2,n-1} + \cdots + a_{n-1,2} + a_{n,1} \\ \vdots \\ c_{2n-2} = a_{n-2,n} + a_{n-1,n-1} + a_{n,n-2} \\ c_{2n-1} = a_{n-1,n} + a_{n,n-1} \\ c_{2n} = a_{n,n} \end{cases} $$ In short notation, for every $ i = 1, \dots, 2n $ we have $ c_i = \sum_{k+l = i} a_{l,k}$.

Since $\a$ is supposed to be symmetric, we enforce condition $a_{l,k} = a_{k,l}$, thus getting
$$ c_i = \sum_{k+l = i} a_{l,k} = \begin{cases} a_{\frac{i}{2},\frac{i}{2}} + \sum_{k = 1}^{i-1}\big( a_{k,i-k} + a_{i-k,k} \big), & i \text{ is even,} \\ \sum_{k = 1}^{i-1} \big( a_{k,i-k} + a_{i-k,k} \big) & i \text{ is odd} \end{cases} \\ c_i = \begin{cases} a_{\frac{i}{2},\frac{i}{2}} + 2\sum_{k = 0}^{i} a_{k,i-k}, & i \text{ is even,} \\ 2\sum_{k = 1}^{i-1} a_{k,i-k} & i \text{ is odd} \end{cases}= $$ Finally, we get the system $$ \begin{cases} c_0 = a_{0,0} \\ c_1 = 2a_{0,1} \\ c_2 = a_{1,1} + 2a_{0,2} \\ c_3 = 2\big(a_{0,3} + a_{1,2}\big) \\ c_4 = a_{2,2} + 2\big(a_{0,4} + a_{1,3}\big) \\ \vdots \\ c_{2k-1} = 2\big(a_{0,2k-1} +a_{1,2k-2} + \cdots + a_{k-2,k} + a_{k-1,k-1}\big)\\ c_{2k} = a_{k,k}+2\big(a_{0,2k}+a_{1,2k-1}+\cdots+a_{k-1,k+1} + a_{k,k}\big)\\ c_{2k+1} = 2\big(a_{0,2k+1} +a_{1,2k} + \cdots + a_{k-1,k+2} + a_{k,k+1}\big)\\ \vdots \\ c_{2n-2} = a_{n-1,n-1} + 2a_{n-2,n} \\ c_{2n-1} = 2a_{n-1,n} \\ c_{2n} = a_{n,n} \end{cases} $$ This is a system of $2n+1$ equations with $\frac{1}{2}n\left(n-1\right)$ unknowns $a{l,k}$. Any solution of this system will give you the symmetric matrix representation of $P(x)$.

---

For simplicity, we can assume

• for every even $i=2j$ $c_i = c_{2j} = a_{j,j}$, so we can set $a_{l,k} = 0$ whenever $l+k = 2j = i$ and $l\neq k\neq j$.
• for every odd $i=2j+1$ $c_i = c_{2j+1} = a_{j+1,j} + a_{j,j+1} $, so we can set $a_{l,k} = 0$ whenever $l+k = 2j+1 = i$ and $l\neq k\neq j+1$.

Then one possible symmetric matrix representation of $P(x)$ will look like $$ \a = \begin{bmatrix} c_0 & \frac{1}{2} c_1 & 0 & 0 &\cdots & 0 & 0 & 0 &0 \\ \frac{1}{2} c_1 & c_2 & \frac{1}{2} c_3 & 0 & \cdots & 0 & 0 & 0 &0 \\ 0 & \frac{1}{2} c_3 & c_4 & \frac{1}{2} c_5 & \cdots & 0 & 0 & 0 &0\\ 0 & 0 & \frac{1}{2} c_5 & c_6 & \ddots & 0 & 0 & 0 &0\\ \vdots & \vdots & \vdots & \ddots & \ddots & \ddots & \vdots & \vdots &\vdots\\ 0 & 0 & 0 & 0 & \ddots &c_{2n-6} & \frac{1}{2}c_{2n-5}& 0 &0\\ 0 & 0 & 0 & 0 & \cdots & \frac{1}{2}c_{2n-5} & c_{2n-4} &\frac{1}{2}c_{2n-3} &0\\ 0 & 0 & 0 & 0 & \cdots & 0 & \frac{1}{2}c_{2n-3}& c_{2n-2} &\frac{1}{2}c_{2n-1}\\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 &\frac{1}{2}c_{2n-1} &c_{2n} \end{bmatrix} $$

---

It is easy to see that for the case of polynomial $P(x)$ of an odd degree $2n-1$
we can use the same symmetric matrix representation s for $2n$ degree polynomial, while setting the highest order coefficient to zero $c_{2n} = 0$. $$