Déterminant d'une matrice entière

34

Avec une matrice entière carrée en entrée, sortie le déterminant de la matrice.

Règles

  • Vous pouvez supposer que tous les éléments de la matrice, le déterminant de la matrice et le nombre total d'éléments de la matrice sont compris dans la plage d'entiers pouvant être représentés pour votre langue.
  • La sortie d'une valeur décimale / float avec une partie décimale de 0 est autorisée (par exemple à la 42.0place de 42).
  • Les commandes intégrées sont autorisées, mais vous êtes invité à inclure une solution qui ne les utilise pas.

Cas de test

[[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
Mego
la source
Existe-t-il une taille maximale de matrice à prendre en charge ou est-ce arbitraire?
Taylor Scott
1
@TaylorScott Première règle listée:You may assume that all elements in the matrix, the determinant of the matrix, and the total number of elements in the matrix are within the representable range of integers for your language.
Mégo
4
Vous savez que vous avez un défi intéressant à relever lorsque vous avez 4 réponses de gelée consécutives qui se
surpassent l'une contre l'

Réponses:

25

Gelée , 15 octets

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

Essayez-le en ligne!

Comment ça marche

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

Pourquoi ça marche - version mathématique

L'opérateur det prend une matrice et retourne un scalaire. Une matrice n -by- n peut être considérée comme une collection de n vecteurs de longueur n , alors det est en réalité une fonction qui prend n vecteurs de n et renvoie un scalaire.

Par conséquent, j'écris det ( v 1 , v 2 , v 3 , ..., v n ) pour det [ v 1 v 2 v 3 ... v n ].

Notez que det est linéaire dans chaque argument, c'est-à-dire det ( v 1 + λ w 1 , v 2 , v 3 , ..., v n ) = det ( v 1 , v 2 , v 3 , ..., v n ) + λ det ( w 1 , v 2 , v 3 , ..., v n ). Par conséquent, il est une carte linéaire de (ℤ n ) n à.

Il suffit de déterminer l’image de la base sous la carte linéaire. La base de (ℤ n ) n est constitué de n produits tensoriels -fold des éléments de base de ℤ n , ieeg e 5 ⊗ e 3 ⊗ e 1 ⊗ e 5 ⊗ e 1 . Les produits de tenseurs comportant des tenseurs identiques doivent être mis à zéro, car le déterminant d'une matrice dans laquelle deux colonnes sont identiques est zéro. Il reste à vérifier à quoi sont envoyés les produits tensoriels d’éléments de base distincts. Les indices des vecteurs dans le produit tensoriel forment une bijection, c'est-à-dire une permutation, dans laquelle les permutations paires sont envoyées à 1 et les permutations impaires à -1.

Par exemple, pour trouver le déterminant de [[1, 2], [3, 4]]: notez que les colonnes sont [1, 3] et [2, 4]. Nous décomposons [1, 3] pour donner (1 e 1 + 3 e 2 ) et (2 e 1 + 4 e 2 ). L'élément correspondant dans le produit tenseur est (1 e 1 2 e 1 + 1 e 1 4 e 2 + 3 e 2 ⊗ 2 e 1 + 3 e 2 4 e 2 ), que nous simplifions en (2 e 1 ⊗ e 1 + 4 e 1 e 2 + 6 e 2 e 1 + 12 e 2 e 2). Par conséquent:

det [[1, 2], [3, 4]]
= det (1 e 1 + 3 e 2 , 2 e 1 + 4 e 2 )
= det (2 e 1 ≤ e 1 + 4 e 1 ≤ e 2 + 6 e 2 ⊗ e 1 + 12 e 2 e 2 )
= det (2 e 1 e 1 ) + det (4 e 1 ⊗ e 2 ) + det (6 e 2 e 1 ) + det (12 e2 ⊗ e 2 )
= 2 det (e 1 e 1 ) + 4 dét (e 1 e 2 ) + 6 dét (e 2 e 1 ) + 12 dét (e 2 e 2 )
= 2 (0) + 4 (1) + 6 (-1) + 12 (0)
= 4 - 6
= -2

Maintenant, il reste à prouver que la formule pour trouver la parité de la permutation est valide. Ce que fait mon code, c'est essentiellement trouver le nombre d'inversions, c'est-à-dire les endroits où un élément de gauche est plus grand qu'un élément de droite (pas nécessairement de manière consécutive).

Par exemple, dans la permutation 3614572, il y a 9 inversions (31, 32, 61, 64, 65, 62, 42, 52, 72), de sorte que la permutation est impair.

La justification est que chaque transposition (permutation de deux éléments) ajoute une inversion ou supprime une inversion en permutant la parité du nombre d'inversions et que la parité de la permutation est la parité du nombre de transpositions nécessaires pour obtenir la permutation.

Donc, en conclusion, notre formule est donnée par:

Pourquoi ça marche - version non mathématique

où σ est une permutation de n le groupe de toutes les permutations sur n lettres, et sgn est le signe de la permutation, AKA (-1) élevé à la parité de la permutation, et a ij est la ( ij ) ème entrée de la matrice ( i down, j across).

Fuite, nonne
la source
17
Cette "version non mathématique" est une sacrée mathématique.
MD XF
6
Les formules @MDXF, les symboles et les nombres ne constituent pas un calcul. La mathématique est l'abstraction, la généralisation et la logique des manipulations formelles des symboles.
Leaky Nun
7
@JAB Jelly implémente sa propre page de code personnalisée . (Un de ces jours, TIO inclura un lien vers la page de code ...)
totalement humain
1
@Mego, les "produits de somme de diagonale" ne fonctionnent que pour les matrices 1x1, 2x2 et 3x3. Pour les matrices plus grandes, vous devez prendre en compte toutes les permutations et leur parité.
Leaky Nun
3
+1 pour inclure réellement la preuve dans le message au lieu de dire "car cette formule est listée sur la page abcxyz, elle doit être vraie".
user202729
11

R , 3 octets

Solution triviale

det

Essayez-le en ligne!

R , 94 92 octets

solution ré-implémentée

surclassé par 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)

Essayez-le en ligne!

Utilise de manière récursive le développement par des mineurs dans la première colonne de la matrice.

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

Giuseppe
la source
32 octets
JAD
9

Jelly , 16 15 12 10 octets

Ḣ×Zß-Ƥ$Ṛḅ-

Utilise l' extension Laplace . Merci à @miles pour le golf de 3 à 5 octets!

Essayez-le en ligne!

Comment ça marche

Ḣ×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.
Dennis
la source
8

Wolfram Language (Mathematica) , entre 14 et 42 octets

Nous avons des solutions intégrées à 3 octets et à 53 octets qui les évitent complètement. Voici donc des solutions plus bizarres.

Le langage Wolfram a beaucoup de fonctions très intenses pour décomposer les matrices en produits d'autres matrices à structure plus simple. L'un des plus simples (ce qui signifie que j'en ai entendu parler auparavant) est la décomposition de Jordan. Chaque matrice est similaire à une matrice triangulaire supérieure (éventuellement à valeurs complexes) constituée de blocs diagonaux de structure spécifique, appelée décomposition de Jordan de cette matrice. La similarité préserve les déterminants et le déterminant d'une matrice triangulaire est le produit des éléments diagonaux. Nous pouvons donc calculer le déterminant avec les 42 octets suivants :

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

Le déterminant est également égal au produit des valeurs propres d'une matrice, avec sa multiplicité. Heureusement, la fonction valeur propre de Wolfram garde la trace de la multiplicité (même pour les matrices non diagonalisables), nous obtenons donc la solution à 20 octets suivante :

1##&@@Eigenvalues@#&

La solution suivante consiste à tricher et je ne sais pas trop pourquoi cela fonctionne. Le Wronskian d'une liste de n fonctions est le déterminant de la matrice des n premières dérivées des fonctions. Si nous donnons à la Wronskianfonction une matrice d’entiers et que nous disons que la variable de différenciation est 1, elle détermine en quelque sorte le déterminant de la matrice. C'est bizarre, mais cela n'implique pas les lettres " Det" et ce n'est que 14 octets ...

#~Wronskian~1&

(Le déterminant Casoratian fonctionne aussi bien, pour une plus octet: #~Casoratian~1&)

Dans le domaine de l’algèbre abstraite, le déterminant d’une matrice n  x  n (considéré comme la carte k → k, multiplication par le déterminant) est la n- ième puissance extérieure de la matrice (après le choix d’un isomorphisme k → n k n ). En langage Wolfram, nous pouvons le faire avec les 26 octets suivants :

HodgeDual[TensorWedge@@#]&

Et voici une solution qui ne fonctionne que pour les déterminants positifs. Si nous prenons un hypercube d'unité à n dimensions et lui appliquons une transformation linéaire, le "volume" à n dimensions de la région résultante est la valeur absolue du déterminant de la transformation. L'application d'une transformation linéaire à un cube donne un parallélépipède et nous pouvons prendre son volume avec les 39 octets de code suivants:

RegionMeasure@Parallelepiped[Last@#,#]&
Pas un arbre
la source
1
La solution que j’avais dans ce sens était Exp@*Tr@*MatrixLog, mais malheureusement, cela ne fonctionne pas pour les matrices singulières.
Misha Lavrov
1
@MishaLavrov Ooh, c'est malin! Je pense que vous pouvez le réparer avec Check[E^Tr@MatrixLog@#,0]&.
Pas un arbre
C'est génial! Je n'avais pas été au courant Checkavant.
Misha Lavrov
1
J'ai créé un défi pour Jordan Decomposition il y a quelque temps. Vous pourriez être intéressé aussi. Quelle bonne réponse!
Mego
8

Haskell , 71 octets

-3 octets grâce à Lynn. Un autre octroie la poussière grâce à Craig Roy.

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

Essayez-le en ligne! Ajout d'un -Odrapeau à des fins d'optimisation. Ce n'est pas nécessaire.

Explication (obsolète)

f implémente de manière récursive l'expansion du cofacteur.

f[[x]]=x

Cette ligne couvre le cas de base d'une matrice 1 × 1 , auquel cas le déterminant est mat[0, 0].

f(h:t)=

Cela utilise la correspondance de motif de Haskell pour diviser la matrice en une tête (la première ligne) et une queue (le reste de la matrice).

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

Énumérez la tête de la matrice (en zippant la liste infinie de nombres entiers et la tête) et parcourez-la.

           (-1)*i*v

Annulez le résultat en fonction de l'indexation même ou non, car le calcul du déterminant implique une addition et une soustraction en alternance.

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

Cela supprime essentiellement la ième colonne de la queue en prenant i éléments et en la concaténant avec la ligne avec le premier (i + 1) ème éléments lâchés pour chaque ligne de la queue.

                   *f

Calculez le déterminant du résultat ci-dessus et multipliez-le par le résultat de (-1)*i*v.

       sum

Faites la somme du résultat de la liste ci-dessus et renvoyez-le.

totalement humain
la source
2
vous pourriez économiser 1 octet si vous remplacez le sum[(-1)^i*...parfoldr(-)0[...
Craig Roy
6

Proton , 99 octets

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)

Essayez-le en ligne!

-3 octets grâce à Mr. Xcoder
-3 octets grâce à Erik the Outgolfer

Expansion sur la première rangée

HyperNeutrino
la source
Tout simplement parce que Proton n’a pas intégré le déterminant.
user202729
103 octets . ((~i%2)*2-1)->((-i%2)|1)
M. Xcoder
Aussi, 102 octets en remplaçant j!=ipar j-iou i-j.
M. Xcoder
99 octets
Erik the Outgolfer
@EriktheOutgolfer Ah oui, merci!
HyperNeutrino
5

Octave , 28 octets

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

Essayez-le en ligne!

Celui - ci utilise la décomposition QR d'une matrice X dans une matrice orthgonal Q et une matrice triangulaire supérieure R . Le déterminant de X est le produit de celles de Q et R . Une matrice orthogonale a un déterminant unitaire et pour une matrice triangulaire, le déterminant est le produit de ses entrées en diagonale. Octave qrfonction appelée avec une seule sortie donne R .

Le résultat est arrondi à l'entier le plus proche. Pour les grandes matrices d’entrée, les imprécisions en virgule flottante peuvent produire un dépassement d’erreur 0.5et donner ainsi un résultat erroné.

Luis Mendo
la source
1
C'est un moyen intéressant d'échapper à l' detincident. ;)
tomsmeding
1
@tomsmeding :-) En outre, il avait déjà été "utilisé" dans la réponse de Stewie
Luis Mendo
5

C,  176  125 octets

Merci à @ceilingcat pour le jeu de 42 octets, et à @Lynn et @Jonathan Frech pour avoir sauvegardé un octet chacun!

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;}

Calcule le déterminant en utilisant l' extension de Laplace le long de la première ligne.

Essayez-le en ligne!

Déroulé:

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;
}
Steadybox
la source
(i%2*-2+1)(1-i%2*2)enregistre un octet supplémentaire.
Lynn
n+1+cpeut être n-~c.
Jonathan Frech
Suggérer i=sau lieu dereturn s
ceilingcat
5

Gelée , 43 octets

Enfin, j'ai fini d'écrire ma solution non intégrée dans un langage de golf!

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

Merci à HyperNeutrino d' avoir sauvegardé un octet!

Essayez-le en ligne! (code espacé pour plus de clarté)

Un très long chemin pour supprimer les éléments d'une liste, s'améliorera plus tard


HyperNeutrino, Dennis et Leaky Nun avaient déjoué les réponses. La gelée est très populaire comme langue de golf.

Explication rapide:

ÇḢḢ$Ṗ?    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.
utilisateur202729
la source
4

Gelée , 24 octets

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

Essayez-le en ligne!

Explication

œ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 octets grâce à la solution de user202729

HyperNeutrino
la source
4

MATL , 3 octets / 5 octets

Avec fonction intégrée

&0|

Essayez-le en ligne!

Sans incorporé

Merci à Misha Lavrov pour avoir signalé une erreur, maintenant corrigée

YvpYo

Essayez-le en ligne!

Ceci calcule le déterminant comme le produit des valeurs propres, arrondi au nombre entier le plus proche pour éviter les inexactitudes en virgule flottante.

Yv       % Implicit input. Push vector containing the eigenvalues
p        % Product
Yo       % Round. Implicit display
Luis Mendo
la source
Le produit des valeurs singulières ne vous dirait-il pas que la valeur absolue du déterminant?
Misha Lavrov
@MishaLavrov Vous avez tout à fait raison! Merci d'avoir remarqué. Je l'ai corrigé en utilisant des valeurs propres au lieu de valeurs singulières ... et qui ont économisé 4 octets \ o /
Luis Mendo
4

R , 32 octets

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

Utilise l'algorithme de Not a Tree pour prendre les valeurs propres de la matrice et prendre la partie réelle de leur produit.

Essayez-le en ligne!

JAD
la source
Très élégant! +1
Giuseppe
3

Octave , 30 octets

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

Essayez-le en ligne!

ou la solution ennuyeuse sur 4 octets (6 octets sauvegardés grâce à Luis Mendo (j'ai oublié les règles concernant les fonctions internes)):

@det

Explication:

À venir! :)

Stewie Griffin
la source
3

TI-Basic, 2 octets

det(Ans

Et bien.

S'il vous plaît ne pas upvote des réponses triviales.

En tant qu'élève du secondaire (qui est obligé de posséder une de ces calculatrices), cette fonction est très utile ...

totalement humain
la source
8
C'est toujours utile au collège - l'algèbre linéaire ne va pas disparaître
Taylor Scott
5
@TaylorScott En fait, il revient avec une vengeance dans les équations différentielles.
Mego
@ Mego - vous avez raison à ce sujet; bien que, pour une raison quelconque, ils me laissent prendre tous les calculs et qu'avant linéaire: /
Taylor Scott
1
@TaylorScott En raison d'un oubli du département de mathématiques de mon université, linalg n'était pas une condition préalable à la diffeq lorsque je l'ai prise. Lorsque mon professeur a compris cela, il nous a rapidement proposé un cours intensif de trois jours sur le linalg.
Mego
3

Haskell, 62 octets

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

Essayez-le en ligne! (Pied de page avec cas de test tirés de la solution de @ totallyhuman.)

dcalcule le déterminant en utilisant une extension de Laplace le long de la première colonne. A besoin de trois octets de plus que le permanent .

Christian Sievers
la source
3

Python 2 , 95 octets

-12 octets grâce à Lynn.

Port de ma réponse 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

Essayez-le en ligne!

totalement humain
la source
1
Ici aussi, vous pouvez utiliser []comme cas de base: 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 1pour 95 octets!
Lynn
m==[]or sum(...)donne 92 octets.
Bubbler
3

Wolfram Language (Mathematica) , 53 52 octets

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

Essayez-le en ligne!

Malheureusement, le calcul du déterminant d'une matrice n par n utilise de cette manière la mémoire O ( n n ), ce qui éloigne de nombreux cas de test.

Comment ça marche

La première partie, 1##&@@@(t=Tuples)@#calcule tous les produits possibles d'un terme à partir de chaque ligne de la matrice donnée. t[Range@Tr[1^#]&/@#]donne une liste de la même longueur dont les éléments sont des choses comme {3,2,1}ou {2,2,3}indiquant quelle entrée de chaque rangée nous avons sélectionnée pour le produit correspondant.

Nous nous appliquons Signatureà la deuxième liste, qui mappe les permutations même en 1, les permutations impaires -1et les non-permutations 0. C'est précisément le coefficient avec lequel le produit correspondant apparaît dans le déterminant.

Enfin, prenons le produit scalaire des deux listes.


Si pair Signatureest trop intégré, à 73 octets, nous pouvons prendre

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

le remplacer par 1##&@@Order@@@#~Subsets~{2}&. Ceci calcule Signatureune éventuelle permutation en prenant le produit de Orderappliqué à tous les couples d'éléments de la permutation. Orderdonnera 1si la paire est dans l'ordre croissant, -1si elle est dans l'ordre décroissant et 0si elles sont égales.


-1 octet grâce à @ user202729

Misha Lavrov
la source
1
52 octets (au cas où vous ne sachiez pas cette astuce de golf de Mathematica)
user202729
Je l'ai fait, mais en quelque sorte oublié ici. Merci!
Misha Lavrov
3

Python 3 , 238 octets , 227 octets , 224 octets , 216 octets

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

Essayez-le en ligne!

Ma solution utilise la définition d'un déterminant pour les calculs. Malheureusement, la complexité de cet algorithme est n!et je ne peux pas montrer le passage du dernier test, mais en théorie c'est possible.

Кирилл Малышев
la source
3

CJam ( 50 45 octets)

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

C'est un bloc anonyme (fonction) qui prend un tableau 2D sur la pile et laisse un entier sur la pile.

Suite de tests en ligne

Dissection

Cela implémente l' algorithme Faddeev-LeVerrier , et je pense que c'est la première réponse à adopter cette approche.

ckn×nA

p(λ)det(λInA)=k=0nckλk
cn=1c0=(1)ndetA

Les coefficients sont déterminés récursivement de haut en bas, en fonction des matrices auxiliaires , M

M00cn=1(k=0)MkAMk1+cnk+1Icnk=1ktr(AMk)k=1,,n .

Le code ne fonctionne jamais directement avec et , mais toujours avec et , la récurrence est donc cnkMk(1)kcnk(1)k+1AMk

(1)kcnk=1ktr((1)k+1AMk)(1)k+2AMk+1=(1)kcnkAA((1)k+1AMk)

{               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
}
Peter Taylor
la source
2

Python 2 , 75 octets

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

Essayez-le en ligne!

Xnor
la source
2

SageMath , divers

Voici un tas de méthodes pour calculer le déterminant que j'ai trouvé intéressant, toutes programmées dans SageMath. Ils peuvent tous être essayés ici .

Builtin, 3 octets

det

Celui-ci n'est pas trop intéressant. Sage fournit des alias de niveau global à de nombreuses opérations courantes qui seraient normalement des méthodes d'objet. C'est donc plus court que lambda m:m.det().


Partie réelle du produit des valeurs propres, 36 octets

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

Malheureusement, ce eigenvaluesn'est pas l'un de ces alias de niveau global. Cela, combiné au fait que Sage n’a pas un moyen astucieux de composer des fonctions, signifie que nous avons un coût élevé lambda. Cette fonction contient des valeurs symboliques qui sont automatiquement converties en valeurs numériques lors de l’impression, de sorte que certaines sorties peuvent comporter une imprécision en virgule flottante.


Produit de Diagonal en Jordanie, forme normale, 60 octets

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

Dans la forme Jordan normale, une matrice NxN est représentée sous la forme d’une matrice de blocs, avec N blocs sur la diagonale. Chaque bloc consiste en une seule valeur propre ou en une matrice MxM avec une valeur propre répétée sur la diagonale et 1s sur la super-diagonale (la diagonale située au-dessus et à droite de la diagonale "principale"). Il en résulte une matrice avec toutes les valeurs propres (avec la multiplicité) sur la diagonale principale et certaines 1s sur la super-diagonale correspondant aux valeurs propres répétées. Ceci retourne le produit de la diagonale de la forme normale de Jordan, qui est le produit des valeurs propres (avec multiplicty). Il s’agit donc d’une manière plus détournée d’effectuer le même calcul que la solution précédente.

Parce que Sage veut que la forme normale de Jordan recouvre le même anneau que la matrice d'origine, cela ne fonctionne que si toutes les valeurs propres sont rationnelles. Les valeurs propres complexes entraînent une erreur (à moins que la matrice d'origine ne soit au-dessus de l'anneau CDF(doubles flottants complexes) ou SR). Cependant, cela signifie que prendre la partie réelle n’est pas nécessaire, par rapport à la solution ci-dessus.


Produit de Diagonal dans Smith Decomposition

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

Contrairement à la forme normale de Jordan, la forme normale de Smith est garantie sur le même champ que la matrice d'origine. Plutôt que de calculer les valeurs propres et de les représenter avec une matrice en bloc diagonale, la décomposition de Smith calcule les diviseurs élémentaires de la matrice (sujet un peu trop compliqué pour cet article), les place dans une matrice diagonale Det calcule deux matrices à unité déterminant Uet Vtel que D = U*A*V(où Aest la matrice d'origine). Depuis le déterminant du produit de matrices est égal au produit des déterminants des matrices ( det(A*B*...) = det(A)*det(B)*...) et Uet Vsont définis pour avoir des déterminants de l' unité, det(D) = det(A). Le déterminant d'une matrice diagonale est simplement le produit des éléments sur la diagonale.

Extension Laplace, 109 octets

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]

Ceci effectue une expansion de Laplace le long de la première ligne, en utilisant une approche récursive. det([[a]]) = aest utilisé pour le cas de base. Son utilisation devrait être plus courte det([[]]) = 1pour le scénario de base, mais ma tentative d' implémentation comportait un bogue que je n'ai pas encore pu localiser.


La formule de Leibniz, 100 octets

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

Ceci implémente directement la formule de Leibniz. Pour une bien meilleure explication de la formule et pourquoi cela fonctionne que je ne pourrais en écrire, voir cette excellente réponse .


Partie réelle de e^(Tr(ln(M))), 48 octets

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

Cette fonction renvoie des expressions symboliques. Pour obtenir une approximation numérique, appelez n(result)avant d’imprimer.

C’est une approche que je n’ai encore vue utiliser. Je vais donner une explication plus longue et plus détaillée pour celle-ci.

Soit Aune matrice carrée sur les réels. Par définition, le déterminant de Aest égal au produit des valeurs propres de A. La trace de Aest égale à la somme des Avaleurs propres de. Pour les nombres réels r_1et r_2, exp(r_1) * exp(r_2) = exp(r_1 + r_2). Puisque la fonction exponentielle de la matrice est définie comme étant analogue à la fonction exponentielle scalaire (en particulier dans l'identité précédente), et que l'exponentielle matricielle peut être calculée en diagonalisant la matrice et en appliquant la fonction exponentielle scalaire aux valeurs propres de la diagonale, nous pouvons dire det(exp(A)) = exp(trace(A))(le produit de exp(λ)chaque valeur propre λde Aest égale à la somme des valeurs propres de exp(A)). Ainsi, si nous pouvons trouver une matrice Ltelle queexp(L) = A, nous pouvons calculer det(A) = exp(trace(L)).

Nous pouvons trouver une telle matrice Len calculant log(A). Le logarithme de la matrice peut être calculé de la même manière que l'exponentielle de la matrice: formez une matrice de diagonale carrée en appliquant la fonction du logarithme scalaire à chaque valeur propre de A(c'est pourquoi nous nous sommes limités Aaux réels). Puisque nous ne nous soucions que de la trace de L, nous pouvons ignorer la construction et additionner directement les exponentielles des valeurs propres. Les valeurs propres peuvent être complexes, même si la matrice n'est pas au-dessus de l'anneau complexe, nous prenons donc la partie réelle de la somme.

Mego
la source
1
La dernière partie est une idée fascinante, mais l'en-tête et l'explication ne correspondent pas au code, ce qui ne prend pas un logarithme matriciel. C'est juste real(prod(m.eigenvalues()))non - golfé.
Peter Taylor
2

Java 8, 266 261 259 258 octets

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;}

Regarde maman, pas de construction .. car Java n'en a pas ..>.>

-7 octets grâce à @ceilingcat .

Explication:

Essayez ici. (Seul le dernier cas de test est trop volumineux pour tenir dans une longtaille de 2 63 -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
Kevin Cruijssen
la source
2

JavaScript (ES6), 91

Laplace récursive

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)

Moins golfé

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

Tester

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)
})

edc65
la source
83 octets avec le même comportement
Arnauld
Ou 85 octets pour prendre en charge la matrice vide (dont le déterminant devrait être 1 ).
Arnauld
(J'ai utilisé les mêmes optimisations dans cette réponse , qui est dérivée de la vôtre.)
Arnauld
1

Java (OpenJDK 8) , 195 192 177 octets

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;}

Essayez-le en ligne!

Comme beaucoup d'autres réponses, cela utilise également la formule de Laplace. Une version légèrement moins golfée:

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;
}
plafondcat
la source