Biorąc pod uwagę kwadratową macierz liczb całkowitych jako dane wejściowe, wyprowadza wyznacznik macierzy.

Zasady

• Możesz założyć, że wszystkie elementy w macierzy, wyznacznik macierzy i całkowita liczba elementów w macierzy mieszczą się w reprezentatywnym zakresie liczb całkowitych dla twojego języka.
• Wyprowadzanie wartości dziesiętnej / zmiennoprzecinkowej z ułamkową częścią 0 jest dozwolone (np. 42.0Zamiast 42).
• Wbudowane są dozwolone, ale zachęcamy do dołączenia rozwiązania, które nie używa wbudowanych.

Przypadki testowe

[[42]] -> 42
[[2, 3], [1, 4]] -> 5
[[1, 2, 3], [4, 5, 6], [7, 8, 9]] -> 0
[[13, 17, 24], [19, 1, 3], [-5, 4, 0]] -> 1533
[[372, -152, 244], [-97, -191, 185], [-53, -397, -126]] -> 46548380
[[100, -200, 58, 4], [1, -90, -55, -165], [-67, -83, 239, 182], [238, -283, 384, 392]] -> 571026450
[[432, 45, 330, 284, 276], [-492, 497, 133, -289, -28], [-443, -400, 56, 150, -316], [-344, 316, 92, 205, 104], [277, 307, -464, 244, -422]] -> -51446016699154
[[416, 66, 340, 250, -436, -146], [-464, 68, 104, 471, -335, -442], [159, -407, 310, -489, -248, 370], [62, 277, 446, -325, 47, -193], [460, 460, -418, -28, 234, -374], [249, 375, 489, 172, -423, 125]] -> 39153009069988024
[[-246, -142, 378, -156, -373, 444], [186, 186, -23, 50, 349, -413], [216, 1, -418, 38, 47, -192], [109, 345, -356, -296, -47, -498], [-283, 91, 258, 66, -127, 79], [218, 465, -420, -326, -445, 19]] -> -925012040475554
[[-192, 141, -349, 447, -403, -21, 34], [260, -307, -333, -373, -324, 144, -190], [301, 277, 25, 8, -177, 180, 405], [-406, -9, -318, 337, -118, 44, -123], [-207, 33, -189, -229, -196, 58, -491], [-426, 48, -24, 72, -250, 160, 359], [-208, 120, -385, 251, 322, -349, -448]] -> -4248003140052269106
[[80, 159, 362, -30, -24, -493, 410, 249, -11, -109], [-110, -123, -461, -34, -266, 199, -437, 445, 498, 96], [175, -405, 432, -7, 157, 169, 336, -276, 337, -200], [-106, -379, -157, -199, 123, -172, 141, 329, 158, 309], [-316, -239, 327, -29, -482, 294, -86, -326, 490, -295], [64, -201, -155, 238, 131, 182, -487, -462, -312, 196], [-297, -75, -206, 471, -94, -46, -378, 334, 407, -97], [-140, -137, 297, -372, 228, 318, 251, -93, 117, 286], [-95, -300, -419, 41, -140, -205, 29, -481, -372, -49], [-140, -281, -88, -13, -128, -264, 165, 261, -469, -62]] -> 297434936630444226910432057

Galaretka , 15 bajtów

LŒ!ðŒcIṠ;ị"Pð€S

Wypróbuj online!

Jak to działa

LŒ!ðŒcIṠ;ị"Pð€S   input
L                 length
 Œ!               all_permutations
   ð        ð€    for each permutation:
    Œc                take all unordered pairs
      I               calculate the difference between
                      the two integers of each pair
       Ṡ              signum of each difference
                      (positive -> 1, negative -> -1)
        ;             append:
         ị"             the list of elements generated by taking
                        each row according to the index specified
                        by each entry of the permutation
           P          product of everything
              S   sum

Dlaczego to działa - wersja mathy

Operator det pobiera macierz i zwraca skalar. An n -by- n matrycy może być traktowana jako zbiór n wektorów o długości n , tak det jest bardzo funkcją wykonuje n wektorów z ℤ ⁿ i zwraca skalarnego.

Dlatego piszę det ( v ₁ , v ₂ , v ₃ , ..., v _n ) dla det [ v ₁ v ₂ v ₃ ... v _n ].

Zauważ, że det jest liniowy w każdym argumencie, tj. Det ( v ₁ + λ w ₁ , v ₂ , v ₃ , ..., v _n ) = det ( v ₁ , v ₂ , v ₃ , ..., v _n ) + λ det ( w ₁ , v ₂ , v ₃ , ..., v _n ). Dlatego jest to mapa liniowa z (ℤ ⁿ ) ^{⊗ n} do ℤ.

Wystarczy określić obraz podstawy pod mapą liniową. Podstawa (ℤ ⁿ ) ^{⊗ n} składa się z n- krotnych produktów tensorowych elementów podstawowych basis ⁿ , tj. E ₅ ⊗ e ₃ ⊗ e ₁ ⊗ e ₅ ⊗ e ₁ . Produkty tensorów, które zawierają identyczne tensory, muszą być wysłane do zera, ponieważ wyznacznikiem macierzy, w której dwie kolumny są identyczne, jest zero. Pozostaje sprawdzić, do jakich produktów tensorowych o odrębnych elementach podstawowych są wysyłane. Wskaźniki wektorów w produkcie tensorowym tworzą bijection, czyli permutację, w której parzyste permutacje są wysyłane do 1, a nieparzyste permutacje są wysyłane do -1.

Na przykład, aby znaleźć wyznacznik [[1, 2], [3, 4]]: zwróć uwagę, że kolumny to [1, 3] i [2, 4]. Rozkładamy [1, 3], aby dać (1 e ₁ + 3 e ₂ ) i (2 e ₁ + 4 e ₂ ). Odpowiednim elementem w produkcie tensorowym jest (1 e ₁ ⊗ 2 e ₁ + 1 e ₁ ⊗ 4 e ₂ + 3 e ₂ ⊗ 2 e ₁ + 3 e ₂ ⊗ 4 e ₂ ), do którego upraszczamy (2 e _{1 1} e ₁ + 4 e ₁ ⊗ e ₂ + 6 e ₂ ⊗ e ₁ + 12 e ₂ ⊗ e ₂). W związku z tym:

det [[1, 2], [3, 4]]
= det (1 e ₁ + 3 e ₂ , 2 e ₁ + 4 e ₂ )
= det (2 e ₁ ⊗ e ₁ + 4 e ₁ ⊗ e ₂ + 6 e ₂ ⊗ e ₁ + 12 e ₂ ⊗ e ₂ )
= det (2 e ₁ ⊗ e ₁ ) + det (4 e ₁ ⊗ e ₂ ) + det (6 e ₂ ⊗ e ₁ ) + det (12 e₂ ⊗ e ₂ )
= 2 det (e ₁ ⊗ e ₁ ) + 4 det (e ₁ ⊗ e ₂ ) + 6 det (e ₂ ⊗ e ₁ ) + 12 det (e ₂ ⊗ e ₂ )
= 2 (0) + 4 (1) + 6 (-1) + 12 (0)
= 4 - 6
= -2

Teraz pozostaje udowodnić, że wzór na znalezienie parzystości permutacji jest prawidłowy. Mój kod polega przede wszystkim na znalezieniu liczby inwersji, tj. Miejsc, w których element po lewej stronie jest większy niż element po prawej stronie (niekoniecznie kolejno).

Na przykład w permutacji 3614572 występuje 9 inwersji (31, 32, 61, 64, 65, 62, 42, 52, 72), więc permutacja jest nieparzysta.

Uzasadnieniem jest to, że każda transpozycja (zamiana dwóch elementów) albo dodaje jedną inwersję, albo usuwa jedną inwersję, zamieniając parytet liczby inwersji, a parzystość permutacji jest parzystością liczby transpozycji potrzebnych do uzyskania permutacji.

Podsumowując, naszą formułę podaje:

Dlaczego to działa - wersja niematyczna

gdzie σ jest permutacją 𝕊 _n grupa wszystkie kombinacje o n liter i sgn jest znakiem permutacji AKA (1) podnosi się do parzystości permutacji i _ij jest ( ij ) ^th wpisu macierz ( i w dół, j w poprzek).

R , 3 bajty

Trywialne rozwiązanie

det

Wypróbuj online!

R , 94 92 bajty

ponownie wdrożone rozwiązanie

rozegrany przez Jarko Dubbeldam

d=function(m)"if"(x<-nrow(m),m[,1]%*%sapply(1:x,function(y)(-1)^(y-1)*d(m[-y,-1,drop=F])),1)

Wypróbuj online!

Rekurencyjnie wykorzystuje ekspansję nieletnich w dół pierwszej kolumny matrycy.

f <- function(m){
 x <- nrow(m)                 # number of rows of the matrix
 if(sum(x) > 1){              # when the recursion reaches a 1x1, it has 0 rows
                              # b/c [] drops attributes
  minor <- function(y){
   m[y] * (-1)^(y-1) *
   d(m[-y,-1])                # recurse with the yth row and first column dropped
   }
  minors <- sapply(1:x,minor) # call on each row
  sum(minors)                 # return the sum
 } else {
  m                           # return the 1x1 matrix
 }
}

Galaretka , 16 15 12 10 bajtów

Ḣ×Zß-Ƥ$Ṛḅ-

Używa rozszerzenia Laplace'a . Dzięki @miles za grę w golfa z 3 5 bajtów!

Wypróbuj online!

Jak to działa

Ḣ×Zß-Ƥ$Ṛḅ-  Main link. Argument: M (matrix / 2D array)

Ḣ           Head; pop and yield the first row of M.
      $     Combine the two links to the left into a monadic chain.
  Z         Zip/transpose the matrix (M without its first row).
   ß-Ƥ      Recursively map the main link over all outfixes of length 1, i.e., over
            the transpose without each of its rows.
            This yields an empty array if M = [[x]].
 ×          Take the elementwise product of the first row and the result on the
            right hand. Due to Jelly's vectorizer, [x] × [] yields [x].
       Ṛ    Reverse the order of the products.
        ḅ-  Convert from base -1 to integer.
                [a]          -> (-1)**0*a
                [a, b]       -> (-1)**1*a + (-1)**0*b = b - a
                [a, b, c]    -> (-1)**2*a + (-1)**1*b + (-1)**0*c = c - b + a
                etc.

Wolfram Language (Mathematica) , od 14 do 42 bajtów

Mamy wbudowane 3-bajtowe i 53-bajtowe rozwiązanie, które całkowicie eliminuje wbudowane, więc oto niektóre dziwniejsze rozwiązania gdzieś pomiędzy.

Język Wolfram ma wiele bardzo intensywnych funkcji rozkładania macierzy na produkty innych macierzy o prostszej strukturze. Jednym z prostszych (co oznacza, że ​​słyszałem o tym wcześniej) jest rozkład Jordana. Każda macierz jest podobna do (prawdopodobnie złożonej) górnej macierzy trójkątnej wykonanej z bloków ukośnych o określonej strukturze, zwanej rozkładem Jordana tej macierzy. Podobieństwo zachowuje wyznaczniki, a wyznacznik macierzy trójkątnej jest iloczynem elementów ukośnych, więc możemy obliczyć wyznacznik na podstawie następujących 42 bajtów :

1##&@@Diagonal@Last@JordanDecomposition@#&

Wyznacznik jest również równy iloczynowi wartości własnych macierzy z wielokrotnością. Na szczęście funkcja wartości własnej Wolframa śledzi wielokrotność (nawet w przypadku matryc nieprzeznaczonych do przekątnej), więc otrzymujemy następujące 20-bajtowe rozwiązanie:

1##&@@Eigenvalues@#&

Kolejnym rozwiązaniem jest oszustwo i nie jestem pewien, dlaczego to działa. Wronskian listy n funkcji jest wyznacznikiem macierzy pierwszych pochodnych n -1 funkcji. Jeśli podamy Wronskianfunkcji macierz liczb całkowitych i powiedzmy, że zmienna różnicowania wynosi 1, to w jakiś sposób wypluwa wyznacznik macierzy. To dziwne, ale nie zawiera liter „ Det” i ma tylko 14 bajtów …

#~Wronskian~1&

(The Casoratian wyznacznikiem działa tak samo, przez 1 bajt więcej: #~Casoratian~1&)

W dziedzinie algebry abstrakcyjnej wyznacznikiem macierzy n  x  n (uważanej za mapę k → k, która jest mnożona przez wyznacznik) jest n- ta zewnętrzna moc macierzy (po wybraniu izomorfizmu k → ⋀ ⁿ k ⁿ ). W języku Wolfram możemy to zrobić za pomocą następujących 26 bajtów :

HodgeDual[TensorWedge@@#]&

A oto rozwiązanie, które działa tylko na pozytywne determinanty. Jeśli weźmiemy hipersześcian n- wymiarowej jednostki i zastosujemy do niego transformację liniową, to n- wymiarowa „objętość” regionu wynikowego jest wartością bezwzględną wyznacznika transformacji. Zastosowanie transformacji liniowej do kostki daje równoległościan i możemy pobrać jego objętość za pomocą 39 bajtów kodu:

RegionMeasure@Parallelepiped[Last@#,#]&

Haskell , 71 bajtów

-3 bajty dzięki Lynn. Kolejny bajtuje kurz dzięki Craig Roy.

f[]=1
f(h:t)=foldr1(-)[v*f[take i l++drop(i+1)l|l<-t]|(i,v)<-zip[0..]h]

Wypróbuj online! Dodano -Oflagę do celów optymalizacji. To nie jest konieczne.

Wyjaśnienie (nieaktualne)

f rekurencyjnie implementuje ekspansję kofaktora.

f[[x]]=x

Ta linia obejmuje podstawowy przypadek macierzy 1 × 1 , w którym to przypadku wyznacznikiem jest mat[0, 0].

f(h:t)=

Wykorzystuje dopasowanie wzoru Haskella do rozbicia matrycy na głowę (pierwszy rząd) i ogon (resztę matrycy).

          [                                     |(i,v)<-zip[0..]h]

Wyliczyć wierzchołek macierzy (zipując nieskończoną listę liczb całkowitych i głowę) i iterować nad nią.

           (-1)*i*v

Neguj wynik na podstawie tego, czy jego indeks jest nawet, ponieważ obliczanie wyznacznika obejmuje naprzemienne dodawanie i odejmowanie.

                     [take i l++drop(i+1)l|l<-t]

Ta zasadniczo usuwa i-tą kolumnę ogona poprzez : i elementów i łączenie go z szeregu z pierwszym (i + 1) -ej elementy spadła dla każdego rzędu w ogonie.

                   *f

Oblicz wyznacznik powyższego wyniku i pomnóż go przez wynik (-1)*i*v.

       sum

Zsumuj wynik z powyższej listy i zwróć ją.

Proton , 99 bajtów

f=m=>(l=len(m))==1?m[0][0]:sum((-1)**i*m[0][i]*f([[m[k][j]for k:1..l]for j:0..l if j-i])for i:0..l)

Wypróbuj online!

-3 bajty dzięki Mr. Xcoder
-3 bajty dzięki Erikowi Outgolfer

Rozszerzenie w pierwszym rzędzie

Oktawa , 28 bajtów

@(x)round(prod(diag(qr(x))))

Wypróbuj online!

This zastosowania rozkładu QR macierzy X w w orthgonal macierzy Q i górna matryca trójkątna R . Wyznacznik X jest produktem tych Q i R . Matryca ortogonalna ma wyznacznik jednostki, a dla macierzy trójkątnej wyznacznik jest iloczynem jej przekątnych wejść. Oktawa jest qrfunkcja wywoływana z pojedynczym wyjściu daje R .

Wynik jest zaokrąglany do najbliższej liczby całkowitej. W przypadku dużych macierzy wejściowych niedokładności zmiennoprzecinkowe mogą powodować przekroczenie błędu, 0.5a tym samym błędny wynik.

Haskell , 59 bajtów

p%(l:r)=l!!0*f(tail<$>p++r)-(p++[l])%r
[]%_=1
p%_=0
f=([]%)

Wypróbuj online!

C,  176  125 bajtów

Dzięki @ceilingcat za grę w golfa 42 bajty, a także @Lynn i @ Jonathan Frech za zapisanie każdego bajtu!

d(M,n)int*M;{int i=n--,s=*M*!n,c,T[n*n];for(;i--;s+=M[i]*(1-i%2*2)*d(T,n))for(c=n*n;c--;T[c]=M[n-~c+c/n+(c%n>=i)]);return s;}

Oblicza wyznacznik za pomocą rozszerzenia Laplace'a w pierwszym rzędzie.

Wypróbuj online!

Rozwinięty:

d(M, n)int*M;
{
    int i=n--, s=*M*!n, c, T[n*n];
    for (; i--; s+=M[i]*(1-i%2*2)*d(T,n))
        for (c=n*n; c--;)
            T[c] = M[n-~c+c/n+(c%n>=i)];
    return s;
}

Galaretka , 43 bajty

Wreszcie skończyłem pisać moje niewbudowane rozwiązanie w języku golfowym!

ḣ⁹’’¤;ṫḊ€Ç×⁸ị@⁹’¤¤ḷ/¤
çЀ⁸J‘¤µJ-*×NS
ÇḢḢ$Ṗ?

Dzięki HyperNeutrino za uratowanie bajtu!

Wypróbuj online! (kod odstępu dla przejrzystości)

strasznie długa droga do usunięcia n-tych elementów z listy, poprawi się później

Ta odpowiedź została obezwładniona odpowiedziami HyperNeutrino, Dennisa i Dziurawej Zakonnicy. Galaretka jest bardzo popularna jako język golfa.

Szybkie wyjaśnienie:

ÇḢḢ$Ṗ?    Main link.
     ?    If
    Ṗ     after remove the last element, the value is not empty (truthy)
Ç         then execute the last link
 ḢḢ$      else get the element at index [1, 1].

çЀ⁸J‘¤µJ-*×NS     Helper link 1, take input as a matrix.
çЀ                Apply the previous link, thread right argument to
   ⁸J‘¤            the range [2, 3, ..., n+1]
       µ           With the result,
        J-*        generate the range [-1, 1, -1, 1, ...] with that length
           ×N      Multiply by negative
             S     Sum

ḣ⁹’’¤;ṫḊ€Ç×⁸ị@⁹’¤¤ḷ/¤    Helper link 2, take left input as a matrix, right input as a number in range [2..n+1]
ḣ
 ⁹’’¤                    Take head ρ-2 of the matrix
     ;                   concatenate with 
      ṫ                  tail ρ (that is, remove item ρ-1)
       Ḋ€                Remove first column
         Ç               Calculate determinant of remaining matrix
          ×         ¤    multiply by
                  ḷ/     the first column,
            ị@           row #
              ⁹’¤        ρ-1 (just removed in determinant calculation routine) of
           ⁸     ¤       the matrix.

Galaretka , 24 bajty

œcL’$ṚÑ€
J-*×Ḣ€×ÇSµḢḢ$Ṗ?

Wypróbuj online!

Wyjaśnienie

œcL’$ṚÑ€         Helper Link; get the next level of subdeterminants (for Laplace Expansion)
œc               Combinations without replacement of length:
  L’$            Length of input - 1 (this will get all submatrices, except it's reversed)
     Ṛ           Reverse the whole thing
      р         Get the determinant of each of these
J-*×Ḣ€×ÇSµḢḢ$Ṗ?  Main Link
              ?  If the next value is truthy
             Ṗ   Remove the last element (truthy if the matrix was at least size 2)
J-*×Ḣ€×ÇSµ       Then expand
          ḢḢ$    Otherwise, get the first element of the first element (m[0][0] in Python)
J                [1, 2, ..., len(z)]
 -*              (-1 ** z) for each z in the length range
   ×             Vectorizing multiply with
    Ḣ€           The first element of each (this gets the first column); modifies each row (makes it golfier yay)
      ×Ç         Vectorizing multiply with the subdeterminants
        S        Sum

-2 bajty dzięki rozwiązaniu user202729

MATL , 3 bajty / 5 bajtów

Z wbudowaną funkcją

&0|

Wypróbuj online!

Bez wbudowanego

Dzięki Misze Ławrow za wskazanie błędu, teraz poprawionego

YvpYo

Wypróbuj online!

Oblicza to wyznacznik jako iloczyn wartości własnych, zaokrąglonych do najbliższej liczby całkowitej, aby uniknąć niedokładności zmiennoprzecinkowych.

Yv       % Implicit input. Push vector containing the eigenvalues
p        % Product
Yo       % Round. Implicit display

R , 32 bajty

function(m)Re(prod(eigen(m)$va))

Wykorzystuje algorytm Not a Tree do pobierania wartości własnych macierzy i przyjmowania rzeczywistej części ich iloczynu.

Wypróbuj online!

Oktawa , 30 bajtów

@(x)-prod(diag([~,l,~]=lu(x)))

Wypróbuj online!

lub nudne rozwiązanie 4-bajtowe (dzięki Luisowi Mendo zapisano 6 bajtów (zapomniałem zasad dotyczących wbudowanych funkcji)):

@det

Wyjaśnienie:

Nadchodzi! :)

TI-Basic, 2 bajty

det(Ans

Ach tak.

Proszę nie głosować na trywialne odpowiedzi.

_{Jako uczeń szkoły średniej (który jest zmuszony do posiadania jednego z tych kalkulatorów), ta funkcja jest bardzo przydatna, więc ...}

Haskell, 62 bajty

a#((b:c):r)=b*d(a++map tail r)-(a++[c])#r
_#_=0
d[]=1
d l=[]#l

Wypróbuj online! (Stopka z przypadkami testowymi zaczerpniętymi z rozwiązania @ całkowicieludzkiego).

doblicza wyznacznik za pomocą rozszerzenia Laplace'a wzdłuż pierwszej kolumny. Potrzebuje trzech bajtów więcej niż stały .

Python 2 , 95 bajtów

-12 bajtów dzięki Lynn.

Port mojej odpowiedzi Haskell .

f=lambda m:sum((-1)**i*v*f([j[:i]+j[i+1:]for j in m[1:]])for i,v in enumerate(m[0]))if m else 1

Wypróbuj online!

Wolfram Language (Mathematica) , 53 52 bajty

1##&@@@(t=Tuples)@#.Signature/@t[Range@Tr[1^#]&/@#]&

Wypróbuj online!

Niestety, obliczenie wyznacznika macierzy n na n w ten sposób wykorzystuje pamięć O ( n ⁿ ), co powoduje, że duże przypadki testowe są poza zasięgiem.

Jak to działa

Pierwsza część 1##&@@@(t=Tuples)@#oblicza wszystkie możliwe produkty terminu z każdego wiersza danej macierzy. t[Range@Tr[1^#]&/@#]daje listę o tej samej długości, której elementami są rzeczy {3,2,1}lub {2,2,3}stwierdzenia, który wpis każdego wiersza wybraliśmy dla odpowiedniego produktu.

Odnosimy się Signaturedo drugiej listy, która mapuje parzyste permutacje 1, nieparzyste permutacje -1i nie-permutacje do 0. Jest to właśnie współczynnik, z którym odpowiadający produkt pojawia się w wyznaczniku.

Na koniec bierzemy iloczyn kropkowy z dwóch list.

Jeśli nawet Signaturejest za dużo wbudowanego, przy 73 bajtach możemy wziąć

1##&@@@(t=Tuples)@#.(1##&@@Order@@@#~Subsets~{2}&/@t[Range@Tr[1^#]&/@#])&

zastępując go przez 1##&@@Order@@@#~Subsets~{2}&. Oblicza Signatureto ewentualnie permutację, przyjmując iloczyn Orderzastosowany do wszystkich par elementów permutacji. Orderda, 1jeśli para jest w porządku rosnącym, -1jeśli jest w porządku malejącym i 0jeśli są równe.

-1 bajt dzięki @ user202729

Python 3 , 238 bajtów , 227 bajtów , 224 bajty , 216 bajtów

from functools import*
from itertools import*
r=range;n=len;s=sum
f=lambda l:s(reduce(lambda p,m:p*m,[l[a][b]for a,b in zip(r(n(l)),j)])*(-1)**s(s(y<j[x]for y in j[x:])for x in r(n(l)))for j in permutations(r(n(l))))

Wypróbuj online!

Moje rozwiązanie korzysta z definicji wyznacznika do obliczeń. Niestety złożoność tego algorytmu jest n!i nie mogę pokazać przejścia ostatniego testu, ale teoretycznie jest to możliwe.

CJam ( 50 45 bajtów)

{:A_,{1$_,,.=1b\)/:CAff*A@zf{\f.*1fb}..-}/;C}

Jest to anonimowy blok (funkcja), który pobiera tablicę 2D na stos i pozostawia liczbę całkowitą na stosie.

Zestaw testów online

Sekcja

To implementuje algorytm Faddeeva-LeVerriera i myślę, że to pierwsza odpowiedź na to podejście.

$c_k$$n\times n$$A$

$$p(\lambda )\equiv \det(\lambda I_{n}-A)=\sum _{k=0}^{n}c_{k}\lambda ^{k}$$ $c_n = 1$$c_0 = (−1)^n \det A$

$M$

$$\begin{aligned}M_{0}&\equiv 0&c_{n}&=1\qquad &(k=0)\\M_{k}&\equiv AM_{k-1}+c_{n-k+1}I\qquad \qquad &c_{n-k}&=-{\frac {1}{k}}\mathrm {tr} (AM_{k})\qquad &k=1,\ldots ,n~.\end{aligned}$$

$c_{n-k}$$M_k$$(-1)^k c_{n-k}$$(-1)^{k+1}AM_k$

{               e# Define a block
  :A            e#   Store the input matrix in A
  _,            e#   Take the length of a copy
  {             e#     for i = 0 to n-1
                e#       Stack: (-1)^{i+2}AM_{i+1} i
    1$_,,.=1b   e#       Calculate tr((-1)^{i+2}AM_{i+1})
    \)/:C       e#       Divide by (i+1) and store in C
    Aff*        e#       Multiply by A
    A@          e#       Push a copy of A, bring (-1)^{i+2}AM_{i+1} to the top
    zf{\f.*1fb} e#       Matrix multiplication
    ..-         e#       Matrix subtraction
  }/
  ;             e#   Pop (-1)^{n+2}AM_{n+1} (which incidentally is 0)
  C             e#   Fetch the last stored value of C
}

Wolfram Language (Mathematica) , 3 bajty

Det

Wypróbuj online!

Zgodnie z meta konsensusem , głosuj głównie za nietradycyjnymi rozwiązaniami, których pisanie wymaga wysiłku.

Python 2 , 75 bajtów

f=lambda m,p=[]:m[0][0]*f(zip(*p+m[1:])[1:])-f(m[1:],p+m[:1])if m else[]==p

Wypróbuj online!

SageMath , różne

Oto kilka metod obliczania wyznacznika, które uważałem za interesujące, wszystkie zaprogramowane w SageMath. Wszystkie można tutaj wypróbować .

Wbudowany, 3 bajty

det

Ten nie jest zbyt interesujący. Sage zapewnia aliasy na poziomie globalnym dla wielu typowych operacji, które normalnie byłyby metodami obiektowymi, więc jest to krótszy niż lambda m:m.det().

Rzeczywista część iloczynu wartości własnych, 36 bajtów

lambda m:real(prod(m.eigenvalues()))

Niestety, eigenvaluesnie jest jednym z tych aliasów na poziomie globalnym. To, w połączeniu z faktem, że Sage nie ma zgrabnego sposobu komponowania funkcji, oznacza, że ​​utknęliśmy na kosztownym lambda. Ta funkcja symboliczne wartości, które są automatycznie konwertowane na wartości liczbowe po wydrukowaniu, więc niektóre niedokładności zmiennoprzecinkowe mogą występować na niektórych wyjściach.

Produkt o przekątnej w normalnej formie Jordana, 60 bajtów

lambda m:prod(m.jordan_form()[x,x]for x in range(m.nrows()))

W postaci Jordan Normal macierz NxN jest reprezentowana jako macierz blokowa, z N blokami na przekątnej. Każdy blok składa się albo z pojedynczej wartości własnej, albo z macierzy MxM z powtarzaną wartością własną na przekątnej is 1na super-przekątnej (przekątna powyżej i na prawo od „głównej” przekątnej). Daje to macierz ze wszystkimi wartościami własnymi (z wielokrotnością) na głównej przekątnej, a niektóre 1s na super-przekątnej odpowiadające powtarzanym wartościom własnym. Zwraca to iloczyn przekątnej normalnej postaci Jordana, który jest iloczynem wartości własnych (z wielokrotnością), więc jest to bardziej okrągły sposób wykonywania tego samego obliczenia, co poprzednie rozwiązanie.

Ponieważ Sage chce, aby normalna forma Jordana znajdowała się nad tym samym pierścieniem co pierwotna matryca, działa to tylko wtedy, gdy wszystkie wartości własne są racjonalne. Złożone wartości własne powodują błąd (chyba że pierwotna macierz znajduje się nad pierścieniem CDF(złożone podwójne zmiennoprzecinkowe) lub SR). Oznacza to jednak, że wzięcie prawdziwej roli nie jest konieczne w porównaniu z powyższym rozwiązaniem.

Produkt przekątnej w rozkładzie Smitha

lambda m:prod(m.smith_form()[0].diagonal())

W przeciwieństwie do normalnej postaci Jordana, normalna forma Smitha ma gwarancję, że znajdzie się nad tym samym polem, co pierwotna matryca. Zamiast obliczać wartości własne i przedstawiać je za pomocą blokowej macierzy diagonalnej, rozkład Smitha oblicza elementarne dzielniki macierzy (co jest tematem zbyt skomplikowanym dla tego postu), umieszcza je w macierzy diagonalnej Di oblicza dwie macierze z jednostką wyznacznik Ui Vtaki, że D = U*A*V(gdzie Ajest oryginalna matryca). Ponieważ determinantą iloczyn macierzy jest równa produkt determinantów (matryc det(A*B*...) = det(A)*det(B)*...) oraz Ui Vsą określone jako determinanty elementarne det(D) = det(A). Wyznacznikiem macierzy diagonalnej jest po prostu iloczyn elementów na przekątnej.

Rozszerzenie Laplace'a, 109 bajtów

lambda m:m.nrows()>1and sum((-1)**j*m[0,j]*L(m[1:,:j].augment(m[1:,j+1:]))for j in range(m.ncols()))or m[0,0]

Spowoduje to rozwinięcie Laplace'a w pierwszym rzędzie, stosując podejście rekurencyjne. det([[a]]) = ajest używany w przypadku podstawowym. Powinien być krótszy do użycia det([[]]) = 1w przypadku podstawowym, ale moja próba implementacji zawierała błąd, którego nie udało mi się jeszcze wyśledzić.

Formuła Leibniza, 100 bajtów

L2 = lambda m:sum(sgn(p)*prod(m[k,p[k]-1]for k in range(m.ncols()))for p in Permutations(m.ncols()))

To bezpośrednio implementuje formułę Leibniza. Aby uzyskać znacznie lepsze wyjaśnienie formuły i dlaczego działa ona, niż mogłabym napisać, zobacz tę doskonałą odpowiedź .

Rzeczywista część e^(Tr(ln(M))), 48 bajtów

lambda m:real(exp(sum(map(ln,m.eigenvalues()))))

Ta funkcja zwraca wyrażenia symboliczne. Aby uzyskać przybliżenie numeryczne, zadzwoń n(result)przed drukowaniem.

To podejście, którego jeszcze nie widziałem. Dam ci dłuższe, bardziej szczegółowe wyjaśnienie tego.

Niech Abędzie kwadratowa matryca nad rzeczywistością. Z definicji wyznacznik Ajest równy iloczynowi wartości własnych A. Ślad Ajest równy sumie Awartości własnych. Dla liczb rzeczywistych r_1i r_2, exp(r_1) * exp(r_2) = exp(r_1 + r_2). Ponieważ funkcja wykładnicza macierzy jest zdefiniowana jako analogiczna do skalarnej funkcji wykładniczej (szczególnie w poprzedniej tożsamości), a wykładnicza funkcja macierzowa może być obliczona poprzez diagonalizację macierzy i zastosowanie skalarnej funkcji wykładniczej do wartości własnych na przekątnej, możemy powiedzieć det(exp(A)) = exp(trace(A))(produkt z przykładu exp(λ)dla każdej wartości własnych λod Arówna sumie wartości własnych exp(A)). Tak więc, jeśli możemy znaleźć macierz Ltaką, żeexp(L) = A, możemy obliczyć det(A) = exp(trace(L)).

Taką matrycę możemy znaleźć, Lobliczając log(A). Logarytm macierzowy można obliczyć w taki sam sposób, jak macierz wykładniczy: uformować kwadratową macierz diagonalną, stosując funkcję logarytmu skalarnego do każdej wartości własnej A(dlatego zmieniliśmy Ana rzeczywiste). Ponieważ zależy nam tylko na śladach L, możemy pominąć konstrukcję i po prostu bezpośrednio zsumować wykładnicze wartości własne. Wartości własne mogą być złożone, nawet jeśli macierz nie znajduje się nad złożonym pierścieniem, więc bierzemy prawdziwą część sumy.

Java 8, 266 261 259 258 bajtów

long d(int[][]m){long r=0;int i=0,j,k,l=m.length,t[][]=new int[l-1][l-1],q=m[0][0];if(l<3)return l<2?q:q*m[1][1]-m[0][1]*m[1][0];for(;i<l;r+=m[0][i]*(1-i++%2*2)*d(t))for(j=0;++j<l;)for(k=l;k-->0;){q=m[j][k];if(k<i)t[j-1][k]=q;if(k>i)t[j-1][k-1]=q;}return r;}

Spójrz mamo, brak wbudowanych .. _{ponieważ Java nie ma ..>.>}

-7 bajtów dzięki @ceilingcat .

Wyjaśnienie:

Wypróbuj tutaj. (Tylko ostatni przypadek testowy jest zbyt duży, aby zmieścił się w longrozmiarze 2 ⁶³ -1.)

long d(int[][]m){             // Method with integer-matrix parameter and long return-type
  long r=0;                   //  Return-long, starting at 0
  int i=0,j,k,                //  Index-integers
      l=m.length,             //  Dimensions of the square matrix
      t[][]=new int[l-1][l-1],//  Temp-matrix, one size smaller than `m`
      q=m[0][0];              //  The first value in the matrix (to reduce bytes)
  if(l<3)                     //  If the dimensions are 1 or 2:
    return l<2?               //   If the dimensions are 1:
      q                       //    Simply return the only item in it
     :                        //   Else (the dimensions are 2):
      q*m[1][1]-m[0][1]*m[1][0];
                              //    Calculate the determinant of the 2x2 matrix
                              //  If the dimensions are 3 or larger: 
  for(;i<l;                   //  Loop (1) from 0 to `l` (exclusive)
      r+=                     //    After every iteration: add the following to the result:
         m[0][i]              //     The item in the first row and `i`'th column,
         *(1-i++%2*2)         //     multiplied by 1 if `i` is even; -1 if odd,
         *d(t))               //     multiplied by a recursive call with the temp-matrix
    for(j=0;                  //   Reset index `j` to 0
        ++j<l;)               //   Inner loop (2) from 0 to `l` (exclusive)
      for(k=l;k-->0;){        //    Inner loop (3) from `l-1` to 0 (inclusive)
        q=m[j][k];            //     Set the integer at location `j,k` to reduce bytes
        if(k<i)               //     If `k` is smaller than `i`:
          t[j-1][k]=q;        //      Set this integer at location `j-1,k`
        if(k>i)               //     Else-if `k` is larger than `i`:
          t[j-1][k-1]=q;      //      Set this integer at location `j-1,k-1`
                              //     Else: `k` and `i` are equals: do nothing (implicit)
      }                       //    End of inner loop (3)
                              //   End of inner loop (2) (implicit / single-line body)
                              //  End of loop (1) (implicit / single-line body)
  return r;                   //  Return the result-long
}                             // End of method

JavaScript (ES6), 91

Laplace rekurencyjne

q=(a,s=1)=>+a||a.reduce((v,[r],i)=>v-(s=-s)*r*q(a.map(r=>r.slice(1)).filter((r,j)=>j-i)),0)

Mniej golfa

q = (a,s=1) => // s used as a local variable
  a[1] // check if a is a single element array 
       // if array, recursive call expanding along 1st column
  ? a.reduce((v,[r],i) => v-(s=-s)*r*q(a.map(r=>r.slice(1)).filter((r,j)=>j-i)),0) 
  : +a // single element, convert to number

Test

q=(a,s=1)=>+a||a.reduce((v,[r],i)=>v-(s=-s)*r*q(a.map(r=>r.slice(1)).filter((r,j)=>j-i)),0)

TestCases=`[[42]] -> 42
[[2, 3], [1, 4]] -> 5
[[1, 2, 3], [4, 5, 6], [7, 8, 9]] -> 0
[[13, 17, 24], [19, 1, 3], [-5, 4, 0]] -> 1533
[[372, -152, 244], [-97, -191, 185], [-53, -397, -126]] -> 46548380
[[100, -200, 58, 4], [1, -90, -55, -165], [-67, -83, 239, 182], [238, -283, 384, 392]] -> 571026450
[[432, 45, 330, 284, 276], [-492, 497, 133, -289, -28], [-443, -400, 56, 150, -316], [-344, 316, 92, 205, 104], [277, 307, -464, 244, -422]] -> -51446016699154`
.split('\n')

TestCases.forEach(r=>{
  [a,k] = r.split (' -> ')
  a = eval(a)
  d = q(a)
  console.log('Test '+(k==d ? 'OK':'KO')+
    '\nMatrix '+a.join('|')+
    '\nResult '+d+
    '\nCheck  '+k)
})

Python 2 + numpy , 29 bajtów

from numpy.linalg import*
det

Wypróbuj online!

Julia , 3 bajty

det

Wypróbuj online!

Pari / GP , 6 bajtów

matdet

Wypróbuj online!

Java (OpenJDK 8) , 195 192 177 bajtów

long d(int[][]m){long D=0;for(int l=m.length-1,t[][]=new int[l][l],i=0,j,k;i<=l;D+=m[0][i]*(1-i++%2*2)*(l<1?1:d(t)))for(j=0;j<l*l;)t[j/l][k=j%l]=m[1+j++/l][k<i?k:k+1];return D;}

Wypróbuj online!

Podobnie jak wiele innych odpowiedzi, wykorzystuje to również formułę Laplace'a. Wersja nieco mniej golfowa:

long d(int[][]m){
  long D=0;
  int l=m.length-1,t[][]=new int[l][l],i=0,j,k;
  for(;i<=l;)
    for(j=0;j<l*l;)
      t[j/l][k=j%l]=m[1+j++/l][k<i?k:k+1];
    D+=m[0][i]*(1-i++%2*2)*(l<1?1:d(t));
  return D;
}

J , 5 bajtów

-/ .*

Wypróbuj online!