Powers of a 2×2 matrix in closed form | Hacker News Reader

Powers of a 2×2 matrix in closed form

johndcook.com

62 pointsKqAmJQ717 comments

A less formula driven approach that I expected this to use is just eigenvalue decompose the matrix (with complex eigenvalues that always exists) then raise each eigenvalue to the power you want and then combine the eigenvectors and eigenvalues together again to get the Nth power. (Requires computing a matrix matrix product but only once and that could be expressed in closed form and it's overall a cheap operation vs actually multiplying the matrix by itself N times.)

It sounds like you're assuming diagonalizability, which is stronger than "eigen values defined over the field".

Even over the complex numbers there are matrices that aren't diagonalizable, like [[2,1],[0,2]].

In practice, all matrices are diagonalizable, because the set of non-diagonalizable matrices is very small. Concretely, a random matrix is almost surely diagonalizable (ie. with probability 1).

This "with zero probability" statement hides that there's a probability distribution assumed. It's really saying that any matrix can be perturbed to be diagonalizable. Which is true. But matrices in that set have a way of showing up a lot in models that the human mind conceives. For example, if you model a point mass accelerating without drag, you will end up with a matrix that isn't diagonalizable. If all matrices were diagonalizable, every linear ODE would be solved by a bunch of exponentials and sinusoids; there'd be no polynomials. But we see things like "1/2 a t^2" all the time.

Also "any matrix can be perturbed" assumes a normed field, though those equations work over other fields as well

> It sounds like you're assuming diagonalizability, which is stronger than "eigen values defined over the field".

> Even over the complex numbers there are matrices that aren't diagonalizable, like [[2,1],[0,2]].

While that's completely true, and I'm glad someone said it, it's not much of an issue for 2×2 matrices. You can tell quickly when it's happened, because the characteristic polynomial is a square (itself easily tested by computing the gcd with the derivative … or just because it's easy to recognize when a quadratic is a perfect square) but the matrix isn't scalar; and then we have that the semisimple part S is scalar, the nilpotent part N satisfies N^2 = 0, and so (S + N)^n equals S^n + n S N^{n - 1} for n > 1.

Thank you! This why the Jordan Form exists at all.

(All real symmetric, or more generally Hermitian matrices are diagonalizable, which is the Spectral Theorem.)

That would be less interesting, since it's the method taught in every first course of linear algebra, right?

> That would be less interesting, since it's the method taught in every first course of linear algebra, right?

But it would be interesting to mention that that's what this method is doing, just using that, in the distinct-eigenvalues case, A - \beta I maps onto the \alpha-eigenspace, so you can simply apply it instead of explicitly finding eigenvectors. In fact, every time I teach linear algebra, one of my students discovers this 2×2 trick for finding eigenvectors, though usually accidentally thinking that they are finding \beta-eigenvectors, rather than \alpha-eigenvectors, by computing the image of A - \beta I instead of its kernel.

Oh. Oh, neat. Thanks!

> A less formula driven approach that I expected this to use is just eigenvalue decompose the matrix (with complex eigenvalues that always exists) then raise each eigenvalue to the power you want and then combine the eigenvectors and eigenvalues together again to get the Nth power.

That's actually what's happening here for the distinct-eigenvalues case: (A - \beta I)/(\alpha - \beta) is the projection on the \alpha-eigenspace, where A^n acts by \alpha^n, with kernel the \beta-eigenspace; and similarly with \alpha and \beta switched. In general, pursuing this same line of attack underlies the proof that the semisimple part of A can be written as a polynomial in A. (Sadly, the polynomial itself depends on A, so this is probably more usefully stated as that the semisimple part of A lies in k[A] if k is perfect.)

Reminds me of Sylvester's formula [0]

[0] https://en.wikipedia.org/wiki/Sylvester%27s_formula

Function in a matrix of A can be expressed in products of A with its eigenvalues.

I must be missing something as this seems very basic.

Assume A = vEv^T , where E is a diagonal matrix of eigenvalues and v is the transformation from A to E. Then A^n = vEv^TvEv^T..vEv^T. vv^T equals the identity matrix and will cancel out. So A^n = vE^nv^T. The closed form in the article is then just inlining the computation of v and v^T to how they apply to alpha and beta.

Oh, and to understand what happens in the more complex case where not all eigenvalues are different, see Jordan Normal Form. That is less basic and not as well covered in the basic courses as the above is.

Any idea what the derivation in [1] looks like?

Let α and β be the eigenvalues of the matrix A. A satisfies its characteristic polynomial so we have

  A^2 - (α + β)A + αβI = 0

If α /= β, define

  X = (A - βI)/(α - β)
  Y = (A - αI)/(β - α)

which satisfy

  X^2 = X
  XY = YX = 0
  Y^2 = Y

so for k >= 2, X^k = X and Y^k = Y. Hence

  A^n = (αX + βY)^n
      = α^n X^n + β^n Y^n
      = α^n X + β^n Y

On the other hand, if α = β, define

  Z = A - αI

which satisfies Z^2 = 0, so Z^k = 0, and

  A^n = (αI + Z)^n
      = α^n I + n α^(n-1) Z

Thanks, that actually looks appropriately elementary.

diagonalization, recurrences, system of equations, etc.

there are many ways to do it

Reply on news.ycombinator.com