Fast trace of inverse of a square matrix - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T18:35:24Z http://mathoverflow.net/feeds/question/46553 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/46553/fast-trace-of-inverse-of-a-square-matrix Fast trace of inverse of a square matrix César 2010-11-18T22:52:57Z 2010-11-19T12:35:07Z <p>Which would be the most efficient way (in computational time) to compute tr(inv(H)), where H is a (dense) square matrix?</p> <p>In my particular problem I also have a LU decomposition of H already available, which was used in a previous context to solve a system of linear equations. My current approach is to simply use the LU to compute the inverse and then calculate the trace. Is there any other more efficient way to achieve this, considering I already have this matrix factorized?</p> <p>I could have first computed the inverse and then made a multiplication by the inverse to solve my previous system of linear equations, but I was trying to avoid multiplication by the inverse to avoid numerical inaccuracies.</p> <p>Edit: Forgot to mention that under normal conditions H should be symmetric.</p> http://mathoverflow.net/questions/46553/fast-trace-of-inverse-of-a-square-matrix/46569#46569 Answer by Agol for Fast trace of inverse of a square matrix Agol 2010-11-19T02:04:22Z 2010-11-19T02:04:22Z <p>If you have an $n\times n$ matrix $A$ with eigenvalues $\lambda_1,\ldots, \lambda_n$, then the characteristic polynomial of $A$ is $det(\lambda I-A)=\prod_{i=1}^n (\lambda-\lambda_i) = \sum_{i=0}^n a_i \lambda^i$. Then $det(A^{-1})=- a_1/a_0$, since the coefficient $a_{n-i}$ is the sum of all products of $i$ eigenvalues, so $a_1/a_0 = \sum_{i=1}^n \lambda_i^{-1}= trace(A^{-1})$. I'm not sure if it helps to compute the characteristic polynomial if you have an LU decomposition though. </p> http://mathoverflow.net/questions/46553/fast-trace-of-inverse-of-a-square-matrix/46620#46620 Answer by J. M. for Fast trace of inverse of a square matrix J. M. 2010-11-19T12:35:07Z 2010-11-19T12:35:07Z <p>Given that the poster has specified that his matrix is symmetric, I offer a general solution and a special case:</p> <ol> <li><p>Eigendecomposition actually becomes more attractive here: the bulk of the work is in reducing the symmetric matrix to tridiagonal form, and finding the eigenvalues of a tridiagonal matrix is an O(n) process. Assuming that the symmetric matrix is nonsingular, summing the reciprocals of the eigenvalues nets you the trace of the inverse.</p></li> <li><p>If the matrix is positive definite as well, first perform a Cholesky decomposition. Then there are <a href="http://books.google.com/books?id=myzIPBwyBbcC&amp;pg=PA119" rel="nofollow">methods</a> for generating the diagonal elements of the inverse.</p></li> </ol>