78

If an $n$ by $n$ complex matrix $A$ has trace zero, then it is a commutator, which means that there are $n$ by $n$ matrices $B$ and $C$ so that $A= BC-CB$. What is the order of the best constant $\lambda=\lambda(n)$ so that you can always choose $B$ and $C$ to satisfy the inequality $\|B\|\cdot \|C\| \le \lambda \|A\|$?

Added June 10: Gideon Schechtman showed me that for normal $A$ you can take $B$ a permutation matrix and $\|C\|\le \|A\|$ s.t. $A=BC-CB$.

YCor
  • 60,149
Bill Johnson
  • 31,077
  • Do you mean the max norm? – Wadim Zudilin Jun 07 '10 at 14:01
  • Dear Bill, great question. Wild uneducated guess: isn't it the case that the norm of A can be essentially as large as the norm of XY-ZU where X and Z have the same notm as B and Y and U have the same norm as C? – Gil Kalai Jun 07 '10 at 16:09
  • 3
    I guess it is Frobenius norm first. For Frobenius norm it is true that $\sqrt{2} |B|\cdot |C| \ge |A|$ for all complex matrices $B, C$. – Sunni Jun 07 '10 at 16:37
  • 1
    I mean the operator norm, $|A|= \max {|Ax|: |x|=1}$ with $|x|$ the Euclidean norm. However, I do not know the answer if you use the Frobenius (Hilbert-Schmidt) norm.

    @Gil: I do not understand your comment.

     – Bill Johnson Jun 07 '10 at 16:53
  • @Gil: did you mean X and U have the same norm as B, and Y and Z have the same norm as C? – Mark Meckes Jun 07 '10 at 17:05
  • Do you have any lower bound better than λ=1/2 or any upper bound at all? I'd just like to get a feel for what the "obvious" bounds are that one should try to beat. – gowers Jun 08 '10 at 07:39
  • No lower bound. Schechtman and I convinced ourselves that the argument in http://www.eecs.berkeley.edu/~wkahan/MathH110/trace0.pdf gives the upper bound $\lambda(n)\le n^{3/2}$. Same upper bound multiplied by a constant less than one for the Hilbert-Schmidt norm. It is easy to compute $\lambda(2) = 1/2$. It seems clear that $\lambda(n)\to \infty$, not that I have any idea how to prove it. We assumed that the actual growth rate was well known even if we could not find it in the books we checked nor by Googling. – Bill Johnson Jun 08 '10 at 10:27
  • 4
    Schechtman showed that $\lambda(n) \le n$. WLOG (conjugate with an appropriate unitary) $C$ has zero diagonal and choose $A$ diagonal so that the magnitude of the difference of any two diagonal entries is at least one and the magnitude of every diagonal entry is less than $(n/2)^{1/2}$ (or a bit larger if $n$ is not a square). When you solve $AB-BA =C$ you see that the norm of $B$ is at most $n^{1/2} |C|$. – Bill Johnson Jun 08 '10 at 11:52
  • @gowers, the Pauli matrices show that a lower bound of λ=1/2 is tight, at least when n is even. – Steve Flammia Jun 08 '10 at 13:14
  • Bill: Can you get $\lambda(n)\le n$ for real matrices? – Mark Meckes Jun 08 '10 at 14:47
  • I don't see how, Mark. The problem reduces to considering a real matrix $A$ with zeros on the diagonal, but then if you use a diagonal real matrix $B$ when writing $A=BC-CB$ you run into problems and get only $|B|\cdot|C|\le n^{3/2}$. – Bill Johnson Jun 08 '10 at 17:26
  • Here's a random quick thought. Schechtman's argument suggests that for a lower bound on $\lambda$ you should investigate $A$ which is far from normal. There exist matrices $A$ with $| [A,A^*] | = | A |^2$; can one bound below $| B| | C |$ for such $A$? – Mark Meckes Jun 11 '10 at 18:42
  • No, Mark--at least not just from that condition, because the shift is not a problem. – Bill Johnson Jun 11 '10 at 18:50
  • Can you handle as well the sum of powers of the shift (i.e. strictly upper triangular $A$ with all 1s above the diagonal)? – Mark Meckes Jun 11 '10 at 19:09
  • We have not thought about that case, Mark. – Bill Johnson Jun 12 '10 at 05:30
  • I did some calculations and found the bounds mentionned in several previous comments, namely $O(n)$ (resp. $O(n^{3/2}$) in the complex (resp. real) case. But what amazes me is that these bounds apply for both the Forbenius norm and the operator norm, and this for different reasons... – Denis Serre Sep 28 '10 at 14:23
  • 6
    Off-line more has happened--the latest upper bound is a power of $\log n$ (sixth power, I think), resulting from combined efforts with N. Ozawa and G. Schechtman. I thought this thread had died and so did not post. The proofs are a bit beyond what should go on MO, but eventually we'll write what we can do and I'll then post a link here. – Bill Johnson Sep 28 '10 at 15:54
  • @ Bill Johnson: Do you mean $|C|\leq\sqrt{2}|A|$ in "Added June 10"? Otherwise you (or Gideon Schechtman) should know the answer to http://mathoverflow.net/questions/40801/representation-of-vectors-in-mathbbr2-via-differences-of-small-vectors . – Fiktor Oct 02 '10 at 14:43
  • See Mark Sapir's answer mathoverflow.net/questions/44715 to a related question of mine, concerning the case where $A$ is nilpotent. We may choose a factor $B=A$, but the price to pay may be to high. – Denis Serre Nov 03 '10 at 21:01
  • 2
    I wanted to know if you are already aware of the result that for the Frobenius norm, the ratio $|BC-CA|/ (|B||C|)$ for randomly chosen $B$ and $C$, tightly concentrates around a number that goes to zero as $n\to \infty$. Thus, it suggests that $\lambda(n) \to \infty$ as $n \to \infty$, right? – Suvrit Jan 01 '11 at 13:20
  • @Suvrit: No, I did not know that. Do you have a reference? – Bill Johnson Jan 01 '11 at 15:47
  • @Bill: I have a few references for you; let me post them below in the answer field. – Suvrit Jan 01 '11 at 17:49

3 Answers3

38

Ozawa, Schechtman, and I finally wrote up what we know on this question. The estimate is that for every $\epsilon > 0$ there is a constant $C_\epsilon$ so that for every $n$, $\lambda(n)\le C_\epsilon n^{\epsilon}$. The paper can be downloaded from the arXiv.

Martin Sleziak
  • 4,608
Bill Johnson
  • 31,077
8

Almost the references cited below discuss upper bounds (i.e., norm(commutator) $\le$ something). One of the most relevant results is in reference #3 that I alluded to in my comment above.

  1. A short note on the Frobenius norm of the commutator
  2. The Frobenius norm and the commutator (PDF)
  3. How big can the commutator of two matrices be and how big is it typically?
  4. Commutators, Pinching, and Spectral variation (Bhatia and Kittaneh)
  5. Norm inequalities for commutators of normal operators

If you chase the citations to these papers in google scholar, you will find several more very interesting and relevant papers—though, I have not been able to (yet) find a paper that discusses lower-bounds like yours.

The Amplitwist
  • 1,446
Suvrit
  • 28,363
7

In a recent paper ([1]), Ravichandran and Srivastava (RS) study pavings for collections of matrices. Their main theorem claims to yield an improvement to the bound obtained by Johnson, Ozawa, and Schechtman (JOS). However, as noted by YCor in a comment, RS [1] cite the JOS work as satisfying a bound on $\max(\|B\|,\|C\|)$, instead of a bound on the product $\|B\| \|C\|$ as in Bill Johnson's answer above.

But as YCor notes, we can scale $B$ by $\|A\|$ (or both $B$ and $C$ by suitably, e.g., $\sqrt{\|A\|}$), to recover the inequality for the case noted in the OP and in the JOS paper.

In particular, Ravichandran and Srivastava's results imply the following:

Corollary (Corollary 3 in [1]). Every zero trace matrix $A \in M_n(\mathbb{C})$ may be written as $A=[B,C]$ such that $\|B\|$, $\|C\| \le K\log^2(n)\|A\|$ for some universal constant $K$.

(By suitable scaling, this translates into $\|B'\|\|C'\| \le K^2\log^4(n)\|A\|$, for $[B',C']=A$).

[1]. M. Ravichandran and N. Srivastava. Asymptotically Optimal Multi-Paving. arXiv. Jun 2017.

Suvrit
  • 28,363
  • I believe existence of such an improvement was essentially prognosticated in the paper of Johnson, Ozawa, and Schechtman already. – Suvrit Aug 11 '17 at 15:14
  • 1
    In the linked paper the BOS paper looks misquoted: the upper bound is on the product $|B|\cdot|C|$, not on $\max(|B|,|C|)$ (written $|B|,|C|\le\dots$ in your link and also in your answer). Or I miss something, could you clarify? – YCor Aug 11 '17 at 16:02
  • @YCor -- indeed, you are right -- the paper that I cite, misquotes BOS, who as you say upper bound the product not the max. I am going to update my answer to reflect this. – Suvrit Aug 11 '17 at 19:31
  • 1
    Anyway for $A\neq 0$ apply the result to $A/|A|$. It yields $B',C$ with $|B'|,|C|\le K\log(n)^2$ with $[B',C]=(1/|A|)A$. Then, for $B=|A|B'$, we have $[B,C]=A$, $|B|\le K\log(n)^2|A|$, $|C|\le K\log(n)^2$. Hence $|B|\cdot|C|\le K^2\log(n)^4|A|$ and of course the case $A=0$ works too. – YCor Aug 11 '17 at 19:39
  • @YCor -- thanks for helping make the answer more precise!! – Suvrit Aug 11 '17 at 19:53
  • 2
    We have realized that that assertion in our paper ' Asymptotically Optimal Multi-Paving' that the existence of $(O(\epsilon^{-2}),\epsilon)$ pavings for zero diagonal matrices implies a polylogarithmic estimate for the quantitative commutator problem is incorrect. We have only been able to very slightly improve the Johnson-Ozawa-Schechtman result: We are able to show that given any zero diagonal $A \in M_m(\mathbb{C})$, there is a representation $A = [B,C]$ such that $||B|| ||C|| \leq C \operatorname{exp}(D\sqrt{\operatorname{log}(m)}) ||A||$, where $C, D$ are universal constants. – mohanravi Aug 14 '17 at 21:21
  • Thanks for the update @mohanravi --- I will update my answer to reflect this changed state of affairs! – Suvrit Aug 14 '17 at 21:38