27
\$\begingroup\$

Somehow, we don't yet have a challenge for finding the inverse of an arbitrarily-sized square matrix, despite having ones for 3x3 and 4x4, as well as a more complex version.

Your task is, given a square \$n\times n\$ non-singular matrix \$M\$, output the matrix \$M^{-1}\$ that satisfies

$$MM^{-1} = I_n$$

There are a number of methods and formulae for calculating \$M^{-1}\$, but one of the most well known is

$$M^{-1} = \frac1{\det(M)}\text{ adj}(M)$$

where \$\det\$ represents the determinant and \$\newcommand{\adj}{\text{adj}}\adj\$ the adjugate

Some definitions:

  • \$I_n\$: The \$n\times n\$ identity matrix i.e. an \$n\times n\$ matrix where the leading diagonal consists entirely of \$1\$s and the rest \$0\$s
  • Non-singular: the determinant of \$M\$ is guaranteed to be non-zero
  • Determinant: a specific number that can be calculated for any given square matrix. Exact methods can be found in the Wikipedia article
  • Adjugate: Formally, the transpose of the cofactor matrix of \$M\$. Informally, this is a operation on \$M\$ which takes determinants of submatrices in a specific way to construct a related matrix. Again, exact details can be found in the linked article.

For sake of simplicity, you may assume:

  • The elements of \$M\$ will all be integers within the native bounds of your language
  • \$n\$, nor \$n^2\$, will never exceed the maximum value in your language, and will always be greater than or equal to \$1\$
  • The elements of \$M^{-1}\$ will never exceed the maximum value in your language (or minimum for negative values)
  • \$M\$ will never be singular

No builtins are banned and you may use whatever (valid) method you like for calculating \$M^{-1}\$. It is acceptable if your program fails for some inputs due to floating point issues, so long as the underlying algorithm or method works for arbitrary matrices.

This is, of course, entirely optional, but if your answer consists entirely of a builtin, consider including a non-builtin method, simply for the sake of general interest.

Standard rules apply. This means you may input or output in any convenient format, and that standard loopholes are forbidden. The shortest code in bytes wins.

This script will take an input \$n\$ and generate an \$n\times n\$ matrix with random integers between \$-10\$ and \$10\$, along with it's inverse. You can use this for test cases.


Worked example

Lets take the \$3\times3\$ matrix \$M\$ as:

$$M = \left[\begin{matrix} 4 & -3 & 0 \\ -4 & -7 & 6 \\ 5 & 7 & 6 \end{matrix}\right]$$

We'll use the above formula, \$M^{-1} = \frac{\adj(M)}{\det(M)}\$ for this example.

First, we'll calculate \$\det(M)\$ by expanding along the third column:

$$\begin{align} \det(M) & = \left|\begin{matrix} 4 & -3 & 0 \\ -4 & -7 & 6 \\ 5 & 7 & 6 \end{matrix}\right| \\ & = 0\left|\begin{matrix} -4 & -7 \\ 5 & 7 \end{matrix}\right| - 6\left|\begin{matrix} 4 & -3 \\ 5 & 7 \end{matrix}\right| + 6\left|\begin{matrix} 4 & -3 \\ -4 & -7 \end{matrix}\right| \\ & = 0 - 6(4\cdot7 - -3\cdot5) + 6(4\cdot-7 - -3\cdot-4) \\ & = -6(28 + 15) + 6(-28 - 12) \\ & = -6\cdot43 + 6\cdot-40 \\ & = -498 \\ \therefore det(M) & = -498 \end{align}$$

We then need to calculate \$\adj(M)\$. As \$\adj(\cdot)\$ of a matrix is the transpose of the cofactor matrix, this essentially boils down to calculating the cofactor matrix of \$M\$, \$C_M\$:

$$\begin{align} \adj(M) & = C_M^T \\ & = \left[\begin{matrix} \left|\begin{matrix} -7 & 6 \\ 7 & 6 \end{matrix}\right| & \left|\begin{matrix} -4 & 6 \\ 5 & 6 \end{matrix}\right| & \left|\begin{matrix} -4 & -7 \\ 5 & 7 \end{matrix}\right| \\ \left|\begin{matrix} -3 & 0 \\ 7 & 6 \end{matrix}\right| & \left|\begin{matrix} 4 & 0 \\ 5 & 6 \end{matrix}\right| & \left|\begin{matrix} 4 & -3 \\ 5 & 7 \end{matrix}\right| \\ \left|\begin{matrix} -3 & 0 \\ -7 & 6 \end{matrix}\right| & \left|\begin{matrix} 4 & 0 \\ -4 & 6 \end{matrix}\right| & \left|\begin{matrix} 4 & -3 \\ -4 & -7 \end{matrix}\right| \end{matrix}\right]^T \\ & = \left[\begin{matrix} -84 & 54 & 7 \\ 18 & 24 & -43 \\ -18 & -24 & -40 \end{matrix}\right]^T \\ & =\left[\begin{matrix} -84 & 18 & -18 \\ 54 & 24 & -24 \\ 7 & -43 & -40 \end{matrix}\right] \end{align}$$

Finally, having calculated both \$\det(M)\$ and \$\adj(M)\$, we divide each element of \$\adj(M)\$ by \$\det(M)\$ to compute the final output, \$M^{-1}\$:

$$\begin{align} M^{-1} & = \frac{\adj(M)}{\det(M)} \\ & = \left[\begin{matrix} \frac{-84}{-498} & \frac{ 18}{-498} & \frac{-18}{-498} \\ \frac{ 54}{-498} & \frac{ 24}{-498} & \frac{-24}{-498} \\ \frac{ 7}{-498} & \frac{-43}{-498} & \frac{-40}{-498} \end{matrix}\right] \\ & = \left[\begin{matrix} \frac{ 14}{ 83} & \frac{-3}{ 83} & \frac{ 3}{ 83} \\ \frac{ -9}{ 83} & \frac{-4}{ 83} & \frac{ 4}{ 83} \\ \frac{ -7}{498} & \frac{43}{498} & \frac{20}{249} \end{matrix}\right] \end{align}$$

Alternatively, as decimals, \$M^{-1}\$ is

[[ 0.1686746987951807,   -0.03614457831325301, 0.03614457831325303],
 [-0.10843373493975902,  -0.04819277108433735, 0.04819277108433734]
 [-0.014056224899598388,  0.08634538152610442, 0.08032128514056225]]
\$\endgroup\$
7
  • 1
    \$\begingroup\$ Needs a plain English spec, a worked example and some test cases. \$\endgroup\$ – Shaggy Oct 20 '20 at 21:29
  • 14
    \$\begingroup\$ @Shaggy How would you suggest "plain English" on a very maths-y challenge? I can add in a worked example, but beyond that, most of the relevant terms are going to be just as (if not more) complicated/specific as the ones I've used already. As for the test cases, I decided to omit specific test cases as the vast majority of matrices have non-integer inverses, which are difficult to represent in a readable format when you have multiple (especially in a matrix format), so I decided to go with a test case generator to make it easier to read (and to avoid any mistakes) \$\endgroup\$ – caird coinheringaahing Oct 20 '20 at 21:50
  • 2
    \$\begingroup\$ Right now, the only part of this challenge I understand is the title and, even then, I don't know what the inverse of a matrix is. MathJax has been a severe detriment to this site :( \$\endgroup\$ – Shaggy Oct 20 '20 at 23:48
  • 7
    \$\begingroup\$ @Shaggy I could include descriptions of the determinate and the adjugate for a given matrix in the question, but given that they're easily found by following the links, I don't think it's worth cluttering the question with even more description, especially as it's fairly easily to understand by following the worked example. Furthermore, I highly disagree that Mathjax is a detriment to the site; rather, with Mathjax, I'm able to express my meaning in a much clearer fashion than before. I'd suggest you read through the worked example and let me know of any misunderstandings you may have. \$\endgroup\$ – caird coinheringaahing Oct 20 '20 at 23:53
  • 3
    \$\begingroup\$ Really, the only part of this question that one needs to understand is the first one. All of the rest are just a collection of results that make computing the solution to that problem easier. It may have been better to leave some of the extra explanation off and instead just briefly explain matrix multiplication? That would make the question self-contained as per the rules. Not every question will be at a level that everyone finds comfortable, and that is fine. \$\endgroup\$ – FryAmTheEggman Oct 21 '20 at 0:07

20 Answers 20

21
+500
\$\begingroup\$

Octave, 57 bytes

A=input('');V=A'/trace(A*A');for i=1:1e4V=2*V-V*A*V;end
V

Try it online!

This is not particularly well golfed, but I wanted to advertise an approach that could be useful for other non-builtin answers.

This uses the Hotelling-Bodewig scheme:

$$ V_{i+1} = V_i\left(2I - AV_i\right)$$

Which iteratively computes the inverse of a non singular matrix. This is guaranteed to converge for \$\left\lVert I - AV_0\right\rVert < 1\$ (under a suitable matrix norm). Choosing the \$V_0\$ is difficult, but Soleymani, F. shows in "A New Method For Solving Ill-Conditioned Linear Systems" that the inital guess \$V_0 = \frac{A^T}{\text{tr}(AA^T)}\$ will always satisfy this condition, so the system is numerically stable.

What makes this a particularly attractive approach to other potential answers is that we don't require any builtin determinant or inverse functions. The most complex part is just matrix multiplication, since the transpose and trace are trivial to compute.

I have chosen 1e4 iterations here to make the runtime somewhat reasonable, although you could of course push it to 1e9 with no loss of byte count.


-10 thanks to xnor for noting we don't need to construct an identity matrix.

\$\endgroup\$
6
  • 4
    \$\begingroup\$ Thanks for sharing this! I didn't know you there was an simple iterative scheme that's guaranteed to converge for an easy-to-compute start value. I know this answer isn't here for golfing, but it looks like you can write V=2*V-V*A*V. There's always writing A^0 for the identity in V*=2*A^0-A*V, but that's one longer. \$\endgroup\$ – xnor Oct 21 '20 at 3:16
  • \$\begingroup\$ Thanks @xnor, that's a significant improvement over explicitly constructing the identity matrix. \$\endgroup\$ – Sisyphus Oct 21 '20 at 4:45
  • 1
    \$\begingroup\$ This is sweet. Wikipedia's page for Matrix inverses notes this formula as a version of Newton's Method but its references are pretty useless for finding \$V_0\$. \$\endgroup\$ – Giuseppe Oct 21 '20 at 14:23
  • 1
    \$\begingroup\$ @TobiasKnauss This was an answer intended to display a neat method without builtins. Of course you could do inv, which is much shorter, but also (imo) much more boring :) \$\endgroup\$ – Sisyphus Oct 22 '20 at 21:47
  • 1
    \$\begingroup\$ THIS IS EFFORT. Really; this is something I love - really good work! :o \$\endgroup\$ – William Martens Feb 19 at 20:11
15
\$\begingroup\$

R, 5 bytes

solve

Try it online!

Nothing new here... Basically, the code solve(A, B) solves \$AX = B\$, but when \$B\$ is not given, it is treated as identity matrix, thus giving us the inverse as the result.

\$\endgroup\$
12
\$\begingroup\$

APL (Dyalog Unicode), 1 byteSBCS

Try it online!

The domino primitive is a very interesting APL "built-in". It already featured in another 1-byte answer of my own where it was used to solve a least-squares problem. When applied to a square matrix, tries to find the matrix inverse of its argument.

Many golfing languages will also have a built-in for this... But mind you, APL is not a golfing language, although it is terse enough to be very competitive and, in cases like this, win.

\$\endgroup\$
11
\$\begingroup\$

R, 72 61 bytes

function(A,V=t(A/sum(diag(A%*%t(A))))){for(i in 1:1e4)V=2*V-V%*%A%*%V;V}

Try it online!

Porting Sisyphus' answer is not futile at all...and thanks to Sisyphus for -11 bytes.

Observes that \$Tr(AA^T)=\sum\limits_{i,j}a_{ij}^2\$.

R, 94 bytes

function(M)outer(k<-1:dim(M),k,Vectorize(function(j,i)det(M[-i,-j,drop=F])*(-1)^(i+j)))/det(M)

Try it online!

Thanks to Robin Ryder for fixing a bug and making this actually work.

Calculates \$A^{-1}\$ using the adjugate/determinant method.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ I think, for the cost of extra warning, you can replace nrow with dim :) \$\endgroup\$ – Kirill L. Oct 20 '20 at 21:44
  • \$\begingroup\$ @KirillL. yes you're right of course, and I got to get rid of the t() by flipping i and j, too! \$\endgroup\$ – Giuseppe Oct 20 '20 at 21:52
  • 2
    \$\begingroup\$ You can save a byte with dim(x<-M) instead of initializing x=M. \$\endgroup\$ – Robin Ryder Oct 20 '20 at 22:00
  • \$\begingroup\$ @RobinRyder neat! I often forget that for is a little odd like that. \$\endgroup\$ – Giuseppe Oct 20 '20 at 22:04
  • 3
    \$\begingroup\$ Nice solution! Actually, sum(diag(A%*%t(A))) is the same as sum(A^2), which saves a few bytes. Being elementwise by default actually helps in R's case here. \$\endgroup\$ – Sisyphus Oct 22 '20 at 10:15
8
\$\begingroup\$

Python 2, 228 bytes

from random import*
a=input()
exec"""$:j,J=i,I;J+=[j==i $]
while~-all(I[i]$):shuffle(a)
$:
 j,J=i,I
 $:
	if j-i:I[:]=[y-I[j]*x/J[j]for x,y in zip(J,I)]
$:print[x/I[i]for x in I][len(a):]""".replace("$","for i,I in enumerate(a)")

Try it online!

Augment the matrix with the identity matrix, then apply Gauss–Jordan elimination. I don't know if this is the shortest approach, but it's the one I wanted to try golfing down.

I use while not all(a[i][i]for i in r):shuffle(a) to move zeros off the diagonal. This loop will definitely terminate, because if there is no permutation of the rows of \$A\$ that makes the diagonal free of zeros, then \$\det(A)=0\$, which we are guaranteed is not the case. This can be seen from the Leibniz formula for \$\det(A)\$:

$$\det(A) = \sum_{\sigma \in S_n} \text{sgn}(\sigma) \prod_{i=1}^n a_{\sigma(i),i}$$

“There is no permutation \$\sigma\$ of the rows that makes the diagonal free of zeros” can be equivalently rephrased as “\$\prod_{i=1}^n a_{\sigma(i),i}\$ is always 0, for all \$\sigma\$” which causes this whole formula to be 0.

\$\endgroup\$
6
\$\begingroup\$

Julia 1.0, 3 bytes

inv

Try it online!

Yet another short built-in solution.

\$\endgroup\$
3
  • \$\begingroup\$ Why such an ancient version of Julia? \$\endgroup\$ – Anush Oct 21 '20 at 9:57
  • 1
    \$\begingroup\$ This is what TIO has as its latest. \$\endgroup\$ – Kirill L. Oct 21 '20 at 10:10
  • \$\begingroup\$ Oh! It needs we upgrade :) \$\endgroup\$ – Anush Oct 21 '20 at 21:12
6
\$\begingroup\$

JavaScript (ES6), 169 bytes

This computes \$M^{-1} = \dfrac{\operatorname{adj}(M)}{\det(M)}\$

M=>M.map((r,y)=>r.map((_,x)=>D(h(M,x).map(r=>h(r,y)))*(x+y&1?-1:1)/D(M)),h=(a,n)=>a.filter(_=>n--),D=M=>+M||M.reduce((s,[v],i)=>s+(i&1?-v:v)*D(h(M,i).map(r=>h(r,0))),0))

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ I don't know if it's standard for JavaScript golf but a.filter(_=>n--) is a very fun way to throw away the n-th element of a! \$\endgroup\$ – Lynn Oct 22 '20 at 12:28
  • \$\begingroup\$ @Lynn I don't think it's used very often. As far as I'm concerned -- and besides other challenges with determinants -- I think I've also used it to compute permutations. \$\endgroup\$ – Arnauld Oct 22 '20 at 13:03
6
\$\begingroup\$

J, 2 bytes

%.

Try it online!

Same as APL, but more powerful, as J can produce exact rational matrix when given a matrix of extended integers as input.

\$\endgroup\$
6
\$\begingroup\$

05AB1E, 38 22 21 20 bytes

˜nO/øтF©I2Føδ*O®}·s-

Port of @Sisyphus' Octave answer, so make sure to upvote him!!
-16 bytes thanks to @ovs.

Try this online.

Code explanation:

˜            # Flatten the (implicit) input-matrix to a single list
 n           # Square each value in this list
  O          # Take the sum (this is the trace of M*M')
   /         # Divide each value in the (implicit) input-matrix by this trace
    ø        # Zip/transpose this matrix; swapping rows/columns
тF           # Loop 100 times:
  ©          #  Store the current matrix in variable `®` (without popping)
   I         #  Push the input-matrix
    2F       #  Loop 2 times:
      ø      #   Zip/transpose the top matrix; swapping rows/columns
       δ     #   Apply double-vectorized with the top two matrices:
        *    #    Multiply
         O   #   Sum each inner row
          ®  #   Push the matrix from variable `®` again
     }·      #  After the inner loop: double all values in matrix `®`
       s     #  Swap so the calculated matrix VMV is at the top again
        -    #  Subtract this VMV from the 2V
             # (after the outer loop, the resulting matrix is output implicitly) 

Original answer (38 bytes) and detailed explanation:

εUεX*O]Å\OIøs/тFxs©εUIøεX*O}U®øεX*O}}-

Try it online.

05AB1E has barely any useful builtins for matrices, not even matrix manipulation. So almost everything has to be done manually..

Since I'm an absolute noob in math, I'm gonna explain everything in full detail to help others like me who want to do this challenge without any builtins, and also to keep this answer self-contained.

Step 1) Matrix manipulation of the input-matrix \$M\$ with it's transpose: \$M\times M'\$:

If we have a matrix \$A\$ and \$B\$ and want to do matrix-manipulation \$AB\$, we take the dot-product of every \$i^{th}\$ row of \$A\$ and \$j^{th}\$ column of B for every coordinate \$i,j\$ in the two matrices.

For example, if we use the matrix in the challenge description:

\$M = \left[\begin{matrix} 4 & -3 & 0 \\ -4 & -7 & 6 \\ 5 & 7 & 6 \end{matrix}\right]\$

We can for example calculate the values in the top row of the resulting \$M\times M'\$ matrix with:

Top-left: \$4\times4+-3\times-3+0\times0 = 25\$
Top-center: \$4\times-4+-3\times-7+0\times6=5\$
Top-right: \$4\times5+-3\times7+0\times6 = -1\$

I've done matrix manipulation in 05AB1E before in this answer of mine, so I've used that code snippet here as well. Since we want to multiply the input-matrix by it's transpose, we actually won't need the transpose builtin here.

ε                  # Map over each row of the (implicit) input-matrix
 U                 #  Pop and store the current row in variable `X`
  ε                #  Map over each row of the (implicit) input-matrix again
   X*              #   Multiply the values of the current row by the values at the same
                   #   positions in row `X`
     O             #   And take the sum of this row
]                  # Close both maps

Try just this step online.

Step 2) Take the trace of this new matrix: \$(M\times M')^T\$

The trace of a square matrix is basically the sum of its main diagonal (the values of the top-left to the bottom-right).

Å\                 # Take the main diagonal of the matrix of step 1
  O                # And sum the values in this list together

Try the first two steps online.

Step 3) Divide all values in the transposed matrix by this trace we calculated:

I                  # Push the input-matrix
 ø                 # Zip/transpose it; swapping rows/columns
  s                # Swap so the trace we calculated it at the top of the stack
   /               # And divide each value in the transposed matrix by this trace

Try the first three steps online.

Step 4) Repeat the following steps (5 through 8) enough times for the answer to not change anymore:

Since this program isn't very fast in 05AB1E, I've decided to loop just 100 times, but this can be increased to improve the accuracy of the decimal results (I've verified with @Sisyphus' Octave answer that changing the 1e4 to 1e2 still holds the same result for most matrices).

тF                 # Loop 100 times:

I'm not sure if the values will eventually not change anymore if we loop enough times. If this is the case we could (in theory) save a byte by changing this тF to Δ (loop until the result no longer changes).

(Let's call the intermediate matrix inside this loop \$V\$ for the explanations of the following steps.)

Step 5) Double each value in the current matrix: \$2V\$:

  x                #  Double each value in the current matrix V (without popping)

Try the first five steps online, excluding the loop of step 4.

Step 6) Do matrix manipulation again for \$VM\$ (where \$M\$ is the input-matrix):

   s               #  Swap to take the non-doubled matrix V at the top again
    ©              #  Store this matrix V in variable `®` (without popping)
     ε             #  Map over each row of matrix V:
      U            #   Pop the current row, and store it in variable `X`
       I           #   Push the input-matrix M
        ø          #   Zip/transpose; swapping rows/columns
         ε         #   Map over each row of this transposed matrix M':
          X*       #    Multiply the values in the current row by row `X`
            O      #    And take the sum

Try the first six steps online, excluding the loop of step 4.

Step 7) And do matrix manipulation yet again right after: \$VMV\$:

         }         #   Close the inner map
          U        #   Pop and store this as new `X`
           ®       #   Push the matrix V from variable `®`
            ø      #   Zip/transpose; swapping rows/columns
             ε     #   Map over each row of this transposed matrix V':
              X*   #    Multiply the values in the current row by row `X`
                O  #    And take the sum
     }}            #  Close both the inner and outer maps

Try the first seven steps online, excluding the loop of step 4.

Step 8) Subtract the values at the same positions of these two matrices from one another: \$2V-VMV\$:

       -           #  Subtract matrix VMV from 2V

Try the first eight steps online, excluding the loop of step 4.

And after the loop is done, the resulting matrix is output implicitly.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I think you have a small mistake in your example for \$ M\times M' \$: The top left value is actually \$4\times4 + (-3)\times(-3) + 0 \times 0\$. See here for a general \$3 \times 3\$-case. \$\endgroup\$ – ovs Oct 21 '20 at 9:13
  • 1
    \$\begingroup\$ Dδ*O works for a product of matrix and its inverse, but since you only care about the trace, nOO is shorter. \$\endgroup\$ – ovs Oct 21 '20 at 9:16
  • 1
    \$\begingroup\$ And øδ*O works for general matrix multiplication, see WolframAlpha for a verification of the test case. Note that matrix multiplication is not commutative. \$\endgroup\$ – ovs Oct 21 '20 at 9:23
  • \$\begingroup\$ @ovs Thanks! I've kept the original answer and explanation (with the fix for the \$M\times M'\$), but I'm down to 20 bytes now thanks to your suggestions. \$\endgroup\$ – Kevin Cruijssen Oct 21 '20 at 9:54
6
\$\begingroup\$

Scala, 237 232 bytes

Uses the method from Sisyphus's answer. Go upvote that!

m=>{val h=m.indices
Seq.iterate(m.transpose.map(_.map(_/m.flatten.map(x=>x*x).sum)),9999){v=>h.map(i=>h.map{j=>2*v(i)(j)-(h.map(k=>v(i).zip(m.transpose.apply(k))map(t=>t._1*t._2)sum),v.transpose.apply(j)).zipped.map(_*_).sum})}last}

Try it online!

h is just a range from 0 until n to reuse later (mostly because Scala doesn't have matrix multiplication builtins). The function makes a sequence of 9999 elements and takes the last element. The first element is the transpose of m divided by the trace of m times its transpose. Subsequent elements are calculated with 2*v-v*m*v, where v was the previous element.

To calculate \$V_0\$ (It turns out the trace of m times its transpose is just the sum of squares of all of m's cells):

m.transpose.map(            //For every row in m's transpose
  _.map(                    //For every cell in that row
    _ /                     //Divide it by (trace(M * M's transpose))
      m.flatten             //Turn m into a 1D list
        .map(x=>x*x)        //Square each cell
        .sum))              //Add them up

To calculate subsequent elements, we use \$2V - (VA)V\$, but you have to map over h instead of over v itself:

h.map(i =>                 //For every i in [0, n)
  h.map{j =>               //For every j in [0, n)
    2*v(i)(j) -            //2V at these coordinates minus
    <(v * m * v)[i][j]> }) //v*m*v at these coordinates (see explanation below)

To calculate (v*m)[i]:

h.map(k =>                //k is the index of a row in [0, n)
  v(i).zip(               //Zip column i of v with
    m.transpose.apply(k)  //Row k of m (apply is used for indexing here)
  ) map(t=>t._1*t._2)     //Multiply v(i)(j) with m(k)(i)
  sum                     //Add then up
)

And getting the cross product of that with row j of v uses pretty much the same approach.


Scala, 346 342 bytes

Saved 4 bytes thanks to @corvus_192!

type M=Seq[Seq[Double]]
def c(m:M)={val I=m.indices;I.map(i=>I.map(j=>m(i)(j)*math.pow(-1,i+j)))}
def d(m:M):(M,Double)=if(m.size<2)m->m(0)(0)else{val I=m.indices
val M=I.map(i=>I.map{j=>d(I.filter(i!=_)map(k=>I.filter(j!=_)map(m(k))))._2})
c(M)->c(m).head.zip(M.head).map(t=>t._1*t._2).sum}
def i(m:M)=d(m)._1.transpose.map(_.map(_/d(m)._2))

Try it in Scastie!

As you can see, I'm not very good at math.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Save 4 bytes with def i(m:M)=d(m)._1.transpose.map(_.map(_/d(m)._2)). \$\endgroup\$ – corvus_192 Oct 21 '20 at 7:14
  • \$\begingroup\$ @corvus_192 Thanks, I was thinking too much about efficiency \$\endgroup\$ – user Oct 21 '20 at 13:20
5
\$\begingroup\$

Wolfram Language (Mathematica), 7 bytes

Inverse

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Python 2, 188 bytes

lambda a:[[c(a,j,i)/d(a)for j,_ in e(a)]for i,_ in e(a)]
c=lambda a,i,j:(-1)**(i+j)*d([b[:j]+b[j+1:]for I,b in e(a)if i-I])
d=lambda a:a==[]or sum(b[0]*c(a,i,0)for i,b in e(a))
e=enumerate

Try it online!

The top lambda computes \$A^{-1} = \frac{1}{\det(A)}\text{adj}(A)\$.

d(a) computes the determinant and c(a,i,j) computes cofactors.

\$\endgroup\$
5
\$\begingroup\$

APL (Dyalog Unicode), 27 23 bytes

-4 bytes thanks to Adám!

This implements the method advertised by Sisyphus.

⊢(⊢+⊢-⊢+.×+.×)⍣≡⍉÷,+.×,

Try it online!

A function that takes the matrix as the right argument.

+.× computes the dot product (sum of element-wise product) of the flattened matrix , and the flattened matrix ,. This is sum of the squared matrix entries, which is equal to \$tr(AA^T)\$.
⍉÷ divides the transposed matrix by the trace.

(⊢+⊢-⊢+.×+.×)⍣≡ is a function which is applied to the original matrix \$A\$ as a left argument () and \$A^T\div tr(AA^T)\$ as the right argument (⍉÷,+.×,):

⊢+⊢-⊢+.×+.× takes the current matrix \$V\$ on its right and the input matrix \$A\$ on its left and executes one iteration step:
+.× is the inner product of + and ×. Given two matrices, this calculates their product. In this case \$ A \times V \$.
is the right argument \$V\$, ⊢+.× the product \$V \times (A \times V)\$.
⊢- subtracts this from the right argument: \$V-V \times A \times V\$.
⊢+ adds this to the right argument: \$V+V-V \times A \times V\$.

⍣≡ applies the function on its left until the result doesn't change. Because of the way equality testing works in Dyalog APL, this actually terminates.

\$\endgroup\$
1
4
\$\begingroup\$

Jelly, 3 bytes

æ*-

Try it online.

Explanation:

     # Full program taking a single integer-matrix as argument
æ*   #  Matrix exponentiation
  -  #  with -1
     #  (after which the result is output implicitly)
\$\endgroup\$
4
\$\begingroup\$

Excel, 29 bytes

=MINVERSE(OFFSET(A2,,,A1,A1))

Straightforward application of the MINVERSE() function. It's boring but I got excited about Excel having a built-in for something. Input \$n\$ in A1, the matrix starting in A2, and the formula anywhere the spill won't interfere.

Screenshot

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can save 2 bytes by changing your excel to Czech language, where MINVERSE -> INVERZE and OFFSET -> POZUN. \$\endgroup\$ – Sisyphus Oct 24 '20 at 3:37
3
\$\begingroup\$

MATL, 4 bytes

-1Y^

Try it online!

Explanation

-1Y^
-1   : Push -1 onto the stack
  Y^ : Raise implicit input to -1 power
\$\endgroup\$
3
\$\begingroup\$

Matlab 6 3 bytes

inv

Computes and prints the inverse of a square matrix. Pretty boring in-built solution. Thanks to @Bubbler for the clarification and -3 bytes.

\$\endgroup\$
2
  • \$\begingroup\$ We require submissions to be either a function or a full program, using one of the valid default I/O methods. Taking input in the form of a predefined variable makes the program a snippet, which is not allowed. I guess the built-in function submission inv is valid though. \$\endgroup\$ – Bubbler Oct 26 '20 at 5:57
  • \$\begingroup\$ Oh I see now. Then I can just use inv as a function. \$\endgroup\$ – Dmitry Kamenetsky Oct 26 '20 at 6:34
3
\$\begingroup\$

Charcoal, 48 bytes

≔Eθ∕Eθ§λκΣEXθ²ΣληFφUMηEκ⁻⊗μΣEθ×ΣEθקκς§ρπ§§ηπνIη

Try it online! Link is to verbose version of code. Explanation: Another port of @Sisyphus's answer.

≔Eθ∕Eθ§λκΣEXθ²Σλη

Transpose the input and divide it by the sum of squares of all the elements. Sadly neither sum nor divide fully vectorise, so I have to divide a row at a time and calculate the sum via a nested loop.

Fφ

Repeat 1000 times, which should be enough for floating-point precision.

UMηEκ⁻⊗μΣEθ×ΣEθקκς§ρπ§§ηπν

Calculate the matrix multiplication and subtraction in-place. Charcoal doesn't have any vector or matrix operations, so we have to loop over the rows and columns manually, but there are a couple of places where we can share variables which saves us a couple of bytes each.

Iη

Output the array. (Note that each element is output on its own line and each row is double-spaced from the previous.)

\$\endgroup\$
2
\$\begingroup\$

SageMath, 14 13 11 bytes

Saved a byte thanks to FryAmTheEggman!!!
Saved 2 bytes thanks to Sisyphus!!!

lambda M:~M

Try it online!

Inputs any square matrix and returns its inverse.

\$\endgroup\$
4
  • \$\begingroup\$ I think you can use (-1).__rpow__ instead? \$\endgroup\$ – FryAmTheEggman Oct 21 '20 at 0:05
  • \$\begingroup\$ @FryAmTheEggman Sweet - thanks! :-) \$\endgroup\$ – Noodle9 Oct 21 '20 at 0:29
  • \$\begingroup\$ lambda M:~M should be even shorter. \$\endgroup\$ – Sisyphus Oct 21 '20 at 7:59
  • \$\begingroup\$ @Sisyphus Very nice - thanks! :D \$\endgroup\$ – Noodle9 Oct 21 '20 at 10:24
1
\$\begingroup\$

Ruby -rmatrix, 23 19 bytes

->a{Matrix[*a].inv}

Try it online!

Returns the result as a Ruby matrix object.

-4 bytes from Dingus.

\$\endgroup\$
1
  • \$\begingroup\$ You can shorten inverse to inv. \$\endgroup\$ – Dingus Oct 21 '20 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.