Question

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

Answer 1

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.

Answer 2

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

Answer 3

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.