Diberikan matriks integer persegi sebagai input, output penentu matriks.
Aturan
- Anda dapat mengasumsikan bahwa semua elemen dalam matriks, penentu matriks, dan jumlah total elemen dalam matriks berada dalam kisaran integer yang dapat diwakili untuk bahasa Anda.
- Mengeluarkan nilai desimal / float dengan bagian pecahan 0 diperbolehkan (misalnya,
42.0
bukan42
). - Builtin diizinkan, tetapi Anda disarankan untuk memasukkan solusi yang tidak menggunakan builtin.
Uji Kasus
[[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
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.
Jawaban:
Jelly , 15 byte
Cobalah online!
Bagaimana itu bekerja
Mengapa ini berfungsi - versi matematika
Operator det mengambil matriks dan mengembalikan skalar. Sebuah n -by- n matriks dapat dianggap sebagai kumpulan n vektor panjang n , sehingga det benar-benar fungsi yang mengambil n vektor dari ℤ n dan kembali skalar.
Karenanya, saya menulis det ( v 1 , v 2 , v 3 , ..., v n ) untuk det [ v 1 v 2 v 3 ... v n ].
Perhatikan bahwa det adalah linear dalam setiap argumen, yaitu 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 ). Oleh karena itu, ini adalah peta linear dari (ℤ n ) ⊗ n ke ℤ.
Cukuplah untuk menentukan gambar dasar di bawah peta linear. Basis dari (ℤ n ) ⊗ n terdiri dari n- kali lipat produk tensor dari elemen dasar ℤ n , yaitueg e 5 ⊗ e 3 ⊗ e 1 ⊗ e 5 ⊗ e 1 . Produk tensor yang menyertakan tensor identik harus dikirim ke nol, karena penentu matriks yang dua kolomnya identik adalah nol. Masih untuk memeriksa apa produk tensor dari elemen dasar berbeda dikirim ke. Indeks vektor dalam produk tensor membentuk suatu bijection, yaitu permutasi, di mana permutasi bahkan dikirim ke 1 dan permutasi ganjil dikirim ke -1.
Misalnya, untuk menemukan determinan [[1, 2], [3, 4]]: perhatikan bahwa kolomnya adalah [1, 3] dan [2, 4]. Kami menguraikan [1, 3] untuk memberi (1 e 1 + 3 e 2 ) dan (2 e 1 + 4 e 2 ). Elemen yang sesuai dalam produk tensor adalah (1 e 1 ⊗ 2 e 1 + 1 e 1 ⊗ 4 e 2 + 3 e 2 ⊗ 2 e 1 + 3 e 2 ⊗ 4 e 2 ), yang kami sederhanakan menjadi (2 e 1 ⊗ e 1 + 4 e 1 ⊗ e 2 + 6 e 2 ⊗ e 1 + 12 e 2 ⊗ e 2). Karena itu:
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 e 2⊗ e 2 )
= 2 det (e 1 ⊗ e 1 ) + 4 det (e 1 ⊗ e 2 ) + 6 det (e 2 ⊗ e 1 ) + 12 det (e 2 ⊗ e 2 )
= 2 (0) + 4 (1) + 6 (-1) + 12 (0)
= 4 - 6
= -2
Sekarang tetap membuktikan bahwa formula untuk menemukan paritas permutasi adalah valid. Apa yang dilakukan kode saya pada dasarnya adalah menemukan jumlah inversi, yaitu tempat-tempat di mana elemen di sebelah kiri lebih besar daripada elemen di sebelah kanan (tidak harus secara berurutan).
Sebagai contoh, dalam permutasi 3614572, ada 9 inversi (31, 32, 61, 64, 65, 62, 42, 52, 72), sehingga permutasi aneh.
Pembenarannya adalah bahwa setiap transposisi (bertukar dua elemen) baik menambah satu inversi atau menghilangkan satu inversi, menukar paritas jumlah inversi, dan paritas permutasi adalah paritas jumlah transposisi yang diperlukan untuk mencapai permutasi.
Karena itu, sebagai kesimpulan, formula kami diberikan oleh:
Mengapa ini berfungsi - versi non-matematika
di mana σ adalah permutasi dari 𝕊 n kelompok semua permutasi pada n huruf, dan sgn adalah tanda dari permutasi, AKA (-1) diangkat ke paritas permutasi, dan sebuah ij adalah ( ij ) th masuk dalam matriks ( i down, j across).
sumber
R , 3 byte
Solusi Sepele
Cobalah online!
R ,
9492 bytesolusi yang diimplementasikan kembali
dikalahkan oleh Jarko Dubbeldam
Cobalah online!
Secara rekursif menggunakan ekspansi oleh anak di bawah umur di kolom pertama dari matriks.
sumber
Jelly ,
16151210 byteMenggunakan ekspansi Laplace . Terima kasih kepada @miles karena bermain golf
35 byte!Cobalah online!
Bagaimana itu bekerja
sumber
Bahasa Wolfram (Mathematica) , antara 14 dan 42 byte
Kami memiliki solusi built-in 3-byte dan 53-byte yang sepenuhnya menghindari built-in, jadi inilah beberapa solusi aneh di antaranya.
Bahasa Wolfram memiliki banyak fungsi yang sangat intens untuk menguraikan matriks menjadi produk dari matriks lain dengan struktur yang lebih sederhana. Salah satu yang lebih sederhana (artinya saya pernah mendengarnya sebelumnya) adalah dekomposisi Jordan. Setiap matriks mirip dengan matriks segitiga atas (mungkin bernilai kompleks) yang terbuat dari balok diagonal dengan struktur tertentu, yang disebut dekomposisi Jordan dari matriks itu. Kesamaan mempertahankan determinan, dan determinan matriks segitiga adalah produk dari elemen diagonal, sehingga kita dapat menghitung determinan dengan 42 byte berikut :
Penentu juga sama dengan produk dari nilai eigen dari sebuah matriks, dengan multiplisitas. Untungnya, fungsi eigenvalue Wolfram melacak multiplisitas (bahkan untuk matriks yang tidak dapat diagonal), jadi kami mendapatkan solusi 20 byte berikut :
Solusi berikutnya adalah jenis kecurangan dan saya tidak begitu yakin mengapa itu berhasil. Wronskian dari daftar fungsi n adalah penentu matriks turunan n -1 pertama dari fungsi. Jika kita memberi
Wronskian
fungsi sebuah matriks bilangan bulat dan mengatakan bahwa variabel diferensiasi adalah 1, entah bagaimana ia memuntahkan determinan matriks tersebut. Ini aneh, tetapi tidak melibatkan huruf "Det
" dan hanya 14 byte ...(Penentu Casoratian bekerja dengan baik, untuk 1 byte:
#~Casoratian~1&
)Di ranah aljabar abstrak, determinan dari suatu n x n matriks (dianggap sebagai peta k → k yaitu perkalian dengan determinan) adalah n th kekuatan luar matriks (setelah memetik isomorfisma k → ⋀ n k n ). Dalam bahasa Wolfram, kita bisa melakukan ini dengan 26 byte berikut :
Dan inilah solusi yang hanya berfungsi untuk penentu positif. Jika kita mengambil unit hypercube n -dimensi dan menerapkan transformasi linear untuknya, "volume" n -dimensi dari wilayah yang dihasilkan adalah nilai absolut dari penentu transformasi. Menerapkan transformasi linear ke kubus memberikan paralelepiped, dan kita dapat mengambil volumenya dengan 39 byte kode berikut:
sumber
Exp@*Tr@*MatrixLog
, tetapi sayangnya ini tidak bekerja untuk matriks tunggal.Check[E^Tr@MatrixLog@#,0]&
.Check
sebelumnya.Haskell , 71 byte
-3 byte terima kasih kepada Lynn. Satu lagi bytes debu berkat Craig Roy.
Cobalah online! Menambahkan
-O
bendera untuk tujuan pengoptimalan. Itu tidak perlu.Penjelasan (kedaluwarsa)
f
secara rekursif mengimplementasikan ekspansi kofaktor.Baris ini mencakup kasus dasar dari 1 × 1 matriks, dalam hal determinan adalah
mat[0, 0]
.Ini menggunakan pencocokan pola Haskell untuk memecah matriks menjadi kepala (baris pertama) dan ekor (sisa matriks).
Hitunglah kepala matriks (dengan membuat zip daftar tak terhingga dari bilangan bulat dan kepala) dan beralih di atasnya.
Meniadakan hasil berdasarkan apakah indeksnya bahkan karena perhitungan faktor penentu melibatkan penambahan dan pengurangan bergantian.
Ini pada dasarnya menghilangkan kolom ke - i dari ekor dengan mengambil elemen i dan menyatukannya dengan baris dengan elemen pertama (i + 1) yang dijatuhkan untuk setiap baris di ekor.
Hitung penentu hasil di atas dan kalikan dengan hasil
(-1)*i*v
.Jumlahkan hasil dari daftar di atas dan kembalikan.
sumber
sum[(-1)^i*...
denganfoldr(-)0[...
Proton , 99 byte
Cobalah online!
-3 byte terima kasih kepada Tn. Xcoder
-3 byte terima kasih kepada Erik the Outgolfer
Perluasan di baris pertama
sumber
((~i%2)*2-1)
->((-i%2)|1)
j!=i
denganj-i
ataui-j
.Oktaf , 28 byte
Cobalah online!
Ini menggunakan satu QR dekomposisi dari matriks X ke dalam matriks orthgonal Q dan segitiga atas matriks R . Determinan X adalah produk dari orang-orang dari Q dan R . Matriks ortogonal memiliki penentu satuan, dan untuk matriks segitiga penentu adalah produk dari entri diagonal. Oktaf
qr
fungsi yang disebut dengan output tunggal memberikan R .Hasilnya dibulatkan ke bilangan bulat terdekat. Untuk matriks input besar, ketidaktepatan titik apung dapat menghasilkan kesalahan yang melebihi
0.5
dan dengan demikian menghasilkan hasil yang salah.sumber
det
builtin. ;)Haskell , 59 byte
Cobalah online!
sumber
C,
176125 byteTerima kasih kepada @ceilingcat untuk bermain golf 42 byte, dan terima kasih kepada @Lynn dan @Jonathan Frech karena telah menghemat setiap byte!
Hitung penentu menggunakan ekspansi Laplace di sepanjang baris pertama.
Cobalah online!
Belum dibuka:
sumber
(i%2*-2+1)
→(1-i%2*2)
menyimpan satu byte lagi.n+1+c
bisan-~c
.i=s
alih-alihreturn s
Jelly , 43 byte
Akhirnya saya selesai menulis solusi non-builtin saya dalam bahasa golf!
Terima kasih kepada HyperNeutrino karena telah menghemat satu byte!
Cobalah online! (kode spasi untuk kejelasan)
Cara yang sangat panjang untuk menghapus elemen ke-n dari daftar, akan ditingkatkan nanti
Jawaban ini dikalahkan oleh jawaban HyperNeutrino, Dennis dan Leaky Nun. Jelly sangat populer sebagai bahasa golf.
Penjelasan cepat:
sumber
Jelly , 24 byte
Cobalah online!
Penjelasan
-2 byte berkat solusi user202729
sumber
MATL , 3 byte / 5 byte
Dengan fungsi bawaan
Cobalah online!
Tanpa built-in
Terima kasih kepada Misha Lavrov karena menunjukkan kesalahan, sekarang diperbaiki
Cobalah online!
Ini menghitung determinan sebagai produk dari nilai eigen, dibulatkan ke bilangan bulat terdekat untuk menghindari ketidakakuratan titik-mengambang.
sumber
R , 32 byte
Menggunakan Algoritma Not a Tree untuk mengambil nilai eigen dari matriks dan mengambil bagian nyata dari produk mereka.
Cobalah online!
sumber
Oktaf , 30 byte
Cobalah online!
atau, solusi 4 byte yang membosankan (disimpan 6 byte berkat Luis Mendo (lupa aturan tentang fungsi fungsi builtin)):
Penjelasan:
Akan datang! :)
sumber
TI-Basic, 2 byte
Ah, baiklah.
Tolong jangan mundur jawaban sepele.
Sebagai siswa sekolah menengah (yang terpaksa memiliki salah satu kalkulator ini), fungsi ini sangat berguna ...
sumber
Haskell, 62 byte
Cobalah online! (Catatan kaki dengan kasus uji diambil dari solusi @ totallyhuman.)
d
menghitung penentu menggunakan ekspansi Laplace di sepanjang kolom pertama. Membutuhkan tiga byte lebih banyak daripada yang permanen .sumber
Python 2 , 95 byte
-12 byte terima kasih kepada Lynn.
Port jawaban Haskell saya .
Cobalah online!
sumber
[]
sebagai alas: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
untuk 95 byte!m==[]or sum(...)
memberikan 92 byte.Bahasa Wolfram (Mathematica) ,
5352 byteCobalah online!
Sayangnya, menghitung determinan matriks n demi n dengan cara ini menggunakan memori O ( n n ), yang menempatkan kotak uji besar di luar jangkauan.
Bagaimana itu bekerja
Bagian pertama
1##&@@@(t=Tuples)@#
,, menghitung semua produk yang mungkin dari suatu istilah dari setiap baris dari matriks yang diberikan.t[Range@Tr[1^#]&/@#]
memberikan daftar dengan panjang yang sama yang elemennya seperti{3,2,1}
atau{2,2,3}
mengatakan entri mana dari setiap baris yang kita pilih untuk produk yang sesuai.Kami berlaku
Signature
untuk daftar kedua, yang memetakan permutasi bahkan1
, permutasi aneh-1
, dan non-permutasi0
. Inilah tepatnya koefisien dengan mana produk yang sesuai muncul dalam determinan.Akhirnya, kami mengambil produk titik dari dua daftar.
Jika bahkan
Signature
terlalu banyak built-in, pada 73 byte kita dapat mengambilmenggantinya dengan
1##&@@Order@@@#~Subsets~{2}&
. Ini menghitungSignature
permutasi-mungkin dengan mengambil produk yangOrder
diterapkan pada semua pasangan elemen permutasi.Order
akan memberi1
jika pasangan dalam urutan naik,-1
jika dalam urutan menurun, dan0
jika mereka sama.-1 byte terima kasih kepada @ user202729
sumber
Python 3 ,
238 byte,227 byte,224 byte, 216 byteCobalah online!
Solusi saya menggunakan definisi penentu untuk perhitungan. Sayangnya, kompleksitas dari algoritma ini
n!
dan saya tidak dapat menunjukkan bagian dari tes terakhir, tetapi secara teori ini mungkin.sumber
CJam (
5045 bytes)Ini adalah blok anonim (fungsi) yang mengambil array 2D pada stack dan meninggalkan integer pada stack.
Test suite online
Pembedahan
Ini mengimplementasikan algoritma Faddeev-LeVerrier , dan saya pikir ini adalah jawaban pertama untuk mengambil pendekatan itu.
The code never works directly withcn−k and Mk , but always with (−1)kcn−k and (−1)k+1AMk , so the recurrence is
(−1)kcn−k=1ktr((−1)k+1AMk)(−1)k+2AMk+1=(−1)kcn−kA−A((−1)k+1AMk)
sumber
Wolfram Language (Mathematica), 3 bytes
Try it online!
Per the meta consensus, mainly upvote nontrivial solutions that take effort to write.
sumber
Python 2, 75 bytes
Try it online!
sumber
SageMath, various
Here are a bunch of methods for computing the determinant that I found interesting, all programmed in SageMath. They can all be tried here.
Builtin, 3 bytes
This one isn't too interesting. Sage provides global-level aliases to many common operations that would normally be object methods, so this is shorter than
lambda m:m.det()
.Real Part of Product of Eigenvalues, 36 bytes
Unfortunately,
eigenvalues
is not one of those global-level aliases. That, combined with the fact that Sage doesn't have a neat way to compose functions, means we're stuck with a costlylambda
. This function symbolic values which are automatically converted to numeric values when printed, so some floating point inaccuracy may be present in some outputs.Product of Diagonal in Jordan Normal Form, 60 bytes
In Jordan Normal form, an NxN matrix is represented as a block matrix, with N blocks on the diagonal. Each block consists of either a single eigenvalue, or a MxM matrix with a repeated eigenvalue on the diagonal and
1
s on the super-diagonal (the diagonal above and to the right of the "main" diagonal). This results in a matrix with all eigenvalues (with multiplicity) on the main diagonal, and some1
s on the super-diagonal corresponding to repeated eigenvalues. This returns the product of the diagonal of the Jordan normal form, which is the product of the eigenvalues (with multiplicty), so this is a more roundabout way of performing the same computation as the previous solution.Because Sage wants the Jordan normal form to be over the same ring as the original matrix, this only works if all of the eigenvalues are rational. Complex eigenvalues result in an error (unless the original matrix is over the ring
CDF
(complex double floats) orSR
). However, this means that taking the real part is not necessary, compared to the above solution.Product of Diagonal in Smith Decomposition
Unlike Jordan normal form, Smith normal form is guaranteed to be over the same field as the original matrix. Rather than computing the eigenvalues and representing them with a block diagonal matrix, Smith decomposition computes the elementary divisors of the matrix (which is a topic a bit too complicated for this post), puts them into a diagonal matrix
D
, and computes two matrices with unit determinantU
andV
such thatD = U*A*V
(whereA
is the original matrix). Since the determinant of the product of matrices equals the product of the determinants of the matrices (det(A*B*...) = det(A)*det(B)*...
), andU
andV
are defined to have unit determinants,det(D) = det(A)
. The determinant of a diagonal matrix is simply the product of the elements on the diagonal.Laplace Expansion, 109 bytes
This performs Laplace expansion along the first row, using a recursive approach.
det([[a]]) = a
is used for the base case. It should be shorter to usedet([[]]) = 1
for the base case, but my attempt at that implementation had a bug that I haven't been able to track down yet.Leibniz's Formula, 100 bytes
This directly implements Leibniz's formula. For a much better explanation of the formula and why it works than I could possibly write, see this excellent answer.
Real Part of
e^(Tr(ln(M)))
, 48 bytesThis function returns symbolic expressions. To get a numerical approximation, call
n(result)
before printing.This is an approach that I haven't seen anyone use yet. I'm going to give a longer, more-detailed explanation for this one.
Let
A
be a square matrix over the reals. By definition, the determinant ofA
is equal to the product of the eigenvalues ofA
. The trace ofA
is equal to the sum ofA
's eigenvalues. For real numbersr_1
andr_2
,exp(r_1) * exp(r_2) = exp(r_1 + r_2)
. Since the matrix exponential function is defined to be analogous to the scalar exponential function (especially in the previous identity), and the matrix exponential can be computed by diagonalizing the matrix and applying the scalar exponential function to the eigenvalues on the diagonal, we can saydet(exp(A)) = exp(trace(A))
(the product ofexp(λ)
for each eigenvalueλ
ofA
equals the sum of the eigenvalues ofexp(A)
). Thus, if we can find a matrixL
such thatexp(L) = A
, we can computedet(A) = exp(trace(L))
.We can find such a matrix
L
by computinglog(A)
. The matrix logarithm can be computed in the same way as the matrix exponential: form a square diagonal matrix by applying the scalar logarithm function to each eigenvalue ofA
(this is why we restricedA
to the reals). Since we only care about the trace ofL
, we can skip the construction and just directly sum the exponentials of the eigenvalues. The eigenvalues can be complex, even if the matrix isn't over the complex ring, so we take the real part of the sum.sumber
real(prod(m.eigenvalues()))
ungolfed.Java 8,
266261259258 bytesLook mom, no build-ins.. because Java has none.. >.>
-7 bytes thanks to @ceilingcat.
Explanation:
Try it here. (Only the last test case is too big to fit in a
long
of size 263-1.)sumber
JavaScript (ES6), 91
Recursive Laplace
Less golfed
Test
sumber
Python 2 + numpy, 29 bytes
Try it online!
sumber
Julia, 3 bytes
Try it online!
sumber
Pari/GP, 6 bytes
Try it online!
sumber
Java (OpenJDK 8),
195 192177 bytesTry it online!
Like many other answers, this also uses the Laplace formula. A slightly less golfed version:
sumber
J, 5 bytes
Try it online!
sumber