{"id":1812,"date":"2011-05-30T21:51:21","date_gmt":"2011-05-30T19:51:21","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=1812"},"modified":"2012-02-02T16:01:16","modified_gmt":"2012-02-02T15:01:16","slug":"some-nonlinear-formulas-in-linear-algebra","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2011\/05\/30\/some-nonlinear-formulas-in-linear-algebra\/","title":{"rendered":"Some nonlinear formulas in linear algebra"},"content":{"rendered":"<p style=\"text-align: center;\"><a href=\"http:\/\/en.wikipedia.org\/wiki\/The_Matrix\"><img loading=\"lazy\" class=\"aligncenter size-medium wp-image-1822\" title=\"Matrix\" src=\"\/blog\/wp-content\/uploads\/2011\/05\/matrix-300x230.jpg\" alt=\"Matrix\" width=\"300\" height=\"230\" srcset=\"https:\/\/djalil.chafai.net\/blog\/wp-content\/uploads\/2011\/05\/matrix-300x230.jpg 300w, https:\/\/djalil.chafai.net\/blog\/wp-content\/uploads\/2011\/05\/matrix.jpg 463w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/a><\/p>\n<p style=\"text-align: justify;\">Here are some of my favorite nonlinear formulas in linear algebra. Most of them play a crucial role in mathematics such as in numerical analysis, in statistics, and in random matrix theory. In what follows, the letters \\( {A,B,C,D,U,V,W,M} \\) denote matrices while the letters \\( {u,v} \\) denote column vectors (special matrices).<\/p>\n<ul>\n<li>The <a href= \"http:\/\/en.wikipedia.org\/wiki\/Invertible_matrix#Blockwise_inversion\"> blockwise inversion formula<\/a> states that as soon as both sides make sense\n<p style=\"text-align: center;\">\\[ \\begin{pmatrix} A & B \\\\ C & D \\end{pmatrix}^{-1} = \\begin{pmatrix} A^{-1}+A^{-1}B(D-CA^{-1}B)^{-1}CA^{-1} & -A^{-1}B(D-CA^{-1}B)^{-1} \\\\ -(D-CA^{-1}B)^{-1}CA^{-1} & (D-CA^{-1}B)^{-1} \\end{pmatrix} \\]<\/p>\n<p> The matrix \\( {D-CA^{-1}B} \\) is the <a href= \"http:\/\/en.wikipedia.org\/wiki\/Schur_complement\">Schur complement<\/a> of \\( {A} \\) in the \\( {(A,B,C,D)} \\) block-matrix above. In particular for every \\( {n\\times n} \\) matrix \\( {M} \\) and any non empty \\( {I\\subset\\{1,\\ldots,n\\}} \\) we have <\/p>\n<p style=\"text-align: center;\">\\[ (M^{-1})_{I,I} = (M_{I,I} - M_{I,I^c}(M_{I^c ,I^c})^{-1}M_{I^c,I})^{-1} . \\]<\/p>\n<p> The Schur complement is at the heart of the Gaussian linear model in statistics. We have already discussed the <a href= \"\/blog\/2010\/08\/31\/schur-complement-and-geometry-of-positive-definite-matrices\/\"> role of the Schur complement in the geometry of positive definite matrices<\/a>, and an application to the <a href= \"\/blog\/2010\/04\/30\/wasserstein-distance-between-two-gaussians\/\">computation of the Wasserstein distance between two Gaussians<\/a>.<\/li>\n<li>The <a href= \"http:\/\/en.wikipedia.org\/wiki\/Woodbury_matrix_identity\">Woodbury matrix identity<\/a> states that as soon as both sides make sense we have\n<p style=\"text-align: center;\">\\[ (A+UCV)^{-1}=A^{-1}-A^{-1}U(C^{-1}+VA^{-1}U)^{-1}VA^{-1} \\]<\/p>\n<p> This contains as a special case the <a href= \"http:\/\/en.wikipedia.org\/wiki\/Sherman-Morrison_formula\">Sherman-Morrison formula<\/a> <\/p>\n<p style=\"text-align: center;\">\\[ (A+uv^\\top)^{-1}=A^{-1}-\\frac{A^{-1}uv^\\top A^{-1}}{1+v^\\top A^{-1}u} \\]<\/p>\n<p> These formulas are at the heart of the Gaussian Kalman filter in engineering and the Cauchy-Stieltjes trace-resolvent method in random matrix theory<\/li>\n<li>The <a href= \"http:\/\/en.wikipedia.org\/wiki\/Binomial_inverse_theorem\">binomial inverse theorem<\/a> provides an alternative to the Woodbury formula\n<p style=\"text-align: center;\">\\[ (A+UCV)^{-1} =A^{-1} - A^{-1}UC(C+CVA^{-1}UC)^{-1}CVA^{-1} \\]<\/p>\n<\/li>\n<li>The <a href= \"http:\/\/en.wikipedia.org\/wiki\/Matrix_determinant_lemma\">matrix determinant lemma<\/a> states that as soon as both sides make sense we have the identity\n<p style=\"text-align: center;\">\\[ \\det(A+UWV^\\top)=\\det(W^{-1}+V^\\top A^{-1}U)\\det(W)\\det(A) \\]<\/p>\n<p> This contains as a special case the <a href= \"http:\/\/en.wikipedia.org\/wiki\/Sylvester's_determinant_theorem\">Sylvester determinant theorem<\/a> <\/p>\n<p style=\"text-align: center;\">\\[ \\det(I_n+AB)=\\det(I_m+BA) \\]<\/p>\n<p> where \\( {I_d} \\) is the \\( {d\\times d} \\) identity matrix, and also the formula <\/p>\n<p style=\"text-align: center;\">\\[ \\det(A+uv^\\top)=(1+v^\\top A^{-1}u)\\det(A). \\]<\/p>\n<\/li>\n<li>The resolvent formula states that for any square matrices \\( {A} \\) and \\( {B} \\) and any \\( {z\\not\\in\\mathrm{spec}(A)\\cup\\mathrm{spec}(B)} \\),\n<p style=\"text-align: center;\">\\[ (A-zI)^{-1}-(B-zI)^{-1} = (A-zI)^{-1}(B-A)(B-zI)^{-1}. \\]<\/p>\n<p> It follows immediatly from the identity \\( {(B-zI)-(A-zI)=B-A} \\).<\/li>\n<\/ul>\n<p style=\"text-align: justify;\">If you don't know these formulas, they know you (everywhere in numerical software packages).<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Here are some of my favorite nonlinear formulas in linear algebra. Most of them play a crucial role in mathematics such as in numerical analysis,&#8230;<\/p>\n<div class=\"more-link-wrapper\"><a class=\"more-link\" href=\"https:\/\/djalil.chafai.net\/blog\/2011\/05\/30\/some-nonlinear-formulas-in-linear-algebra\/\">Continue reading<span class=\"screen-reader-text\">Some nonlinear formulas in linear algebra<\/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":297},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/1812"}],"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=1812"}],"version-history":[{"count":14,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/1812\/revisions"}],"predecessor-version":[{"id":4148,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/1812\/revisions\/4148"}],"wp:attachment":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/media?parent=1812"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/categories?post=1812"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/tags?post=1812"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}