A conjecture about traces of projections
Solution 1:
I prove only $y\ge \frac x2(3x-1)$. We know that $A+B+C\ge 0$, so let $\lambda_1,\dots,\lambda_n$ be its eigenvalues. Then $$ \frac 1n Tr(A+B+C)=\frac 1n \sum \lambda_i=\bar \lambda= 3x $$ and $$ Tr((A+B+C)^2)=\sum \lambda_i^2\ge n \bar \lambda^2=9nx^2. $$ But $$ (A+B+C)^2=A^2+B^2+C^2+AB+AC+BA+BC+CA+CB $$ and so $$ Tr((A+B+C)^2)=Tr(A+B+C)+2Tr(AB+BC+CA)=3nx+6ny. $$ Hence $3nx+6ny\ge 9nx^2$ which yields $y\ge \frac x2(3x-1)$.
${\bf{Edit:}}$
The bound given by the OP is attained for every $n$ and every admissible $x$: Set $$ A_0=\begin{pmatrix} 1&0\\ 0&0 \end{pmatrix},\quad B_0=\begin{pmatrix} 1/4&-\sqrt{3}/4\\ -\sqrt{3}/4&3/4 \end{pmatrix}\quad\text{and}\quad C_0=\begin{pmatrix} 1/4&\sqrt{3}/4\\ \sqrt{3}/4&3/4 \end{pmatrix}. $$ Then $Tr(A_0B_0+B_0C_0+C_0A_0)=\frac 34$.
Let now $n$ be given, and $x=\frac {n+k}{3n}$ be admissible, i.e., $0\le k\le n/2$. Define $A$ to have $k$ times the block matrix $A_0$ on the diagonal, and complete the diagonal with $n-2k$ times 1: $$ A=\begin{pmatrix} A_0&&&&& \\&\ddots&&& 0& \\ && A_0&&&\\ &&&1 && \\ &0&&& \ddots &\\ &&&&& 1\end{pmatrix}. $$ Define $B$ to have $k$ times the block matrix $B_0$ on the diagonal, and complete the diagonal with $n-2k$ times 0: $$ B=\begin{pmatrix} B_0&&&&& \\&\ddots&&& 0& \\ && B_0&&&\\ &&&0 && \\ &0&&& \ddots &\\ &&&&& 0\end{pmatrix}. $$ Define $C$ to have $k$ times the block matrix $C_0$ on the diagonal, and complete the diagonal with $n-2k$ times 0: $$ C=\begin{pmatrix} C_0&&&&& \\&\ddots&&& 0& \\ && C_0&&&\\ &&&0 && \\ &0&&& \ddots &\\ &&&&& 0\end{pmatrix}. $$
Then $x=\frac{1}{3n}Tr(A+B+C)=\frac{n+k}{3n}$ (which implies $\frac kn=3x-1$) and $$ y=\frac{1}{3n}Tr(AB+BC+CA)=\frac{1}{3n}Tr(k(A_0B_0+B_0C_0+C_0A_0))=\frac{1}{3n}\frac 34k= \frac 14 \frac kn=\frac{3x-1}{4}, $$ hence the bound is attained.
Solution 2:
We will use the following results of my first answer:
$y\ge \frac x2(3x-1)$.
The bound given by the OP is attained for every $n$ and every admissible $x$.
Set $$ A_0=\begin{pmatrix} 1&0\\ 0&0 \end{pmatrix},\quad B_0=\begin{pmatrix} 1/4&-\sqrt{3}/4\\ -\sqrt{3}/4&3/4 \end{pmatrix}\quad\text{and}\quad C_0=\begin{pmatrix} 1/4&\sqrt{3}/4\\ \sqrt{3}/4&3/4 \end{pmatrix}. $$ Then $Tr(A_0B_0+B_0C_0+C_0A_0)=\frac 34$, which yields a minimum.
$\bf{Corollary:}\ $ If $n=2$ and $x=1/2$, then the minimum is $y=1/8$, and is attained for $$ A_0=\begin{pmatrix} 1&0\\ 0&0 \end{pmatrix},\quad B_0=\begin{pmatrix} 1/4&-\sqrt{3}/4\\ -\sqrt{3}/4&3/4 \end{pmatrix}\quad\text{and}\quad C_0=\begin{pmatrix} 1/4&\sqrt{3}/4\\ \sqrt{3}/4&3/4 \end{pmatrix}. $$
$\bf{Corollary:}\ $ Assume $A$, $B$ and $C$ minimize $y$ for a given $x$, and there exists a 2-dimensional subspace $E$ such that both $E$ and $E^\bot$ are invariant under $A$, $B$ and $C$, (which means that the projection on that subspace $P_E$ commutes with $A$, $B$ and $C$). If $Tr((A+B+C)|_E)=3$ then $Tr((AB+BC+CA)|_E)=3/4$.
${\bf Proof:}$ Write $A_E=A|_E$. Clearly $x_E=\frac 13\frac 12 Tr(A_E+B_E+C_E)=1/2$, hence $y_E=\frac 13\frac 12 Tr(A_EB_E+B_EC_E+C_EA_E)\ge 1/8$. But if $y_E=\frac 13\frac 12 Tr(A_EB_E+B_EC_E+C_EA_E)> 1/8$, then we can replace $A_E$ by $A_0$, $B_E$ by $B_0$ and $C_E$ by $C_0$, i.e., $\bar A:=A-A_E+A_0$, where $A_0$ is the matrix above on some orthogonal basis of $E$ and similarly $\bar B$ and $\bar C$; and then $$ \bar y=\frac 1{3n}Tr(\bar A\bar B+\bar B\bar C+\bar C\bar A)< \frac 1{3n}Tr(AB+BC+CA)=y $$ which contradicts the minimality condition of $A$, $B$ and $C$. $\quad \quad\Box$
The following proposition is central in the argument. I don't know if it holds for the complex case. So, from now on we assume that $A$, $B$ and $C$ are real matrices.
${\bf Proposition:}$ Assume $A$, $B$ and $C$ minimize $y$ for a given $x$. Then $A$ commutes with $B+C$, in particular they have the same eigenvectors, similarly $B$ commutes with $A+C$ and $C$ commutes with $A+B$.
${\bf Proof:}$ We give the proof only in the case that $A$, $B$ and $C$ are real matrices. Let $\{v_i\}_{i\in I}$, $\{w_j\}_{j\in J}$ and $\{z_k\}_{k\in K}$ be orthonormal basis of $Im(A)$, $Im(B)$ and $Im(C)$, respectively. Let $I=\{1,\dots,a\}$, $J=\{1,\dots,b\}$ and $K=\{1,\dots,c\}$. Then $Tr(A)=a$, $Tr(B)=b$ and $Tr(C)=c$. Moreover $$ Tr(AB)=\sum_{i\in I}\sum_{j\in J}\langle v_i,w_j\rangle\langle w_j,v_i\rangle. $$ This follows from the fact that $A(v)=\sum_{i\in I} \langle x,v_i\rangle v_i$ and $Tr(T)=\sum_{i=1}^n \langle T e_i,e_i\rangle$ for any orthonormal basis $\{e_i\}$.
Then $(v_i,w_j,z_k)\in \Bbb{R}^{n(a+b+c)}$ gives a solution to the following minimization problem:
Minimize $$ f=6ny=\sum_{i\in I}\sum_{j\in J}\langle v_i,w_j\rangle\langle w_j,v_i\rangle+ \sum_{k\in K}\sum_{j\in J}\langle z_k,w_j\rangle\langle w_j,z_k\rangle+ \sum_{i\in I}\sum_{k\in K}\langle v_i,z_k\rangle\langle z_k,v_i\rangle $$ subject to the restrictions that $\{v_i\}$, $\{w_j\}$ and $\{z_k\}$ are ortonormal families, i.e., $$ g_{i,j}^{(1)}=\langle v_i,v_j \rangle-\delta_{ij}=0,\quad g_{i,j}^{(2)}=\langle w_i,w_j \rangle-\delta_{ij}=0,\quad\text{and}\quad g_{i,j}^{(3)}=\langle z_i,z_j \rangle-\delta_{ij}=0. $$ Then, by the optimization method with Lagrange multipliers, there exist $\lambda_{i,j}^{(k)}$ such that $$ \nabla f=\sum_{i,j,k}\lambda_{i,j}^{(k)}\nabla g_{i,j}^{(k)}. $$ We have $$ \frac{\partial f}{\partial(v_i)_s}=\sum_j\langle v_i,w_j\rangle (w_j)_s+\sum_j\langle v_i,z_k\rangle (z_k)_s $$ and $$ \frac{\partial g_{ij}^{(1)}}{\partial(v_i)_s}=(v_j)_s+\delta_{ij}(v_i)_s\quad\text{and}\quad \frac{\partial g_{ij}^{(2)}}{\partial(v_i)_s}=0 =\frac{\partial g_{ij}^{(3)}}{\partial(v_i)_s}, $$ hence $$ \sum_j\langle v_i,w_j\rangle w_j+\sum_j\langle v_i,z_k\rangle z_k=-\sum_{j\in I}\lambda_{ij}^{(1)}(v_j+\delta_{ij}v_i). $$ Since $\sum_j\langle v_i,w_j\rangle w_j=B v_i$ and $\sum_j\langle v_i,z_k\rangle z_k=C v_i$, it follows that $(B+C)v_i\in Im(A)$, and so, for all $x$, we have $$ (B+C)Ax=(B+C)\sum_i\langle x,v_i\rangle v_i\in Im(A), $$ hence $A(B+C)Ax=(B+C)A(x)$ for all $x$, which means that $A(B+C)A=(B+C)A$. Since $A$, $B$ and $C$ are selfadjoint, we obtain $A(B+C)=(B+C)A$, as desired. The other cases follow by the same argument. In the complex case, with Lagrange we only obtain that $(\bar B+\bar C)v_i\in Im(A)$, where $\bar B$ is the conjugate linear morphism given by $\bar B(x)=\sum_j \langle w_j,x\rangle w_j$. $\quad\quad\Box$
$\bf{Lemma:}$ Assume $(A+B)v=\alpha v$ for some $\alpha\in \Bbb{R}\setminus\{1\}$. Then $\|Av\|^2=\|Bv\|^2=\frac \alpha 2\|v\|^2$.
${\bf Proof:}$ Clearly it suffices to prove the lemma for the case $\|v\|=1$. So assume $\|v\|=1$ and set $a:=\|Av\|$ and $b:=\|Bv\|$. Since $$ Av+Bv=\alpha v=proj_v(\alpha v)=proj_v(Av)+proj_v(Bv)=\langle Av,v\rangle v+\langle Bv, v\rangle v, $$ we have $\alpha=a^2+b^2$ (note that $a^2=\|Av\|^2=\langle Av,Av\rangle=\langle Av,v\rangle$), and $$ \|Av\|^2-\|proj_v(Av)\|^2=\|Av-proj_v(Av)\|^2=\|Bv-proj_v(Bv)\|^2=\|Bv\|^2-\|proj_v(Bv)\|^2. $$ Hence $a^2-a^4=b^2-b^4$ and so $(a^2-b^2)(a^2+b^2-1)=0$. Since $a^2+b^2-1=\alpha-1\ne 0$, we have $a=b$ as desired, and $\alpha=a^2+b^2$ yields $\|Av\|^2=\|Bv\|^2=\frac \alpha 2$. $\quad\quad\Box$
${\bf Definition:}$ We say that a linear subspace $E\subset \Bbb{R}^n$ splits a projection $A$, if $A(E)\subset E$ and $(Id-A)(E)\subset E$.
${\bf Definition:}$ We define $S_A:=\{v\in Im(A), \|v\|=1\}$ and similarly $S_B$ and $S_C$.
${\bf Theorem:}$ Assume $A$, $B$ and $C$ minimize $y$ for a given $1/3<x\le 1/2$, such that $$ Im(A)\cap Im(B)=Im(B)\cap Im(C)=Im(C)\cap Im(A)=\{0\}. $$ Then there exists a 2-dim subspace $E\subset \Bbb{R}^n$ which splits $A$, $B$ and $C$, and such that $rk(A|_E)=rk(B|_E)=rk(C|_E)=1$.
${\bf Proof:}$ Define $\mu_{AB}=max\{\langle v,w\rangle, s.t.\ \|v\|=1=\|w\|, v\in Im(A), w\in Im(B)\}$ and similarly $\mu_BC$ and $\mu_{CA}$. We assume wlog that $\mu_{AB}\ge \mu_{BC},\mu_{CA}$, in particular one verifies that $\mu_{AB}>0$. Let $v\in S_A$, $w\in S_B$ be such that $\langle v,w\rangle=\mu=\mu_{AB}$. Then we can find an orthonormal basis $\{v_i\}_{i\in I}$ of $Im(A)$ and an orthonormal basis $\{w_j\}_{j\in J}$ of $Im(B)$ such that $v_1=v$ and $w_1=w.$
We claim that $v_1\bot w_j$ for $j>1$ and $w_1\bot v_i$ for $i>1$. In fact, if $\langle v,w_j\rangle\ne 0$, then define $u:=proj_w v+proj_{w_j}v$, so $$ \|u\|^2= \|proj_w v\|^2+\|proj_{w_j}v\|^2=\langle v,w\rangle^2+\langle v,w_j\rangle^2. $$ But then $\frac{u}{\|u\|}\in S_B$ and $$ \langle v,\frac{u}{\|u\|}\rangle=\frac{1}{\|u\|}(\langle v,proj_{w_j}v\rangle+\langle v,proj_{w}v\rangle) =\frac{1}{\|u\|}(\langle v,w\rangle^2+\langle v,w_j\rangle^2)=\|u\|>\langle v,w\rangle, $$ which contradicts the minimality of $\langle v,w\rangle$ and proves the claim. Moreover $\mu<1$ since $Im(A)\cap Im(B)=\{0\}$, and so the subspace $E_{v,w}:=\Bbb{R}v+\Bbb{R}w$ generated by $v$ and $w$ is 2-dimensional. By the above discussion, it splits simultaneously $A$ and $B$, and $rk(A|_E)=1=rk(B|_E)$. Now $z:=v+w$ satisfies $$ (A+B)(z)=Av+Bv+Aw+Bw=v+w+Aw+Bv=v+w+\langle w,v\rangle v+\langle v,w\rangle w=(1+\langle v,w\rangle)(v+w), $$ so $z$ is an eigenvector of $A+B$ corresponding to the eigenvalue $1+\mu_{AB}>1$. Then the eigenspace $E_{1+\mu}$ splits $C$, since $C$ commutes with $A+B$.
We now claim that $E_{1+\mu}\subset Ker(C)=Im(I-C)$. In fact, there is a basis of $E_{1+\mu}$ consisting of eigenvectors of $C$ (with eigenvalues 0 or 1). Assume by contradiction that there exists an eigenvector $z$ of $C$ in $E_{1+\mu}$ with $Cz=z$. Then we can assume $\|z\|^2=\frac{2}{1+\mu}$, and then by the Lemma we have $\|Az\|^2=\|Bz\|^2=\frac{1+\mu}{2}\|z\|^2=1$. But then $$ \mu_{AC}\ge \langle Az,\frac{z}{\|z\|}\rangle=\sqrt{\frac{1+\mu}{2}}>\mu=\mu_{AB} $$ (note that $\frac{1+\mu}{2}>\mu^2$ for $0<\mu<1$), which contradicts the assumption $\mu_{AB}\ge \mu_{AC}$, and proves the claim: $E_{1+\mu}\subset Ker(C)=Im(I-C)$.
Let $v\in S_A$, $w\in S_B$ be such that $\langle v,w\rangle=\mu=\mu_{AB}$. Then $(A+B)(v-w)=(1-\mu)(v-w)$, so $v-w$ is an eigenvector of $A+B$ corresponding to the eigenvalue $1-\mu_{AB}<1$. Then the eigenspace $E_{1-\mu}$ splits $C$, since $C$ commutes with $A+B$.
We now claim that there exists $z\in E_{1-\mu}$ such that $Cz=z$. In fact, there is a basis of $E_{1-\mu}$ consisting of eigenvectors of $C$ (with eigenvalues 0 or 1). If all eigenvalues are zero, then $E_{1-\mu}\subset Ker(C)$, and then for any $v\in S_A$, $w\in S_B$ with $\langle v,w\rangle=\mu=\mu_{AB}$, the subspace $E_{v,w}$ generated by $v,w$ splits $A$, $B$ and $C$, but then we can replace $A$ by $\bar A:=A-proj_v+proj_{v_1}$ where $v_1$ is in $E_{v,w}$ and is orthogonal to $w$. Then $Tr(\bar A B+BC+C\bar A)=Tr(AB+BC+CA)-\mu^2$, which contradicts the minimality of $y$ and proves the claim.
So let $z\in E_{1-\mu}$ such that $Cz=z$ and we can assume that $\|z\|^2=2(1-\mu)$. Define $v:=\frac{1}{1-\mu}Az$ and $w:=\frac{1}{\mu-1}Bz$. Then $v-w=\frac{1}{1-\mu}(Az+Bz)=z$. Moreover by the Lemma $\|Az\|^2=\|Bz\|^2=\frac{1-\mu}{2}\|z\|^2=(1-\mu)^2$, and so $\|Az\|=\|Bz\|=1-\mu$, consequently $\|v\|=\|w\|=1$. We also have $$ 2-2\langle v,w\rangle=\|v-w\|^2=\|z\|^2=2(1-\mu), $$ hence $\langle v,w\rangle=\mu$. Then by the previous discussion $v+w\in Ker(C)$. Hence $E_{v,w}$ splits $A$, $B$ and $C$, and $rk(A|_E)=rk(B|_E)=rk(C|_E)=1$, as desired. $\quad\quad \Box$
${\bf Corollary:}$
(1) Assume $A$, $B$ and $C$ minimize $y$ for a given $1/3<x\le 1/2$ and that $Im(A)\cap Im(B)=Im(B)\cap Im(C)=Im(C)\cap Im(A)=\{0\}$. Then $y= (3x-1)/4$.
(2) $y\ge (3x-1)/4$ for all $n$ and all admissible $x\le 1/2$.
${\bf Proof:}$
(1). We prove this by induction on $n$. For $n=1$ it is clear, and for $n=2$ it is proven above. Now assume $A$, $B$ and $C$ in $M_n(\Bbb{R})$ minimize $y$ for a given $1/3<x\le 1/2$ (with $3nx=Tr(A+B+C)=n+k$) and that $Im(A)\cap Im(B)=Im(B)\cap Im(C)=Im(C)\cap Im(A)=\{0\}$. By the theorem, there exists 2-dim subspace $E\subset \Bbb{R}^n$ which splits $A$, $B$ and $C$, and such that $rk(A|_E)=rk(B|_E)=rk(C|_E)=1$. Let $F:=E^{\bot}$. Then $y_F=\frac{1}{3(n-2)}Tr(A_FB_F+B_FC_F+C_FA_F)$ is minimal, hence, by the inductive hypothesis, $y_F=(3x_F-1)/4$, since $$ Im(A_F)\cap Im(B_F)=Im(B_F)\cap Im(C_F)=Im(C_F)\cap Im(A_F)=\{0\}. $$ Here $$ x_F=\frac{1}{3(n-2)}Tr(A_F+B_F+C_F)=\frac{n+k-3}{3(n-2)}, $$ and so $y_F=\frac{k-1}{4(n-2)}$. But then $$ 3ny=Tr(A_FB_F+B_FC_F+C_FA_F)+Tr(A_0B_0+B_0C_0+C_0A_0)=3(n-2)y_F+\frac 34=\frac 34k, $$ and so $y=\frac 14\frac kn=\frac{3x-1}{4}$, as desired.
(2). Now we prove that $Im(A)\cap Im(B)=Im(B)\cap Im(C)=Im(C)\cap Im(A)=\{0\}$. If this is not true, then one of $Im(A)\cap Im(B)$, $Im(B)\cap Im(C)$ or $Im(C)\cap Im(A)$ is not zero, let's say $Im(A)\cap Im(B)\ne \{0\}$. Then $Im(A)\cap Im(B)$ is the eigenspace of $A+B$ corresponding to the eigenvalue 2. Since $A+B$ and $C$ commute, $Im(A)\cap Im(B)$ splits $C$, i.e., $$ Im(A)\cap Im(B)=Im(A)\cap Im(B)\cap Im(C)\oplus Im(A)\cap Im(B)\cap Ker(C), $$ Similarly $$ Im(B)\cap Im(C)=Im(B)\cap Im(C)\cap Im(B)\oplus Im(B)\cap Im(C)\cap Ker(A), $$ and $$ Im(A)\cap Im(C)=Im(A)\cap Im(C)\cap Im(B)\oplus Im(A)\cap Im(C)\cap Ker(B). $$ Then each of the five subspaces $$ E_0=Im(A)\cap Im(B)\cap Im(C),\quad E_1=Im(A)\cap Im(B)\cap Ker(C), $$ $$ E_2=Im(A)\cap Ker(B)\cap Im(C),\quad E_1=Ker(A)\cap Im(B)\cap Im(C),\quad E:=(E_0\oplus E_1\oplus E_2\oplus E_3)^{\bot}, $$ splits $A$, $B$ and $C$, i.e., $A$ is formed by five block matrices in the diagonal, $A_0$, $A_1$, $A_2$, $A_3$ and $A_E$, and similarly $B$ and $C$. Then $3nx=n+k=Tr(A+B+C)$ implies $(3x-1)/4=\frac 14 \frac kn$. Let $r_i=dim(E_i)$ and $r_E=dim(E)$. We have $Tr(A_0+B_0+C_0)=3r_0$ and $Tr(A_i+B_i+C_i)=2r_i$ for $i=1,2,3$. Moreover $Tr(A_0B_0+B_0C_0+C_0A_0)=3r_0$ and $Tr(A_iB_i+B_iC_i+C_iA_i)=r_i$ for $i=1,2,3$, and so $$ \sum_{i=0}^3 Tr(A_iB_i+B_iC_i+C_iA_i)=2r_0+\sum_{i=0}^3 r_i. $$
Set $n_E:=n-\sum_{i=0}^3 r_i=dim(E)$. Then $$ 3 n_E x_E=Tr(A+B+C)-\sum_{i=0}^3 Tr(A_i+B_i+C_i)=n+k-r_0-2\sum_{i=0}^3r_i=n_E+k-r_0-\sum_{i=0}^3r_i, $$ and since $A_E$, $B_E$ and $C_E$ satisfy the conditions of the theorem and $x_E<x\le 1/2$, $$ Tr(A_E B_E+B_E C_E+C_E A_E)=3n_E y_E\ge 3n_E \frac{ 3x_E-1}{4}=\frac 34 (3n_E x_E-n_E)=\frac 34(k-r_0-\sum_{i=0}^3r_i). $$ Note that $y_E$ is minimal and so $y_E=(3x_E-1)$ if $x_E\ge 1/3$, and else $y_E=0>(3x_E-1)$. Since $$ 3ny=Tr(AB+BC+CA)=Tr(A_E B_E+B_E C_E+C_E A_E)+\sum_{i=0}^3 Tr(A_iB_i+B_iC_i+C_iA_i), $$ it follows that $$ 3ny\ge \frac 34(k-r_0-\sum_{i=0}^3r_i)+2r_0+\sum_{i=0}^3 r_i=\frac 34 k+\frac 54 r_0+\frac 14 \sum_{i=0}^3r_i>\frac 34 k, $$ contradicting the minimality condition on $A$, $B$ and $C$, since we have constructed an example with $3ny=3n\frac{3x-1}{4}=\frac 34 k$. This concludes the proof. $\quad\quad\Box$
${\bf{ Final\ Remark:}}$ In the complex case I think that one can adapt the proof, the difficult part is the Lagrangian method.