User markus schweighofer - MathOverflow

Answer by Markus Schweighofer for Relating a Polynomial equation to the characteristic equation of a Hermitian matrix

2012-11-23T17:28:33Z

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).

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$.

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$.

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$.

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}$.

All this is folklore.

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:

http://arxiv.org/pdf/0811.2365v1.pdf

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:

http://arxiv.org/abs/1108.4380

Answer by Markus Schweighofer for Level of a commutative ring and its quotient field.

2012-11-20T15:53:20Z

Concerning question 1, such examples have been found independently by David Leep (unpublished) and J. K. Arason and R. Baeza:

Arason, J. K.; Baeza, R. On the level of principal ideal domains. Arch. Math. (Basel) 96 (2011), no. 6, 519–524

http://link.springer.com/article/10.1007%2Fs00013-011-0253-2

Answer by Markus Schweighofer for Application of polynomials with non-negative coefficients

2012-11-09T07:22:38Z

One answer to question 2 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).

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

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

Answer by Markus Schweighofer for Quadratic Farkas' Lemma?

2012-11-06T04:11:49Z

Here is a counterexample: Take $n=2$ variables $X$ and $Y$. Let $L_1,\dots,L_5$ be linear polynomials such that $$S:=\{ (x, y) \in {\mathbb R}^2 ~|~ L_i(x,y) \ge 0\}$$ 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$.

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$.

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...

Marshall: Positive polynomials and sums of squares
Prestel: Positive polynomials
Bochnak, Coste, Roy: Real algebraic geometry
Basu, Pollack, Roy: Algorithms in real algebraic geometry
Knebusch, Scheiderer: Einführung in die reelle Algebra
Andradas, Bröcker, Ruiz: Constructible sets in real geometry

...and the following articles...

Also the so-called "S-procedure" could be of interest for you.

Answer by Markus Schweighofer for Computing a determinantal representation of a bivariate polynomial

2012-10-24T08:52:41Z

This is discussed in a recent work of Plaumann, Sturmfels and Vinzant:

http://arxiv.org/abs/1011.6057

Answer by Markus Schweighofer for Counting roots: multidimensional Sturm's theorem

2012-10-24T08:15:04Z

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:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.9539

Answer by Markus Schweighofer for linear objective function, non-linear constraints involving square-root of variables

2012-10-21T10:38:31Z

You can try the Lasserre moment relaxations of polynomial optimization problems, see the survey of Monique Laurent:

http://homepages.cwi.nl/~monique/files/moment-ima-update-new.pdf

The code for your example in YALMIP (a MATLAB package) is:

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>=0) + set(r^2<=1+m^2) + set(m>=0)
for i = 1 : size(x,1)
constraints = constraints + set(0 <= x(i,2)-x(i,1)*m-c <= b*r)
end

relaxdeg=4

[info,sol,mom,cert]=solvemoment(constraints,b,[],relaxdeg)

sol{1}

This gives the following (at least numerically) optimal solution:

b = 4.7548
c = -9.9939
m = 1.8874
r = 2.1350

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:

http://www.math.uni-konstanz.de/~schweigh/presentations/polopt-kirchberg.pdf

Answer by Markus Schweighofer for Real functions with finitely many zeroes

2012-10-16T09:28:22Z

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

http://perso.univ-rennes1.fr/michel.coste/polyens/OMIN.pdf

or the book of van den Dries (Tame Topology and o-minimal Structures, 1998).

Answer by Markus Schweighofer for Polynomial positive on an interval

2012-10-11T00:39:36Z

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.

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.

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}.$$

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}$.

This approach unfortunately does not carry over for the numerous generalizations of the theorem.

Answer by Markus Schweighofer for Every positive polynomial with rational coefficients is above a completely Q-factorized nonnegative polynomial ?

2012-09-11T17:40:11Z

The answer to your question is yes by the following lemma:

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.

In my Diplomarbeit (written in German)

http://www.math.uni-konstanz.de/~schweigh/publications/diploma.thesis.pdf

from 1999, I proved this lemma. More precisely I proved ("Satz 2.27" in the Diplomarbeit):

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< t < 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$.

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.

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.

Answer by Markus Schweighofer for does anyone have a copy of schmid's effective work on hilbert 17th?

2012-07-26T15:12:42Z

Here is a copy:

http://math.usask.ca/fvk/schmid.ps

Answer by Markus Schweighofer for Groebner basis for Sudoku

2012-06-24T22:23:37Z

Here is a Singular Code that works quite well:

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<=8; i++) {for (j=i+1; j<=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. */

Answer by Markus Schweighofer for Can Gröbner bases be used to compute solutions to large, real-world problems?

2011-12-08T21:20:36Z

Concerning your questions 1 and 4, you should also have a look at border bases:

http://www.risc.jku.at/Groebner-Bases-Bibliography/gbbib_files/publication_1140.pdf

Comment by Markus Schweighofer

2012-11-17T09:42:50Z

@Denis: For polynomials with all roots real, Descartes' rule gives the exact number of roots.

Comment by Markus Schweighofer

2012-11-11T10:55:22Z

@Rudi: Okay, sorry, I rather should get a coffee, too.

Comment by Markus Schweighofer

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?

Comment by Markus Schweighofer

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.

Comment by Markus Schweighofer

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 "technical condition" for the "only if" 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>0$ (instead of $p$) has such a sums of squares representation.

Comment by Markus Schweighofer

2012-11-09T07:13:50Z

@Patricia: Sums of squares don't necessarily have all coefficients nonnegative.

Comment by Markus Schweighofer

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.

Comment by Markus Schweighofer

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.

Comment by Markus Schweighofer

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ö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ö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öbner bases of $I$ also over $K$. Because of the unicity of the reduced Gröbner basis, we have $G=H$. Hence $I$ is generated by polynomials with coefficients in $E\cap F$.

Comment by Markus Schweighofer

2012-10-24T11:10:21Z

The following slides might be of interest to you: leo.technion.ac.il/DelRob11/talks/Henrion.pdf

Comment by Markus Schweighofer

2012-10-24T09:55:22Z

This is very interesting. May I ask what is the paper you are reading?

Comment by Markus Schweighofer

2012-10-24T07:37:20Z

I just remarked that I accidentally added the constraint "set(m>=0)". 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 "set(m<=0)", 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<=0. Henceforth, the solution I gave above should nevertheless be correct (numerically).

Comment by Markus Schweighofer

2012-10-16T21:22:08Z

What is exactly your quadratic program? Do you have linear constraints? And how do you relax them?

Comment by Markus Schweighofer

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 ̈\"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.