# dominant eigenvector

Hi, everyone! Is there any efficient way to simplify the following tensor product

$X \otimes X + X^T \otimes X^T$, where $X$ is a square $n \times n$ matrix.

My goal is to efficiently compute the dominant eigenvector of $X \otimes X + X^T \otimes X^T$. However, the direct way is computationally expensive. Is it possible to simplify it avoid tensor computation.

For example, to compute the dominant eigenvector of $X \otimes X$, i can compute the dominant eigenvector of $X$ first, denoted by $v$. Then i only need to compute $v \cdot v^T$, which is the dominant eigenvector of $X \otimes X$. However, when it comes to $X \otimes X + X^T \otimes X^T$, i have no idea. Could anyone give me some suggestion or reference? Thank you in advance!

• PS: My initial intuition is to avoid using tensor product when computing $X \otimes X$. Hence, a naive idea is to rewrite the dominant eigenvector $X \otimes X +X^T \otimes X^T$ in term of the dominant eigenvector $X$ or that of $X+X^T$, $X \cdot X^T$ and so forth, but i'm not sure whether it is feasible. – person Feb 4 '11 at 9:17

What you can do computationally is switching to iterative algorithms (Arnoldi method; eigs in Matlab, scipy.sparse.linalg.eigs, or the library Arpack if you are stuck with Fortran/C++). In this way, the computational cost is $O(M\cdot steps)$, where $steps$ is the number of steps needed (usually moderate, if the dominant eigenvalue is well-separated and/or you only need a small number of significant digits), and $M$ is the cost of a matrix-vector multiplication with your matrix, which is easier in your case due to the simple tensor product structure. You will need to code a subroutine for the map $v\mapsto Mv$.
(This is generally a good idea anyway if $n$ is large and you only need a small part of the spectrum.)
• First idea that comes into my mind: if your vector was in the form $a\otimes b$, then it would be easy to code the map $v\mapsto Mv$ without computing explicitly the tensor product. Since it is not, you may cheat and decompose it into the sum of $n$ vector of this kind, just take $a=e_1,e_2,\dots,e_n$. This should cost $O(n^2\cdot n)$ ops, assuming no structure on $X$. If $X$ is sparse or Toeplitz, well, you should've mentioned that from the start. :) Maybe someone else will come up with a better strategy though. – Federico Poloni Feb 4 '11 at 22:59