(zainspirowany tym pytaniem dotyczącym matematyki)

Definicje

Biorąc pod uwagę n x nmacierz kwadratowa , można nazwać Jeżeli istnieje jakiś macierzy kwadratowej B jest takie, że AB = BA = I _n , o , że _n jest macierzą jednostkową wielkości (matrycy z głównych ukośnych s do niczego innego ) i AB i BA reprezentujące zwykłe mnożenie macierzy (nie wchodzę w to tutaj - idź wziąć klasę algebry liniowej).invertiblen x nn x n10

Z tym, można nazwać m x nmacierzy C totally invertible , jeżeli każdy k x kpodmatryca (zdefiniowane niżej) w ° C jest odwracalny dla wszystkich k > 1, k <= (smaller of m,n).

Podmacierz jest definiowana jako macierz wynikowa po usunięciu dowolnej liczby wierszy i / lub kolumn z oryginalnej macierzy. Na przykład poniższą 3x3macierz C można przekształcić w 2x2submatrix C ' , usuwając pierwszy wiersz 1 2 3i środkową kolumnę 2 5 8w następujący sposób:

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

Zauważ, że istnieje wiele różnych możliwości submatriksów, powyższy jest tylko przykładem. To wyzwanie dotyczy tylko tych, w których wynikowa submatrix jest k x k macierzą kwadratową .

Wyzwanie

Biorąc pod uwagę macierz wejściową, określ, czy jest ona całkowicie odwracalna, czy nie.

Wejście

• Pojedyncza matryca rozmiaru m x nw dowolnym odpowiednim formacie .
• Bez utraty ogólności możesz założyć m <= nlub m >= n, w zależności od tego, który kod jest bardziej golfowy, i wziąć dane wejściowe w ten sposób (tzn. Możesz otrzymać operację transpozycji za darmo, jeśli chcesz).
• Rozmiar matrycy wejściowej nie będzie mniejszy niż 3 x 3i nie będzie większy niż Twój język.
• Macierz wejściowa będzie się składać tylko z wartości liczbowych z Z ⁺ ( dodatnie liczby całkowite ).

Wyjście

• Truthy / falsey wartość tego, czy matrycy wejściowej jest całkowicie odwracalna.

Zasady

• Dopuszczalny jest pełny program lub funkcja.
• Standardowe luki są zabronione.
• To jest golf golfowy, więc obowiązują wszystkie zwykłe zasady gry w golfa, a wygrywa najkrótszy kod (w bajtach).

Przykłady

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

Galaretka , 26 24 23 20 19 17 16 bajtów

-1 bajt dzięki @miles (niepotrzebne dla każdego €, przy przyjmowaniu wyznaczników)
-2 bajty, @miles ponownie! (niepotrzebne rozdzielenie łańcucha i użycie Ѐszybkiego)

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

TryItOnline! lub wszystkie 8 testów

W jaki sposób?

œ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 bajty

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

Łańcuch 6 tyld ... nowy osobisty rekord!

MATL, 57 bajtów

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

Oczywiście możesz wypróbować online!

Dane wejściowe powinny być w orientacji „pionowej” (nRows> = nColumns). Wydaje mi się, że to może nie być najskuteczniejsze rozwiązanie ... Ale przynajmniej zostawiam miejsce dla innych, aby mnie obezwładnić. Chciałbym usłyszeć konkretne wskazówki, które mogłyby skrócić to konkretne podejście, ale myślę, że ta ogromna liczba bajtów powinna zainspirować innych do wprowadzenia wpisu MATL z zupełnie innym podejściem. Wyświetlacze 0 jeśli falsy lub wartość masywne czy truthy (szybko się Inf jeśli matryca zbyt duże, 1 dodatkowy bajt, można wymienić H*z H&Ylogicznego (i)). Zaoszczędź kilka bajtów dzięki @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.