# Sign symmetry

[L09] Lofberg, Johan. Pre-and post-processing sum-of-squares programs in practice. IEEE transactions on automatic control 54, no. 5 (2009): 1007-1011.

using DynamicPolynomials
@polyvar x[1:3]
(DynamicPolynomials.Variable{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}}[x₁, x₂, x₃],)

We would like to determine whether the following polynomial is a sum-of-squares.

poly = 1 + x^4 + x * x + x^4 + x^2
$$$1 + x_{3}^{2} + x_{1}x_{2} + x_{2}^{4} + x_{1}^{4}$$$

In order to do this, we can solve the following Sum-of-Squares program.

import CSDP
solver = CSDP.Optimizer
using SumOfSquares
function sos_check(sparsity)
model = Model(solver)
con_ref = @constraint(model, poly in SOSCone(), sparsity = sparsity)
optimize!(model)
println(solution_summary(model))
return gram_matrix(con_ref)
end

g = sos_check(Sparsity.NoPattern())
g.basis.monomials
7-element DynamicPolynomials.MonomialVector{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}}:
1
x₃
x₂
x₁
x₂²
x₁x₂
x₁²

As detailed in the Example 4 of [L09], we can exploit the sign symmetry of the polynomial to decompose the large positive semidefinite matrix into smaller ones.

g = sos_check(Sparsity.SignSymmetry())
monos = [sub.basis.monomials for sub in g.blocks]
3-element Vector{DynamicPolynomials.MonomialVector{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}}}:
[x₂, x₁]
[x₃]
[1, x₂², x₁x₂, x₁²]