The complex matrix cube problem summer project – summary of results
by Orr Shalit
In the previous post I announced the project that I was going to supervise in the Summer Projects in Mathematics week at the Technion. In this post I wish to share what we did and what we found in that week.
I had the privilege to work with two very bright students who have recently finished their undergraduate studies: Mattya Ben-Efraim (from Bar-Ilan University) and Yuval Yifrach (from the Technion). It is remarkable the amount of stuff they learned for this one week project (the basics of C*-algebras and operator spaces), and that they actually helped settle the question that I raised to them.
I learned a lot of things in this project. First, I learned that my conjecture was false! I also learned and re-learned some programming abilities, and I learned something about the subtleties and limitations of numerical experimentation (I also learned something about how to supervise an undergraduate research project, but that’s besides the point right now).
Statement of the problem
Following old advice of Halmos, the problem that I posed to Mattya and Yuval was in the form a yes/no question. To state this question, we need to recall some definitions. If is an matrix, another matrix is said to be a dilation of if
In this case, is said to be a compression of . We then write . If and are tuple of matrices, we say that is a dilation of , and that is a compression of , if for all . We then write .
A -tuple is said to be normal if is normal and for all . Normal tuples of matrices (or operators) are the best understood ones, because – thanks to the spectral theorem – they are simultaneously unitarily diagonalizable.
If is an matrix, we define its norm to be the operator norm of when considered as an operator on , that is: (here denotes the Euclidean norm ).
The complex matrix cube problem: Given a tuple of matrices, can one find a normal dilation of such that for all ?
I had some reasons to believe that the answer is yes, one of which was that it was proved that the answer is yes if are all selfadjoint; see this paper by Passer, Solel, and myself (I reported on this paper in this previous post). Passer later proved that if we replace with then the answer is yes for arbitrary tuples. Passer’s proof did not look optimal to me. Also, I carried out some primitive numerical experimentation that seemed to verify that is plausible.
Methods and results
Suppose we are given a -tuple of contractions . We wish to know whether it is true or false that has a normal dilation such that for all (this is not exactly the way we formulated the problem above, but it can be seen to be equivalent).
The first observation is that it is enough to consider only tuples of unitaries. Indeed, if is a contraction (meaning that ) then
is a unitary dilation of . So given a -tuple of contractions, we can find a -tuple of unitaries such that . Thus, we may as well assume that is a tuple of unitaries, and ask whether we can dilate .
We considered normal tuples with joint eigenvalues at the vertices of the polytope , where is a regular polygon with vertices that circumscribes the unit disc . When is moderately large, the boundary of is very close to , and in this post I will ignore this difference (the reader can check that for the results we get, ignoring this difference actually puts us on the safe side of things).
Given a fixed tuple of unitaries , it can be shown that has a normal dilation with for all if and only if
for every matrix valued polynomial of degree one , where is the fixed normal tuple we constructed above. Let me emphasize: here is some normal dilation that we don’t know whether it exists or not, and is the fixed tuple with joint eigenvalues at the vertices of the polytope from above. We recall that a matrix valued polynomial is evaluated on a tuple of matrices as follows:
So the first method of attack was the following: we randomly sampled a unitary tuple , and then we tried to find a polynomial such that (*) was violated, with . We thought of several ways to look for such a polynomial given , one of which was naively trying to iterate over a mesh of all possible coefficients . As you can easily see this method is so inefficient that even for moderately small and the search could take us a lifetime. Another idea was to try to run some numerical optimization such as gradient descent on the function but since this function is not convex this was also quite futile. And all this just for a given tuple , which might happen to have a dilation.
The second general approach was still to randomly select a tuple of unitaries and to check whether it has a normal dilation, but this time the test was somewhat more indirect. Basically, modulo some equivalences within the theory, we know that has the required dilation of size at most , if and only if there exists a UCP map sending to for , where is the tuple of normals constructed above. This, modulo some more equivalences (and as been noted in this paper of Helton, Klep and McCullough) is equivalent to the existence of positive semidefinite matrices such that
where , for , and
The existence of such semidefinite matrices can be interpreted as the feasibility of a certain semidefinite program (SDP). In fact, we decided to treat the full semidefinite program as follows
Note that we moved to the right hand side, to make the equality constraint afiine in the variables and . Recall that and are all fixed. In the implementation we actually defined this as a minimization problem
Now, there exists available software in Matlab that let’s one solve the above SDP quite reliably, and we used the high level interface CVX which invoked either one of the solvers SDPT3 and SeDuMi (we used both solvers and played with precision parameters to increase our confidence that the results we got were correct). This approach had the great advantage that (besides being much faster), it could tell us what is the smallest such that had a normal dilation such that .
We ran the tests for small values of and . You can see some histograms in the presentation (the value plotted in the histograms in the presentation is , in order to have a direct comparison with the conjecture). Interestingly, we see that with very high probability, the required value of is on average significantly lower than . For and , we found a few random counter examples, but they required that was just 2% over .
Once we know that the average value of is less than , it heuristically becomes reasonable that counter examples are hard to come by, because of concentration of measure phenomena: roughly speaking, the probability of a Lipschitz function on the unitaries (say) to be away from the mean goes down exponentially like with the dimension. For the same reason, once we found a counter example , it is very hard to find coefficients of a matrix valued polynomial such that . And indeed, we did not yet verify by an independent method that our counter examples are indeed counter examples.
The counter examples we found are very unlikely to be caused by numerical error, since we tested the result with a couple of solvers and also the advertised precision of the solvers is several orders of magnitude less than 2%.
After we found the random counter examples, it occurred to us that there was no reason to sample the unitaries independently. We recalled that in the selfadjoint case, tightness of the constant was established using anti-commuting unitaries. Indeed, since counter examples are rare, one would think that the matrices would have to conspire somehow in order to mess up the inequality. So we searched for things that are anti-commuting-like. And it did indeed turn out that the commuting matrices
where are also a counter example (in the case ). We also still haven’t found a polynomial for which . We will probably continue looking for one when the holiday is over, and then I will update.
Materials and summary
Here are Mattya and Yuval’s slides which they presented in the talk they gave at the end of the week. I also plan to put the code and files with raw results online on my homepage at some point.
Acknowledgements and credits
The main method for checking what is the “inflation constant” required for a dilation, using a semidefinite program, is based on basic operator space theory, and in particular draws upon the algorithm described in this paper of Helton, Klep and McCullough.
We used Matlab. The numerical heavy lifting was done by others. We solved the semidefinite program using CVX – a high level Matlab software package for specifying and solving convex programs. We also used YALMIP – another high level Matlab software package for specifying and solving convex programs – to verify the results we obtained with CVX. Both CVX and YALMIP invoked SDP solvers SDPT3 and SeDuMi.
This project came after several years of collaboration with colleagues, and in particular, I had many conversations on the subject with Ben Passer before and during the projects week.