# What is the best algorithm to find the inverse of matrix $A$

I'm going to build a C-library so I can do linear algebra at embedded systems. It's most for machine learning. https://github.com/DanielMartensson/EmbeddedAlgebra/

Anyway, I need to compute inverse of matrix $$A$$. What is the absolute best algorithm to use for that? Remember it must be a numerical algorithm.

Which one should I use?

Analytic solution

$$\mathbf{A}^{-1}={1 \over \begin{vmatrix}\mathbf{A}\end{vmatrix}}\mathbf{C}^{\mathrm{T}}={1 \over \begin{vmatrix}\mathbf{A}\end{vmatrix}} \begin{pmatrix} \mathbf{C}_{11} & \mathbf{C}_{21} & \cdots & \mathbf{C}_{n1} \\ \mathbf{C}_{12} & \mathbf{C}_{22} & \cdots & \mathbf{C}_{n2} \\ \vdots & \vdots & \ddots & \vdots \\ \mathbf{C}_{1n} & \mathbf{C}_{2n} & \cdots & \mathbf{C}_{nn} \\ \end{pmatrix}$$

Cholesky decomposition

$$\mathbf{A}^{-1} = (\mathbf{L}^{*})^{-1} \mathbf{L}^{-1}$$

Eigendecomposition

$$\mathbf{A}^{-1}=\mathbf{Q}\mathbf{\Lambda}^{-1}\mathbf{Q}^{-1}$$

Cayley–Hamilton method

$$\mathbf{A}^{-1} = \frac{1}{\det (\mathbf{A})}\sum_{s=0}^{n-1}A^s$$

Newton's method

$$X_{k+1} = 2X_k - X_k A X_k$$

Neuman series $$\lim_{n \to \infty} (\mathbf I - \mathbf A)^n = 0$$

Gaussian elimination

$$A = \begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{bmatrix}$$

To find the inverse of this matrix, one takes the following matrix augmented by the identity, and row reduces it as a 3 × 6 matrix: $$[ A | I ] = \left[ \begin{array}{rrr|rrr} 2 & -1 & 0 & 1 & 0 & 0\\ -1 & 2 & -1 & 0 & 1 & 0\\ 0 & -1 & 2 & 0 & 0 & 1 \end{array} \right]$$

By performing row operations, one can check that the reduced row echelon form of this augmented matrix is:

$$[ I | B ] = \left[ \begin{array}{rrr|rrr} 1 & 0 & 0 & \frac34 & \frac12 & \frac14\\[3pt] 0 & 1 & 0 & \frac12 & 1 & \frac12\\[3pt] 0 & 0 & 1 & \frac14 & \frac12 & \frac34 \end{array} \right]$$

• As a non-mathematical comment: for the love of god, don't. Firstly, you probably don't want to invert a matrix at all (see, for example, here). Secondly, use one of the many impementations that already exist. – user3482749 Jan 11 '19 at 20:16
• So what should I do? – Daniel Mårtensson Jan 11 '19 at 21:24
• In almost all cases, you should just solve $Ax = b$, since that's probably what you want to do anyway, and it's vastly quicker than computing $A^{-1}$ then calculating $A^{-1}b$ (indeed, it's quicker than either of those steps alone). If you really must invert $A$, just use one of the implementations that already exist in other people's algorithms. – user3482749 Jan 11 '19 at 21:33
• See here. The correct, answer, however, is almost certainly "just use somebody else's solution". – user3482749 Jan 11 '19 at 22:35
• All six of them are in C. – user3482749 Jan 12 '19 at 11:27