ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 9 (2015) 243-259 Rational sums of hermitian squares of free noncommutative polynomials Kristijan Cafuta * University of Ljubljana, Faculty of Electrical Engineering, Laboratory of Applied Mathematics, Tržaška cesta 25, 1000 Ljubljana, Slovenia Igor Klep f The University of Auckland, Department of Mathematics, Private Bag 92019, Auckland 1142, New Zealand Janez Povh * Faculty of Information studies in Novo mesto, Novi trg 5, 8000 Novo mesto, Slovenia Received 25 July 2013, accepted 13 March 2014, published online 11 January 2015 In this paper we consider polynomials in noncommuting variables that admit sum of hermitian squares and commutators decompositions. We recall algorithms for finding decompositions of this type that are based on semidefinite programming. The main part of the article investigates how to find such decomposition with rational coefficients if the original polynomial has rational coefficients. We show that the numerical evidence, obtained by the Gram matrix method and semidefinite programming, which is usually an almost feasible point, can be frequently tweaked to obtain an exact certificate using rational numbers. In the presence of Slater points, the Peyrl-Parrilo rounding and projecting method applies. On the other hand, in the absence of strict feasibility, a variant of the facial reduction is proposed to reduce the size of the semidefinite program and to enforce the existence of Slater points. All these methods are implemented in our open source computer algebra package NCSOStools. Throughout the paper many worked out examples are presented to illustrate our results. * Partially supported by the Slovenian Research Agency grants P1-0222 and L1-6722. t Supported by the Marsden Fund Council of the Royal Society of New Zealand. Partially supported by the Slovenian Research Agency grants P1-0222, L1-4292 and L1-6722. Part of this research was done while the author was on leave from the University of Maribor. * The author wishes to thank to Slovenian research agency for support via program P1-0383 and project L74119 and to Creative Core FISNM-3330-13-500033 Simulations project funded by the European Union. Abstract ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 244 Ars Math. Contemp. 9 (2015) 151-163 Keywords: Sum of squares, semidefinite programming, noncommutative polynomial, Matlab toolbox, commutator, cyclic equivalence, free positivity, real algebraic geometry, Motzkin polynomial, Bessis-Moussa-Villani (BMV) conjecture, NCSOStools. Math. Subj. Class.: Primary 13J30, 90C22; Secondary 08B20, 11E25, 90C90 1 Introduction In this paper we consider free noncommutative (nc) polynomials that are sums of hermitian squares (and commutators). We focus on the following important question: how to obtain a rational certificate (i.e., a symbolic proof) for such a decomposition when the given nc polynomial has rational coefficients and we have numerical (approximate) evidence of a sum of hermitian squares (and commutators) decomposition obtained by mathematical optimization methods (e.g. by using open-source software package NCSOStools)? 1.1 Notation Nc polynomials with real coefficients, denoted by r(X}, are (real) linear combinations of words in letters X^ ..., Xn, including the empty word 1. We shortly denote by X the n-tuple of letters (X1,..., Xn). These nc polynomials form a free algebra, which we equip with the involution * that fixes r and letters point-wise and thus reverses words, e.g. (X1X2X3 - X3X1)* = X3X2X1 - 2X1X3?. Hence r(X} is the *-algebra freely generated by n symmetric letters. The subset of r(X} consisting of all symmetric nc polynomials is denoted by Symr(X} := {f € r(X} | f = f *}. If V = (vj) is a (column) vector of nc polynomials vj € r(X}, then V* is the row vector with components v* and V1 denotes the row vector with components vj. The length of the longest word in an nc polynomial f € r(X} is the degree of f and is denoted by deg f. The degree of f in Xj, degi f, is the largest number of occurrences of the letter Xj in a monomial appearing in f. Similarly, the length of the shortest word appearing in f € r(X} is called the min-degree of f and denoted by mindeg f. Likewise, mindegj f is introduced. If the variable Xj does not occur in any monomial of f, then mindegj f = 0. The set of all nc polynomials of degree < d will be denoted by r(X} 0 for every n-tuple of real symmetric matrices A of the same order. Note that positivity implies trace positivity while the converse is not true. Helton [16] and McCullough [27] proved that a symmetric nc polynomial f is positive if and only if it can be decomposed as a sum ofhermitian squares (SOHS), that is, there exist nc polynomials g1,... ,gm such that f = J2 9i9i. We denote all nc polynomials that admit SOHS decompositions as m £2 := {f e Symr(X> | f = ^gUu gi e r(X>, m > l}. i=i For trace positivity there is no necessary and sufficient condition of this type but there exists an important sufficient condition, obtained using cyclic equivalence to SOHS [18]; for a more example specific approach to certificates for trace positivity we refer to [36]. Nc polynomials f,g e r(X> are cyclically equivalent (f ~c g) if and only if there exist nc polynomials pi,qi e r(X> such that k f - g = ^2(Piqi - qiPi). i=i We call an element of the form [p, q] := pq - qp, where p, q e r(X>, a commutator. Cyclically equivalent nc polynomials have equal trace if they are evaluated at the same n-tuple of real symmetric matrices, since the trace of every commutator of matrices is zero. Therefore if f is cyclically equivalent to SOHS, it is trace positive. We denote the set of nc polynomials of this type by e2 := {f e r(X> |3g e £2 : f c£c g}. By definition, the elements in e2 are exactly the nc polynomials which can be written as sums of hermitian squares with commutators. Although any bivariate nc polynomial of degree at most 4 is trace positive if and only if it is a sum of (four) squares with commutators [5, 8], there are trace positive nc polynomials which are not members of e2. Probably the easiest example is the noncommutative Motzkin polynomial, XY4X + YX4 Y - 3XY2X + 1 [18, Example 4.4]; see also Subsection 3.3.2. We also refer the reader to [19, Example 3.5] for more sophisticated examples obtained by considering the BMV conjecture. Cyclic equivalence is obviously an equivalence relation. It can be easily detected by the following remark. Remark 1.2 ([18]). (a) For words v,w e (X>, we have v ~c w if and only if there are words v1, v2 e (X> such that v = v1v2 and w = v2v1. That is, v ~c w if and only if w is a cyclic permutation of v. (b) Nc polynomials f = Ewe aw w and g = Ewe bw w (aw, bw e r) are cyclically equivalent if and only if for each word v e (X >, ^ bw. (1.1) ^cyc^ E E a w 246 Ars Math. Contemp. 9 (2015) 151-163 Example 1.3. Let f = 1 + X2 + 2X2Y - 2XY + 2XY2X G r(X, Y). Since f = (X + XY)*(X + XY) + (1 - YX)* (1 - YX) + [X2 - X,Y] + [XY,YX] it follows that f c~ (X + XY)*(X + XY) + (1 - YX)*(1 - YX), and therefore f G ©2. 1.2 Motivation and related work There is s surge of interest in free real algebraic geometry in the last decade, partially due to many facets of applications. A nice survey on connections to control theory, systems engineering and optimization is given by de Oliveira, Helton, McCullough, Putinar [13]. Applications to quantum physics are explained e.g. by Pironio, Navascu6s, Acin [32] who also consider computational aspects related to sums of hermitian squares. On the theoretical level, trace positive nc polynomials arise e.g. in the Lieb-Seiringer reformulation of the famous Bessis-Moussa-Villani (BMV) conjecture [2] from statistical quantum mechanics, which was recently proved by Stahl [39]. This connection will be explained in detail later to demonstrate the usage of our proposed algorithm. In addition, trace positive nc polynomials occur naturally in von Neumann algebras and functional analysis. For instance, Connes' embedding problem [12] on finite II i-factors is a question about the existence of a certain type of sum of hermitian squares certificates for trace positive nc polynomials [18]. Motivated by this intensive research in free real algebraic geometry we have developed NCSOStools [10] - an open source Matlab toolbox for solving such problems using semidefinite programming. As a side product our toolbox implements symbolic computation with free noncommuting variables in Matlab. 1.3 Contribution The main contribution of this paper is the following. Once we know that a given rational nc polynomial f can be decomposed as a sum of hermitian squares (with commutators), i.e., we have numerical evidence for the existence of such a decomposition, we aim to obtain an exact (rational) certificate. Following ideas from [31] (see also [17]) we propose an algorithm which under a strict feasibility assumption theoretically and practically always yields a rational certificate. On the other hand, in the absence of strict feasibility, a variant of the facial reduction [3] (in our case projecting onto the orthogonal complement of the nullspace of the analytic center) is used to reduce the size of the semidefinite program and enforce the existence of Slater points. We employ the noncommutative version of Motzkin's polynomial to demonstrate how the proposed algorithm as implemented in NCSOStools is used and provide new rational certificates for some instances of nc polynomials related to the Bessis-Moussa-Villani conjecture. 2 Nc polynomials and semidefinite programming 2.1 Semidefinite programming Semidefinite programming (SDP) is a generalization of linear programming (LP) where one looks for the optimum of a linear function over the intersection of an affine subspace K. Cafuta et al.: Rational sums of hermitian squares of free noncommutative polynomials 247 with the cone of positive semidefinite matrices. Although this is a far-reaching extension of LP, there exists several methods that can solve semidefinite programs efficiently in theory and practice. Given s x s self-adjoint matrices C, A^,..., Am of the same size over r and a vector b e rm, we formulate a semidefinite program in standard primal form as follows: inf (C, G) s.t. (Ai,G) = bi, i = l,...,m (PSDP) G h 0. Here (•, •) stands for the standard inner product of matrices: (A,B) = tr(B*A),and G h 0 means that G is positive semidefinite. If C = 0 or if C is not important, we call such a problem a semidefinite programming feasibility problem: ♦ /A G h 0, • 1 (FSDP) s.t. (Ai,G) = bi, i = 1,... ,m. The complexity of solving semidefinite programs is mainly determined by the order s of matrix variable G and the number of linear constraints m. Given e > 0, the interior point methods can find an e-optimal solution with polynomially many iterations, where each iteration takes polynomially many real number operations, provided that (PSDP) and its dual both have non-empty interiors of feasible sets and we have good initial points. The variables appearing in these polynomial bounds are s,m and log e (cf. [40, Chapter 10.4.4]). Many problems in control theory, system identification and signal processing can be formulated using SDPs [4, 30, 1]. Combinatorial optimization problems can often be modeled or approximated by SDPs [14,23, 34, 35, 33]. SDP has important role in real algebraic geometry, where it is used e.g. for finding sums of squares decompositions of polynomials or approximating the moment problem [22, 21, 26, 24], and in free real algebraic geometry [18, 20, 6], as is recalled in the following subsection. 2.2 Sums of hermitian squares (with commutators) and semidefinite programming Testing whether a given nc polynomial f e r(X) is an element of £2 can be done efficiently by using semidefinite programming [20, 10]. This is the Gram matrix method, which is based on the following proposition [16, 28], the noncommutative version of the classical result for commuting variables. Proposition 2.1. Suppose the nc polynomial f e Sym r(X) is of degree < 2d and let Wd be the vector of all words w e (X) of degree < d. Then f e £2 if and only if there exists a positive semidefinite matrix Gf (called a Gram matrix for f) satisfying f = W^Gf Wd. Example 2.2. Take f = 1 + X2 + XY + YX + 4YX2 Y + Y2 and let V = [1 X Y XYY be a subvector of W2. Then the Gram matrix for nc polynomial f corresponding to the vector V is "10 0 u' , 0 1 1 — u 0 G(u) := 0 1 — u 1 0 0 0 4 248 Ars Math. Contemp. 9 (2015) 151-163 The question is: does there exist (at least one) u such that G(u) is a positive semidefinite matrix? Since G(2) = Cf'C for C 10 0 2 0 1-10 it follows that f = (1 + 2XY)*(1 + 2XY) + (X - Y)*(X - Y) e S2. As we saw in the last example we can sometimes replace Wd with a smaller subvector in the Gram matrix method. An algorithm (the Newton chip method) for reducing the size of needed word vector is presented in [20] and is implemented in NCSOStools. See also [29] for a strengthening. Similarly we can use semidefinite programming to test whether a given nc polynomial f e r(X} is an element of ©2 as first observed in [19], see also [10, 7, 6]. The method behind it is a variant of the Gram matrix method: Proposition 2.3. Suppose that an nc polynomial f e r(X} is of degree < 2d and let Wd be as above. Then f e ©2 if and only if there exists a positive semidefinite matrix Gf (called a tracial Gram matrix for f) such that f ~c W*Gf Wd. Again we can sometimes replace the full word vector Wd with a smaller subvector. An algorithm (the Newton cyclic chip method) for reducing the size of needed word vector is presented in [6] and is implemented in NCSOStools. Following Proposition 2.1, we can decide whether an nc polynomial f is a sum of hermitian squares by solving a semidefinite programming feasibility problem in the matrix variable G, where the constraints (Ai, G} = hi are implied by the fact that for each product of monomials w e {p*q | p,q e W} the following must be true: ] Gp,q = aw, (2.1) p,qeW p* q=w where aw is the coefficient of w in f (aw =0 if the monomial w does not appear in f). Since any input nc polynomial f is symmetric (so aw = aw* for all w), the corresponding SDP feasibility problem is as follows: G ^ 0 s.t. (Aw,G} = aw + aw* Vw e {p*q | p,q e W}, where Aw = Aw* is the symmetric matrix defined by 2; if u*v e {w,w*}, w* = w, (Aw )u,v \ 1; (SOHSsdp) 0 if u* v e { w, w* } , w* = w, otherwise. Similarly, following Proposition 2.3, an nc polynomial f is cyclically equivalent to a sum of hermitian squares if and only if there exists a positive semidefinite matrix G such that f c~ W *GW. Again, this is an SDP feasibility problem (FSDP) in the matrix variable G, where the constraints (Ai, G} = hi are essentially equations (1.1), i.e., for each product of monomials v e {p*q | p,q e W} the following must be true: Gp,q =53 aw. (2.2) p,q^W w%cv * eye p q ~ V K. Cafuta et al.: Rational sums of hermitian squares of free noncommutative polynomials 249 The SDP feasibility problem is as follows [6, Corollary 4.5]: G h 0, ¡s.t Y, A,G = + aw), Vv 6 W (CSOHSsdp) where Av = Av* is the symmetric matrix defined by ( o -f * cyc o * cyc * I 2; it p q ~ v & p q ~ v *, (Av)p,q = % 1; if p*q cyc v & p*q ^ v*, 0; otherwise. Remark 2.4. Finding a Gram matrix for the sum of hermitian squares (and commutators) decomposition problem by solving (SOHSsdp) and (CSOHSsdp) gives a solution of highest rank since under a strict feasibility assumption the interior point methods yield solutions in the relative interior of the optimal face, which is in our case the whole feasibility set. If strict complementarity is additionally provided, the interior point methods lead to the analytic center of the feasibility set [15]. Alternately, we can consider these SDP problems as usual SDP problems by using a non-zero choice of C. The choice C = I is a commonly used heuristic for matrix rank minimization [37], and it tends to give sum of hermitian squares (and commutators) with a small number of hermitian squares. Even though the above assumptions do not always hold for the instances of SDPs we construct, in our experiments the choice C = 0 in the objective function almost always gave a solution of higher rank than the choice C = I. High ranks are desired and exploited when trying to compute a rational (exact) Gram matrix from numerical solution of (SOHSsdp) and (CSOHSsdp). 3 Rational sums of hermitian squares and facial reduction In this section particular emphasis is given to the extraction of rational certificates if the input data is rational. We present several examples illustrating our results, e.g. concerning the recently proven BMV conjecture [39] from statistical physics (Subsection 3.3.1) and the noncommutative Motzkin polynomial (Subsection 3.3.2). 3.1 Rational sums of hermitian squares Consider a feasibility SDP in primal form (FSDP) and assume the input data Aj ,6j is rational for i = 1,..., m. If the problem is feasible, does there exist a rational solution? If so, can one use a combination of numerical and symbolic computation to produce one? Example 3.1. Some caution is necessary, as a feasible SDP of the form (FSDP) need not admit a rational solution. For a simple concrete example, note that In fact there are commutative polynomials with rational coefficients that are sums of squares of polynomials over the reals, but not over the rationals (see [38]). Adapting an example of 2 x x 1 x 1 0 © 1 x 1 h 0 ^ x = V2. 01x x 250 Ars Math. Contemp. 9 (2015) 151-163 Scheiderer, we obtain an nc polynomial with rational coefficients that is cyclically equivalent to a sum of hermitian squares of nc polynomials over the reals, but not over the rationals: 3 3 11 f = 1 + X3 + X4 - -XY - - YX - 4XYX + 2Y2 + Y3 + -XY3 + -Y3X + Y4. This is a dehomogenized and symmetrized noncommutative version of the (commutative) polynomial from [38, Theorem 2.1] (setting x0 = 1, x1 = X and x2 = Y). So f is not cyclically equivalent to a sum of hermitian squares with rational coefficients. By [38, Theorem 2.1], f |R2 > 0. Together with the fact that f is cyclically sorted, [18, Proposition 4.2] implies that f is trace positive. Since f is of degree 4 in two variables it is a sum of hermitian squares with commutators [5, 8] (with real coefficients). On the other hand, if (FSDP) admits a feasible positive definite solution, then it admits a (positive definite) rational solution. More exactly, we have the following: Theorem 3.2 (Peyrl & Parrilo [31]). If an approximate feasible point G0 for (FSDP) satisfies S := min(eig(Go)) > ||«Ai,Go> - &<)<|| =: e, (3.1) then a (positive definite) rational feasible point G exists. It can be obtained from G0 in the following two steps (cf. Figure 1): (1) compute a rational approximation G of G0 with t := ||G-G0|| satisfying t 2+e2 < S2; (2) project G onto the affine subspace L given by the equations (Aj, G> = bi to obtain G. PsD G G TG 0 Figure 1: Rounding and projecting to obtain a rational solution Note that the results in [31] are stated for SDPs arising from sum of squares problems, but their results carry over verbatim to the setting of (the seemingly more) general SDPs. K. Cafuta et al.: Rational sums of hermitian squares of free noncommutative polynomials 251 The rationalization scheme based on this Peyrl-Parrilo technique has been implemented in NCSOStools; see Example 3.5 for a demonstration. 3.2 Facial reduction Not all is lost, however, if the SDP solver gives a singular feasible point G0 for (FSDP). Suppose that z is a rational nullvector for G0. Let P be a change of basis matrix containing z as a first column and a (rational) orthogonal basis for the orthogonal complement {z}± as its remaining columns. Then P tGoP i.e., G0 = P- for some symmetric G0. Hence bi = (Ai, Go) = tr(AjGo) = tr (ä^P-t So if 0 0 ' o Go 0 0 ' 0 Go P- 00 0 Go P tr (P -1A,P 00 0 G o ai ci ci Ai P-1AiP-t then Ai is a symmetric matrix with rational entries and bi = tr ai cit 0 0 ci Ai 0 G o_ tr(AiGo) = (Ai, Go). We have established a variant of the facial reduction [3] which applies whenever the original SDP is given by rational data and has a singular feasible point with a rational nullvector: Theorem 3.3. Let (FSDP), Ai and G0 be as above. Consider the feasibility SDP G h 0 s.t. (Ai;G) = bi, i = l,...,m (1) (FSDP') is feasible if and only if (FSDP) is feasible. (2) (FSDP') admits a rational solution if and only if (FSDP) does. (FSDP') i t 3.3 Examples 3.3.1 BMV conjecture In their 2004 paper [25], Lieb and Seiringer gave the following purely algebraic reformulation of the Bessis-Moussa-Villani (BMV) conjecture [2] from quantum statistical physics, which was recently proved in the original formulation by Stahl [39]: 252 Ars Math. Contemp. 9 (2015) 151-163 Conjecture 3.4. For all positive semidefinite matrices A and B and all m G n, the polynomial p(t) := tr((A + tB)m) G r[t] has only nonnegative coefficients. The coefficient of tk in p(t) for a given m is the trace of Sm,k (A, B), where Sm,k (A, B) is the sum of all words of length m in the letters A and B in which B appears exactly k times. For example, S4,2 (A, B) = A2B2 + ABAB + AB2A + BABA + B2 A2 + BA2B. Thus Sm k (X, Y) is an nc polynomial; it is the sum of all words in two variables X, Y of degree m in which Y appears exactly k times. Even though the motivating conjecture was proved, the related questions concerning nc polynomials remain interesting. In the last few years there has been much activity around the following question: which pairs (m, k) does Sm,k(X2, Y2) G ©2 or Sm,k(X, Y) G ©2 hold for? An affirmative answer (for all m, k) to the former would imply the BMV conjecture. This question has been resolved completely (see e.g. [19, 11, 9]), however only finitely many nontrivial Sm,k(X2, Y2) admit a ©2-certificate. Adding to the current state of knowledge (nicely summarized in [11]), we shall use our computer algebra system NCSOStools to establish Sio,2(X, Y) g ©2 and Si4,6(X, Y) G ©2. We also show that S2m,2(X, Y) G ©2 holds for all m G n. Example 3.5. Consider the nc polynomial f = S10,2(X, Y), i.e., the sum of all words of degree 10 in the nc variables X and Y in which Y appears exactly twice. To prove that f G ©2 with the aid of NCSOStools, proceed as follows: (1) Define two noncommuting variables: >> NCvars x y (2) Our nc polynomial f is constructed using BMV(10,2). For a numerical test whether f G ©2, run >> p.obj = 0; >> [IsCycEq,G0,W,sohs,g,SDP_data] = NCcycSos(BMV(10,2),p); Using the SDP solver SDPT3, this yields a floating point Gram matrix G o Go = 5.0000 2.5000 -1.8851 1.6770 10.6424 0.8230 -2.7313 1.6770 -0.0899 0.8230 -1.8851 2.5000 2.5000 -1.8851 0.8230 -0.0899 8.7702 1.6770 -2.7313 0.8230 1.6770 -1.8851 8.7702 2.5000 5.0000 for the word vector W = [X 4Y X 3YX X 2 YX2 XYX3 YXY . The rest of the output: IsCycEq = 1 since f is (numerically) an element of ©2; sohs is a vector of nc polynomials g with f ~c J2 i 9i9i = g; SDP_data is the SDP data for (2.2) constructed from f. (3) To round and project the obtained floating point solution G0 following Theorem 3.2, feed G0 and SDP_data into RprojRldlt: K. Cafuta et al.: Rational sums ofhermitian squares of free noncommutative polynomials 253 >> [G,L,D,P,err]=RprojRldlt(G0,SDP_data,true) This produces a rational Gram matrix G for f with respect to W and its LDU decomposition PLDL'P', where P is a permutation matrix, L lower unitriangular, and D a diagonal matrix with positive entries. We caution the reader that l,d, and G are cells, each containing numerators and denominators separately as a matrix. Finally, the obtained rational sum of hermitian squares certificate for f = S10,2 (X, Y) is , eye > . * for gi = X2YX2 + — X3YX + — XYX3 - ^X4Y - ^YX4 g2 = X3YX - 577 1535 XYX3 + 408 1535 X 4Y + 188 1535 -YX 4 g3 = XYX 3 + 1^09 X 4Y + ^ YX 4 45984 g4 = X4Y - 296301 YX4 15328 647065 g5 = YX4 and A1 = 11, A. 1535 2= A3 = 11496 A4 = 647065 A5 = 1242629 176 3 1535 4 183936 5 647065 This example is not surprising, as it is a particular instance of a larger pattern: Proposition 3.6. For all m G n we have: S2m,2(X, Y) G ©2. Proof. We first point out that for all m G n we have S2m,2(X,Y )= ^ X aYX P YX2m-2-a-p a+^<2m-2 2m-2 tv v2m-2-t Y^ (2m - 2 - t + 1)YX'YX t=0 2m-2 - ^ (2m - 2 - t + 1)(YX'YX2m-2-' + YX2m-2-'YX') t=0 2m 2 - ^ ((2m - 2 - t +1)YX'YX2m-2-' + (t + 1)YX'YX t=0 2m-2 m ^ YX 'YX ty2m-2-i r2m-2-' '=0 254 Ars Math. Contemp. 9 (2015) 151-163 Note that for t = 2s we have YX'YX2m-2-t c£c Xm-s-1YX2sYXm-s-1 G S2, hence we next turn our attention to words YX'YX2m-2-t for odd t. In such cases we write t = 2s + 1 and observe that 2s + 1v v2m-3-2s YX 2s+1YX CyC _ ^(Xm-s-2 + XSYXm—s — 1)*(Xm-s-2 + XSYXm-s-1jj _ _Xm—s —2yx2s+2yXm—s —2 _ _Xm—s —iyx2syxm —s—1 2 2 ' Therefore each word with odd t is cyclically equivalent to a hermitian square minus two hermitian squares. These two negative hermitian squares cancel out with the "even" words for t = 2s and t = 2s + 2. In fact, each word with odd t cancels one half of these two even terms, hence all even terms finally cancel out and only one half of the first and the last even term remains (these two terms are cyclically equivalent). Finally we get S2m,2 (X? Y) 2m—2 cyf m ^ ^ (Xs + 1yxm—s —2 + Xsyxm—s —1)(Xs + 1^Xm—s —2 + Xsyxm—s —1)* 2 t=0 + Xm—1Y 2X m—1. □ Example 3.7. We conclude this subsubsection by showing S14,6(X, Y) G ©2. We define two noncommuting variables and run NCcycSos as in the previous examples: >> NCvars x y >> [IsCycEq,G0,V,sohs,g,SDP_data] = NCcycSos(BMV(14,6)); However, this seems to be an infeasible problem. In fact, we shall use the generated data SDP_data to prove it is strongly infeasible by computing a rational hyperplane separating ©2 and S14,6 (X, Y). Let P be the set of all nc polynomials p with degX p = mindegX p = 8 and degY p = mindegY p = 6. Obviously, S14,6(X, Y) G P. Each p G P can be represented by a 35 x 35 Gram matrix using the basis V from given as output of NCcycSos. An important observation is that p G ©2 if and only if there is a positive semidefinite matrix G satisfying p c~ V*GV, cf. Proposition 2.3. Let L : P ^ r be a linear *-map nonnegative on ©2 n P. It can be represented as p ^ (M, Gp) for a symmetric 35 x 35 matrix M, where Gp is a Gram matrix for p. Since L(£2) C [0, to), the matrix M is positive semidefinite. The fact that L(f) = 0 for all f c~ 0, can be modeled with constraints (M, H) =0 for all H G A^, cf. [9, Section 2.2]. Here, A^ is the orthogonal complement of the span of the Av from Section 2.2 in the set of symmetric matrices. Clearly, it suffices to consider H from a linearly independent generating subset C of A^. To express L(S14 6(X, Y)) < 0, we first compute a Gram matrix for S14 6(X, Y). The matrix A = SDP_data.A and vector b = SDP_data.b model the linear constraints (Av, G) = bv for v G (X, Y) with degX v = 8, degY v = 6. Hence a symmetrized solution of the linear system >> SDP_data.A\SDP_data.b K. Cafuta et al.: Rational sums of hermitian squares of free noncommutative polynomials 255 will be a Gram matrix G for S14j6(X, Y). Now consider the feasibility SDP M ^ 0 s.t. (M,G) = -35, VH eC : (M, H) = 0. (Here, -35 is just a convenient scaling factor.) Every feasible point induces a hyperplane separating ©2 and S14 6(X, Y). Solving this SDP with SeDuMi (using the trivial objective function C = 0) yields a floating point solution M0 in the relative interior of the optimal face, see Remark 2.4, with minimal eigenvalue S = 0.3426 and residual norm e = 6.8 • 10-9. Thus we can find a rational feasible solution M as explained in Theorem 3.2, using RprojRldlt. This proves S14j6(X, Y) e ©2. 3.3.2 Noncommutative Motzkin polynomial The nc polynomial /Mot(X, Y) = XY4X + YX4Y - 3XY2X + 1 e r(X, Y) is a noncommutative version of the (commutative) Motzkin polynomial. The Motzkin polynomial is a well-known example of a (commutative) polynomial which is nonnegative on r2 but is not a sum of squares of polynomials. Similarly, /Mot is an example of trace positive nc polynomial which is not a member of ©2 [18, Example 4.4]. Indeed, since the (commutative) Motzkin polynomial is not a sum of squares of polynomials, /Mot is not a member of ©2. An alternative proof for trace positivity of /Mot (X, Y) follows from the fact that /Mot (X3, Y3) e ©2, as we can show with the aid of the facial reduction procedure from Subsection 3.2. Example 3.8. Consider / = /Mot(X3, Y3) = X3Y12X3 + Y3X12Y3 - 3X3Y6X3 + 1. To prove that / e ©2 with the aid of NCSOStools, proceed as follows: (1) Define two noncommuting variables and the nc polynomial /: >> NCvars x y >> f = xA3*yA12*xA3 + yA3*xA12*yA3 - 3*xA3*yA6*xA3 + 1; (2) Define a custom vector of monomials W >> W = {''; 'x*y*y'; 'x*x*y'; 'x*x*y*y*y*y'; 'x*x*x*x*y*y'; 'x*x*x*y*y*y*y*y*y'; 'x*x*x*x*y*y*y*y*y'; 'x*x*x*x*x*y*y*y*y'; 'x*x*x*x*x*x*y*y*y'}; (3) For a numerical test whether / e ©2, run >> param.V = W; [IsCycEq,G0,W,sohs,g,SDP_data] = NCcycSos(f,param); This yields a floating point Gram matrix G0 that is singular. (4) Try to round and project the obtained floating point solution G0 , feed G0 and SDP_data into RprojRldlt: 256 Ars Math. Contemp. 9 (2015) 151-163 >> [G,L,D,P,err] = RprojRldlt(G0,SDP_data) This exits with an error, since unlike in Example 3.5, the rounding and projecting alone does not yield a rational feasible point. (5) Instead, let us reexamine G0. A detailed look at the matrix reveals three nullvectors. We thus run our interactive procedure which aids the computer in reducing the size of the SDP as in Theorem 3.3. >> [G,SDP_data] = fac_reduct(f,param) This leads the computer to return a floating point feasible point G0 e r9x9 and the data for this SDP, SDP_data. It also stays in interactive mode and the user can inspect the matrix and enter the nullvector z to be used in the dimension reduction. We feed in three nullvectors as a matrix of three columns: K>> z = [0-10; -10 0; 0 0 1; 0-10; 0-10; -10 0; 0 0 1; -1 0 0; 0 0 1]; return Inside the interactive routine this enables the computer to produce a positive definite feasible G0 e r6x6. Hence we exit the interactive routine. K>> stop = 1; return Now, NCSOStools uses G0 to produce a rational positive semidefinite Gram matrix G for f, which proves f e ©2. Like in the Example 3.5, the solution G is a cell containing two matrices with numerators and denominators of the rational entries of G. The reader can verify that f ~c W*GW exactly by doing rational arithmetic or approximately by computing floating point approximation for G and using floating point arithmetic. (6) To compute the LDU decomposition PLDLtPt for the rational Gram matrix G of f with respect to W (where G,l,d are cells, each containing numerators and denominators separately as a matrix) run >> [L,D,P] = Rldlt(G) The obtained rational sum of hermitian squares certificate for fMot (X3 , Y3) is then 6 fMot (X3, Y3) Xc Y WiQi i=i K. Cafuta et al.: Rational sums of hermitian squares of free noncommutative polynomials 257 for and gl — 1 - 1X 2 2Y4 _ 1 2 X4Y2 g2 — XY2 - 1X 3Y 6 2 - 1X 5 Y4 2 g3 — X2Y - 1X 4Y 5 2 - 1X 6 Y3 2 g4 — X2Y4 - X4Y2 g5 — X3Y6 - -X 5y 4 g6 — X4Y5 - X6Y3 Ai — — A3 — 1, A4 — A5 — Aß Remark 3.9. We point out that this yields a rational sum of squares certificate for f (x3, y3) where f (x, y) = 1 + x4y2 + x2y4 — 3x2y2 is the commutative Motzkin polynomial. 4 Conclusions In this paper we considered nc polynomials p in freely noncommuting variables which can be decomposed as a sum of hermitian squares (and commutators) with a special focus on nc polynomials with rational coefficients that admit rational decompositions. We explained how to obtain rational decompositions in theory and practice: if the related semidefinite programming problems have strictly feasible solutions then the algorithm we proposed - a variant of Peyrl-Parrilo rounding and projecting method - always yields a rational (i.e., exact symbolic) decomposition. In the absence of strict feasibility we proposed a variant of the facial reduction to reduce the size of the semidefinite program and enforce the existence of Slater points. We implemented both methods in our open source software package NCSOStools [10] and demonstrated them on several illustrative examples. References [1] M. Anjos and J. Lasserre, Handbook of Semidefinite, Conic and Polynomial Optimization, volume 166 of International Series in Operational Research and Management Science, Springer, 2012. [2] D. Bessis, P. Moussa and M. Villani, Monotonic converging variational approximations to the functional integrals in quantum statistical mechanics, J. Mathematical Phys. 16 (1975), 23182325. [3] J. Borwein and H. Wolkowicz, Facial reduction for a cone-convex programming problem, J. Austral. Math. Soc. Ser. A 30 (1980/81), 369-380. [4] S. Boyd, L. E. Ghaoui, E. Feron and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory, Studies in Applied Mathematics, SIAM, 1994. [5] S. Burgdorf and I. Klep, Trace-positive polynomials and the quartic tracial moment problem, C. R. Math. Acad. Sci. Paris 348 (2010), 721-726. [6] S. Burgdorf, K. Cafuta, I. Klep and J. Povh, Algorithmic aspects of sums of Hermitian squares of noncommutative polynomials, Comput. Optim. Appl. 55 (2013), 137-153. 258 Ars Math. Contemp. 9 (2015) 151-163 [7] S. Burgdorf, K. Cafuta, I. Klep and J. Povh, The tracial moment problem and trace-optimization of polynomials, Math. Program. 137 (2013), 557-578. [8] K. Cafuta, On matrix algebras associated to sum-of-squares semidefinite programs, Linear Multilinear Algebra 61 (2013), 1496-1509. [9] K. Cafuta, I. Klep and J. Povh, A note on the nonexistence of sum of squares certificates for the Bessis-Moussa-Villani conjecture., J. Math. Phys. 51 (2010), 083521, 10. [10] K. Cafuta, I. Klep and J. Povh, NCSOStools: a computer algebra system for symbolic and numerical computation with noncommutative polynomials, Optim. Methods and Softw. 26 (2011), 363-380,http://ncsostools.fis.unm.si/ [11] B. Collins, K. Dykema and F. Torres-Ayala, Sum-of-squares results for polynomials related to the Bessis-Moussa-Villani conjecture, J. Stat. Phys. 139 (2010), 779-799. [12] A. Connes, Classification of injective factors. Cases IIi, IITC, IIIa, A = 1., Ann. of Math. (2) 104 (1976), 73-115. [13] M. de Oliveira, J. Helton, S. McCullough and M. Putinar, Engineering systems and free semi-algebraic geometry, in: M. Putinar and S. Sullivant (eds.), Emerging applications of algebraic geometry, Springer, New York, volume 149 of IMA Vol. Math. Appl., pp. 17-61, 2008. [14] M. Goemans and D. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the Association for Computing Machinery 42 (1995), 1115-1145. [15] M. Halická, E. de Klerk and C. Roos, On the convergence of the central path in semidefinite optimization, SIAM J. Optim. 12 (2002), 1090-1099. [16] J. Helton, "Positive" noncommutative polynomials are sums of squares, Ann. of Math. (2) 156 (2002), 675-694. [17] E. Kaltofen, B. Li, Z. Yang and L. Zhi, Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients, J. Symbolic Comput. 47 (2012), 1-15. [18] I. Klep and M. Schweighofer, Connes' embedding conjecture and sums of Hermitian squares, Adv. Math. 217 (2008), 1816-1837. [19] I. Klep and M. Schweighofer, Sums of Hermitian squares and the BMV conjecture, J. Stat. Phys 133 (2008), 739-760. [20] I. Klep and J. Povh, Semidefinite programming and sums of hermitian squares of noncommutative polynomials, J. Pure Appl. Algebra 214 (2010), 740-749. [21] J. B. Lassere, Moments, positive polynomials and their applications, volume 1 of Imperial College Press Optimization Series, Imperial College Press, London, 2009. [22] J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim. 11 (2000/01), 796-817. [23] M. Laurent and F. Rendl, Semidefinite programming and integer programming, in: G. N. K. Aardal and R. Weismantel (eds.), Discrete Optimization, Elsevier, volume 12 of Handbooks in Operations Research and Management Science, pp. 393 - 514, 2005. [24] M. Laurent, Sums of squares, moment matrices and optimization over polynomials, in: Emerging applications of algebraic geometry, Springer, New York, volume 149 of IMA Vol. Math. Appl., pp. 157-270, 2009. [25] E. Lieb and R. Seiringer, Equivalent forms of the Bessis-Moussa-Villani conjecture, J. Stat. Phys. 115 (2004), 185-190. K. Cafuta et al.: Rational sums of hermitian squares of free noncommutative polynomials 259 [26] M. Marshall, Positive polynomials and sums of squares, volume 146 of Mathematical Surveys and Monographs, American Mathematical Society, Providence, RI, 2008. [27] S. McCullough, Factorization of operator-valued polynomials in several non-commuting variables, Linear Algebra Appl. 326 (2001), 193-203. [28] S. McCullough and M. Putinar, Noncommutative sums of squares, Pacific J. Math. 218 (2005), 167-171. [29] C. Nelson, A real nullstellensatz for matrices of non-commutative polynomials, http:// arxiv.org/abs/1305.07 9 9 [30] P. Parrilo, Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization, Ph.D. thesis, California Institute of Technology, 2000. [31] H. Peyrl and P. Parrilo, Computing sum of squares decompositions with rational coefficients, Theoret. Comput. Sci. 409 (2008), 269-281. [32] S. Pironio, M. Navascués and A. Acín, Convergent relaxations of polynomial optimization problems with noncommuting variables, SIAM J. Optim. 20 (2010), 2157-2180. [33] J. Povh, Contribution of copositive formulations to the graph partitioning problem, Optimization: A Journal of Mathematical Programming and Operations Research (2011), 1-13. [34] J. Povh and F. Rendl, A copositive programming approach to graph partitioning, SIAM Journal on Optimization 18 (2007), 223-241. [35] J. Povh and F. Rendl, Copositive and semidefinite relaxations of the quadratic assignment problem, Discrete Optimization 6 (2009), 231-241. [36] R. Quarez, Some examples of trace-positive quaternary quartics, to appear in Proc. Amer. Math. Soc., http://hal.archives-ouvertes.fr/hal-0 0 685397 [37] B. Recht, M. Fazel and P. A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev. 52 (2010), 471-501. [38] C. Scheiderer, Sums of squares of polynomials with rational coefficients, to appear in J. Eur. Math. Soc., http://arxiv.org/abs/1209.2 976 [39] H. R. Stahl, Proof of the BMV conjecture, Acta Math. 211 (2013), 255-290. [40] H. Wolkowicz, R. Saigal and L. Vandenberghe, Handbook of semidefinite programming: Theory, Algorithms, and Applications, volume 27 of International Series in Operations Research & Management Science, Kluwer Academic Publishers, Boston, MA, 2000.