# Recursive 2x2 determinant

The determinant of a 2 by 2 matrix

``````a b
c d
``````

is given by `ad - bc`.

Given a matrix of digits with dimensions 2n by 2n, 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

``````3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3
``````

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 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 Feb 9 at 14:20
@MartinBüttner: I get 6, 22560, 10160459763342013440, ... which matches A055165. – Charles Feb 9 at 18:36
@Charles odd, I'll check my code – Martin Ender Feb 9 at 18:43
@MartinBüttner: Possibly we're just computing two different things? – Charles Feb 9 at 18:49

# 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.

-

# Jelly, 20 17 bytes

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

### 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.
``````
-

# 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 *)
``````
-
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. :) – Martin Ender Feb 9 at 12:38
@MartinBüttner I failed. :( – njpipeorgan Feb 9 at 12:55
You can avoid the `[[1,1]]` with `Tr` and the `Nest` with `//.`: `Tr[#//.l:{_,__}:>BlockMap[Det,l,{2,2}]]&` – Martin Ender Feb 9 at 21:15
@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 – njpipeorgan Feb 9 at 23:08
feel free to use my solution to update your answer – Martin Ender Feb 9 at 23:09

# 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.

-

# 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`.

-

# MATL, 26 30 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
``````
-

## 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.

-