태그 보관물: linear-algebra

linear-algebra

정수 행렬의 결정자 244, -422]] -> -51446016699154 [[416, 66, 340,

입력으로 제곱 정수 행렬이 주어지면 행렬의 행렬식을 출력하십시오.

규칙

  • 행렬의 모든 요소, 행렬의 결정 요인 및 행렬의 총 요소 수는 사용 가능한 언어의 정수 범위 내에 있다고 가정 할 수 있습니다.
  • 소수 부분이 0 인 10 진수 / 부동 값을 출력 할 수 있습니다 (예 : 42.0대신 42).
  • 내장은 허용되지만 내장을 사용하지 않는 솔루션을 포함하는 것이 좋습니다.

테스트 사례

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


답변

젤리 , 15 바이트

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

온라인으로 사용해보십시오!

작동 원리

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

작동하는 이유-Mathy 버전

연산자 det 는 행렬을 취하고 스칼라를 반환합니다. N -by- N의 행렬의 집합으로 간주 될 수 N 길이의 벡터 N 있도록 DET가 취하는 함수 정말 N ℤ로부터 벡터 n은 스칼라 및 반환.

따라서 det [ v 1 v 2 v 3v n ]에 대해 det ( v 1 , v 2 , v 3 , …, v n )를 작성 합니다.

공지 것을 DET는 각각 인수 선형, 즉 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 ). 따라서 (ℤ n ) n 의 선형 맵입니다. ℤ.

선형 맵에서 기본 이미지를 결정하면 충분합니다. (ℤ 용의 기초 N ) n은 구성 N ℤ의 기본 요소 -fold 텐서 제품 N , E ieeg 5 ⊗ 예 3 ⊗ 예 1 ⊗ 예 5 ⊗ 예 1 . 두 열이 동일한 행렬의 행렬식이 0이므로 동일한 텐서가 포함 된 텐서 제품을 0으로 보내야합니다. 별개의 기본 요소의 텐서 제품이 전송되는 것을 확인해야합니다. 텐서 곱에서 벡터의 인덱스는 bijection, 즉 순열을 형성하는데,이 순열은 심지어 순열도 1로 보내지고 홀수 순열은 -1로 보내진다.

예를 들어 [[1, 2], [3, 4]]의 결정자를 찾으려면 열이 [1, 3] 및 [2, 4]입니다. [1, 3]을 분해하여 (1 e 1 + 3 e 2 )와 (2 e 1 + 4 e 2 )를 제공합니다. 텐서 제품의 해당 요소는 (1 e 1 ⊗ 2 e 1 + 1 e 1 ⊗ 4 e 2 + 3 e 2 ⊗ 2 e 1 + 3 e 2 ⊗ 4 e 2 )이며, 우리는 (2 e 1 ⊗ e 1 + 4 e 1 ⊗ e 2 + 6 e 2 ⊗ e 1 + 12 e 2 ⊗ e 2). 따라서:

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

이제 순열의 패리티를 찾는 공식이 유효하다는 것을 증명해야합니다. 내 코드의 역할은 본질적으로 반전의 수, 즉 왼쪽의 요소가 오른쪽의 요소보다 큰 곳을 찾는 것입니다 (반드시 연속적이지는 않음).

예를 들어 순열 3614572에는 9 개의 반전 (31, 32, 61, 64, 65, 62, 42, 52, 72)이 있으므로 순열이 홀수입니다.

각 전치 (두 요소를 교환)는 하나의 반전을 추가하거나 하나의 반전을 제거하여 반전 수의 패리티를 바꾸고 순열의 패리티는 순열을 달성하는 데 필요한 조옮김 수의 패리티입니다.

결론적으로 우리의 공식은 다음과 같습니다.

왜 작동합니까?

여기서 σ는 n 문자 에 대한 모든 순열의 그룹 𝕊 n 의 순열 이며, sgn 은 순열의 부호이며, AKA (-1)은 순열의 패리티로 올렸으며 , ij 는 ( ij ) 번째 항목입니다. 행렬 ( i down, j across).


답변

R , 3 바이트

사소한 솔루션

det

온라인으로 사용해보십시오!

R , 94 92 바이트

재 구현 된 솔루션

Jarko Dubbeldam에 의해 outgolfed

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

온라인으로 사용해보십시오!

행렬의 첫 번째 열 아래에있는 마이너에 의한 확장을 재귀 적으로 사용합니다.

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

답변

젤리 , 16 15 12 10 바이트

Ḣ×Zß-Ƥ$Ṛḅ-

Laplace 확장을 사용합니다 . 3 5 바이트 를 골라 낸 @miles에게 감사 합니다!

온라인으로 사용해보십시오!

작동 원리

Ḣ×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.

답변

14에서 42 바이트 사이의 Wolfram Language (Mathematica)

우리는 내장 을 완전히 피하는 3 바이트 내장53 바이트 솔루션 을 가지고 있으므로 여기에 어딘가에있는 더 이상한 솔루션이 있습니다.

볼프람 언어가 많은 간단한 구조로 다른 행렬의 제품으로 행렬을 분해 매우 강렬 기능을. 가장 간단한 것 중 하나 (이전에 들어 본 것을 의미 함)는 요르단 분해입니다. 모든 행렬은 해당 행렬의 요르단 분해라고하는 특정 구조의 대각선 블록으로 구성된 (복잡한 값을 갖는) 상단 삼각 행렬과 유사합니다. 유사성은 결정자를 유지하며, 삼각 행렬의 결정자는 대각선 요소의 곱이므로 다음 42 바이트로 결정자를 계산할 수 있습니다 .

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

또한 행렬식은 행렬의 고유 값 곱과 동일합니다. 운 좋게도 Wolfram의 고유 값 함수는 다중화를 추적합니다 (대각선이 가능하지 않은 행렬의 경우에도). 따라서 다음 20 바이트 솔루션을 얻습니다 .

1##&@@Eigenvalues@#&

다음 해결책은 일종의 부정 행위이며 그것이 왜 효과가 있는지 잘 모르겠습니다. n 함수 목록의 Wronskian은 함수의 첫 번째 n -1 미분의 행렬을 결정 합니다. Wronskian함수에 정수의 행렬을 제공하고 미분 변수가 1이라고 말하면 어떻게 든 행렬의 결정자를 뱉어냅니다. 이상하지만 문자 ” Det“를 포함하지 않으며 14 바이트에 불과 합니다 .

#~Wronskian~1&

(Casoratian 결정 요인도 1 바이트 이상 작동합니다. #~Casoratian~1&)

추상 대수의 영역에서, n  x  n 행렬의 결정 인자 (결정자에 의해 곱하는 맵 k → k로 생각됨)는 행렬 의 n 번째 외부 거듭 제곱입니다 (동 형사를 선택한 후 k → ⋀ n k n ). Wolfram 언어에서는 다음과 같은 26 바이트로이를 수행 할 수 있습니다 .

HodgeDual[TensorWedge@@#]&

그리고 여기에 긍정적 결정 요인에 대해서만 작동하는 솔루션이 있습니다. n 차원 단위 하이퍼 큐브를 가져와 선형 변환을 적용 하면 결과 영역 의 n 차원 “볼륨”이 변환 결정 요인의 절대 값입니다. 큐브에 선형 변환을 적용하면 평행 육면체가 생성되며 다음 39 바이트 코드로 볼륨을 계산할 수 있습니다 .

RegionMeasure@Parallelepiped[Last@#,#]&

답변

하스켈 , 71 바이트

Lynn 덕분에 -3 바이트. 크레이그 로이 덕분에 또 하나의 먼지가 먼지입니다.

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

온라인으로 사용해보십시오! 최적화 목적으로 플래그를 추가했습니다 -O. 필요하지 않습니다.

설명 (오래됨)

f 코 팩터 확장을 재귀 적으로 구현합니다.

f[[x]]=x

이 선은 1 × 1 행렬 의 기본 경우를 다루며, 이 경우 결정자는 mat[0, 0]입니다.

f(h:t)=

Haskell의 패턴 일치 를 사용 하여 행렬을 머리 (첫 번째 행)와 꼬리 (행렬의 나머지 ) 로 나눕니다 .

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

정수의 정수 목록과 머리를 압축하여 행렬의 머리를 열거하고 반복합니다.

           (-1)*i*v

행렬식의 계산에 덧셈과 뺄셈이 교대로 포함되므로 인덱스의 지수에 따라 결과를 무효화합니다.

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

이것은 본질적으로 i 요소 를 가져 와서 꼬리 의 모든 행에 대해 첫 번째 (i + 1) 번째 요소가 떨어진 행과 연결 하여 꼬리 의 i 번째 열을 제거합니다 .

                   *f

위 결과의 결정 요인을 계산하고 결과에 곱하십시오 (-1)*i*v.

       sum

위 목록의 결과를 합산하여 반환합니다.


답변

양성자 , 99 바이트

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)

온라인으로 사용해보십시오!

Mr. Xcoder 덕분에
-3 바이트 Outgofer Erik 덕분에 -3 바이트

첫 번째 행을 통한 확장


답변

옥타브 , 28 바이트

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

온라인으로 사용해보십시오!

이것은 행렬 X 의 직교 행렬 Q 및 상부 삼각 행렬 R 로의 QR 분해 를 사용한다 . 결정의 X는 의 이들의 제품 QR . 직교 행렬은 단위 결정자를 가지며, 삼각 행렬의 경우 결정자는 대각선 항목의 곱입니다. 단일 출력으로 호출 된 옥타브의 함수는 R을 제공합니다 .qr

결과는 가장 가까운 정수로 반올림됩니다. 큰 입력 행렬의 경우 부동 소수점 부정확성이 오류를 초과 0.5하여 잘못된 결과를 생성 할 수 있습니다.