Total invertierbare Submatrizen

16

(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

Die Regeln

  • Es ist entweder ein vollständiges Programm oder eine Funktion zulässig.
  • Standardlücken sind verboten.
  • Dies ist 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]]
AdmBorkBork
quelle
Wo ist die singuläre Untermatrix 2 6 3; 1 12 2; 5 3 1?
Feersum
1
@feersum Whoops - danke für den Fang. Das hätte unter die Wahrheit fallen sollen, und das darunter sollte eine 6Ecke sein, nicht eine 7. Unbeholfene Tippfehler.
AdmBorkBork
Zuerst dachte ich, der Titel besagt "total invertierbare U-Boote".
user2357112 unterstützt Monica

Antworten:

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
Jonathan Allan
quelle
Ich dachte, ich brauche es, weil ich eine Reihe von Kombinationen habe, aber nein, ich muss nicht explizit anweisen. Vielen Dank!
Jonathan Allan
Ich habe es aus dieser letzten Herausforderung mit Hilfe von Determinanten gelernt und verifiziert, dass es tatsächlich ldepth = 2in der Quelle vorhanden ist
Meilen
1
Außerdem denke ich, dass Sie ein Byte in Link 2 mit ZœcLÆḊund ein weiteres Byte im Hauptlink mitçЀJȦ
Meilen
Gutes Zeug @ Meilen nochmals vielen Dank! Ich dachte, dass der erste von diesen beiden nicht funktioniert hat, als ich es ausprobiert habe, aber es muss gewesen sein, als ich den Golfspieler benutzt habe. Völlig vergessen Ѐ.
Jonathan Allan
2
Nizza Kombination, ich denke, Sie können es zu einem Einzeiler machen, wenn Sie wollen, mit œcЀJµZœcLÆḊµ€€Ȧdem auch 16 Bytes sind
Meilen
4

Mathematica 10.0, 34 Bytes

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

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

Feersum
quelle
3

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.
Sanchises
quelle