5 ms·

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

by naillo 3y ago

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.)

henrydark 3y ago
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]].
- xyzzyz 3y ago
  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).
  - FooBarBizBazz 3y ago
    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.
    - henrydark 3y ago
      Also "any matrix can be perturbed" assumes a normed field, though those equations work over other fields as well
- JadeNB 3y ago
  > 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.
- deleted 3y ago
  [deleted]
- FooBarBizBazz 3y ago
  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.)
tptacek 3y ago
That would be less interesting, since it's the method taught in every first course of linear algebra, right?
- JadeNB 3y ago
  > 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.
  - tptacek 3y ago
    Oh. Oh, neat. Thanks!
JadeNB 3y ago
> 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.)

by naillo 3y ago

henrydark 3y ago

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]].

xyzzyz 3y ago
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).
- FooBarBizBazz 3y ago
  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.
  - henrydark 3y ago
    Also "any matrix can be perturbed" assumes a normed field, though those equations work over other fields as well
JadeNB 3y ago
> 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.
deleted 3y ago
[deleted]
FooBarBizBazz 3y ago
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.)

tptacek 3y ago

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

JadeNB 3y ago
> 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.
- tptacek 3y ago
  Oh. Oh, neat. Thanks!

JadeNB 3y ago

> 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.)