User markus schweighofer - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T05:46:07Z http://mathoverflow.net/feeds/user/15506 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/114234/relating-a-polynomial-equation-to-the-characteristic-equation-of-a-hermitian-matr/114266#114266 Answer by Markus Schweighofer for Relating a Polynomial equation to the characteristic equation of a Hermitian matrix Markus Schweighofer 2012-11-23T17:28:33Z 2012-11-24T11:56:19Z <p>Let $K$ be a subfield of $\mathbb R$ (e.g., $K=\mathbb Q$) and $f\in K[x]$ be a monic polynomial of degree $n$ all of whose roots are real. We want to compute a symmetric matrix $A\in K^{n\times n}$ such that $f=\det(xI_n-A)$. By squarefree decomposition in $K[x]$ we can assume that $f$ has only simple roots (otherwise perform euclidean divisions to compute the squarefree decomposition, find a determinantal representation for each factor in this decomposition and use diagonal blocks).</p> <p>Of course, the idea is to start off with the companion matrix $C\in K^{n\times n}$ of $f$ which represents the vector space endomorphism $$\varphi\colon K[x]/(f)\to K[x]/(f),\ \overline p\mapsto\overline{xp}$$ with respect to the canonical monomial basis. We know that $f=\det(xI_n-C)$. In particular, $C$ is similar to a triangular matrix and therefore $\text{tr}(C^k)$ is the sum of the $k$-th powers of the roots of $f$ for each $k\in\mathbb N$.</p> <p>Now $C$ itself is almost never symmetric but $\varphi$ is self-adjoint with respect to the $L_2$ "scalar product" given by a measure whose mass is uniformly distributed on the roots of $f$ (we use here that the roots are simple so that this really gives a non-degenerate bilinear form). Denoting the usual scalar product on $\mathbb R^n$ by $\langle.,.\rangle$ and by $V\in \mathbb R^{n\times n}$ the Vandermonde matrix corresponding to the roots of $f$, this means that $\langle VCx,Vy\rangle=\langle Vx,VCy\rangle$ for all $x,y\in\mathbb R^n$. In other words, we have $C^TV^TV=V^TVC$.</p> <p>Now the Hermite matrix $H:=V^TV$ of $f$ comes naturally into play. It is a Hankel matrix whose entries are power sums of roots of $f$. But these power sums are traces of powers of $C$ and therefore lie in $K$ and can easily be computed. The idea is to replace $V$ by another matrix $W$ with $H=W^TW$. In contrast to $V$, the matrix $W$ should have entries in $K$ and should be easily computed. But this is possible: Just take any $W\in K^{n\times n}$ with $H=W^TW$. You get such a $W$ even in a triangular form if you use the Cholesky decomposition of the positive definite matrix $H$.</p> <p>Now $C^TW^TW=C^TH=C^TV^TV=V^TVC=HC=W^TWC$ and since $W$ is invertible (note that $V$ and $H$ are invertible since all roots of $f$ are simple) this shows that $WCW^{-1}$ is symmetric. So you can set $A:=WCW^{-1}$.</p> <p>All this is folklore.</p> <p>If you want a tridiagonal $A$ then you would have to perform Sturm's algorithm as indicated above by Denis. In fact, finding a tridiagonal $A$ is essentially equivalent to Sturm's algorithm, see the recent interesting work of Ronan Quarez:</p> <p><a href="http://arxiv.org/pdf/0811.2365v1.pdf" rel="nofollow">http://arxiv.org/pdf/0811.2365v1.pdf</a></p> <p>If the coefficients of the monic polynomial are itself polynomials in variables $y_i$ such that for each fixed real value of the $y_i$ the polynomial has again only real roots (cf. Garding's notion of hyperbolic polynomials), then you can still use the Hermite matrix to do something, see the recent article of Netzer, Plaumann and Thom:</p> <p><a href="http://arxiv.org/abs/1108.4380" rel="nofollow">http://arxiv.org/abs/1108.4380</a></p> http://mathoverflow.net/questions/112633/level-of-a-commutative-ring-and-its-quotient-field/113955#113955 Answer by Markus Schweighofer for Level of a commutative ring and its quotient field. Markus Schweighofer 2012-11-20T15:53:20Z 2012-11-20T15:53:20Z <p>Concerning question 1, such examples have been found independently by David Leep (unpublished) and J. K. Arason and R. Baeza:</p> <p>Arason, J. K.; Baeza, R. On the level of principal ideal domains. Arch. Math. (Basel) 96 (2011), no. 6, 519–524</p> <p><a href="http://link.springer.com/article/10.1007%2Fs00013-011-0253-2" rel="nofollow">http://link.springer.com/article/10.1007%2Fs00013-011-0253-2</a></p> http://mathoverflow.net/questions/91827/application-of-polynomials-with-non-negative-coefficients/111872#111872 Answer by Markus Schweighofer for Application of polynomials with non-negative coefficients Markus Schweighofer 2012-11-09T07:22:38Z 2012-11-09T07:22:38Z <p>One answer to <strong>question 2</strong> is Polya's theorem on forms positive on an orthant: Let a form (i.e. homogeneous polynomial) in several variables be given which is (strictly) positive whenever evaluated on non zero tuples of nonnegative reals. Then you can multiply it with a high power of the sum of the variables such that you obtain a form with all coefficients nonnegative (actually all coefficients of the "right" degree are positive).</p> <p>You can also prove a lower bound on the exponent required, see: Powers, Reznick: A new bound for Polya’s Theorem with applications to polynomials positive on polyhedra</p> <p>This theorem can be used in representation theorems involving sums of squares (cf. Patricia's answer), see my article: An algorithmic approach to Schmüdgen’s Positivstellensatz</p> http://mathoverflow.net/questions/111576/quadratic-farkas-lemma/111612#111612 Answer by Markus Schweighofer for Quadratic Farkas' Lemma? Markus Schweighofer 2012-11-06T04:11:49Z 2012-11-06T22:42:36Z <p>Here is a counterexample: Take $n=2$ variables $X$ and $Y$. Let $L_1,\dots,L_5$ be linear polynomials such that <code>$$S:=\{ (x, y) \in {\mathbb R}^2 ~|~ L_i(x,y) \ge 0\}$$</code> is a pentagon inscribed in the unit circle. Furthermore set $P:=1-X^2-Y^2$. Assume we could write $P$ as the sum of a globally nonnegative quadratic polynomial $Q$ and nonnegative linear combinations of the $L_i$ and $L_iL_j$. Now $P$ vanishes at the vertices of the pentagon and each $L_i$ is nonnegative at these vertices. Therefore $Q$ vanishes also at the vertices. But being a nonnegative quadratic polynomial, $S$ is a sum of squares of linear polynomials which all have also to vanish at the vertices and therefore are identically zero. This shows that $S$ is the zero polynomial. Now notice that each of the $L_i$ and $L_iL_j$ is strictly positive on at least one of the vertices of the pentagon (at which $P$ vanishes, of course). Since $P$ is a nonnegative linear combination of the $L_i$ and $L_iL_j$, this shows that $P=0$.</p> <p>If the set $S$ defined by the $L_i$ has non-empty interior, then the convex cone of quadratic polynomials which can be written as a globally nonnegative quadratic polynomial $Q$ and nonnegative linear combinations of the $L_i$ and $L_iL_j$ is closed. In fact, this follows from a much more general result on truncated quadratic modules, see e.g. the book of Marshall cited below (Lemma 4.1.4). This implies that, in the above counterexample, even $P+\varepsilon$ for small $\varepsilon>0$ will fail though this polynomial is strictly positive on $S$.</p> <p>However, there are a lot theorems going into the direction of what you want. You might want to have a look at the following books...</p> <ul> <li>Marshall: Positive polynomials and sums of squares</li> <li>Prestel: Positive polynomials</li> <li>Bochnak, Coste, Roy: Real algebraic geometry</li> <li>Basu, Pollack, Roy: Algorithms in real algebraic geometry</li> <li>Knebusch, Scheiderer: Einführung in die reelle Algebra</li> <li>Andradas, Bröcker, Ruiz: Constructible sets in real geometry</li> </ul> <p>...and the following articles...</p> <ul> <li><a href="http://homepages.cwi.nl/~monique/files/moment-ima-update-new.pdf" rel="nofollow">http://homepages.cwi.nl/~monique/files/moment-ima-update-new.pdf</a></li> <li><a href="http://www.math.uni-konstanz.de/~schweigh/publications/purestates.pdf" rel="nofollow">http://www.math.uni-konstanz.de/~schweigh/publications/purestates.pdf</a></li> <li><a href="http://www.math.uni-konstanz.de/~schweigh/publications/sosdualsdp.pdf" rel="nofollow">http://www.math.uni-konstanz.de/~schweigh/publications/sosdualsdp.pdf</a></li> </ul> <p>Also the so-called "S-procedure" could be of interest for you.</p> http://mathoverflow.net/questions/91627/computing-a-determinantal-representation-of-a-bivariate-polynomial/110524#110524 Answer by Markus Schweighofer for Computing a determinantal representation of a bivariate polynomial Markus Schweighofer 2012-10-24T08:52:41Z 2012-10-24T08:52:41Z <p>This is discussed in a recent work of Plaumann, Sturmfels and Vinzant:</p> <p><a href="http://arxiv.org/abs/1011.6057" rel="nofollow">http://arxiv.org/abs/1011.6057</a></p> http://mathoverflow.net/questions/43979/counting-roots-multidimensional-sturms-theorem/110520#110520 Answer by Markus Schweighofer for Counting roots: multidimensional Sturm's theorem Markus Schweighofer 2012-10-24T08:15:04Z 2012-10-24T08:15:04Z <p>The Hermite method for real root counting generalizes to the multivariate case if your system of polynomial inequalities has only a finite number of COMPLEX roots. this was shown by Becker and Wörmann and independently by Pedersen, see:</p> <p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.9539" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.9539</a></p> http://mathoverflow.net/questions/110219/linear-objective-function-non-linear-constraints-involving-square-root-of-variab/110227#110227 Answer by Markus Schweighofer for linear objective function, non-linear constraints involving square-root of variables Markus Schweighofer 2012-10-21T10:38:31Z 2012-10-23T14:43:31Z <p>You can try the Lasserre moment relaxations of polynomial optimization problems, see the survey of Monique Laurent:</p> <p><a href="http://homepages.cwi.nl/~monique/files/moment-ima-update-new.pdf" rel="nofollow">http://homepages.cwi.nl/~monique/files/moment-ima-update-new.pdf</a></p> <p>The code for your example in YALMIP (a MATLAB package) is:</p> <pre><code>clear b c m r sdpvar b c m r x = [1 2; 3 5; 9 7; 6 8; 7 6.5; 3 5.8; 10 19; 4 6] constraints = set(b&gt;=0) + set(r^2&lt;=1+m^2) + set(m&gt;=0) for i = 1 : size(x,1) constraints = constraints + set(0 &lt;= x(i,2)-x(i,1)*m-c &lt;= b*r) end relaxdeg=4 [info,sol,mom,cert]=solvemoment(constraints,b,[],relaxdeg) sol{1} </code></pre> <p>This gives the following (at least numerically) optimal solution:</p> <pre><code>b = 4.7548 c = -9.9939 m = 1.8874 r = 2.1350 </code></pre> <p>For this to work you need an SDP solver like SeDuMi. Implementations of the Lasserre moment approach other than YALMIP are SOSTools, GloptiPoly and SparsePOP. I have also some slides which might be helpful:</p> <p><a href="http://www.math.uni-konstanz.de/~schweigh/presentations/polopt-kirchberg.pdf" rel="nofollow">http://www.math.uni-konstanz.de/~schweigh/presentations/polopt-kirchberg.pdf</a></p> http://mathoverflow.net/questions/109705/real-functions-with-finitely-many-zeroes/109798#109798 Answer by Markus Schweighofer for Real functions with finitely many zeroes Markus Schweighofer 2012-10-16T09:28:22Z 2012-10-16T09:28:22Z <p>I think that the theory of o-minimal structures could provide a good answer to your question. See the Pisa lecture notes of Michel Coste</p> <p><a href="http://perso.univ-rennes1.fr/michel.coste/polyens/OMIN.pdf" rel="nofollow">http://perso.univ-rennes1.fr/michel.coste/polyens/OMIN.pdf</a></p> <p>or the book of van den Dries (Tame Topology and o-minimal Structures, 1998).</p> http://mathoverflow.net/questions/39292/polynomial-positive-on-an-interval/109344#109344 Answer by Markus Schweighofer for Polynomial positive on an interval Markus Schweighofer 2012-10-11T00:39:36Z 2012-10-11T09:30:29Z <p>As Vicki already pointed out above, Polya-Szegö (Problems and Theorems in Analysis II. Theory of Functions. Zeros. Polynomials. Determinants. Number Theory. Geometry.) is a good reference for this particular result.</p> <p>See §6, Problem 49 in that book: By the Fundamental Theorem of Algebra you can restrict to quadratic polynomials. For lines it is trivial. For parabolas opening down it is easy. The only nontrivial case happens for parabolas opening up. Parabolas opening up whose minimum lies above the interval are also just a little exercise. The only case remaining is parabolas opening up without zero on the real line.</p> <p>Now determine a polynomial $h \in \mathbb Z[K,L,A,B,C]_ 4$ such that for all $a,b,c\in\mathbb R$ and all $\ell\in\mathbb N_{\ge2}$ one has $$aX^2+bX+c=\sum_{k=0}^\ell\frac{(\ell-2)!}{k!(\ell-k)!}h(k,\ell,a,b,c)X^k(1-X)^{\ell-k}.$$</p> <p>Show that each $f\in\mathbb R[X]_ 2$ with $f>0$ on $\mathbb R$ has the desired representation by comparing the discriminants of $f=aX^2+bX+c\in\mathbb R[X]_ 2$ and $h(K,\ell,a,b,c)\in\mathbb Z[K]_ 2$ for $a,b,c\in\mathbb R$ and large $\ell\in\mathbb N_{\ge2}$.</p> <p>This approach unfortunately does not carry over for the numerous generalizations of the theorem.</p> http://mathoverflow.net/questions/87461/every-positive-polynomial-with-rational-coefficients-is-above-a-completely-q-fact/106934#106934 Answer by Markus Schweighofer for Every positive polynomial with rational coefficients is above a completely Q-factorized nonnegative polynomial ? Markus Schweighofer 2012-09-11T17:40:11Z 2012-09-11T17:40:11Z <p>The answer to your question is yes by the following lemma:</p> <p>Let $f$ be a polynomial with rational coefficients which is (strictly) positive on the real line and has degree at least $4$. Then there is a nonnegative quadratic polynomial $p$ with rational coefficients such that $f-p$ is nonnegative on the real line and has a multiple rational root.</p> <p>In my Diplomarbeit (written in German)</p> <p><a href="http://www.math.uni-konstanz.de/~schweigh/publications/diploma.thesis.pdf" rel="nofollow">http://www.math.uni-konstanz.de/~schweigh/publications/diploma.thesis.pdf</a></p> <p>from 1999, I proved this lemma. More precisely I proved ("Satz 2.27" in the Diplomarbeit):</p> <p>Let $f\in\mathbb R[X]$ be a polynomial of degree $>0$ such that $f(x)>0$ for all $x\in\mathbb R$. Denote by $a$ the smallest global minimizer of $f$. Then there is $\varepsilon>0\in\mathbb R$ such that for all $t\in\mathbb R$ satisfying $a-\varepsilon&lt; t &lt; a$ $$p_t := f(t)+f'(t)(X-t)+\frac{(f'(t))^2}{4f(t)}(X-t)^2\in\mathbb R[X]$$ is a polynomial of degree 2 such that $p_t \leq f$ on $\mathbb R$.</p> <p>Note that $p_t$ is a parabola with vanishing discriminant and that $f-p_t$ has a multiple root at $t$ with even multiplicity. If you choose $t$ rational, then $p_t$ has rational coefficients.</p> <p>In fact, in my Diplomarbeit you find a code which implements in the computer algebra system REDUCE (version 3.6) to find such a $t$. Thus you can compute the $q_k$ in your question using Sturm sequences.</p> http://mathoverflow.net/questions/42146/does-anyone-have-a-copy-of-schmids-effective-work-on-hilbert-17th/103209#103209 Answer by Markus Schweighofer for does anyone have a copy of schmid's effective work on hilbert 17th? Markus Schweighofer 2012-07-26T15:12:42Z 2012-07-26T15:12:42Z <p>Here is a copy:</p> <p><a href="http://math.usask.ca/fvk/schmid.ps" rel="nofollow">http://math.usask.ca/fvk/schmid.ps</a></p> http://mathoverflow.net/questions/91666/groebner-basis-for-sudoku/100547#100547 Answer by Markus Schweighofer for Groebner basis for Sudoku Markus Schweighofer 2012-06-24T22:23:37Z 2012-06-24T22:39:57Z <p>Here is a Singular Code that works quite well:</p> <pre><code>ring A = 0,(t,x(1..9)),lp; /* Characteristic 0 works suprisingly well for this problem. */ /* We choose a lexicographic ordering since we will compute an elimination ideal. */ poly p = (t-x(1))*(t-x(2))*(t-x(3))*(t-x(4))*(t-x(5))*(t-x(6))*(t-x(7))*(t-x(8))*(t-x(9))-(t-1)*(t-2)*(t-3)*(t-4)*(t-5)*(t-6)*(t-7)*(t-8)*(t-9); /* p(x)=0 in Q[t] implies that x is a permutation of the numbers 1 to 9. */ matrix c = coeffs(p,t); ideal J = (c[1..9,1]); /* J expresses that x is a permutation of the numbers 1 to 9. However, surprisingly, it is better to use only constraints saying that x(8) and x(9) are distinct integers between 1 and 9. This is done by computing an elimination ideal. */ ideal JG = groebner(J); ideal J2 = (JG[1],JG[2]); /* J2 is the ideal expressing that x(1) and x(2) are distinct integers between 1 and 9. */ ring R=0,(x(1..81)),dp; ideal I; map psi; proc f(k,l,m,n,o,p,q,r,s) {intvec v = k,l,m,n,o,p,q,r,s; int i,j; for (i=1; i&lt;=8; i++) {for (j=i+1; j&lt;=9; j++) {psi = A,0,1,2,3,4,5,6,7,x(v[i]),x(v[j]); I = I + psi(J2);}}} /* Code the rules into the ideal. */ f(1,2,3,4,5,6,7,8,9); f(10,11,12,13,14,15,16,17,18); f(19,20,21,22,23,24,25,26,27); f(28,29,30,31,32,33,34,35,36); f(37,38,39,40,41,42,43,44,45); f(46,47,48,49,50,51,52,53,54); f(55,56,57,58,59,60,61,62,63); f(64,65,66,67,68,69,70,71,72); f(73,74,75,76,77,78,79,80,81); f(1,10,19,28,37,46,55,64,73); f(2,11,20,29,38,47,56,65,74); f(3,12,21,30,39,48,57,66,75); f(4,13,22,31,40,49,58,67,76); f(5,14,23,32,41,50,59,68,77); f(6,15,24,33,42,51,60,69,78); f(7,16,25,34,43,52,61,70,79); f(8,17,26,35,44,53,62,71,80); f(9,18,27,36,45,54,63,72,81); f(1,2,3,10,11,12,19,20,21); f(4,5,6,13,14,15,22,23,24); f(7,8,9,16,17,18,25,26,27); f(28,29,30,37,38,39,46,47,48); f(31,32,33,40,41,42,49,50,51); f(34,35,36,43,44,45,52,53,54); f(55,56,57,64,65,66,73,74,75); f(58,59,60,67,68,69,76,77,78); f(61,62,63,70,71,72,79,80,81); /* Code a uniquely solvable Sudoku problem into the ideal. */ I=I+(x(3)-4); I=I+(x(6)-3); I=I+(x(7)-6); I=I+(x(9)-9); I=I+(x(12)-8); I=I+(x(13)-9); I=I+(x(16)-2); I=I+(x(18)-1); I=I+(x(22)-8); I=I+(x(23)-1); I=I+(x(27)-7); I=I+(x(28)-6); I=I+(x(33)-7); I=I+(x(37)-8); I=I+(x(40)-3); I=I+(x(42)-9); I=I+(x(45)-5); I=I+(x(49)-6); I=I+(x(54)-3); I=I+(x(55)-4); I=I+(x(59)-7); I=I+(x(60)-6); I=I+(x(64)-2); I=I+(x(66)-7); I=I+(x(69)-5); I=I+(x(70)-1); I=I+(x(73)-9); I=I+(x(75)-1); I=I+(x(76)-2); I=I+(x(79)-4); option(redSB); groebner(I,30); /* You get the solution quickly. */ </code></pre> http://mathoverflow.net/questions/5760/can-grobner-bases-be-used-to-compute-solutions-to-large-real-world-problems/83003#83003 Answer by Markus Schweighofer for Can Gröbner bases be used to compute solutions to large, real-world problems? Markus Schweighofer 2011-12-08T21:20:36Z 2011-12-08T21:20:36Z <p>Concerning your questions 1 and 4, you should also have a look at border bases:</p> <p><a href="http://www.risc.jku.at/Groebner-Bases-Bibliography/gbbib_files/publication_1140.pdf" rel="nofollow">http://www.risc.jku.at/Groebner-Bases-Bibliography/gbbib_files/publication_1140.pdf</a></p> http://mathoverflow.net/questions/107593/computing-signature/107619#107619 Comment by Markus Schweighofer Markus Schweighofer 2012-11-17T09:42:50Z 2012-11-17T09:42:50Z @Denis: For polynomials with all roots real, Descartes' rule gives the exact number of roots. http://mathoverflow.net/questions/75730/finding-smallest-ellipsoid-that-circumscribes-over-intersection-of-two-ellipsoids/112016#112016 Comment by Markus Schweighofer Markus Schweighofer 2012-11-11T10:55:22Z 2012-11-11T10:55:22Z @Rudi: Okay, sorry, I rather should get a coffee, too. http://mathoverflow.net/questions/75730/finding-smallest-ellipsoid-that-circumscribes-over-intersection-of-two-ellipsoids/112016#112016 Comment by Markus Schweighofer Markus Schweighofer 2012-11-11T10:42:19Z 2012-11-11T10:42:19Z @Rudi: Okay, but with the new notation, wouldn't you have to minimize $\log(\det(B))$ now? So after all, it can still not be done with semidefinite programming, right? http://mathoverflow.net/questions/75730/finding-smallest-ellipsoid-that-circumscribes-over-intersection-of-two-ellipsoids/112016#112016 Comment by Markus Schweighofer Markus Schweighofer 2012-11-11T10:12:43Z 2012-11-11T10:12:43Z @Rudi: Can you explain further. You want p to be of a certain shape, right? On the other hand, this shape seems to contradict the positive semidefiniteness constraint you put on $B$, doesn't it? By the way there seems to be a little typo in the shape you specify for $p$. Anyway, I guess something must be wrong for in the equation $p=s_1q_1+s_2q_2+t+(y-1)u$ you could always choose $s_1=s_2=u=0$ so that $p$ can be any positive semidefinite quadratic form in $x$ and $y$. So maximizing $\log(\det(B))$ is un unbounded problem. http://mathoverflow.net/questions/75730/finding-smallest-ellipsoid-that-circumscribes-over-intersection-of-two-ellipsoids/112016#112016 Comment by Markus Schweighofer Markus Schweighofer 2012-11-10T20:56:43Z 2012-11-10T20:56:43Z @Rudi: This won't give a semidefinite program (at least not in an obvious way) since $p$ depends in a cubic way on the entries of $A$ and $z$. To have a semidefinite program you can only afford linear dependence. The other problem is that the &quot;technical condition&quot; for the &quot;only if&quot; part is not so clear. This would be worth investigating. What I know immediately is that if the two original ellipsoids are compact (which is not always the case in the problem as it is posed), then it is true that $p+\varepsilon$ for each $\varepsilon&gt;0$ (instead of $p$) has such a sums of squares representation. http://mathoverflow.net/questions/91827/application-of-polynomials-with-non-negative-coefficients/104067#104067 Comment by Markus Schweighofer Markus Schweighofer 2012-11-09T07:13:50Z 2012-11-09T07:13:50Z @Patricia: Sums of squares don't necessarily have all coefficients nonnegative. http://mathoverflow.net/questions/111576/quadratic-farkas-lemma/111612#111612 Comment by Markus Schweighofer Markus Schweighofer 2012-11-06T20:12:29Z 2012-11-06T20:12:29Z I am so sorry, you are again right. But if you take a pentagon instead of a square, then it works. Not all of the $L_i L_j$ were strictly positive on at least one of the vertices of the square but for the pentagon this works. http://mathoverflow.net/questions/111576/quadratic-farkas-lemma/111612#111612 Comment by Markus Schweighofer Markus Schweighofer 2012-11-06T14:50:52Z 2012-11-06T14:50:52Z You are right, I am sorry for suggesting this counterexample. However, I think that I have now a valid counterexample, see above. http://mathoverflow.net/questions/110939/origin-of-the-theorem-on-the-existence-of-the-smallest-field-of-definition-of-an Comment by Markus Schweighofer Markus Schweighofer 2012-10-28T21:51:45Z 2012-10-28T21:51:45Z I am sorry, I don't know the answer to your question but I just realized that you can prove it using Gr&#246;bner basis. Let $E$ and $F$ be subfields of $K$ such that $I$ is generated by polynomials with coefficients in $E$ and in $F$, respectively. Then choose reduced Gr&#246;bner bases $G$ and $H$ of $I$ with respect to the same term ordering having all coefficients in $E$ and in $F$, respectively. Now both $G$ and $H$ are reduced Gr&#246;bner bases of $I$ also over $K$. Because of the unicity of the reduced Gr&#246;bner basis, we have $G=H$. Hence $I$ is generated by polynomials with coefficients in $E\cap F$. http://mathoverflow.net/questions/110496/can-you-maximize-the-spectral-norm-of-a-matrix-in-a-semidefinite-program Comment by Markus Schweighofer Markus Schweighofer 2012-10-24T11:10:21Z 2012-10-24T11:10:21Z The following slides might be of interest to you: <a href="http://leo.technion.ac.il/DelRob11/talks/Henrion.pdf" rel="nofollow">leo.technion.ac.il/DelRob11/talks/Henrion.pdf</a> http://mathoverflow.net/questions/110521/finding-the-spectrum-of-the-composition-of-a-projection-with-a-multiplication-ope Comment by Markus Schweighofer Markus Schweighofer 2012-10-24T09:55:22Z 2012-10-24T09:55:22Z This is very interesting. May I ask what is the paper you are reading? http://mathoverflow.net/questions/110219/linear-objective-function-non-linear-constraints-involving-square-root-of-variab/110227#110227 Comment by Markus Schweighofer Markus Schweighofer 2012-10-24T07:37:20Z 2012-10-24T07:37:20Z I just remarked that I accidentally added the constraint &quot;set(m&gt;=0)&quot;. However, without this constraint YALMIP does not find (at least at this relatively low relaxation degree of 4) an optimal solution. And moreover, if you add the constraint &quot;set(m&lt;=0)&quot;, then YALMIP gives a lower bound of 11.7390 (at the same relaxation degree) for the true optimal value of the problem with the additional constraint m&lt;=0. Henceforth, the solution I gave above should nevertheless be correct (numerically). http://mathoverflow.net/questions/106829/reference-request-semidefinite-relaxation Comment by Markus Schweighofer Markus Schweighofer 2012-10-16T21:22:08Z 2012-10-16T21:22:08Z What is exactly your quadratic program? Do you have linear constraints? And how do you relax them? http://mathoverflow.net/questions/102933/reconstructing-a-word Comment by Markus Schweighofer Markus Schweighofer 2012-07-26T19:18:58Z 2012-07-26T19:18:58Z If the answer to your question were no, then by a result of Bre\v sar and Klep (Corollary 5.8, Tracial Nullstellens ̈\&quot;atze, Notions of Positivity and the Geometry of Polynomials, Trends in Mathematics, 79–101) the difference of the two words would be a binomial in two non-commuting variables over the rational numbers which can be written as the sum of a non-trivial polynomial identity in two variables for $3\times 3$-matrices and a sum of commutators. In particular, the answer to your questions is yes if both words have length at most five.