PolynomialAsMatrix

PolynomialAsMatrix
Creates a compact fully symmetric matrix representation of a polynomial
Other toolboxes required	none
Related functions	CopositivePolynomial PolynomialOptimize PolynomialSOS
Function category	Polynomial optimization
Usable within CVX?	yes

PolynomialAsMatrix is a function that computes a compact form of a fully symmetric matrix representation of an even-degree homogeneous polynomial. More specifically, if p is a homogeneous polynomial of degree 2d then there is a unique fully symmetric matrix \(M\) with the property that \(p(x_1,x_2,\ldots,x_n) = (\mathbf{x}^{\otimes d})^T M(\mathbf{x}^{\otimes d})\), where \(\mathbf{x} = (x_1,x_2,\ldots,x_n)\) as a column vector. Here, "fully symmetric" means that \(M^T = M\), \(M\) is supported on the symmetric subspace (i.e., \(PMP = M\), where \(P\) is the symmetric projection), and \(M\) equals its own partial transpose (across any bipartition).

This function returns this fully symmetric matrix \(M\), in symmetric coordinates. That is, there is an isometry \(V\) from the symmetric subspace of \((\mathbb{C}^n)^{\otimes d}\) to \((\mathbb{C}^n)^{\otimes d}\) itself with the property that the output of this function equals \(V^*MV\). This isometry \(V\) is computed by SymmetricProjection(N,D,1,0).

Syntax

• M = PolynomialAsMatrix(P,N,D)
• M = PolynomialAsMatrix(P,N,D,K)

Argument descriptions

• P: The polynomial, represented as a vector of coefficients of its monomials in lexicographic order.
• N: The number of variables in the polynomial.
• D: Half the degree of the polynomial.
• K (optional, default 0): A non-negative integer that indicates the level of the SOS or SOS-type hierarchy. More specifically, this input argument causes the output matrix to represent the polynomial (S(x))^K * P(x) instead of P(x) itself, where S(x) = x1^2 + x2^2 + ... + xN^2.

Examples

A simple low-degree polynomial

Let's turn the homogeneous polynomial \(p(x,y,z) = x^2 + 2xy + 3xz + 4y^2 + 5yz + 6z^2\) into its fully symmetric matrix representation.

>> n = 3;% number of variables
>> d = 1;% half the degree of the polynomial
>> p = [1;2;3;4;5;6];% coefficients of the polynomial, in lexicographical order of the monomials
>> M = full(PolynomialAsMatrix(p,n,d))

M =

    1.0000    1.0000    1.5000
    1.0000    4.0000    2.5000
    1.5000    2.5000    6.0000

The output of this function is always sparse, so we used the full function around the output above just to make the output easier to see. Since \(d = 1\), the above matrix is the usual symmetric matrix representation of the quadratric form \(p\). The following verification of this fact requires MATLAB's symbolic toolbox:

>> syms x y z
>> expand([x y z]*M*[x;y;z])
 
ans =
 
x^2 + 2*x*y + 3*x*z + 4*y^2 + 5*y*z + 6*z^2

The Motzkin polynomial

The Motzkin polynomial is the following degree-6 homogeneous polynomial\[p(x,y,z) = x^4y^2 + x^2y^4 - 3x^2y^2z^2 + z^6\]. To use this PolynomialAsMatrix function, we have to first arrange the monomials of p (even the ones with coefficient 0) in lexicographical order and list them in a vector. To make this task (much!) easier, we use the exp2ind helper function:

>> n = 3;% number of variables
>> d = 3;% half the degree of the polynomial
>> p = zeros(nchoosek(n+2*d-1,2*d),1);% initialize p to have the correct size
>> p(exp2ind([4 2 0])) = 1;% the "4 2 0" here are the exponents in the term x^4y^2z^0, while the "1" is the coefficient of this term
>> p(exp2ind([2 4 0])) = 1;
>> p(exp2ind([2 2 2])) = -3;
>> p(exp2ind([0 0 6])) = 1;% now p represents the Motzkin polynomial
>> M = full(PolynomialAsMatrix(p,n,d))

M =

         0         0         0    0.1155         0         0         0         0         0         0
         0    0.2000         0         0         0         0    0.1155         0   -0.1000         0
         0         0         0         0         0         0         0   -0.1000         0         0
    0.1155         0         0    0.2000         0   -0.1000         0         0         0         0
         0         0         0         0   -0.2000         0         0         0         0         0
         0         0         0   -0.1000         0         0         0         0         0         0
         0    0.1155         0         0         0         0         0         0         0         0
         0         0   -0.1000         0         0         0         0         0         0         0
         0   -0.1000         0         0         0         0         0         0         0         0
         0         0         0         0         0         0         0         0         0    1.0000

The output of this function is always sparse, so we used the full function around the output above just to make the output easier to see. When \(d > 1\) (like in this example), we can verify that the above matrix represents the given polynomial via the isometry created by the SymmetricProjection function. The following verification of this fact requires MATLAB's symbolic toolbox:

>> P = SymmetricProjection(n,d,1,0);
>> MF = P*M*P';
>> syms x y z
>> v = [x;y;z];
>> expand(Tensor(v,3).'*MF*Tensor(v,3))
 
ans =
 
x^4*y^2 + x^2*y^4 - 3*x^2*y^2*z^2 + z^6

Source code

Click here to view this function's source code on github.

References

Coming soon.