{"id":281,"date":"2010-08-31T17:06:06","date_gmt":"2010-08-31T15:06:06","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=281"},"modified":"2011-10-23T18:06:05","modified_gmt":"2011-10-23T16:06:05","slug":"schur-complement-and-geometry-of-positive-definite-matrices","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2010\/08\/31\/schur-complement-and-geometry-of-positive-definite-matrices\/","title":{"rendered":"Schur complement and geometry of positive definite matrices"},"content":{"rendered":"<p style=\"text-align: justify;\">This post concerns the geometry of the convex cone of positive definite symmetric matrices. Let us denote by \\( {\\mathcal{S}_n} \\) the set of \\( {n\\times n} \\) real symmetric matrices, and by \\( {\\mathcal{S}_n^+} \\) the subset of positive definite matrices. Let us fix some \\( {K\\in\\mathcal{S}_n} \\) and write<\/p>\n<p style=\"text-align: center;\">\\[ K:= \\begin{pmatrix} A & W \\\\ W^\\top & S \\end{pmatrix} \\]<\/p>\n<p style=\"text-align: justify;\">with \\( {A\\in\\mathcal{S}_{n-m}} \\) and \\( {S\\in\\mathcal{S}_{m}} \\) for some fixed \\( {1\\leq m&lt;n} \\). If \\( {A\\in\\mathcal{S}_{n-m}^+} \\) then the <b>Schur complement<\/b> of \\( {A} \\) with respect to \\( {K} \\) is the matrix<\/p>\n<p style=\"text-align: center;\">\\[ T:=S-W^\\top A^{-1}W\\in\\mathcal{S}_m. \\]<\/p>\n<p style=\"text-align: justify;\">It is well known that<\/p>\n<p style=\"text-align: center;\">\\[ K\\in\\mathcal{S}_n^+ \\quad\\text{iff}\\quad A\\in\\mathcal{S}_{n-m}^+ \\quad\\text{and}\\quad T\\in\\mathcal{S}_m^+, \\]<\/p>\n<p style=\"text-align: justify;\">and moreover, \\( {K^{-1}} \\) admits the block decomposition<\/p>\n<p style=\"text-align: center;\">\\[ K^{-1} = \\begin{pmatrix} I_n & -A^{-1}W \\\\ 0 & I_m \\\\ \\end{pmatrix} \\begin{pmatrix} A^{-1} & 0 \\\\ 0 & T^{-1} \\\\ \\end{pmatrix} \\begin{pmatrix} I_n & 0 \\\\ -W^\\top A^{-1} & I_m \\\\ \\end{pmatrix}, \\]<\/p>\n<p style=\"text-align: justify;\">see for instance Theorem 7.7.6 page 472 in <a href= \"http:\/\/www.ams.org\/mathscinet-getitem?mr=1084815\">Horn and Johnson, Matrix analysis, Cambridge University Press, 1990<\/a>. In terms of Gaussian random vectors, if \\( {X=(Y,Z)} \\) is a Gaussian random vector of \\( {\\mathbb{R}^n=\\mathbb{R}^{n-m}\\times\\mathbb{R}^m} \\) with \\( {1\\leq m&lt;n} \\), with covariance matrix \\( {K} \\), then<\/p>\n<p style=\"text-align: center;\">\\[ Y\\sim\\mathcal{N}(0,A) \\quad\\text{and}\\quad Z\\sim\\mathcal{N}(0,S) \\quad\\text{and}\\quad \\mathcal{L}(Z\\,\\vert\\,Y)=\\mathcal{N}(W^\\top A^{-1}Y,T). \\]<\/p>\n<p style=\"text-align: justify;\">More generally, for a non empty \\( {I\\subset\\{1,\\ldots,n\\}} \\), we have, with \\( {J:=I^c} \\),<\/p>\n<p style=\"text-align: center;\">\\[ X_I\\sim\\mathcal{N}(0,K_{I,I}) \\quad\\text{and}\\quad X_{J}\\sim\\mathcal{N}(0,K_{J,J}) \\]<\/p>\n<p style=\"text-align: justify;\">and the Schur complement of \\( {K_{J,J}} \\) in \\( {K} \\) is \\( {K_{I,I}-K_{I,J}(K_{J,J})^{-1}K_{J,I}} \\) and<\/p>\n<p style=\"text-align: center;\">\\[ \\mathcal{L}(X_I\\,\\vert\\,X_{J}) \\sim\\mathcal{N}(K_{I,J}(K_{J,J})^{-1}X_{J},\\,K_{I,I}-K_{I,J}(K_{J,J})^{-1}K_{J,I}). \\]<\/p>\n<p style=\"text-align: justify;\">Moreover, from the block inverse formula we get<\/p>\n<p style=\"text-align: center;\">\\[ (K^{-1})_{I,I} = (K_{I,I}-K_{I,J}(K_{J,J})^{-1}K_{J,I})^{-1}. \\]<\/p>\n<p style=\"text-align: justify;\">The components of \\( {X_I} \\) are <b>conditionally independent<\/b> given the remaining components iff \\( {((K^{-1})_{I,I})^{-1}} \\) is diagonal, i.e. iff \\( {(K^{-1})_{I,I}} \\) is diagonal. In particular, if \\( {I=\\{i,j\\}} \\) with \\( {i\\neq j} \\) then \\( {X_i} \\) and \\( {X_j} \\) are conditionally independent given the remaining components iif \\( {(K^{-1})_{i,j}=0} \\).<\/p>\n<p style=\"text-align: justify;\">The extremal elements of the closed convex cone \\( {\\overline{\\mathcal{S}_n^+}} \\) are the unit rank matrices \\( {\\{uu^\\top: u\\in\\mathbb{R}^n\\}} \\). Every \\( {A\\in\\overline{\\mathcal{S}_n^+}} \\) can be written as \\( {A=\\lambda_1 u_1u_1^\\top+\\cdots+\\lambda_n u_nu_n^\\top} \\) where \\( {\\lambda_1,\\ldots,\\lambda_n} \\) and \\( {u_1,\\ldots,u_n} \\) denote the spectrum and the eigenvectors of \\( {A} \\) respectively. This is the Carath&eacute;odory local parametrization of the convex cone \\( {\\overline{\\mathcal{S}_n^+}} \\) with \\( {n} \\) Carath&eacute;odory conic rays \\( {\\lambda_1 u_1u_1^\\top,\\ldots,\\lambda_r u_nu_n^\\top} \\).<\/p>\n<p style=\"text-align: justify;\">For any \\( {K\\in\\mathcal{S}_n} \\), any \\( {1\\leq i\\leq j\\leq n} \\), and any \\( {x\\in\\mathbb{R}} \\), let \\( {\\xi_{i,j}(K,x)} \\) be the element of \\( {\\mathcal{S}_n} \\) obtained from \\( {K} \\) by replacing \\( {K_{i,j}} \\) and \\( {K_{j,i}} \\) by \\( {x} \\). In particular,<\/p>\n<p style=\"text-align: center;\">\\[ K=\\xi_{i,j}(K,K_{i,j}). \\]<\/p>\n<p style=\"text-align: justify;\">Now for which values of \\( {x} \\) the matrix \\( {\\xi_{i,j}(K,x)} \\) belongs to \\( {\\mathcal{S}_n^+} \\)? The answers is as follows.<\/p>\n<blockquote style=\"background: white; border: solid thick #e4e5e7; text-align: justify; padding-left: 1em;\"><p><b>Theorem 1<\/b> <em><a id=\"thcov-ext\" id= \"thcov-ext\"><\/a> Set \\( {K\\in\\mathcal{S}_n^+} \\), \\( {n\\geq2} \\), \\( {1\\leq i\\leq j\\leq n} \\), and \\( {x\\in\\mathbb{R}} \\).<\/em> <\/p>\n<ol>\n<li><em><b>Off-diagonal.<\/b> If \\( {i&lt;j} \\) then<\/em>\n<p style=\"text-align: center;\"><em>\\[ \\xi_{i,j}(K,x)\\in\\mathcal{S}_n^+ \\quad\\text{iff}\\quad \\delta_{i,j}^-(K)&lt;x&lt;\\delta_{i,j}^+(K) \\]<\/em><\/p>\n<p> <em>where \\( {\\delta_{1,2}^{\\pm}(K):=\\pm\\sqrt{K_{1,1}K_{2,2}}} \\) if \\( {n=2} \\), while if \\( {n&gt;2} \\),<\/em> <\/p>\n<p style=\"text-align: center;\"><em>\\[ \\delta_{i,j}^\\pm(K):= \\frac{-u^\\top v\\pm\\left((u^\\top v)^2- (A^{-1})_{i,i}(v^\\top Bv-K_{j,j})\\right)^{1\/2}} {(A^{-1})_{i,i}}. \\]<\/em><\/p>\n<p> <em>with<\/em> <\/p>\n<p style=\"text-align: center;\"><em>\\[ A:=K_{-j,-j},\\quad B:=(A^{-1})_{-i,-i},\\quad u:=A_{-i,i},\\quad v:=K_{-\\{i,j\\},j}. \\]<\/em><\/p>\n<\/li>\n<li><em><b>Diagonal.<\/b><\/em>\n<p style=\"text-align: center;\"><em>\\[ \\xi_{i,i}(K,x)\\in\\mathcal{S}_n^+ \\quad\\text{iff}\\quad x &gt; \\delta_{i,i}(K), \\]<\/em><\/p>\n<p> <em>where<\/em> <\/p>\n<p style=\"text-align: center;\"><em>\\[ \\delta_{i,i}(K):=w^\\top W^{-1}w \\]<\/em><\/p>\n<p> <em>with<\/em> <\/p>\n<p style=\"text-align: center;\"><em>\\[ W:=K_{-i,-i}\\quad w:=K_{-i,i}. \\]<\/em><\/p>\n<\/li>\n<\/ol>\n<p> <em>In particular, \\( {\\delta_{i,i}(K)&lt;K_{i,i}} \\) for any \\( {1\\leq i\\leq n} \\) and \\( {\\delta_{i,j}^-(K)&lt; K_{i,j}&lt;\\delta_{i,j}^+(K)} \\) for any \\( {1\\leq i&lt;j\\leq n} \\). Moreover, \\( {\\xi_{i,j}(K,0)\\in\\mathcal{S}_n^+} \\) iff \\( {v^\\top Bv\\leq K_{j,j}} \\).<\/em><\/p><\/blockquote>\n<p style=\"text-align: justify;\"><em>Proof:<\/em> We prove the first part for \\( {n&gt;2} \\) and leave the remaining statements to the reader. The matrix \\( {A} \\) is non singular since \\( {K} \\) is non singular. Moreover, \\( {K\\in\\mathcal{S}_n^+} \\) implies \\( {A^{-1}\\in\\mathcal{S}_n^+} \\), and in particular \\( {(A^{-1})_{i,i}&gt;0} \\). The set<\/p>\n<p style=\"text-align: center;\">\\[ \\{x\\in\\mathbb{R}:\\xi_{i,j}(K,x)\\in\\mathcal{S}_n^+\\} \\]<\/p>\n<p style=\"text-align: justify;\">is non empty and convex (an interval), as the intersection of an affine subspace with a convex cone, both containing \\( {K=\\xi_{i,j}(K,K_{i,j})} \\). For any \\( {x\\in\\mathbb{R}} \\),<\/p>\n<p style=\"text-align: center;\">\\[ (\\xi_{i,j}(K,x))_{-j,-j}=K_{-j,-j}=A. \\]<\/p>\n<p style=\"text-align: justify;\">By considering the Schur complement, the matrix \\( {\\xi_{i,j}(K,x)} \\) belongs to \\( {\\mathcal{S}_n^+} \\) iff<\/p>\n<p style=\"text-align: center;\">\\[ \\sum_{1\\leq k,k'\\leq n} z_k (A^{-1})_{k,k'} z_{k'} &lt;K_{j,j}, \\]<\/p>\n<p style=\"text-align: justify;\">where \\( {z:=(\\xi_{i,j}(K,x))_{-j,j}} \\). By rewriting \\( {z} \\) in terms of \\( {K} \\), we get the equation<\/p>\n<p style=\"text-align: center;\">\\[ (A^{-1})_{i,i}\\,x^2+(2u^\\top v)\\,x+v^\\top Bv-K_{j,j}&lt;0. \\]<\/p>\n<p style=\"text-align: justify;\">Recall that \\( {(A^{-1})_{i,i}&gt;0} \\). Next, since \\( {K=\\xi_{i,j}(K,K_{i,j})} \\) belongs to \\( {\\mathcal{S}_n^+} \\), the equation admits \\( {x=K_{i,j}} \\) as a solution, and thus the discriminant<\/p>\n<p style=\"text-align: center;\">\\[ (u^\\top v)^2- (A^{-1})_{i,i}(v^\\top Bv-K_{j,j}) \\]<\/p>\n<p style=\"text-align: justify;\">is positive. This leads to the non empty interval \\( {(\\delta_{i,j}^-(K),\\delta_{i,j}^+(K))} \\). &#9744;<\/p>\n<p style=\"text-align: justify;\">Let \\( {K\\in\\mathcal{S}_n^+} \\) with \\( {n&gt;2} \\), and consider the notations of theorem <a href=\"#thcov-ext\">1<\/a>. For any \\( {1\\leq i&lt;j\\leq n} \\), we define the matrices \\( {\\xi_{i,j}^-(K)} \\) and \\( {\\xi_{i,j}^+(K)} \\) by<\/p>\n<p style=\"text-align: center;\">\\[ \\xi_{i,j}^\\pm(K):=\\xi_{i,j}(K,\\delta_{i,j}^\\pm(K)). \\]<\/p>\n<p style=\"text-align: justify;\">Similarly, for any \\( {1\\leq i\\leq n} \\), we define<\/p>\n<p style=\"text-align: center;\">\\[ \\xi_{i,i}(K):=\\xi_{i,i}(K,\\delta_{i,i}(K)). \\]<\/p>\n<p style=\"text-align: justify;\">The elements of<\/p>\n<p style=\"text-align: center;\">\\[ \\mathcal{E}(K):= \\{\\xi_{i,j}^\\pm(K);1\\leq i&lt; j\\leq n\\} \\cup\\{\\xi_{i,i}(K);1\\leq i\\leq n\\} \\]<\/p>\n<p style=\"text-align: justify;\">are not of full rank and belong to the boundary of \\( {\\mathcal{S}_n^+} \\). If \\( {E_1,\\ldots,E_r\\in\\mathcal{E}(K)} \\), and \\( {\\lambda_1&gt;0,\\ldots,\\lambda_r&gt;0} \\), then \\( {\\lambda_1 E_1+\\cdots+\\lambda_r E_r\\in\\mathcal{S}_n^+} \\). These sums construct from \\( {K} \\) an open convex cone, included in \\( {\\mathcal{S}_n^+} \\), and containing \\( {K} \\).<\/p>\n","protected":false},"excerpt":{"rendered":"<p>This post concerns the geometry of the convex cone of positive definite symmetric matrices. Let us denote by \\( {\\mathcal{S}_n} \\) the set of \\(&#8230;<\/p>\n<div class=\"more-link-wrapper\"><a class=\"more-link\" href=\"https:\/\/djalil.chafai.net\/blog\/2010\/08\/31\/schur-complement-and-geometry-of-positive-definite-matrices\/\">Continue reading<span class=\"screen-reader-text\">Schur complement and geometry of positive definite matrices<\/span><\/a><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"iawp_total_views":380},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/281"}],"collection":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/comments?post=281"}],"version-history":[{"count":11,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/281\/revisions"}],"predecessor-version":[{"id":290,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/281\/revisions\/290"}],"wp:attachment":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/media?parent=281"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/categories?post=281"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/tags?post=281"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}