{"id":2066,"date":"2025-02-25T03:18:39","date_gmt":"2025-02-25T03:18:39","guid":{"rendered":"https:\/\/www.ethanepperly.com\/?p=2066"},"modified":"2025-02-25T15:43:34","modified_gmt":"2025-02-25T15:43:34","slug":"the-schur-product-theorem","status":"publish","type":"post","link":"https:\/\/www.ethanepperly.com\/index.php\/2025\/02\/25\/the-schur-product-theorem\/","title":{"rendered":"The Schur Product Theorem"},"content":{"rendered":"\n

The Schur product theorem<\/a> states that the entrywise product<\/a> \"A\circ M\" of two positive semidefinite matrices<\/a> is also positive semidefinite. This post will present every proof I know for this theorem, and I intend to edit it to add additional proofs if I learn of them. (Please reach out if you know another!) My goal in this post is to be short and sweet, so I will assume familiarity with many properties for positive semidefinite matrices.<\/p>\n\n\n\n

For this post, a matrix \"A\in\real^{n\times n}\" is positive semidefinite (psd, for short) if it is symmetric<\/a> and satisfies \"x^\top Ax\ge 0\" for all vectors \"x\in\real^n\". All matrices in this post are real, though the proofs we\u2019ll consider also extend to complex matrices. The entrywise product will be denoted \"\circ\" and is defined as \"(A\circ M)_{ij} = A_{ij}M_{ij}\". The entrywise product is also known as the Hadamard product or Schur product.<\/p>\n\n\n\n

It is also true that the entrywise product of two positive definite<\/em> matrices is positive definite. The interested reader may be interested in seeing which of the proofs also yield this result.<\/p>\n\n\n\n

Proof 1: Trace formula<\/h1>\n\n\n\n

We start by computing \"x^\top (A\circ M)x\":

  <\/span>   <\/span>\"\[x^\top (A\circ M)x = \sum_{i,j=1}^n x_i (A\circ M)_{ij} x_j = \sum_{i,j=1}^n x_i A_{ij} M_{ij} x_j.\]\"<\/p>Now, we may rearrange the sum, use symmetry of \"M\", and repackage it as a trace<\/a>

  <\/span>   <\/span>\"\[x^\top (A\circ M)x = \sum_{i,j=1}^n x_i A_{ij} x_j M_{ji} = \tr(\operatorname{diag}(x) A \operatorname{diag}(x) M).\]\"<\/p>This the trace formula<\/a><\/em> for quadratic forms<\/a> in the Schur product.<\/p>\n\n\n\n

Recall that a matrix \"A\" is psd if and only if<\/a> it \"A\" is a Gram matrix<\/a><\/em> (able to be expressed as \"A = B^\top B\"). Thus, we may write \"A = B^\top B\" and \"M = C^\top C\". Substituting these expressions in the trace formula and invoking the cyclic property<\/a> of the trace, we get

  <\/span>   <\/span>\"\[x^\top (A\circ M)x = \tr(\operatorname{diag}(x) B^\top B \operatorname{diag}(x) C^\top C) = \tr(C\operatorname{diag}(x) B^\top B \operatorname{diag}(x) C^\top).\]\"<\/p>The matrix on the right-hand side has the expression

  <\/span>   <\/span>\"\[C\operatorname{diag}(x) B^\top B \operatorname{diag}(x) C^\top = G^\top G \quad \text{for } G = B \operatorname{diag}(x) C^\top.\]\"<\/p>Therefore, it is psd and so<\/a> its trace is psd:

  <\/span>   <\/span>\"\[x^\top (A\circ M)x = \tr(G^\top G) \ge 0.\]\"<\/p>We have shown \"x^\top (A\circ M)x\ge 0\" for every vector \"x\", so \"A\circ M\" is psd.<\/p>\n\n\n\n

Proof 2: Gram matrix<\/h2>\n\n\n\n

Since \"A\" and \"M\" are psd, they may be written as \"A = B^\top B\" and \"M = C^\top C\". Letting \"b_i^\top\" and \"c_i^\top\" denote the \"i\"th rows of \"B\" and \"C\", we have

  <\/span>   <\/span>\"\[A = \sum_i b_ib_i^\top \quad \text{and} \quad M = \sum_j c_jc_j^\top.\]\"<\/p>Computing the Schur product and distributing, we have

  <\/span>   <\/span>\"\[A\circ M = \sum_{i,j} (b_ib_i^\top \circ c_jc_j^\top).\]\"<\/p>The Schur product of rank-one matrices \"b_ib_i^\top\" and \"c_jc_j^\top\" is, by direct computation, \"(b_i\circ c_j)(b_i\circ c_j)^\top\". Thus,

  <\/span>   <\/span>\"\[A\circ M = \sum_{i,j} (b_i\circ c_j)(b_i\circ c_j)^\top\]\"<\/p>is a sum of (rank-one) psd matrices and is thus<\/a> psd.<\/p>\n\n\n\n

Proof 3: Covariances<\/h2>\n\n\n\n

Let \"x\" and \"y\" be independent<\/a> random vectors with zero mean<\/a> and covariance matrices<\/a> \"A\" and \"M\". The vector \"x\circ y\" is seen to have zero mean as well. Thus, the \"ij\" entry of the covariance matrix \"\Cov(x\circ y)\" of \"x\circ y\" is

  <\/span>   <\/span>\"\[\expect[x_iy_ix_jy_j] = \expect[x_ix_j] \expect[y_iy_j] = A_{ij} M_{ij} = (A\circ M)_{ij}.\]\"<\/p>The second equality is the independence of \"x\" and \"y\", and the third equality uses the fact that \"A\" and \"M\" are the covariance matrices of \"x\" and \"y\". Thus, the covariance matrix of \"x\circ y\" is \"A\circ M\". All covariance matrices are psd<\/a>, so \"A\circ M\" is psd as well.1<\/a><\/sup>One I first saw this proof, I found it almost magical. Upon closer inspection, however, proof 3 is seen to be essentially a variant of proof 2 where sums \"A=\sum_i b_ib_i^\top\" have replaced by expectations \"A = \expect [xx^\top]\".<\/span>\n\n\n\n

Proof 4: Kronecker product<\/h1>\n\n\n\n

The Kronecker product<\/a> \"A\otimes M\" of two psd matrices is<\/a> psd. The entrywise product \"A\circ M\" is a principal submatrix<\/a> of \"A\otimes M\":

  <\/span>   <\/span>\"\[A\circ M = ((A\otimes M)_{(i+n(i-1))(i+n(i-1))} : i = 1,\ldots,n).\]\"<\/p>All principal submatrices of a psd matrix are psd<\/a>, so \"A\circ M\" is psd.<\/p>\n","protected":false},"excerpt":{"rendered":"

The Schur product theorem states that the entrywise product of two positive semidefinite matrices is also positive semidefinite. This post will present every proof I know for this theorem, and I intend to edit it to add additional proofs if I learn of them. (Please reach out if you know another!) My goal in thisRead more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"class_list":["post-2066","post","type-post","status-publish","format-standard","hentry","category-expository"],"_links":{"self":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/2066","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/comments?post=2066"}],"version-history":[{"count":4,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/2066\/revisions"}],"predecessor-version":[{"id":2070,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/2066\/revisions\/2070"}],"wp:attachment":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/media?parent=2066"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/categories?post=2066"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/tags?post=2066"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}