How to calculate $A^{-1}$, $A^{-7}$ efficiently

Question

excuse me for maybe misstating the question. I studied linear algebra about a year ago in university. I remember learning how to easily calculate

$$A^{-7}$$

or any larger number instead of $-7$. (or simply calculating $A^{-1}$ inverse of an $n \times n$ square matrix efficiently without really inverting it)

I learnt it in the section about diagnolizability. I think it had to do with upper and lower triangular matrices.

I didn't think I'd have to use this knowledge of linear algebra ever again, but turns out I do now because I am using a computer and need to do it efficiently, and I vaguely remember learning about this in university. Anyone know what I am talking about?

Answer 1

One super simple method is to use elementary row operations on the matrix $A$ to take it to the Identity (so Gaussian elimination).

At the same time you are doing this you do the same row operations to the identity matrix.

After you are done, the matrix that started out being $I$ is going to be $A^{-1}$.

Afer doing this you can exponentiate $A^{-1}$ to the desired power with binary exponentiation.

Answer 2

If $A$ is diagonalizable, then $A = P \Lambda P^{-1}$ for a diagonal matrix $\Lambda$. Then $A^n = P \Lambda^n P^{-1}$ for any positive integer $n$. If none of the eigenvalues are zero, the diagonal entries in $\Lambda$ are nonzero, so $\Lambda^{-1}$ exists; its entries are the reciprocals of the entries in $\Lambda$. Therefore $A^{-1} = P \Lambda^{-1} P^{-1}$, and $A^{-n} = P (\Lambda^{-1})^n P^{-1}$.

That having been said, if you're writing code and efficiency is important, find a library that does the computation for you!

Answer 3

First caculate $A^{-1}$ using Gaussian eliminations and then $$A^{-7} = (A^{-1})^7 = A\cdot (A^{-1})^8 = A\cdot (((A^{-1})^2)^2)^2$$

In other words, square $A^{-1}$, then square the result and square the result again. Finally, multiply it by $A$.