Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs

Dashboard
Notifications
Mark all as read
Challenges

Compute the determinant

+2
−0

Challenge

A simple challenge: Given a two-dimensional matrix (an array of arrays) of real numbers, compute the determinant.

The determinant of a matrix is a mathematical construct used in many applications, such as solving polynomial equations, identifying the invertibility of the matrix, and finding the scaling factor under a matrix transformation. For more information about it, see this Wikipedia entry.

There are a couple of different ways to compute the determinant, and it is up to you how you implement it.

For instance, you may compute it using the Laplace expansion, a recursive algorithm which goes

  1. Pick a row or column.
  2. Start with a sum of zero.
  3. For each entry of the row/column:
    1. Create a new matrix with the row and column of the entry removed. This new matrix is a square matrix of size one less that the original.
    2. Compute the determinant of that smaller matrix.
    3. Multiply that determinant by the entry.
    4. If the row index plus the column index is even[1], add it to the sum, otherwise, subtract it.
  4. The final sum is the determinant.

As an example, here is an ungolfed implementation along the first column.

function laplaceDet(matrix) {
	if (matrix.length === 1) return matrix[0][0];

	let sum = 0;
	for (let rowIndex = 0; rowIndex < matrix.length; ++rowIndex) {
		let minorMatrix = matrix.filter((_, index) => index !== rowIndex)
			          .map(row => row.slice(1));
		sum += ((-1) ** rowIndex) * matrix[rowIndex][0] * laplaceDet(minorMatrix);
	}
	return sum;
}

Try it online!

This is code-golf, so the program with the lowest byte-count wins!

Test cases

$$ \begin{aligned} \det\begin{bmatrix}1&0\\0&1\end{bmatrix}&=1 \\ \det\begin{bmatrix}1.5&2\\-3&4.5\end{bmatrix}&=12.75 \\ \det\begin{bmatrix}3&7\\1&-4\end{bmatrix}&=-19 \\ \det\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}&=1 \\ \det\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}&=0 \end{aligned} $$

In text form,

[[1,0],[0,1]] -> 1
[[1.5,2],[-3,4.5]] -> 12.75
[[3,7],[1,-4]] -> -19
[[1,0,0],[0,1,0],[0,0,1]] -> 1
[[1,2,3],[4,5,6],[7,8,9]] -> 0

  1. Note that it doesn't matter if it is 1-indexed or 0-indexed, as 1+1 and 0+0 are both the same parity. ↩︎

Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

1 comment thread

Trivial builtins (1 comment)

6 answers

+4
−0

CJam, 45 bytes

{:A_,{1$_,,.=:+\)/:CAff*A@zf{\f.*::+}..-}/;C}

This implementation is an anonymous block (~function). Online test suite.

Dissection

This implements the Faddeev-LeVerrier algorithm.

The objective is to calculate the coefficients $c_k$ of the characteristic polynomial of the $n\times n$ matrix $A$, $$\begin{eqnarray}p(\lambda)\equiv \det(\lambda I_{n}-A) = \sum_{k=0}^{n}c_{k}\lambda^{k}\end{eqnarray}$$ where, evidently, $c_n = 1$ and $c_0 = (-1)^n \det A$.

The coefficients are determined recursively from the top down, by dint of the auxiliary matrices $M$, $$\begin{aligned}M_{0}&\equiv 0&c_{n}&=1\qquad &(k=0)\\M_{k}&\equiv AM_{k-1}+c_{n-k+1}I\qquad \qquad &c_{n-k}&=-{\frac {1}{k}}\mathrm {tr} (AM_{k})\qquad &k=1,\ldots ,n~.\end{aligned}$$

The code never works directly with $c_{n-k}$ and $M_k$, but always with $(-1)^k c_{n-k}$ and $(-1)^{k+1}AM_k$, so the recurrence is $$\begin{eqnarray*}(-1)^k c_{n-k} &=& \frac1k \mathrm{tr} ((-1)^{k+1} AM_{k}) \\ (-1)^{k+2} AM_{k+1} &=& (-1)^k c_{n-k}A - A((-1)^{k+1}A M_k)\end{eqnarray*}$$

{               e# Define a block
  :A            e#   Store the input matrix in A
  _,            e#   Take the length of a copy
  {             e#     for i = 0 to n-1
                e#       Stack: (-1)^{i+2}AM_{i+1} i
    1$_,,.=:+   e#       Calculate tr((-1)^{i+2}AM_{i+1})
    \)/:C       e#       Divide by (i+1) and store in C
    Aff*        e#       Multiply by A
    A@          e#       Push a copy of A, bring (-1)^{i+2}AM_{i+1} to the top
    zf{\f.*::+} e#       Matrix multiplication
    ..-         e#       Matrix subtraction
  }/
  ;             e#   Pop (-1)^{n+2}AM_{n+1} (which incidentally is 0)
  C             e#   Fetch the last stored value of C
}
Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

+2
−0

Scala, 130 125 bytes

Saved 5 bytes by returning 1 like Hakerh400's great answer

def f(m:Seq[Seq[Double]]):Double=if(m.size<1)1 else(m.indices:\.0){(i,a)=>m(0)(i)*f(m.tail.map(r=>r.take(i)++r.drop(i+1)))-a}

Try it in Scastie!

A recursive function that uses the first row for the Laplace expansion. Explanation coming soon.

def f(m: Seq[Seq[Double]]): Double =
  if (m.size < 1) 1 //If it's empty, return 1
  else
    //Otherwise, fold right over [0..m.size-1]
    //The initial accumulator is 0.0
    (m.indices :\ .0) {
      (i, a) =>
        //Multiply the entry by
        m(0)(i) *
          //The determinant of the smaller matrix
          f(
            //Drop the first row
            m.tail.map(
              //And for each row r, drop column i (0-indexed)
              r => r.take(i) ++ r.drop(i + 1)
            )
          )
          //Subtract the accumulator from that to invert
          //its sign each time
          - a
    }
Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

+2
−0

Python 3.8 (pre-release), 106 bytes

f=lambda m:sum((-1)**i*m[0][i]*f([r[:i]+r[i+1:]for r in m[1:]])for i in range(len(m)))if m[1:]else m[0][0]

Try it online!

Here's an attempt at beating Quintec's answer. Only 78 more bytes to go!

Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

+2
−0

Haskell, 75 73 bytes

-2 bytes thanks to @user

f[]=1
f(x:y)=foldr(-)0$zipWith(\i->(*f[take i r++drop(i+1)r|r<-y]))[0..]x

Try it online!

Why does this post require moderator attention?
You might want to add some details to your flag.

1 comment thread

73 bytes (1 comment)
+1
−0

Python 3, 29 bytes

import numpy
numpy.linalg.det

Yeah, this is really boring, but I'm curious if this can be beat in Python.

Try it online!

Why does this post require moderator attention?
You might want to add some details to your flag.

2 comment threads

Your TIO link doesn't work (lol) (2 comments)
A determinant in 28 bytes or less without using numpy or other libraries? That's highly unlikely. (1 comment)
+1
−0

C, 147 bytes

float d(float**m,int r){if(r<2)return**m;int i=r,j;float s=0,*n[--r];for(;i--;s+=(i%2?-1:1)**m[i]*d(n,r))for(j=r;j--;)n[j]=m[j+(j>=i)]+1;return s;}

Try it online!

Basically a C version of my example code. Takes an array of pointers and the size.

Prettified and commented version:

float d(float **m, int r) {
	if(r < 2) return **m;  // Base case: 1x1 matrix

	int i = r, j;          // Variable initialization, i and j are counters
	float s = 0, *n[--r];  // s is the sum, n is the minor matrix

	for(; i--; s += (i % 2 ? -1 : 1) * *m[i] * d(n, r)) // Outer loop: loop over the rows of M.
	                                                    // After each iteration, add the term to the sum
		for(j = r; j--; )                           // Inner loop to fill in the minor matrix
			n[j] = m[j + (j >= i)] + 1;         // (j >= i) term skips over the ith row of M.
			                                    // Addition of 1 effectively removes the first element
	return s;
}

Try it online!

Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

Sign up to answer this question »

This community is part of the Codidact network. We have other communities too — take a look!

You can also join us in chat!

Want to advertise this community? Use our templates!