Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 6 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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