(inspiriert von dieser Frage über Mathe)

Die Definitionen

Gegeben eine n x nquadratische Matrix A , können wir es nennen , invertiblewenn es etwas gibt n x nquadratische Matrix B , so dass AB = BA = I _n , mit I _n die Identitätsmatrix der Größe zu sein n x n(die Matrix mit den Hauptdiagonalen 1s und alles andere 0) und AB und BA repräsentieren die übliche Matrixmultiplikation (ich werde hier nicht darauf eingehen - nehmen Sie eine lineare Algebra-Klasse).

Daher können wir eine m x nMatrix C nennen, totally invertible wenn jede k x k(unten definierte) Submatrix von C für alle invertierbar k > 1ist k <= (smaller of m,n).

Eine Submatrix wird als die resultierende Matrix definiert, nachdem eine beliebige Anzahl von Zeilen und / oder Spalten aus der ursprünglichen Matrix gelöscht wurde. Beispielsweise kann die folgende 3x3Matrix C in eine 2x2Untermatrix C 'umgewandelt werden, indem die erste Zeile 1 2 3und die mittlere Spalte 2 5 8wie folgt entfernt werden:

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

Beachten Sie, dass es viele verschiedene Submatrix-Möglichkeiten gibt. Die obigen sind nur ein Beispiel. Diese Herausforderung betrifft nur diejenigen, bei denen die resultierende Untermatrix eine k x k quadratische Matrix ist .

Die Herausforderung

Bestimmen Sie anhand einer Eingabematrix, ob diese vollständig invertierbar ist oder nicht.

Die Eingabe

• Eine einzelne Größenmatrix m x nin jedem geeigneten Format .
• Ohne Verlust der Allgemeinheit können Sie davon ausgehen m <= nm >= n Einschränkung oder , was für Ihren Code besser geeignet ist, und die Eingabe auf diese Weise vornehmen (dh Sie erhalten eine kostenlose Transponierungsoperation, wenn Sie dies wünschen).
• Die Größe der Eingabematrix ist nicht kleiner als 3 x 3und nicht größer als Ihre Sprache.
• Die Eingabematrix besteht nur aus numerischen Werten von Z ⁺ (den positiven ganzen Zahlen ).

Die Ausgabe

• Ein wahrer / falscher Wert, der angibt , ob die Eingabematrix vollständig invertierbar ist.

Die Regeln

• Es ist entweder ein vollständiges Programm oder eine Funktion zulässig.
• Standardlücken sind verboten.
• Dies ist Codegolf, daher gelten alle üblichen Golfregeln, und der kürzeste Code (in Byte) gewinnt.

Die Beispiele

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

Jelly , 26 24 23 20 19 17 16 Bytes

-1 Byte dank @miles (für jedes unnötig €, wenn Determinanten genommen werden)
-2 Byte, wieder @miles! (unnötige kettentrennung und verwendung von Ѐquick)

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

TryItOnline! oder alle 8 Tests

Wie?

œ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

Mathematica 10.0, 34 Bytes

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

Eine 6-Tilde-Kette ... neuer persönlicher Rekord!

MATL, 57 Bytes

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

Natürlich können Sie es online ausprobieren!

Die Eingabe sollte im Hochformat erfolgen (nRows> = nColumns). Ich bin der Meinung, dass dies möglicherweise nicht die effizienteste Lösung ist ... Aber zumindest lasse ich einigen Spielraum für andere, um mich zu übertreiben. Ich würde gerne spezielle Hinweise hören, die diesen bestimmten Ansatz hätte verkürzen können, aber ich denke, dieser massive Bytecount sollte andere dazu inspirieren, einen MATL-Eintrag mit einem völlig anderen Ansatz zu machen. Zeigt 0 an, wenn es falsch ist, oder einen massiven Wert, wenn es wahr ist (wird schnell zu Inf, wenn die Matrix zu groß ist; für 1 zusätzliches Byte könnte man H*durch H&Y(logisch und) ersetzen ). Ein paar Bytes gespart dank @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.