{"id":996,"date":"2014-09-24T07:49:59","date_gmt":"2014-09-24T12:49:59","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/?p=996"},"modified":"2014-09-16T13:56:22","modified_gmt":"2014-09-16T18:56:22","slug":"symbolic-math-solves-a-linear-algebra-conundrum","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2014\/09\/24\/symbolic-math-solves-a-linear-algebra-conundrum\/","title":{"rendered":"Symbolic Math Solves a Linear Algebra Conundrum"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p>I'd like to introduce this week's guest blogger <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/answers\/contributors\/1033975-alan-weiss\">Alan Weiss<\/a>. Alan writes documentation for mathematical toolboxes here at MathWorks.<\/p><p>An economist I know (well, he's my son) asked me a question the other day. I was able to answer him quickly by using Symbolic Math Toolbox&#8482; calculations. You might find the steps to be an interesting case of a somewhat nonstandard use of symbolic mathematics<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#bdcd9c0f-4d13-4df9-936a-6bdb0f55c8dd\">A Linear Algebra Question<\/a><\/li><li><a href=\"#76d83891-e240-4268-9608-cdd1b562bc71\">A Symbolic Approach<\/a><\/li><li><a href=\"#f77e9a1f-41be-4e11-80c1-cc5496cabea1\">Feedback<\/a><\/li><\/ul><\/div><h4>A Linear Algebra Question<a name=\"bdcd9c0f-4d13-4df9-936a-6bdb0f55c8dd\"><\/a><\/h4><p>My son was working through a paper that described a computational algorithm. He got stuck on one step of the algorithm:<\/p><p>If $A$ is a positive definite (symmetric) matrix, find a <b>lower triangular<\/b> matrix $G$ such that<\/p><p>$$GAG^{-1} = D, \\mbox{ where }D\\mbox{ is diagonal.}$$<\/p><p>He called me asking if there was some linear algebra that he just never learned. I knew how to find a matrix $G$ that would diagonalize $A$ using the <tt>eig<\/tt> function. But a lower triangular version? I didn't know how to do that. I told him I would call him back after some investigation.<\/p><h4>A Symbolic Approach<a name=\"76d83891-e240-4268-9608-cdd1b562bc71\"><\/a><\/h4><p>After spending a couple of minutes fruitlessly looking through a linear algebra book, I decided to see what Symbolic Math Toolbox had to say about the equations that any such matrix $G$ would have to satisfy. Here were my steps.<\/p><pre class=\"codeinput\">syms <span class=\"string\">a<\/span> <span class=\"string\">b<\/span> <span class=\"string\">c<\/span> <span class=\"string\">g1<\/span> <span class=\"string\">g2<\/span> <span class=\"string\">g3<\/span> <span class=\"string\">real<\/span> <span class=\"comment\">% Create symbolic variables<\/span>\r\nG = [g1,0;g2,g3] <span class=\"comment\">% Lower triangular matrix<\/span>\r\nH = inv(G) <span class=\"comment\">% Its inverse<\/span>\r\nA = [a,b;b,c] <span class=\"comment\">% Symmetric matrix A<\/span>\r\nD = G*A*H <span class=\"comment\">% D is supposed to be diagonal<\/span>\r\n<\/pre><pre class=\"codeoutput\">G =\r\n[ g1,  0]\r\n[ g2, g3]\r\nH =\r\n[        1\/g1,    0]\r\n[ -g2\/(g1*g3), 1\/g3]\r\nA =\r\n[ a, b]\r\n[ b, c]\r\nD =\r\n[                                 a - (b*g2)\/g3,        (b*g1)\/g3]\r\n[ (a*g2 + b*g3)\/g1 - (g2*(b*g2 + c*g3))\/(g1*g3), (b*g2 + c*g3)\/g3]\r\n<\/pre><p>Look at the upper right entry in D. If D is diagonal, then b*g1 = 0. This means b = 0 or g1 = 0. But if b = 0 then A is already diagonal. And if g1 = 0 then the first row of G is zero, so G is not invertible.<\/p><p>In other words, I had just proved that there is no such thing as a lower triangular matrix that diagonalizes a symmetric matrix in this way.<\/p><p>I called my son back and explained the calculation. We decided that the paper he was reading had a misstatement, and he went ahead and used <tt>eig<\/tt> to diagonalize the matrix in his application. He will get in touch with the author of the paper to explain the misstatement in the algorithm.<\/p><p>I was quite happy with this result. Symbolic math calculations had saved us both a lot of time searching for an algorithm that doesn't exist.<\/p><h4>Feedback<a name=\"f77e9a1f-41be-4e11-80c1-cc5496cabea1\"><\/a><\/h4><p>Do you use symbolic math calculations in cute or innovative ways? Tell us about it <a href=\"https:\/\/blogs.mathworks.com\/loren\/?p=996#respond\">here<\/a>.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_0713346d2e924dd2a6c337eb37390fa5() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='0713346d2e924dd2a6c337eb37390fa5 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 0713346d2e924dd2a6c337eb37390fa5';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2014 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_0713346d2e924dd2a6c337eb37390fa5()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2014a<br><\/p><\/div><!--\r\n0713346d2e924dd2a6c337eb37390fa5 ##### SOURCE BEGIN #####\r\n%% Symbolic Math Solves a Linear Algebra Conundrum\r\n% I'd like to introduce this week's guest blogger\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/answers\/contributors\/1033975-alan-weiss Alan Weiss>.\r\n% Alan writes documentation for mathematical toolboxes here at MathWorks. \r\n%\r\n% An economist I know (well, he's my son) asked me a question the other\r\n% day. I was able to answer him quickly by using Symbolic Math Toolbox(TM)\r\n% calculations. You might find the steps to be an interesting case of a\r\n% somewhat nonstandard use of symbolic mathematics\r\n%% A Linear Algebra Question\r\n% My son was working through a paper that described a computational\r\n% algorithm. He got stuck on one step of the algorithm:\r\n%\r\n% If $A$ is a positive definite (symmetric) matrix, find a *lower triangular*\r\n% matrix $G$ such that\r\n%\r\n% $$GAG^{-1} = D, \\mbox{ where }D\\mbox{ is diagonal.}$$\r\n%\r\n% He called me asking if there was some linear algebra that he just never\r\n% learned. I knew how to find a matrix $G$ that would diagonalize $A$ using\r\n% the |eig| function. But a lower triangular version? I didn't know how to\r\n% do that. I told him I would call him back after some investigation.\r\n%% A Symbolic Approach\r\n% After spending a couple of minutes fruitlessly looking through a linear\r\n% algebra book, I decided to see what Symbolic Math Toolbox had to say\r\n% about the equations that any such matrix $G$ would have to satisfy. Here\r\n% were my steps.\r\nsyms a b c g1 g2 g3 real % Create symbolic variables\r\nG = [g1,0;g2,g3] % Lower triangular matrix\r\nH = inv(G) % Its inverse\r\nA = [a,b;b,c] % Symmetric matrix A\r\nD = G*A*H % D is supposed to be diagonal\r\n%%\r\n% Look at the upper right entry in D. If D is diagonal, then b*g1 = 0. This\r\n% means b = 0 or g1 = 0. But if b = 0 then A is already diagonal. And if g1\r\n% = 0 then the first row of G is zero, so G is not invertible.\r\n%\r\n% In other words, I had just proved that there is no such thing as a lower\r\n% triangular matrix that diagonalizes a symmetric matrix in this way.\r\n%\r\n% I called my son back and explained the calculation. We decided that the\r\n% paper he was reading had a misstatement, and he went ahead and used |eig|\r\n% to diagonalize the matrix in his application. He will get in touch with\r\n% the author of the paper to explain the misstatement in the algorithm.\r\n%\r\n% I was quite happy with this result. Symbolic math calculations had saved\r\n% us both a lot of time searching for an algorithm that doesn't exist.\r\n%% Feedback\r\n% Do you use symbolic math calculations in cute or innovative ways? Tell\r\n% us about it <https:\/\/blogs.mathworks.com\/loren\/?p=996#respond here>.\r\n\r\n##### SOURCE END ##### 0713346d2e924dd2a6c337eb37390fa5\r\n-->","protected":false},"excerpt":{"rendered":"<!--introduction--><p>I'd like to introduce this week's guest blogger <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/answers\/contributors\/1033975-alan-weiss\">Alan Weiss<\/a>. Alan writes documentation for mathematical toolboxes here at MathWorks.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/loren\/2014\/09\/24\/symbolic-math-solves-a-linear-algebra-conundrum\/\">read more >><\/a><\/p>","protected":false},"author":39,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[38],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/996"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/users\/39"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/comments?post=996"}],"version-history":[{"count":6,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/996\/revisions"}],"predecessor-version":[{"id":1008,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/996\/revisions\/1008"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=996"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=996"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=996"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}