MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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|cite|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

share|cite|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|cite|improve this answer

Your Answer


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.