Maximizing trace of mixed products of two real symmetric matrices

Let $A$, $B$ be two $N \times N$ real symmetric matrices whose entries i.i.d.r.v. from a mean 0, variance 1 distribution.

Let $I, J$ be even positive integers, and let $i_k, j_k$ for $k = 1,\ldots,n$ be arbitrary finite sequences of positive integers such that $\sum i_k = I$ and $\sum j_k = J$.

Is it true that

$\text{Tr} (A^I B^J) \geq \text{Tr}\left( A^{i_1} B^{j_1} \cdots A^{i_n} B^{j_n} \right) $?

I have run extensive numerical experiments in Mathematica on large (10K x 10K) random real symmetric matrices, and have been unable to find a counterexample; I am wondering if this might be established in a theoretical sense.

Solution 1:

@DavidESpeyer The inequality is false for general symmetric real $A,B$. A simple example is as follows. Let $P,Q$ be two orthogonal projections in $\mathbb R^2$ so that $0<\|PQ\|_F<\frac 12$ and let $P',Q'$ be the complementary orthogonal projections. Then $U=(P-P')(Q-Q')$ is a product of two reflections, i.e., a rotation and we can easily arrange it to be a rotation by an irrational multiple of $\pi$. Then for every unit vector $x$, the orbit $U^mx:m\ge 0$ is dense on the unit circle.

In particular, if $x$ is a unit vector such that $Qx=x$ and $y$ is a unit vector such that $Py=y$, then we can find $m$ so that $U^mx\approx y$ and, thereby, $\|PU^mQ\|\approx 1$ even for the operator norm.

Now choose $a\in(0,1)$ so close to $1$ that the same holds for $U_a=(P-aP')(Q-aQ')$ instead of $U$. At last, put $A=P-aP', B=Q-aQ'$ and choose so large power $N$ that $A^n\approx P$ and $B^n\approx Q$ for all $n\ge N$. Then $$ \|A^N(AB)^mB^N\|_F\approx \|PU_a^m Q\|_F\ge \|PU_a^mQ\|\approx 1 \\ >\frac 12>\|PQ\|_F\approx \|A^{N+m}B^{N+m}\|_F $$ I cannot pull this trick with positive definite $A,B$ though, so that case still remains to be investigated.

Edit Here is a counterexample in $\mathbb R^3$ for the positive semi-definite case. Let $x,y$ be 2 orthogonal unit vectors in $\mathbb R^3$ and let $z$ be the unit vector that is linearly independent with $x,y$ and makes an angle $\pi/3$ with both of them (the exact angle value is not important as long as it is strictly smaller than $\pi/2$). For unit vectors $u,v$, let $P_u$ be the orthogonal projection to the line spanned by $u$ and let $P_{uv}$ be the orthogonal projection to the plane spanned by $u$ and $v$.

Note that $(P_{xz}P_{yz})^m\to P_z$ as $m\to\infty$. Choose a large $m$ so that $(P_{xz}P_{yz})^m\approx P_z$ with high precision. Now let $x'$ be the unit vector orthogonal to $x$ in the plane spanned by $x,z$ and let $y'$ be the unit vector orthogonal to $y$ in the plane spanned by $y,z$. We have $P_{xz}=P_x+P_{x'}$ and similarly for $P_{yz}$. Choose $a\in (0,1)$ so close to $1$ that the operators $A=P_x+aP_{x'}$ and $B=P_y+aP_{y'}$ still satisfy $(AB)^m\approx P_z$. Now choose $N$ so that for all $n\ge N$, we have $A^n\approx P_x$, $B^n\approx P_y$. Then $$ \|A^N(AB)^mB^N\|_F\approx\|P_xP_zP_y\|_F=\frac 14 \\ >0=\|P_xP_y\|_F\approx \|A^{N+m}B^{N+m}\|_F\,. $$
Thus there is no hope for the general version of the problem even for positive definite matrices. However, for positive definite matrices there are two statements that are true and not too hard to prove:

(1) The conjecture holds in $\mathbb R^2$ (so my 3-dimensional counter-example is a minimal one)

(2) If $\alpha_j\ge 0, \sum_j \alpha_j=1$, then for any positive definite $A,B$ in any dimension, we have $$ \|C_1\dots C_m\|_F\le \|AB\|_F $$ where each $C_j$ is either $A^{\alpha_j}B^{\alpha_j}$ or $B^{\alpha_j}A^{\alpha_j}$. This takes care of the products like $AB^2AB$, but not of $A^2BAB$, say. I wonder if this restricted type of products is actually the best we can confirm the conjecture for.