# Totally Invertible Submatrices

(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]]

• Where is the singular submatrix in 2 6 3; 1 12 2; 5 3 1? – feersum Oct 24 '16 at 19:26
• @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. – AdmBorkBork Oct 24 '16 at 19:43
• At first, I thought the title said "totally invertible submarines". – user2357112 Oct 24 '16 at 21:56

# 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Ç€€Ȧ


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

• I was thinking I needed it because I have a bunch of combinations, but no I do not need to instruct to explicitly. Thanks! – Jonathan Allan Oct 24 '16 at 21:17
• I learned about it from that last challenge using determinants, and verified that it indeed does have ldepth = 2 in the source – miles Oct 24 '16 at 21:18
• Also I think you can save a byte in link 2 using ZœcLÆḊ and another byte in the main link by çÐ€JȦ – miles Oct 25 '16 at 6:35
• 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 Ð€. – Jonathan Allan Oct 25 '16 at 6:49
• Nice combining, I think you can make it a one liner if you want with œcÐ€JµZœcLÆḊµ€€Ȧ which is also 16 bytes – miles Oct 25 '16 at 7:10

# Mathematica 10.0, 34 bytes

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


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

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