Data Science Notes: 6. Finding eigenvectors by hand

On By dchoyleIn Algorithms, Data Science, Linear Algebra, Machine Learning, Mathematical Analysis, Mathematics

In another post I had to find the eigenvalues and eigenvectors of the following matrix,

\underline{\underline{M}}\;=\; a\underline{\underline{I}}_{N} + b\underline{1}_{N}\underline{1}_{N}^{\top}    Eq.1

where \underline{1}_{N} is an N-dimensional vector with elements all 1, whilst \underline{\underline{I}}_{N} is the N\times N identity matrix.

In that original post I said that diagonalizing this matrix (finding its eigenvalues and eigenvectors) was easy. A colleague asked me why I thought it was easy. My answer, “well because it is the only matrix form whose eigen-decomposition I explicitly remember”. And there’s a reason why I remember how to decompose by hand these types of matrices,

  1. It is easy to do.
  2. These types of matrices are very common.

Okay, I know that reason 1 is a circular argument, but it’s true. These types of matrices are easy to diagonalize and you’ll agree when you learn the trick to calculate their eigenvalues and eigenvectors. And like all the posts in my Data Science Notes series, I’m basing this post on experience. It is nearly 29 years since I first learnt this trick, and I have used it many time since. The reason I find it so useful is because of reason 2 above.

Reason 2 is equally important. As a Data Scientist you will encounter this form of matrix often, and so there is an advantage to knowing how to calculate the eigenvectors and eigenvalues of a matrix such as \underline{\underline{M}} in Eq.1, and you learn a lot about eigenvectors and eigenvalues in doing so; you learn what they are, what they represent, how to manipulate them, and how to use them to do useful things. We can view the matrix \underline{\underline{M}} in Eq.1 as a low-rank perturbation of the identity matrix, and manipulating matrices by adding a low-rank perturbation is a common trick in the mathematical and statistical sciences, most recently used in LoRA (low-rank adaptation) algorithms for fine-tuning Large Language Models (LLMs). So getting comfortable with the mathematics of eigen-decompositions of low-rank perturbations will pay off.

Let’s begin. To start we’ll need to do a quick recap of what an eigenvector is and what an eigenvalue is.

Recap of what eigenvectors and eigenvalues are

An eigenvector \underline{v} of a square matrix \underline{\underline{M}} is a vector that satisfies the following equation,

\underline{\underline{M}}\, \underline{v}\;=\; \lambda \underline{v}     Eq.2

The scalar quantity \lambda is the eigenvalue corresponding to the eigenvector \underline{v}. Given a vector \underline{v} that satisfies Eq.2, then the vector a\underline{v} also satisfies Eq.2 for any choice of the scalar a. This means we have the freedom to set the norm of the vector \underline{v} since we can effectively absorb the effect of any choice of norm into the effective value of a. So without loss of generality we can set \underline{v}^{\top}\underline{v}\;=\;1.

An N \times N matrix will have N different eigenvectors, some of which may have the same eigenvalue. So overall we have a set \{\underline{v}_{k}\}_{k=1}^{N} of eigenvectors with corresponding eigenvalues \{\lambda_{k}\}_{k=1}^{N}. Eigenvectors corresponding to eigenvalues that have different values are orthogonal to each other. Eigenvectors corresponding to the same eigenvalue need not be orthogonal to each other, but we can always construct an orthonormal set that spans the same subspace, so without loss of generality we can take the set of eigenvectors \{\underline{v}_{k}\}_{k=1}^{N} to form an orthonormal set.

The eigen-decomposition of a matrix

We can see from Eq.2 that the effect of the matrix \underline{\underline{M}} on an eigenvector \underline{v} is simply to multiply it by a scale factor \lambda. Consequently, the eigenvectors of a matrix are very special. In fact they allow us to characterize or represent the matrix \underline{\underline{M}} in the following way,

\underline{\underline{M}}\;=\; \sum_{k=1}^{N}\lambda_{k} \underline{v}_{k}\,\underline{v}_{k}^{\top}   Eq.3

And once we have all the eigenvectors \{\underline{v}\}_{k=1}^{N} and corresponding eigenvalues \{\lambda_{k}\}_{k=1}^{N} of a matrix \underline{\underline{M}} we can do useful things such as calculate its inverse or calculate its determinant, which occur in multiple places in multi-variate statistics, machine learning, and GenAI. I also needed them for the calculations in my original blog-post . The inverse and determinant of \underline{\underline{M}} are given by the usual formulae,

\underline{\underline{M}}^{-1}\;=\;\sum_{k=1}^{N}\lambda_{k}^{-1}\underline{v}_{k}\,\underline{v}_{k}^{\top}   Eq.4

\det \underline{\underline{M}}\;=\;\prod_{k=1}^{N}\lambda_{k}    Eq.5

Identifying our eigenvectors

Now, our goal is the work out the eigenvalues and eigenvectors of the matrix,

\underline{\underline{M}} \;=\; a_{0}\underline{\underline{I}}_{N} + \sum_{k=1}^{K} a_{k}\underline{u}_{k}\underline{u}_{k}^{\top}     Eq.6

In Eq.6 I have generalized from the matrix form in Eq.1 a little here, so we have 1 \leq K \ll N vectors \underline{u}_{k}, k=1,\ldots,K, which form an orthonormal set, i.e. they are all of unit length and orthogonal to each other.

Let’s write the right-hand-side of Eq. 6 as a sum of two matrices, i.e. we write, \underline{\underline{M}} in Eq.6 as,

\underline{\underline{M}} = a_{0}\underline{\underline{I}}_{N} \;+\; \underline{\underline{A}}    Eq. 7,

with the matrix \underline{\underline{A}} defined as,

\underline{\underline{A}}\;=\; \sum_{k=1}^{K} a_{k}\underline{u}_{k}\underline{u}_{k}^{\top}    Eq.8

This leads us to our first trick. If we have a vector \underline{v} which is an eigenvector of \underline{\underline{A}} with eigenvalue \lambda, then we can easily work out the effect of \underline{\underline{M}} on \underline{v} because the identity matrix \underline{\underline{I}} leaves \underline{v} unchanged. So overall we have,

\underline{\underline{M}}\, \underline{v}\;=\; \left ( a_{0}\underline{\underline{I}} + \underline{\underline{A}} \right )\, \underline{v}\;=\; a_{0}\underline{\underline{I}}\, \underline{v} \;+\; \underline{\underline{A}}\, \underline{v}\;=\; \left ( a_{0} + \lambda \right ) \underline{v}     Eq. 9

Eq.9 tells us that eigenvectors of \underline{\underline{A}} are eigenvectors of \underline{\underline{M}}. We only need to find eigenvectors and eigenvalues of \underline{\underline{A}}.

Now we introduce our second trick. We look at the definition of \underline{\underline{A}} in Eq. 8 and compare it to the eigen-decomposition in Eq.3. They are of the same form. Matrix \underline{\underline{A}} is already in the form an eigen-decomposition. The vectors \underline{u}_{k} are the eigenvectors \underline{\underline{A}}. And the corresponding eigenvalues are a_{k}.

Ok, but we only have K vectors \underline{u}_{k} and we need N eigenvectors. Easy, consider any vector, \underline{v} that is orthogonal to all the vectors \{\underline{u}_{k}\}_{k=1}^{K}. The effect of \underline{\underline{A}} on that vector \underline{v} is as follows,

\underline{\underline{A}}\, \underline{v} \;=\; \underline{0}    Eq.10

So any vector orthogonal to all the vectors \{\underline{u}_{k}\}_{k=1}^{K} will be an eigenvector of \underline{\underline{A}} with an eigenvalue of zero.

Now we can combine our first and second tricks together the finally work out the eigenvectors and eigenvalues of \underline{\underline{M}}. These are,

Eigenvalue = a_{0} + a_{1} , Eigenvector = \underline{u}_{1}
Eigenvalue = a_{0} + a_{2}, Eigenvector = \underline{u}_{2}
……
Eigenvalue = a_{0} + a_{K}, Eigenvector = \underline{u}_{K}
Eigenvalue = a_{0} , Eigenvectors = Any orthonormal set that spans the subspace orthogonal to the vectors \{\underline{u}_{k}\}_{k=1}^{K}.

Putting it all together

Let’s put this into action. Let’s go back to our original matrix in Eq.1 at the start of this post. That matrix was of the form,

\underline{\underline{M}}\;=\; a\underline{\underline{I}}_{N} + b\underline{1}_{N}\underline{1}_{N}^{\top}    Eq.11

So comparing Eq.11 to Eq.6 we have a_{0} = a, K=1, \underline{u}_{1} = \frac{1}{\sqrt{N}}\underline{1}_{N}, and a_{1} = Nb. So our eigenvectors and corresponding eigenvalues are,

Eigenvalue 1 = a + Nb , Eigenvector 1 = \frac{1}{\sqrt{N}}\underline{1}_{N}
Eigenvalues 2 to N = a , Eigenvectors 2 to N = an orthonormal set orthogonal to \underline{1}_{N} .

We can now easily calculate the determinant of our matrix in Eq.1 and we get,

\det \underline{\underline{M}}\;=\;(a+Nb)a^{N-1}     Eq.12

We can also easily calculate the inverse of the matrix in Eq.1. In this case we get,

\underline{\underline{M}}^{-1}\;=\;\sum_{k=2}^{N}\frac{1}{a}\underline{v}_{k}\underline{v}_{k}^{\top}\;+\; \frac{1}{(a+Nb)N}\underline{1}_{N}\underline{1}_{N}^{\top}     Eq.13

In Eq.13 the vectors \underline{v}_{k}\; ,\;k=2,\ldots, N form an orthonormal set orthogonal to \underline{1}_{N}.

Now, we can use one final little trick to simplify the right-hand-side of Eq.13. If we recall that the effect of the identity matrix \underline{\underline{I}}_{N} on any vector v_{k} from an orthonormal set \{\underline{v}_{k}\}_{k}^{N} is to leave those vectors unchanged, then this means we can write the identity matrix \underline{\underline{I}}_{N} in terms of an eigen-decomposition, and that decomposition is as follows,

\underline{\underline{I}}_{N}\;=\; \sum_{k=1}^{N}\underline{v}_{k}\underline{v}_{k}^{\top}     Eq.14

Now Eq.14 is almost what we have in the first term on the right-hand-side of Eq.13. Our sum in Eq.13 runs from k=2 to k=N, whilst the sum in Eq.14 runs from k=1 to k=N. If only we had another vector \underline{v}_{1} that was orthogonal to \underline{v}_{2}, \underline{v}_{3} etc.? But we do! We have \frac{1}{\sqrt{N}}\underline{1}_{N}. In fact, that is how we defined \underline{v}_{2}, \underline{v}_{3} etc. – they are all orthogonal to \frac{1}{\sqrt{N}}\underline{1}_{N}. This means if we set \underline{v}_{1} = \frac{1}{\sqrt{N}}\underline{1}_{N}, we can re-write the sum in the right-hand-side of Eq.13 as,

\sum_{k=2}^{N}\frac{1}{a}\underline{v}_{k}\underline{v}_{k}^{\top}\;=\; \frac{1}{a}\sum_{k=2}^{N}\underline{v}_{k}\underline{v}_{k}^{\top}\;+\; \frac{1}{aN} \underline{1}_{N}\underline{1}_{N}^{\top}\;-\; \frac{1}{aN} \underline{1}_{N}\underline{1}_{N}^{\top}
=\; \frac{1}{a}\sum_{k=1}^{N} \underline{v}_{k}\underline{v}_{k}^{\top}\;-\;\frac{1}{aN} \underline{1}_{N}\underline{1}_{N}^{\top}    Eq.15

where the vectors \underline{v}_{1}, \underline{v}_{2},\underline{v}_{3} etc. form an orthonormal set in \mathbb{R}^{N}. This means (by comparing to Eq.14) we can also write the last expression in Eq.15 as,

\frac{1}{a}\underline{\underline{I}}_{N}\;-\;\frac{1}{aN} \underline{1}_{N}\underline{1}_{N}^{\top}     Eq.16

Combining this with the final term on the right-hand-side of Eq.13 we get our final simplified expression for \underline{\underline{M}}^{-1}, which is,

\underline{\underline{M}}^{-1}\;=\; \frac{1}{a}\underline{\underline{I}}_{N}\;-\; \frac{b}{a(a+Nb)}\underline{1}_{N}\underline{1}_{N}^{\top}     Eq.17

That’s it. If you want a challenge to test your understanding, then using the ideas and tricks we introduced above see if you can construct a closed form expression for the inverse of the matrix in Eq.6, not just the special case of the matrix in Eq.1.

Other low-rank perturbation tricks

In my original post I wanted to find the eigenvectors and eigenvalues of the matrix in Eq.1. I’ve also illustrated that once we have closed-form expressions for the eigenvectors and eigenvalues we can calculate the determinant and inverse of \underline{\underline{M}} in Eq.1 very easily. But it is also worth pointing out that there are a couple of other tricks for evaluating the determinant and inverse of matrices of the form in Eq.1 and Eq.6, namely,

  1. Sylvester’s determinant theorem. The Wikipedia link here is for the Weinstein–Aronszajn identity as it turns out that the deteminant theorem has been mis-attributed to Sylvester – I was taught it as Sylvester’s theorem in university. This allows us to calculate the determinant of a low-rank pertubation in terms of a determinant of a smaller matrix.
  2. The Woodbury formula. This allows us to express the inverse of a low-rank perturbation in terms of matrix multiplications involving the inverse of the unperturbed matrix. In fact the result in Eq.17 can also be obtained by using the Shermann-Morrison formula, which is a special case of the Woodbury formula.

Sylvester’s theorem and the Woodbury formula only give us information about the determinant and inverse of the low-rank perturbation, so if we explicitly want information about the eigenvectors and eigenvalues we will probably have to use the tricks I have outlined in this post. However, the advantage of the Sylvester and Woodbury formulae is that they can be used when we have a base-case (the unperturbed matrix) that isn’t necessarily the identity matrix, i.e. they are more widely applicable than the tricks I’ve outlined in this post. What the Sylvester and Woodbury formulae also illustrate is that we shouldn’t be frightened of working with low-rank perturbations of base-case matrices. Once you learn a few tricks working with them becomes very easy.

What have we learnt?

  1. How to calculate analytically (by hand) the eigenvectors and eigenvalues of matrices of the form in Eq.6.
  2. But more importantly, we’ve learnt along the way that eigenvectors and eigenvalues are not that scary. They are easy to manipulate and work with once you get comfortable with a few concepts that you have probably already learnt at college or at university. Matrices of the form in Eq.6 are the simplest, realistic matrices which bring those concepts to life. These matrices are a great learning ground.
  3. Even better, matrices of the type in Eq.6 occur a lot in Data Science, Machine Learning, and AI. In fact, it is probably one of Data Science’s secrets; 95% or more of Data Scientists, myself included, stick to using matrices of this form or a low-rank perturbation of some other known base-case matrix when modelling a real problem. And why not!? When modelling a real problem we start with the base-case we understand and change it as little as possible, both for model complexity reasons (number of extra parameters etc.) and for reasons of computational complexity (can we easily compute and understand the properties of the new matrix). So if you get comfortable working with eigenvectors and eigenvalues of low-rank perturbations of simple base-case matrices, you’ve cracked it for 95% of Data Science use-cases.

 

© 2026 David Hoyle. All Rights Reserved

Leave a comment