Product of Positive Matrices - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T14:06:17Z http://mathoverflow.net/feeds/question/19100 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/19100/product-of-positive-matrices Product of Positive Matrices Aaron 2010-03-23T09:01:31Z 2010-03-23T10:50:44Z <p>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$' ?</p> http://mathoverflow.net/questions/19100/product-of-positive-matrices/19102#19102 Answer by darij grinberg for Product of Positive Matrices darij grinberg 2010-03-23T10:26:25Z 2010-03-23T10:50:44Z <p><strong>Lemma 1.</strong> Let $k$ be a field, and $A\in k^{n\times n}$ be a symmetric matrix.</p> <p><strong>(a)</strong> 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$.</p> <p><strong>(b)</strong> Let the field $k$ be ordered. The matrix $A$ is nonnegative-definite if and only if all entries of the matrix $D$ are nonnegative.</p> <p>I'm writing a proof of this, mainly because too many sources do it wrong (for instance, by assuming $k$ to be ordered in <strong>(a)</strong>, 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.</p> <p>EDIT: I'm not writing a proof of this. Too tired from the rest. See Proposition 15.1 in <a href="http://jmilne.org/math/CourseNotes/ALA1.pdf" rel="nofollow">J. S. Milne's "Algebraic Groups, Lie Groups, and their Arithmetic Subgroups" Chapter I</a> for a proof of Lemma 1 <strong>(a)</strong>, and derive Lemma 1 <strong>(b)</strong> from it.</p> <p><strong>Corollary 2.</strong> 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$.</p> <p><em>Proof of Corollary 2.</em> 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.</p> <p>Lemma 1 <strong>(a)</strong> 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 <strong>(b)</strong> shows that all entries of the matrix $D$ are nonnegative. Similarly, Lemma 1 <strong>(a)</strong> (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 <strong>(b)</strong> 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).</p> <p>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.</p> <p>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.</p>