# What is eigenvalue decomposition and why would it be useful in games?

In various math libraries developed for game engines, I see 2x2 and 3x3 square matrices having this function (along with some helper functions). I tried to find information regarding it but did not come across game specific material (wikipedia entry is quite heavy and does not relate to games).

It would be great if in your answer, you could provide an example or two on how it is used in games.

• can you name a library that does this for 2x2 or 3x3 matrices? Not all the matrices can be spectral decomposed, I see little 3x3 applications that can and they don't do something interisting. – FxIII Jun 26 '11 at 17:02
• WildMagic5 (geometrictools.com) engine does it with its Matrix library. So does Ogre's (ogre3d.org/docs/api/html/classOgre_1_1Matrix3.html). You are right that not all matrices can be solved for. In this case, they must be symmetric. – Samaursa Jun 26 '11 at 17:12
• To be picky: symmetry is necessary and sufficient for real matrices that has to be decomposed to real factors. If the second falls then the necessarity falls (which is good); if the first falls then the sufficiency falls (which is bad). But who cares?:) – FxIII Jun 27 '11 at 8:43

Eigenvalues and eigenvectors are very commonly used in math, so it's good to understand them even if you don't have an immediate use for the in games. They're generally covered near the end of an undergraduate-level linear algebra course.

One I can think of is for dealing with the moment of inertia in physics. This is a symmetric positive-definite matrix, so all the eigenvalues are guaranteed to be real and positive. If you compute the principal axes of a rigid body (which are the eigenvectors of the matrix), you can rotate the body so that its moment of inertia is diagonal - this would allow you to store just the diagonal components as a vector3, instead of the full matrix.

Another place I've seen them used is computing the best-fit plane to a set of points, or to find the best-fit bounding box (section 6.1.2 in the link)

Have you searched in the WildMagic or Ogre code to see where else they're used?

• In WildMagic5 it is being used in a sample project that performs intersection of ellipses and ellipsoids. I do not have Ogre3d source in front of me atm, so I cannot tell if it is being used internally or not. – Samaursa Jun 26 '11 at 22:31
• Ok, this makes sense. If A is the matrix that transforms a unit circle into your ellipse, the eigenvalues are the length of your axis and the eigenvectors are the directions of them. – FxIII Jun 27 '11 at 7:16

As far as I know, eigenvalue decomposition is a middle-step that can be performed in some algorithms for things with more readily apparent uses, such as matrix inverting.

• If you mean matrix inverse (I have never used any technique to calculate an inverse using eigenvalue decomposition... then again, I have used 3x3 and 2x2 matrices only), for a 2x2, the inverse is very simple and does not (should not) require a middle-step. A 3x3 Matrix inverses requires an adjunct, which is calculated using matrix of minors transposed. Since the decomposition is a lot more steps, I would deduce it is a lot more costly and has other uses than being used as a middle step. Also note, these methods are available in 2x2 and 3x3 matrices in the libraries. – Samaursa Jun 26 '11 at 20:33
• Computing eigenvalues is a "harder" problem than matrix inversion. For anything over a 4x4 matrix, it's impossible to compute the exact eigenvalues, because the problem is equivalent to solving for the roots of an N-degree polynomial. – celion Jun 26 '11 at 21:08