2
$\begingroup$

Is there a nice trick for this? I would like to compute the eigenvalues more efficiently.

$\endgroup$

3 Answers 3

6
$\begingroup$

If you have a lot of duplicate rows (and you know what they are), you can reduce to a smaller matrix. I'll start with an example, because writing out the general case will be notationally annoying.

Let $$A = \begin{pmatrix} a & a & b & c \\ a & a & b & c \\ b & b & d & e \\ c & c & e & f \end{pmatrix}$$ Then $A$ has a zero eigenvalue, and the other eigenvalues are the same as those of $$A'=\begin{pmatrix} 2a & b \sqrt{2} & c \sqrt{2} \\ b \sqrt{2} & d & e \\ c \sqrt{2} & e & f \end{pmatrix}$$

Proof: Let $v_1$, $v_2$, $v_3$ be the orthonormal vectors $(1/\sqrt{2}, 1/\sqrt{2}, 0,0)$, $(0,0,1,0)$ and $(0,0,0,1)$. Complete to an orthonormal basis $(v_1, v_2, v_3, w)$. Then $A$ annihilates $w$, and takes $\mathrm{Span}(v_1, v_2, v_3)$ to itself by the matrix $A'$.

In general, if $I$ is a set of rows which are identical, then let $v_I$ be the vector which is $1/\sqrt{|I|}$ on the coordinates in $I$ and $0$ elsewhere. The $v_I$ are orthonormal, complete them to an orthonormal basis by adding vectors $w_j$. Then $A$ will annihilate the $w_j$ and will take $\mathrm{Span}(v_I)$ to itself. The matrix of endomorphism of $\mathrm{Span}(v_I)$ will have entries that look like $\sqrt{IJ} \cdot a_{ij}$, with $i \in I$ and $j \in J$. So you ar reduced to computing the eigenvalues of this smaller matrix.

$\endgroup$
1
$\begingroup$

If you have a lot of duplicate rows, and you know which ones they are, you get a lot of repetitions (which thus don't need to be computed) in product of matrix times vector in the Power Iteration method

http://en.wikipedia.org/wiki/Power_iteration

$\endgroup$
0
1
$\begingroup$

For the special case of your matrix with duplicate rows being positive semidefinite, one possible route would be to take the unique rows, construct a matrix whose columns correspond to those unique rows, and then perform singular value decomposition; the singular values you will obtain are the nonzero eigenvalues of your original matrix.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.