Recursive 2x2 determinant

Question

The determinant of a 2 by 2 matrix

a b
c d

is given by ad - bc.

Given a matrix of digits with dimensions 2ⁿ by 2ⁿ, n ≥ 1, output the result obtained by recursively computing the determinant of each 2 by 2 sub-block until we reach a single number.

For example, given the input

After one step, we obtain:

(3*9 - 1*5)    (4*6 - 1*2)    =    22  22
(5*7 - 3*9)    (5*3 - 8*9)         8  -57

And iterating once more, we get:

(22*-57 - 22*8) = -1430

Hence, the output should be -1430.

Rules

The elements of the matrix will always be single digit integers, i.e. 0 to 9.
You may take input in any convenient list or string format, as long as no preprocessing of data is done. Since the matrix is always square, you may take input as a single 1D list instead of a 2D list if you wish.
Input can be via function input, STDIN, command-line argument or closest alternative.
Output should be a single integer to function output, STDOUT or closest alternative. You may not output the single integer in a list or matrix.
You may use builtin determinant and matrix manipulation methods if your language happens to support them.
Your algorithm must work in theory for any valid input.
Standard code-golf rules apply.

Test cases

The following test cases are given as Python-style lists:

[[1,0],[0,1]] -> 1
[[1,9],[8,4]] -> -68
[[0,1,2,3],[4,5,6,7],[8,9,0,1],[2,3,4,5]] -> 40
[[3,1,4,1],[5,9,2,6],[5,3,5,8],[9,7,9,3]] -> -1430
[[9,0,0,9],[0,9,9,0],[9,0,9,0],[0,9,0,9]] -> 13122
[[1,0,0,0,0,0,0,0],[2,1,0,0,0,0,0,0],[3,2,1,0,0,0,0,0],[4,3,2,1,0,0,0,0],[5,4,3,2,1,0,0,0],[6,5,4,3,2,1,0,0],[7,6,5,4,3,2,1,0],[8,7,6,5,4,3,2,1]] -> 1
[[7,1,0,5,8,0,1,5],[9,9,6,6,1,2,4,8],[4,8,7,3,8,7,4,7],[4,6,1,9,7,0,1,7],[7,6,7,1,9,4,1,6],[8,0,0,8,5,5,9,9],[4,6,4,8,9,4,8,6],[9,0,8,7,6,2,1,5]] -> 2937504
[[1,2,3,4,5,6,7,8],[2,3,4,5,6,7,8,1],[3,4,5,6,7,8,1,2],[4,5,6,7,8,1,2,3],[5,6,7,8,1,2,3,4],[6,7,8,1,2,3,4,5],[7,8,1,2,3,4,5,6],[8,1,2,3,4,5,6,7]] -> -10549504
[[1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0],[0,1,1,1,1,0,0,1,0,1,1,1,1,1,1,0],[1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,0],[0,1,1,1,1,0,0,0,0,1,1,1,1,1,0,1],[1,0,1,0,1,1,1,0,0,1,1,1,1,0,1,0],[0,0,1,1,1,0,1,1,1,1,1,1,1,0,0,0],[1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1],[1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1],[1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1],[0,1,1,1,1,1,1,1,1,0,0,1,0,1,0,1],[1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,1,0,1,1,0,1,1,1,1,1,0,0,1,1,0],[1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,0,1,0,0,1,0,1,0,1,1,1,1,1,0,1],[1,1,1,1,1,1,1,1,1,0,0,1,1,1,0,1]] -> -8

(Thanks to @MartinBüttner for help with this challenge)

Fun fact: I ran some experiments on this and there is a surprisingly large number of binary matrices with non-zero recursive determinant. For sizes 2x2, 4x4, 8x8, 16x16, we get 6, 16488, 2229617029168687104, 3349795881591711813037585032680117995553655026185547430764970842694019448832 matrices with non-zero determinant which corresponds to 37.5%, 25.1587%, 12.0868%, 2.89294%, respectively. — Martin Ender, Commented Feb 9, 2016 at 14:20
@MartinBüttner: I get 6, 22560, 10160459763342013440, ... which matches A055165. — Charles, Commented Feb 9, 2016 at 18:36
@MartinBüttner: Possibly we're just computing two different things? — Charles, Commented Feb 9, 2016 at 18:49
@Charles Consider the matrix [1,0,1,0;1,1,1,1;1,1,1,1;0,0,0,1]. The full determinant of it is zero since it has two identical rows. This one is therefore a singular (meaning non-invertible) 4×4 matrix, so it is not counted by A055165. However, the "recursive" determinant discussed here is 1*1-1*0==1. In the opposite direction, the matrix [0,0,0,1;1,0,0,0;0,1,0,0;0,0,1,0] has "recursive" determinant 0*0-0*0==0. However, its full determinant must be non-zero because its rows is just the rows of the identity matrix in another order; and it is counted by A055165. — Jeppe Stig Nielsen, Commented Oct 10, 2017 at 22:05

randomra · Accepted Answer · 2016-02-09 20:34:13Z

8

J, 21 25 bytes

0{0{(_2(_2-/ .*\|:)\])^:_

Usage:

   ]input=.(3,1,4,1),(5,9,2,6),(5,3,5,8),:(9,7,9,3)
3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3
   (0{0{(_2(_2-/ .*\|:)\])^:_) input
_1430

At every step we cut up the matrix to 2-by-2's and compute each ones determinant resulting in the next step's input matrix. We repeat this process until the result doesn't change (the final element is the determinant itself). We convert the final result to a scalar with 0{0{.

Try it online here.

edited Feb 9, 2016 at 20:34

answered Feb 9, 2016 at 14:04

randomra

20.9k4 gold badges46 silver badges110 bronze badges

\$\begingroup\$ Tried using Cut's tiling function to do this, but wasn't able to golf it as far as your version. 29 bytes: (2 2$2)&(-/ .*;._3^:(2^.#@])) Try it online! \$\endgroup\$
– Jonah
Commented Oct 13, 2017 at 4:19

Add a comment |

njpipeorgan · Accepted Answer · 2016-02-09 23:14:59Z

5

Mathematica, 52 40 bytes

Thanks to Martin Büttner for saving 12 bytes.

Tr[#//.l:{_,__}:>BlockMap[Det,l,{2,2}]]&

Explanation

BlockMap[f,expr,n] split expr into sublists of size n and map f on every sublists. BlockMap[Det,#,{2,2}]& split the input array into 2*2 blocks and calculate their determinants.

Test case

%[{{3,1,4,1},{5,9,2,6},{5,3,5,8},{9,7,9,3}}]
(* -1430 *)

edited Feb 9, 2016 at 23:14

answered Feb 9, 2016 at 12:01

njpipeorgan

3,10214 silver badges15 bronze badges

1

\$\begingroup\$ I wrote a reference implementation in Mathematica while discussing the challenge idea with Sp3000 and it's 40 bytes. It's pretty similar to yours though, so I'll give you some time to find it yourself if you like. :) \$\endgroup\$
– Martin Ender
Commented Feb 9, 2016 at 12:38
\$\begingroup\$ @MartinBüttner I failed. :( \$\endgroup\$
– njpipeorgan
Commented Feb 9, 2016 at 12:55
1

\$\begingroup\$ You can avoid the [[1,1]] with Tr and the Nest with //.: Tr[#//.l:{_,__}:>BlockMap[Det,l,{2,2}]]& \$\endgroup\$
– Martin Ender
Commented Feb 9, 2016 at 21:15
\$\begingroup\$ @MartinBüttner Actually, I came up with //. idea when reading the answer in J, but stuck in finding a good way to match the array. :P \$\endgroup\$
– njpipeorgan
Commented Feb 9, 2016 at 23:08
\$\begingroup\$ feel free to use my solution to update your answer \$\endgroup\$
– Martin Ender
Commented Feb 9, 2016 at 23:09

Add a comment |

Dennis · Accepted Answer · 2016-02-09 19:11:18Z

Jelly, 20 17 bytes

s€2s2U×¥/€ḅ-µL¡SS

Try it online! or verify all test cases at once.

How it works

s€2s2U×¥/€ḅ-µL¡SS  Main link. Input: M (matrix)

s€2                Split each row of M into pairs.
   s2              Split the result into pairs of rows.
        /€         Reduce each pair...
       ¥             by applying the following, dyadic chain:
     U                 Reverse each pair of the left argument (1st row).
      ×                Multiply element-wise with the right argument (2nd row).
          ḅ-       Convert each resulting pair from base -1 to integer.
                   This maps [a, b] -> b - a.
            µ      Turn the previous links into a monadic chain. Begin a new one.
             L     Yield the length of the input.
              ¡    Execute the previous chain L times.
                   log2(L) times would do, but who's counting?
               SS  Sum twice to turn the resulting 1x1 matrix into a scalar.

colossus16 · Accepted Answer · 2017-10-11 13:06:45Z

Haskell, 93 86 bytes

EDIT: Thanks to @Laikoni for shortening this a whole 7 bytes!

f[[a,b],[c,d]]=a*d-b*c
f m|let l=[take,drop]<*>[div(length m)2]=f[f.($b<$>m)<$>l|b<-l]

I didn't know you could put a let statement before the = and I've never gotten used to those monad operators. Thanks again @Laikoni

Old version:

f[[a,b],[c,d]]=a*d-b*c
f m=f[[f$a$map b m|a<-l]|b<-l]where h=length m`div`2;l=[take h,drop h]

Try it online!

This is a function that recurs on itself in two different ways. First the pattern matching catches the the base case: a 2x2 matrix and it does the calculation. I use this to do the calculation in the recursive case by calling the function with a 2x2 matrix I generate that has the recursive solutions in it. That matrix is generated by iterating twice over an array of functions that each chop a list in half. I apply it to rows with a simple call and apply it to columns using map.

Instead of where h=length m`div`2;l=[take h,drop h], you can use f m|let l=[take,drop]<*>[length m`div`2]=. map b m can be b<$>m, and [f$a$b<$>m|a<-l] can be further shortened to f.($b<$>m)<$>l. Altogether 86 bytes: [tio.run/… Try it online!] — Laikoni, Commented Oct 11, 2017 at 12:35

Razetime · Accepted Answer · 2020-11-02 04:50:04Z

MATL, 30 26 bytes

`tnX^teHHhZC2Ih2#Y)pwp-tnq

Input is a 2D array with rows separated by ;, that is,

[3 1 4 1; 5 9 2 6; 5 3 5 8; 9 7 9 3]

Try it online!

`             % do...while loop
  tnX^te      %   reshape into square matrix. Implicitly asks for input the first time
  HHhZC       %   transform each 2x2 block into a column
  2Ih2#Y)     %   push matrix with rows 2,3, and also matrix with remaining rows (1,4)
  pwp-        %   multiplications and subtraction to compute the 2x2 determinants
  tnq         %   condition of do...while loop: is number of elements greater than 1?
              % implicitly end loop
              % implicitly display

basile-henry · Accepted Answer · 2016-02-09 14:15:35Z

1

Python, 166 bytes

def f(m):l=len(m)/2;g=lambda x,y:[(s[:l],s[l:])[x]for s in(m[:l],m[l:])[y]];return f(g(0,0))*f(g(1,1))-f(g(0,1))*f(g(1,0)) if l>1 else m[0][0]*m[1][1]-m[1][0]*m[0][1]

This passes all the test cases provided. m has to be a 2D array (like in the test cases), g selects the sub matrix.

answered Feb 9, 2016 at 14:15

basile-henry

3811 silver badge5 bronze badges

Add a comment |

FryAmTheEggman · Accepted Answer · 2016-02-09 14:38:16Z

Pyth, 26

M-F*VG_HhhumgMCcR2dcG2llQQ

Test Suite

This has two parts: M-F*VG_H redefines the function g to calculate the determinant of a two by two matrix. This saves bytes even though we only use it once because it unpacks the two rows.

The other part is a large reduce statement that we call log_2( len( input() ) ) times. Unfortunately, performing a step in the reduction on a 1 by 1 matrix causes the result to be wrapped in a list, so we don't get a fixed point. The reduce is mostly just splitting up the matrix to get 2 by 2 matrices and then applying g.

Xcali · Accepted Answer · 2017-10-12 22:28:45Z

1

Perl 5, 120 + 1 (`-a`) = 121 bytes

while($#F){@r=();for$i(@o=0..($l=sqrt@F)/2-1){push@r,$F[$k=$i*$l*2+2*$_]*$F[$k+$l+1]-$F[$k+$l]*$F[$k+1]for@o}@F=@r}say@F

Try it online!

Takes the input as a list of space separated numbers.

answered Oct 12, 2017 at 22:28

Xcali

15.7k2 gold badges15 silver badges39 bronze badges

Add a comment |

Neil · Accepted Answer · 2016-02-10 00:20:01Z

0

ES6, 91 bytes

(a,x=0,y=0,w=a.length)=>(w>>=1)?f(a,x,y,w)*f(a,x+w,y+w,w)-f(a,x,y+w,w)*f(a,x+w,y,w):a[x][y]

Straightforward recursive solution.

answered Feb 10, 2016 at 0:20

Neil

174k12 gold badges73 silver badges277 bronze badges

Add a comment |

Giuseppe · Accepted Answer · 2017-10-10 23:19:44Z

0

R, 111 bytes

f=function(m)"if"((n=nrow(m))-2,f(matrix(c(f(m[x<-1:(n/2),x]),f(m[y<-x+n/2,x]),f(m[x,y]),f(m[y,y])),2)),det(m))

Try it online!

Takes input as an R matrix (which is converted by the function in the header).

answered Oct 10, 2017 at 23:19

Giuseppe

28.8k3 gold badges31 silver badges104 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

Groovy, 221 189 bytes (At this point, could've used Java)

f={x->b=x.size();c=b/2-1;a=(0..c).collect{i->(0..c).collect{j->z=x.toList().subList(i*2,i*2+2).collect{it.toList().subList(j*2,j*2+2)};z[0][0]*z[1][1]-z[0][1]*z[1][0];}};a.size()==1?a:f(a)}

Old crappy version, which might as well be Java (221 bytes):

f={x->b=x.size();a=new int[b/2][b/2];for(i=0;i<b-1;i+=2){for(j=0;j<b-1;j+=2){z=x.toList().subList(i,i+2).collect{it.toList().subList(j,j+2)};a[(int)(i/2)][(int)(j/2)]=z[0][0]*z[1][1]-z[0][1]*z[1][0];}};a.size()==1?a:f(a)}

Ungolfed code:

f=
{x->
  b=x.size();
  int[][]a=new int[b/2][b/2];
  for(i=0;i<b-1;i+=2) {
    for(j=0;j<b-1;j+=2) {
      z=x.toList().subList(i,i+2).collect{
        it.toList().subList(j,j+2)
      };
      a[(int)(i/2)][(int)(j/2)]=z[0][0]*z[1][1]-z[0][1]*z[1][0];
    }
  }
  a.size()==1
    ?
      a:f(a)
}

Razetime · Accepted Answer · 2020-11-02 04:49:02Z

0

Husk, 25 bytes

ω(m(moF`-Fz*C2z*:1İ_)TmC2

Try it online!

The testcases in this one are great.

answered Nov 2, 2020 at 4:49

Razetime

27.4k3 gold badges29 silver badges72 bronze badges

Add a comment |

Stack Exchange Network

Recursive 2x2 determinant

Rules

Test cases

12 Answers 12

J, 21 25 bytes

Mathematica, 52 40 bytes

Jelly, 20 17 bytes

How it works

Haskell, 93 86 bytes

MATL, 30 26 bytes

Python, 166 bytes

Pyth, 26

Perl 5, 120 + 1 (`-a`) = 121 bytes

ES6, 91 bytes

R, 111 bytes

Groovy, 221 189 bytes (At this point, could've used Java)

Husk, 25 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
arithmetic
linear-algebra
matrix
or ask your own question.

Hot Network Questions

Recursive 2x2 determinant

Rules

Test cases

12 Answers 12

J, 21 25 bytes

Mathematica, 52 40 bytes

Jelly, 20 17 bytes

How it works

Haskell, 93 86 bytes

MATL, 30 26 bytes

Python, 166 bytes

Pyth, 26

Perl 5, 120 + 1 (-a) = 121 bytes

ES6, 91 bytes

R, 111 bytes

Groovy, 221 189 bytes (At this point, could've used Java)

Husk, 25 bytes

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

Perl 5, 120 + 1 (`-a`) = 121 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
arithmetic
linear-algebra
matrix
or ask your own question.