Question

Is the product of non-negative definite matrices also non-negative definite? If not, let A and B be non-negative definite matrices, is '$tr(A^T B) >=0$' ?

Answer 1

Lemma 1. Let $k$ be a field, and $A\in k^{n\times n}$ be a symmetric matrix.

(a) Then, there exist an invertible matrix $U\in k^{n\times n}$ and a diagonal matrix $D\in k^{n\times n}$ such that $A=U^TDU$.

(b) Let the field $k$ be ordered. The matrix $A$ is nonnegative-definite if and only if all entries of the matrix $D$ are nonnegative.

I'm writing a proof of this, mainly because too many sources do it wrong (for instance, by assuming $k$ to be ordered in (a), where it is useless, or using the spectral theorem, which is much stronger and requires $k=\mathbb R$). But it isn't necessary for your question: you only seem to need the $k=\mathbb R$ case, where any proof would do.

EDIT: I'm not writing a proof of this. Too tired from the rest. See Proposition 15.1 in J. S. Milne's "Algebraic Groups, Lie Groups, and their Arithmetic Subgroups" Chapter I for a proof of Lemma 1 (a), and derive Lemma 1 (b) from it.

Corollary 2. Let $k$ be an ordered field. Let $A\in k^{n\times n}$ and $B\in k^{n\times n}$ be two symmetric nonnegative-definite matrices. Then, $\mathrm{Tr}\left(AB\right)\geq 0$.

Proof of Corollary 2. Consider the Kronecker product $A\otimes B\in k^{n^2\times n^2}$ of the two matrices $A$ and $B$. This Kronecker product $A\otimes B$ is defined as the matrix $\left(A_{i,j}B_{i',j'}\right)_{\left(1,1\right)\leq \left(i,i'\right)\leq \left(n,n\right),\ \left(1,1\right)\leq \left(j,j'\right)\leq \left(n,n\right)}$. Here, $A_{i,j}$ is the $\left(i,j\right)$-th entry of the matrix $A$, and $B_{i',j'}$ is the $\left(i',j'\right)$-th entry of the matrix $B$. Besides, the coordinates in the vector space $k^{n^2}$ are indexed by pairs $\left(i,i'\right)\in\left\lbrace 1,2,...,n\right\rbrace^2$, and these pairs are ordered lexicographically.

Lemma 1 (a) yields the existence of an invertible matrix $U\in k^{n\times n}$ and a diagonal matrix $D\in k^{n\times n}$ such that $A=U^TDU$, and Lemma 1 (b) shows that all entries of the matrix $D$ are nonnegative. Similarly, Lemma 1 (a) (applied to the matrix $B$ instead of $A$) yields the existence of an invertible matrix $V\in k^{n\times n}$ and a diagonal matrix $E\in k^{n\times n}$ such that $B=V^TEV$, and Lemma 1 (b) shows that all entries of the matrix $E$ are nonnegative. Thus, $A\otimes B=\left(U^TDU\right)\otimes\left(V^TEV\right)=\left(U\otimes V\right)^T\left(D\otimes E\right)\left(U\otimes V\right)$, so that the matrix $A\otimes B$ is nonnegative-definite (because the matrix $D\otimes E$ is a diagonal matrix all of whose entries are nonnegative, and therefore it is nonnegative-definite).

Now, let $v\in k^{n^2}$ be the vector given by $v_{\left(i,i'\right)}=\left[i=i'\right]$ for any pair $\left(i,i'\right)\in\left\lbrace 1,2,...,n\right\rbrace^2$. Here, for any assertion $\mathcal A$, we denote by $\left[\mathcal A\right]$ the truth value of $\mathcal A$, defined by $\left[\mathcal A\right]=1$ if $\mathcal A$ is true and $\left[\mathcal A\right]=0$ otherwise.

Now, an easy computation yields $v^T\left(A\otimes B\right)v=\mathrm{Tr}\left(AB^T\right)$. Since $B^T=B$, this becomes $v^T\left(A\otimes B\right)v=\mathrm{Tr}\left(AB\right)$. But $v^T\left(A\otimes B\right)v\geq 0$, since $A\otimes B$ is a nonnegative-definite matrix. Thus, $\mathrm{Tr}\left(AB\right)\geq 0$, proving Corollary 2.