8
$\begingroup$

Let $A$ and $B$ be two positive definite $n \times n$ matrices. It is, of course, not true that $AB+BA$ is necessarily positive definite.

Consider, though, the results of the following numerical experiment. I generated $A$ by letting its eigenvalues be random in $[0,1]$, and selecting its eigenvectors by generating a random matrix of standard Gaussians and applying Gram-Schmidt to it. The matrix $B$ is generated in the same way.

I did this 1000 times and checked what proportion of times the matrix $AB+BA$ has at least one negative eigenvalue [1]. Here are the results for different dimensions $n$:

  • $n=2, ~~~~94.8 \%$
  • $n=3, ~~~~89.4 \%$.
  • $n=4, ~~~~78 \%$.
  • $n=5, ~~~~72.7 \%$.
  • $n=10, ~~~40.3 \%$.
  • $n=15, ~~~20.1 \%$.
  • $n=20, ~~~11.4 \%$.
  • $n=50, ~~~0.3\%$.
  • $n=100, ~~0 \%$.

This suggests that, as a function of $n$, examples with $AB+BA$ not psd tend to get rarer and rarer. Is it possible to give a proof of this?

It may be more natural to consider a different random model of randomly generated psd matrices; I only generated them in the way I described above because it seemed easiest.

[1] Actually, I checked if there is an eigenvalue less then $-1 \cdot 10^{-5}$ in MATLAB to account for rounding error.

$\endgroup$
  • 4
    $\begingroup$ Is it immediately clear that you are noticing a tendency of all positive semidefinite matrices? I can't see why your method of generating candidate $A$'s and $B$'s would give the uniform distribution on psd matrices, so maybe this phenomenon is a property of the measure rather than the set? $\endgroup$ – Vidit Nanda Aug 4 '16 at 20:20
  • $\begingroup$ Real? Complex? Hermitian? Symmetric? $\endgroup$ – მამუკა ჯიბლაძე Aug 4 '16 at 20:52
  • 1
    $\begingroup$ This seems to be a byproduct of the specific choices of eigenvalues and eigenvectors.... $\endgroup$ – Suvrit Aug 4 '16 at 21:18
  • 4
    $\begingroup$ Are you sure you don't have the percentages backwards? I tried to reproduce your experiment (using Mathematica), and I find probabilities that are precisely one minus yours -- it is rarer and rarer for $AB+BA$ to be psd as $n$ increases. I am using precisely the same random generation technique. $\endgroup$ – David Zhang Aug 4 '16 at 22:46
13
$\begingroup$

$\text{tr}(AB+BA) = 2 \text{tr}(A^{1/2} B A^{1/2}) > 0$, so that may produce some bias toward positive eigenvalues. In particular if you generate your "random" matrices in such a way that the eigenvalues of $AB+BA$ will tend to be concentrated very close together, this may produce the results you observed.

But I tried a different experiment: $A = X^T X$ and $B = Y^T Y$ where $X$ and $Y$ are random $n \times n$ matrices with integer entries in $[-100,100]$.
For the case $n=10$, I found that it was very rare (0 occurrences in 3000 trials) for $AB + BA$ to be positive definite.

$\endgroup$
  • 2
    $\begingroup$ I just add a proof for the reader that might be puzzled by your first formula. It is based (I imagine that it is also your way for proving it) on the following lemma (known as invariance by cylic permutations) $tr(MNP)=tr(PMN)=tr(NPM)$ for any square matrices with the same dimensions. Thus it suffices to write $AB=A^{1/2}A^{1/2}B=A^{1/2}BA^{1/2}$, and the same for $BA$. $\endgroup$ – Jean Marie Becker Aug 4 '16 at 22:19
  • 2
    $\begingroup$ May I suggest not using the symbol $T$ two different ways in one equation? $\endgroup$ – Gerry Myerson Aug 4 '16 at 23:14
  • 1
    $\begingroup$ Good suggestion: changed $S$ and $T$ to $X$ and $Y$. $\endgroup$ – Robert Israel Aug 5 '16 at 0:39
21
$\begingroup$

Your question appears to be based on a false premise. In fact $AB+BA$ does not tend to be positive definite as $n$ increases, even within the particular distribution you happen to be using.

To demonstrate this, here is a simple piece of Mathematica code that implements precisely the numerical experiment you described:

randMat[n_] := With[{
    eigval = RandomReal[{0, 1}, n],
    eigvec = Orthogonalize @ RandomVariate[NormalDistribution[], {n, n}]},
  Transpose[eigvec] . DiagonalMatrix[eigval] . eigvec];

prob[n_] := Table[With[{A = randMat[n], B = randMat[n]},
  PositiveDefiniteMatrixQ[A.B + B.A]], {10000}];

The results obtained (from running 10,000 trials for each value of $n$) are as follows:

+-----+-------------------------------+-----------------------------------+
| n   | probability that AB+BA is pd  | probability that AB+BA is NOT pd  |
+-----+-------------------------------+-----------------------------------+
| 2   | 94.67%                        | 05.33%                            |
+-----+-------------------------------+-----------------------------------+
| 3   | 87.09%                        | 12.91%                            |
+-----+-------------------------------+-----------------------------------+
| 4   | 79.57%                        | 20.43%                            |
+-----+-------------------------------+-----------------------------------+
| 5   | 71.26%                        | 28.74%                            |
+-----+-------------------------------+-----------------------------------+
| 10  | 39.94%                        | 60.06%                            |
+-----+-------------------------------+-----------------------------------+
| 15  | 21.78%                        | 78.22%                            |
+-----+-------------------------------+-----------------------------------+
| 20  | 10.31%                        | 89.69%                            |
+-----+-------------------------------+-----------------------------------+
| 50  | 00.16%                        | 99.84%                            |
+-----+-------------------------------+-----------------------------------+
| 100 | 00.00%                        | 100.00%                           |
+-----+-------------------------------+-----------------------------------+

From this it is clear that you must have accidentally switched the two columns. As $n$ increases, it is becomes rarer for $AB + BA$ to be positive definite.

As an aside, I find it surprising that this question and its currently accepted answer have received a combined 17 upvotes, when seemingly nobody has even tried to replicate the OP's trivial numerical experiment.

$\endgroup$
  • $\begingroup$ Hmm. I thought it looked fishy, especially for $n=2$. $\endgroup$ – Robert Israel Aug 5 '16 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.