Wprowadzenie

Dzisiaj zajmiemy się zmorą studentów pierwszego roku algebry liniowej: definitywnością macierzy! Najwyraźniej nie stanowi to jeszcze wyzwania, więc zaczynamy:

Wejście

• A symetryczna Matryca w dowolnym dogodnym formacie (możesz oczywiście wziąć tylko górną lub dolną część matrycy)$n\times n$ $A$
• Opcjonalnie: rozmiar matrycy$n$

Co robić?

Wyzwanie jest proste: biorąc pod uwagę macierz o wartości rzeczywistej Macierz decyduje, czy jest ona pozytywnie określona, ​​podając prawdziwą wartość, jeśli tak, i wartość falsey, jeśli nie.$n\times n$

Możesz założyć, że Twoje wbudowane naprawdę działają dokładnie, a zatem nie musisz brać pod uwagę problemów numerycznych, które mogłyby prowadzić do niewłaściwego zachowania, jeśli strategia / kod „możliwe do udowodnienia” przyniosą poprawny wynik.

Kto wygrywa?

To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach (na język)!

---

Czym w każdym razie jest Matryca dodatnia?

Istnieje najwyraźniej 6 równoważnych sformułowań, w których matryca symetryczna jest dodatnia. Powtórzę trzy łatwiejsze i odsyłam do Wikipedii w przypadku bardziej złożonych.

• Jeśli to jest dodatnie. Można to ponownie sformułować w następujący sposób: Jeżeli dla każdego niezerowego wektora iloczyn (standardowy) kropek i jest dodatni, to jest dodatnio określony.$\forall v\in\mathbb R^n\setminus \{0\}: v^T Av>0$$A$
  
  $v$$v$$Av$$A$
• Niech być wartości własne z , jeśli teraz (to jest wszystkich wartości własne są dodatnie), a następnie jest pozytywnie określone. Jeśli nie wiesz, jakie są wartości własne, sugeruję skorzystanie z ulubionej wyszukiwarki, aby się dowiedzieć, ponieważ wyjaśnienie (i potrzebne strategie obliczeniowe) jest zbyt długie, aby mogło zostać zawarte w tym poście.$\lambda_i\quad i\in\{1,\ldots,n\}$A ∀ i ∈ { 1 , … , n } : λ i > 0 A$A$$\forall i\in\{1,\ldots,n\}:\lambda_i>0$$A$
  
• Jeżeli Cholesky'ego-rozkładu z istnieje, to istnieje dolną trójkątne matrycy takie, że następnie jest dodatnio określony. Zauważ, że jest to równoważne wczesnemu zwróceniu wartości „fałsz”, jeśli w dowolnym momencie obliczenie katalogu głównego podczas algorytmu nie powiedzie się z powodu argumentu ujemnego.$A$$L$$LL^T=A$$A$

Przykłady

Dla prawdziwej wydajności

$$\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}$$

$$\begin{pmatrix}1&0&0&0\\0&2&0&0\\0&0&3&0\\0&0&0&4\end{pmatrix}$$

$$\begin{pmatrix}5&2&-1\\2&1&-1\\-1&-1&3\end{pmatrix}$$

$$\begin{pmatrix}1&-2&2\\-2&5&0\\2&0&30\end{pmatrix}$$

$$\begin{pmatrix}7.15&2.45\\2.45&9.37\end{pmatrix}$$

Dla wyjścia falsey

(co najmniej jedna wartość własna wynosi 0 / dodatnia półokreślona)

$$\begin{pmatrix}3&-2&2\\-2&4&0\\2&0&2\end{pmatrix}$$

(wartości własne mają różne znaki / nieokreślony)

$$\begin{pmatrix}1&0&0\\0&-1&0\\0&0&1\end{pmatrix}$$

(wszystkie wartości własne mniejsze niż 0 / definitywnie ujemne)

$$\begin{pmatrix}-1&0&0\\0&-1&0\\0&0&-1\end{pmatrix}$$

(wszystkie wartości własne mniejsze niż 0 / definitywnie ujemne)

$$\begin{pmatrix}-2&3&0\\3&-5&0\\0&0&-1\end{pmatrix}$$

(wszystkie wartości własne mniejsze niż 0 / definitywnie ujemne)

$$\begin{pmatrix}-7.15&-2.45\\-2.45&-9.37\end{pmatrix}$$

(trzy dodatnie, jedna ujemna wartość własna / nieokreślona)

$$\begin{pmatrix}7.15&2.45&1.23&3.5\\2.45&9.37&2.71&3.14\\1.23&2.71&0&6.2\\3.5&3.14&6.2&0.56\end{pmatrix}$$

C, 108 bajtów

-1 bajt dzięki Logern
-3 bajty dzięki ceilingcat

f(M,n,i)double**M;{for(i=n*n;i--;)M[i/n][i%n]-=M[n][i%n]*M[i/n][n]/M[n][n];return M[n][n]>0&(!n||f(M,n-1));}

Wypróbuj online!

Przeprowadza eliminację Gaussa i sprawdza, czy wszystkie elementy ukośne są dodatnie (kryterium Sylwestra). Argument njest rozmiarem macierzy minus jeden.

MATLAB / Octave , 19 17 12 bajtów

@(A)eig(A)>0

Wypróbuj online!

Funkcja eig zapewnia wartości własne w porządku rosnącym, więc jeśli pierwsza wartość własna jest większa od zera, pozostałe też są.

Galaretka , 11 10 bajtów

ṖṖ€$ƬÆḊṂ>0

Wykorzystuje kryterium Sylvester .

Wypróbuj online!

Jak to działa

ṖṖ€$ƬÆḊṂ>0  Main link. Argument: M (matrix)

   $Ƭ       Do the following until a fixed point is encountered.
Ṗ             Pop; remove the last row of the matrix.
 Ṗ€           Pop each; remove the last entry of each row.
     ÆḊ     Take the determinants of the resulting minors.
       Ṃ    Take the minimum.
        >0  Test if the least determinant is positive, i.e., if all determinants are.

R , 29 bajtów

function(m)all(eigen(m)$va>0)

Wypróbuj online!

---

Alternatywne użycie cholesky:

R , 34 33 bajtów

function(m)is.array(try(chol(m)))

Wypróbuj online!

-1 bajt dzięki @Giuseppe

Haskell , 56 bajtów

f((x:y):z)=x>0&&f[zipWith(-)v$map(u/x*)y|u:v<-z]
f[]=1>0

Wypróbuj online!

Zasadniczo port odpowiedzi nwellnhofa . Dokonuje eliminacji gaussowskiej i sprawdza, czy elementy na głównej przekątnej są dodatnie.

Nie udaje się uzyskać pierwszego wyniku falsey z powodu błędów zaokrąglania, ale teoretycznie działałoby to z nieskończoną precyzją. Dzięki sugestii Curtisa Bechtela wszystkie wyniki są teraz prawidłowe.

Wolfram Language (Mathematica) , 20 bajtów

0<Min@Eigenvalues@#&

Wypróbuj online!

MATL , 4 bajty

Yv0>

Wypróbuj online!

[3 -2 2; -2 4 0; 2 0 2]0$10^{-18}$

Mathematica, 29 28 bajtów

AllTrue[Eigenvalues@#,#>0&]&

Definicja 2.

Julia 1.0 , 28 bajtów

using LinearAlgebra
isposdef

Wypróbuj online!

---

Julia 0.6 , 8 bajtów

isposdef

Wypróbuj online!

MATL , 6 bajtów

Można to zrobić przy użyciu jeszcze mniej bajtów @Mr. Xcoderowi udało się znaleźć 5-bajtową odpowiedź MATL !

YvX<0>

Wyjaśnienie

Yv     compute eigenvalues
  X<   take the minimum
    0> check whether it is greather than zero

Wypróbuj online!

Klon , 33 bajty

(tj. moje 2 centy)

with(LinearAlgebra):
IsDefinite(A)

JavaScript (ES6),  99 95  88 bajtów

$0$$1$

f=(m,n=0,R=m[n])=>R?f(m,n+1)&R[m.map((r,y)=>y<n&&R.map((v,x)=>r[x]-=v*r[n]/R[n])),n]>0:1

Wypróbuj online!