6
\$\begingroup\$

Task

Given is a square matrix of any dimension and any integer n.

Output all possible matrices(without duplicates) by removing columns and rows from the input matrix such that the determinant of these new matrices is n.

Rules

Output should include original if determinant of original is n.

Output should be all the chopped off matrices. In case no output matrix is possible, return 0 or None or anything similar.

The input matrix will be at least of size 2x2 and all elements will be integers.

If n=1 empty matrix must also be in the output.

Test Cases

inputs:
[[1,0,5],
[1,0,5],
[1,2,4]],2

[[1, 3, 5],
[1, 3, 5],
[1, 45, 4]],0

[[1, 22, 5, 4],
[1, 3, 5, 5],
[1, 45, 4, 6],
[3, 4, 1, 4]],5

[[1, 22, 5, 4],
[1, -32, 51, 5],
[1, 45, 9, 0],
[3, 4, -1, -6]],-54

[[1, 22, 5, 4],
[1, -32, 51, 5],
[1, 45, 9, 0],
[3, 4, -1, -6]],1

outputs:
[[[2]], [[1, 0], [1, 2]]]

[[[1, 3], [1, 3]], [[1, 5], [1, 5]], [[3, 5], [3, 5]], [[1, 3, 5], [1, 3, 5], [1, 45, 4]]]

[[[5]], [[5, 4], [5, 5]]]

[[[1, 22], [1, -32]], [[9, 0], [-1, -6]]]

[[], [[1]], [[1, 4], [1, 5]]]

The shortest code wins.

\$\endgroup\$
  • 2
    \$\begingroup\$ +1 for making me think about why the determinant of the empty matrix really should be 1. \$\endgroup\$ – ngm Nov 13 '18 at 19:43
5
\$\begingroup\$

Jelly, 20 16 bytes

ZŒPZœcLƊ€ẎQÆḊ⁼¥Ƈ

Try it online!

Challenge finished. Unfortunately, my brain wasn't in its best mood, so Dennis pushed it until I finally managed to get here (you can see how it went). ~1 hour.

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

JavaScript (ES6), 246 238 196 192 bytes

Credits: the function \$D\$ is derived from this answer by edc65.

Takes input as (integer)(matrix). Prints the results to the console.

d=>g=m=>(F=(a,i)=>a.filter(_=>i--),m.map((_,i)=>m.map((_,j)=>g(F(m,i).map(r=>F(r,j))))),D=m=>m+m?m.reduce((n,[r],i)=>n+(i&1?-r:r)*D(F(m,i).map(r=>F(r,0))),0):1)(m)-d||g[m]||console.log(g[m]=m)

Try it online!

How?

Removing rows and columns

The helper function \$F\$ creates a copy of a given array \$a\$ with the \$i^\text{th}\$ item removed (0-indexed).

F = (a, i) => a.filter(_ => i--)

Computing the determinant

The recursive function \$D\$ computes the determinant of a matrix \$m\$, using Laplace expansion.

D = m =>                       // m = matrix
  m + m ?                      // if the matrix is not empty:
    m.reduce((n, [r], i) =>    //   for each value r at (0, i):
      n                        //     take the previous sum n
      + (i & 1 ? -r : r)       //     using the parity of i, either add or subtract r
      * D(                     //     multiplied by the result of a recursive call:
        F(m, i)                //       using m with the i-th row removed
        .map(r => F(r, 0))     //       and the first column removed
      ),                       //     end of recursive call
      0                        //     start with n = 0
    )                          //   end of reduce()
  :                            // else (the matrix is empty):
    1                          //   determinant = 1

Example:

$$m=\begin{bmatrix}\color{red}1&\color{red}2&\color{red}3\\\color{green}4&\color{green}5&\color{green}6\\\color{blue}7&\color{blue}8&\color{blue}9\end{bmatrix}$$

First iteration:

$$|m|= \color{red}1\times\left|\begin{bmatrix}\color{green}5&\color{green}6\\\color{blue}8&\color{blue}9\end{bmatrix}\right| -\color{green}4\times\left|\begin{bmatrix}\color{red}2&\color{red}3\\\color{blue}8&\color{blue}9\end{bmatrix}\right| +\color{blue}7\times\left|\begin{bmatrix}\color{red}2&\color{red}3\\\color{green}5&\color{green}6\end{bmatrix}\right|$$

which eventually leads to:

$$1\times(5\times9-8\times6)-4\times(2\times9-8\times3)+7\times(2\times6-5\times3) = 0$$

Main function

We recursively remove rows and columns from the original matrix \$m\$ and invoke \$D\$ on all resulting matrices, printing those whose determinant is equal to the expected value \$d\$.

d =>                           // d = expected determinant value
  g = m =>                     // g = recursive function taking the matrix m,
    (                          //     also used to store valid matrices
      m.map((_, i) =>          // for each i in [0 ... m.length - 1]:
        m.map((_, j) =>        //   for each j in [0 ... m.length - 1]:
          g(                   //     do a recursive call with:
            F(m, i)            //       the i-th row of m removed
            .map(r => F(r, j)) //       the j-th column of m removed
          )                    //     end of recursive call
        )                      //   end of inner map()
      ),                       // end of outer map()
      D                        // invoke D ...
    )(m)                       // ... on m
    - d                        // provided that the result is equal to d
    || g[m]                    // and provided that this matrix was not already printed,
    || console.log(g[m] = m)   // print m and store it in the underlying object of g
\$\endgroup\$
2
\$\begingroup\$

R, 129 bytes

f=function(m,n,o={},z=nrow(m)){for(i in r<-1:z)for(j in r)o=c(o,if(round(det(m))==n)list(m),if(z)f(m[-i,-j,drop=F],n));unique(o)}

Try it online!

Recursive function returning a list of submatrices. Outputs NULL for no solution. It is a bit unfortunate that the determinant value has to be explicitly rounded (otherwise some tests fail due to numerical imprecision), but at least we have a built-in for calculating it.

\$\endgroup\$
  • \$\begingroup\$ Here's a case where the growing object o seems like it must be explicitly initialized to NULL and the built-in abuse of F or T won't work. \$\endgroup\$ – ngm Nov 14 '18 at 19:11

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.