Trace Inequality: prove that for arbitrary square matrix A and B: tr((A+B)(A+B)^T) \leq 2 * tr(AA^T+BB^T)

Question

prove that for arbitrary square matrix A and B:

$$ tr((A+B)(A+B)^T) \leq 2 \cdot tr(AA^T+BB^T) $$

---

Here is what i did so far:

left side:

$$ tr((A+B)(A+B)^T) = tr(AA^T)+tr(AB^T) +tr(BA^T)+tr(BB^T) $$

right side: $$ 2 \cdot tr(AA^T+BB^T) = 2 tr(AA^T) + 2 tr(BB^T) $$

we now have :

$$ tr(AA^T)+tr(AB^T) +tr(BA^T)+tr(BB^T) \leq 2 tr(AA^T) + 2 tr(BB^T) $$ $$ \Rightarrow tr(AB^T) +tr(BA^T) \leq tr(AA^T) + tr(BB^T) $$

And then I get kinda stuck here. I tried to use the property: $tr(A)=\sum_{i=1}^n \lambda_i$ where $\lambda_i$ is the i'th eigenvalue of $A$ but it didnt seem to get me anywhere.

Answer 1

To prove the given inequality:

$ \mathrm{tr} \left((A+B)(A+B)^T\right) \leq 2 \cdot \mathrm{tr}(AA^T + BB^T) $

Note than LHS can be written as:

$ \mathrm{tr}\left(AA^T + AB^T\right) + \mathrm{tr}\left(A^TB + B^TB\right) = \mathrm{tr}(AA^T) + \mathrm{tr}(AB^T) + \mathrm{tr}(A^TB) + \mathrm{tr}(B^TB) $

Now, notice that $\mathrm{tr}(AB^T)$ and $\mathrm{tr}(A^TB)$ are equal because the trace of a product of matrices is invariant under cyclic permutation. Proof is simple. Take $C = B^{T}A$ and write,

$\mathrm{tr}(AB^T) = \mathrm{tr}(B^TA)=\sum_{i=1}^n c_{ii}=\sum_{i=1}^n\sum_{k=1}^m b_{ki}a_{ki} = a_{ki}b_{ki} = \mathrm{tr}(A^TB)$

So:

$ \operatorname{tr}(AA^T) + \operatorname{tr}(AB^T) + \operatorname{tr}(A^TB) + \operatorname{tr}(B^TB) = \operatorname{tr}(AA^T) + 2 \cdot \operatorname{tr}(AB^T) + \operatorname{tr}(B^TB) $

Now, let's use the fact that the trace of a matrix is equal to the sum of its eigenvalues. Let $\lambda_1, \lambda_2, \ldots, \lambda_n$ be the eigenvalues of $A$, and $\mu_1, \mu_2, \ldots, \mu_m$ be the eigenvalues of $B$. Then,

$ \operatorname{tr}(AA^T) + 2 \cdot \operatorname{tr}(AB^T) + \operatorname{tr}(B^TB) = \sum(\lambda_i^2) + 2 \sum(\lambda_i \mu_j) + \sum(\mu_j^2) $

Now, we can use the fact that the sum of the squares of the eigenvalues of a matrix is greater than or equal to twice the sum of the products of the eigenvalues (which follows from the Cauchy-Schwarz inequality for inner products):

$ \sum(\lambda_i^2) + \sum(\mu_j^2) \geq 2 \cdot \sum(\lambda_i \mu_j) $

Now, substitute this inequality with the expression above to get:

$ \sum(\lambda_i^2) + 2 \cdot \sum(\lambda_i \mu_j) + \sum(\mu_j^2) \leq 2(\sum(\lambda_i^2) + \sum(\mu_j^2)) $

This proves

$ \operatorname{tr}\left((A+B)(A+B)^T\right) \leq 2 \cdot \operatorname{tr}(AA^T + BB^T) $

I hope this helps!