# CopositivePolynomial

 Other toolboxes required CopositivePolynomial Creates a homogenous polynomial whose non-negativity is equivalent to copositivity of a given matrix none PolynomialAsMatrixPolynomialOptimizePolynomialSOS Polynomial optimization no

CopositivePolynomial is a function that computes the standard quartic homogeneous polynomial that is associated with a copositive matrix (or any symmetric matrix, in the hope of determining whether or not the matrix is copositive). For example, the Horn matrix

$$C = \begin{bmatrix}1 & -1 & 1 & 1 & -1 \\ -1 & 1 & -1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & -1 & 1 & -1 \\ -1 & 1 & 1 & -1 & 1\end{bmatrix}$$

is associated with the quartic polynomial

$$\displaystyle p(x) = \begin{bmatrix}x_1^2 & x_2^2 & x_3^2 & x_4^2 & x_5^2\end{bmatrix}C\begin{bmatrix}x_1^2 \\ x_2^2 \\ x_3^2 \\ x_4^2 \\ x_5^2\end{bmatrix} = \sum_{i=1}^5 x_i^4 - 2\sum_{i=1}^5x_i^2x_{i+1}^2 + 2\sum_{i=1}^5x_i^2x_{i+2}^2,$$

where the sums in the subscripts are understood to be modulo 5. Copositivity of $$C$$ is equivalent to non-negativity of the polynomial $$p$$.

## Syntax

• P = CopositivePolynomial(C)

• C: A matrix.

## Examples

### The Horn matrix

Let's compute the polynomial (as a vector) representation of the Horn matrix.

>> C = [1,-1,1,1,-1;-1,1,-1,1,1;1,-1,1,-1,1;1,1,-1,1,-1;-1,1,1,-1,1];% the Horn matrix
>> p = CopositivePolynomial(C);
>> sparse(p)% displays the non-zero coefficients of this polynomial

ans =

(1,1)        1
(6,1)       -2
(10,1)        2
(13,1)        2
(15,1)       -2
(36,1)        1
(40,1)       -2
(43,1)        2
(45,1)        2
(56,1)        1
(59,1)       -2
(61,1)        2
(66,1)        1
(68,1)       -2
(70,1)        1

To verify that the above vector of coefficients really does represent the polynomial associated with the Horn matrix, we can perform the follow computation (which requires MATLAB's symbolic computation package):

>> syms x1 x2 x3 x4 x5
>> x = [x1;x2;x3;x4;x5];
>> n = 5;% number of variables = size of Horn matrix
>> d = 2;% half of the degree of the (quartic) polynomial
>> M = PolynomialAsMatrix(p,n,d);% compute a compact fully symmetric matrix representation of this polynomial
>> P = SymmetricProjection(n,d,1,0);% used to expand M to non-symmetric coordinates
>> MF = P*M*P';% MF is a matrix representation in non-symmetric coordinates
>> expand(kron(x,x).'*MF*kron(x,x))% expand to a polynomial

ans =

x1^4 - 2*x1^2*x2^2 + 2*x1^2*x3^2 + 2*x1^2*x4^2 - 2*x1^2*x5^2 + x2^4 - 2*x2^2*x3^2 + 2*x2^2*x4^2 + 2*x2^2*x5^2 + x3^4 - 2*x3^2*x4^2 + 2*x3^2*x5^2 + x4^4 - 2*x4^2*x5^2 + x5^4

Regardless of whether or not the above verification is performed, the vector p can now be used in polynomial optimization functions like PolynomialOptimize and PolynomialSOS.

### Clique polynomial

To be filled in: an example of using this function to create a polynomial whose maximum value bounds the maximum clique size in a graph.