16
\$\begingroup\$

(inspired by this question over on Math)

The Definitions

Given an n x n square matrix A, we can call it invertible if there exists some n x n square matrix B such that AB = BA = In, with In being the identity matrix of size n x n (the matrix with the main diagonal 1s and anything else 0), and AB and BA representing usual matrix multiplication (I won't go into that here - go take a linear algebra class).

From that, we can call an m x n matrix C totally invertible if every k x k submatrix (defined below) of C is invertible for all k > 1, k <= (smaller of m,n).

A submatrix is defined as the resulting matrix after deletion of any number of rows and/or columns from the original matrix. For example, the below 3x3 matrix C can be transformed into a 2x2 submatrix C' by removing the first row 1 2 3 and the middle column 2 5 8 as follows:

C = [[1 2 3]
     [4 5 6]    -->  C' = [[4 6]
     [7 8 9]]              [7 9]]

Note that there are many different submatrix possibilities, the above is just an example. This challenge is only concerned with those where the resulting submatrix is a k x k square matrix.

The Challenge

Given an input matrix, determine if it is totally invertible or not.

The Input

  • A single matrix of size m x n, in any suitable format.
  • Without loss of generality, you can assume m <= n or m >= n, whichever is golfier for your code, and take the input that way (i.e., you get a transpose operation for free if you want it).
  • The input matrix size will be no smaller than 3 x 3, and no larger than your language can handle.
  • The input matrix will consist of only numeric values from Z+ (the positive integers).

The Output

  • A truthy/falsey value for whether the input matrix is totally invertible.

The Rules

  • Either a full program or a function are acceptable.
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

The Examples

Truthy

[[1 2 3]
 [2 3 1]
 [3 1 2]]

[[2 6 3]
 [1 12 2]
 [5 3 1]]

[[1 2 3 4]
 [2 3 4 1]
 [3 4 1 2]]

[[2  3  5  7  11]
 [13 17 19 23 29]
 [31 37 41 43 47]]


Falsey

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

[[1 6 2 55 3]
 [4 5 5 5  6]
 [9 3 7 10 4]
 [7 1 8 23 9]]

[[2 3 6]
 [1 2 12]
 [1 1 6]]

[[8 2 12 13 2]
 [12 7 13 12 13]
 [8 1 12 13 5]]
\$\endgroup\$
  • \$\begingroup\$ Where is the singular submatrix in 2 6 3; 1 12 2; 5 3 1? \$\endgroup\$ – feersum Oct 24 '16 at 19:26
  • 1
    \$\begingroup\$ @feersum Whoops - thanks for the catch. That was supposed to have gone under Truthy and the one below it was supposed to be a 6 in the corner, not a 7. Clumsy typos. \$\endgroup\$ – AdmBorkBork Oct 24 '16 at 19:43
  • \$\begingroup\$ At first, I thought the title said "totally invertible submarines". \$\endgroup\$ – user2357112 Oct 24 '16 at 21:56
5
\$\begingroup\$

Jelly, 26 24 23 20 19 17 16 bytes

-1 byte thanks to @miles (unnecessary for each, , when taking determinants)
-2 bytes, @miles again! (unnecessary chain separation, and use of Ѐ quick)

ZœcLÆḊ
œcЀJÇ€€Ȧ

TryItOnline! or all 8 tests

How?

œcЀJÇ€€Ȧ  - Main link: matrix as an array, M
    J      - range of length -> [1,2,...,len(a)] (n)
  Ѐ       - for each of right argument
œc         -     combinations of M numbering n
     Ç€€   - call the last link (1) as a monad for €ach for €ach
        Ȧ  - all truthy (any determinant of zero results in 0, otherwise 1)
                 (this includes an implicit flattening of the list)

ZœcLÆḊ - Link 1, determinants of sub-matrices: row selection, s
Z      - transpose s
   L   - length of s
 œc    - combinations of transposed s numbering length of s
    ÆḊ - determinant
\$\endgroup\$
  • \$\begingroup\$ I was thinking I needed it because I have a bunch of combinations, but no I do not need to instruct to explicitly. Thanks! \$\endgroup\$ – Jonathan Allan Oct 24 '16 at 21:17
  • \$\begingroup\$ I learned about it from that last challenge using determinants, and verified that it indeed does have ldepth = 2 in the source \$\endgroup\$ – miles Oct 24 '16 at 21:18
  • 1
    \$\begingroup\$ Also I think you can save a byte in link 2 using ZœcLÆḊ and another byte in the main link by çЀJȦ \$\endgroup\$ – miles Oct 25 '16 at 6:35
  • \$\begingroup\$ Good stuff @miles thanks again! I thought that the first of those two did not work when I tried it, but it must have been when I was using the you golfed off. Totally forgot about Ѐ. \$\endgroup\$ – Jonathan Allan Oct 25 '16 at 6:49
  • 2
    \$\begingroup\$ Nice combining, I think you can make it a one liner if you want with œcЀJµZœcLÆḊµ€€Ȧ which is also 16 bytes \$\endgroup\$ – miles Oct 25 '16 at 7:10
4
\$\begingroup\$

Mathematica 10.0, 34 bytes

#~Minors~n~Table~{n,Tr@#}~FreeQ~0&

A 6-tilde chain... new personal record!

\$\endgroup\$
3
\$\begingroup\$

MATL, 57 bytes

tZyt:Y@!"@w2)t:Y@!"@w:"3$t@:)w@:)w3$)0&|H*XHx]J)]xxtZy]H&

Of course, you can Try it online!

Input should be in 'portrait' orientation (nRows>=nColumns). I feel that this may not be the most efficient solution... But at least I'm leaving some room for others to outgolf me. I would love to hear specific hints that could have made this particular approach shorter, but I think this massive bytecount should inspire others to make a MATL entry with a completely different approach. Displays 0 if falsy, or a massive value if truthy (will quickly become Inf if matrix too large; for 1 extra byte, one could replace H* with H&Y (logical and)). Saved a few bytes thanks to @LuisMendo.

tZy  % Duplicate, get size. Note that n=<m.   
%   STACK:  [m n], [C]
t: % Range 1:m                           
%   STACK:  [1...m], [m n], [C]
Y@   % Get all permutations of that range. 
%   STACK:  [K],[m n],[C] with K all perms in m direction.
!"   % Do a for loop over each permutation.
%   STACK:  [m n],[C], current permutation in @.
@b   % Push current permutation. Bubble size to top.
%   STACK:  [m n],[pM],[C] with p current permutation in m direction.
2)t:Y@!" % Loop over all permutations again, now in n direction
%   STACK: [n],[pM],[C] with current permutation in @.
@w:" % Push current permutation. Loop over 1:n (to get size @ x @ matrices)
%   STACK: [pN],[pM],[C] with loop index in @.
3$t  % Duplicate the entire stack.
%   STACK: [pN],[pM],[C],[pN],[pM],[C]
@:)  % Get first @ items from pN
%   STACK: [pNsub],[pM],[C],[pN],[pM],[C]
w@:) % Get first @ items from pM
%   STACK: [pMsub],[pNsub],[C],[pN],[pM],[C]
w3$)  % Get submatrix. Needs a `w` to ensure correct order.
%   STACK: [Csub],[pN],[pM],[C]
0&|  % Determinant.
%   STACK: [det],[pN],[pM],[C]
H*XHx% Multiply with clipboard H.
%   STACK: [pN],[pM],[C]
]    % Quit size loop
%   STACK: [pN],[pM],[C]. Expected: [n],[pM],[C]
J)   % Get last element from pN, which is n.
%   STACK: [n],[pM],[C]
]    % Quit first loop
xxtZy% Reset stack to
%   STACK: [m n],[C]
]    % Quit final loop.
H& % Output H only.
\$\endgroup\$

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.