Product of Positive Matrices

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 '$\operatorname{tr}(A^T B) \ge0$' ?

Answer 1

Lemma 1. Let $k$ be a field of characteristic $\neq 2$, 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. Observe that Lemma 1 (a) is equivalent to the fact that a symmetric bilinear form on a finite-dimensional vector space has an orthogonal basis (indeed, $A$ is the matrix representing the form, and $U$ is the change-of-basis matrix between the standard basis and the orthogonal basis). But this fact is proven, e.g., in Theorem 4.7 of Keith Conrad, Bilinear forms or in Proposition 18.1 in J. S. Milne's "Algebraic Groups, Lie Groups, and their Arithmetic Subgroups" Chapter I. Lemma 1 (b) is easy to derive from Lemma 1 (a).

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, $\operatorname{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=\operatorname{Tr}\left(AB^T\right)$. Since $B^T=B$, this becomes $v^T\left(A\otimes B\right)v=\operatorname{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, $\operatorname{Tr}\left(AB\right)\geq 0$, proving Corollary 2.