most recent 30 from http://mathoverflow.net 2013-05-18T18:52:51Z http://mathoverflow.net/feeds/question/82291 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/82291/eigen-decomposition-of-a-special-companion-matrix ibbore 2011-11-30T17:14:11Z 2011-12-01T08:52:09Z

<p>I have a special type of companion matrix, where the "special" part is that each element in the matrix are matrices. For instance, the diagonal with "1":s is instead a diagonal with identity matrices, and so on... My question is if anyone knows of a solid algorithm for finding the eigen-decomposition of such a matrix? If you don't know the exact algorithm, perhaps you know of some work that has been done in the area?</p> <p>If anyone is interested, I can clarify what my eigendecomposition will be used; AND this poses another problem, which is really the core problem I am facing. </p> <p>I want to simulate a companion matrix (p x p), with each element being a matrix (n x n). The only restriction I have is that all eigenvalues must satisfy |λ|&lt;1 . Ultimately, I would like to simulate the eigenvalues from (−1,1) , and then produce a companion matrix from that. I realize there might be (most likely are) multiple solutions, but that does not matter. I would settle for any solution. :) </p> <p>My idea of solving this is to look at the general eigendecomposition of a companion matrix, simulate the eigenvalues, possible simulate the eigenvectors, and then reproduce the companion matrix. </p> <p>Am I making any sense with this? I hope you understand the issue I have, and if not, please feel free to ask. As I said above, this area is fairly new to me...</p>

http://mathoverflow.net/questions/82291/eigen-decomposition-of-a-special-companion-matrix/82304#82304 Federico Poloni 2011-11-30T19:05:57Z 2011-11-30T19:05:57Z

<p>You can get some savings with respect to the naive $O(n^3d^3)$ by using the semiseparable structure, but I don't think you can get anything faster than $O(n^3d^2)$ (stable) or $O(n^3d\log d)$ (maybe unstable). Algorithms for semiseparable matrices aren't exactly easy to start working with unless you work in numerical linear algebra, so unless $d$ is large, this isn't typically worth the trouble.</p> <p>Inside Matlab there are some computations that use this problem (see <code>polyeig</code>), but as far as I know they run unoptimized QR.</p> <p>Good Google search words for related literature are "companion linearizations of matrix polynomials". Though I'm afraid you won't find much in the direction you are interested in.</p>