Introdução

Hoje nós vamos cuidar da desgraça dos alunos do primeiro ano de álgebra linear: definição de matriz! Aparentemente, isso ainda não tem um desafio, então vamos lá:

Entrada

• Uma Matriz $n\times n$ simétrica $A$ em qualquer formato conveniente (você também pode, naturalmente, pegar apenas a parte superior ou a parte inferior da matriz)
• Opcionalmente: o tamanho da matriz $n$

O que fazer?

O desafio é simples: dada uma matriz com valor real $n\times n$ Matriz decide se é definida positivamente emitindo um valor verdadeiro, se for o caso, e um valor falsey, se não.

Você pode supor que seus internos realmente funcionem com precisão e, portanto, não sejam responsáveis ​​por problemas numéricos que podem levar ao comportamento errado se a estratégia / código "provável" produzir o resultado correto.

Quem ganha?

Isso é código-golfe , então o código mais curto em bytes (por idioma) vence!

---

O que é uma matriz positiva definida de qualquer maneira?

Aparentemente, existem 6 formulações equivalentes de quando uma matriz simétrica é definida positivamente. Vou reproduzir os três mais fáceis e referenciá-lo à Wikipedia para os mais complexos.

• Se $\forall v\in\mathbb R^n\setminus \{0\}: v^T Av>0$ então $A$ é positivo-definido.
  Isto pode ser formulado como re-:
  Se para cada diferente de zero vetor $v$ o (padrão) dot produto de $v$ e $Av$ for positivo, então $A$ será positivo.
• Seja $\lambda_i\quad i\in\{1,\ldots,n\}$ são osautovaloresde$A$ , se agora$\forall i\in\{1,\ldots,n\}:\lambda_i>0$ (ou seja, todos os autovalores são positivos), então$A$ é positivo-definido.
  Se você não sabe quais são os autovalores, sugiro que você use seu mecanismo de pesquisa favorito para descobrir, porque a explicação (e as estratégias de computação necessárias) é muito longa para ser contida neste post.
• Se a decomposição de Cholesky de $A$ existe, isto é, existe uma matriz triangular inferior $L$ tal que $LL^T=A$ então $A$ é definida positiva. Observe que isso é equivalente a "false" de retorno antecipado se a qualquer momento o cálculo da raiz durante o algoritmo falhar devido a um argumento negativo.

Exemplos

Para saída de verdade

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

Para saída falsey

(pelo menos um valor próprio é 0 / semi-definido positivo)

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

(valores próprios têm sinais diferentes / indefinidos)

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

(todos os autovalores menores que 0 / negativo definido)

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

(todos os autovalores menores que 0 / definido negativo)

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

(todos os autovalores menores que 0 / definido negativo)

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

(três positivos, um autovalor negativo / indefinido)

$$\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 bytes

-1 byte graças ao Logern
-3 bytes graças ao 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));}

Experimente online!

Executa a eliminação gaussiana e verifica se todos os elementos diagonais são positivos (critério de Sylvester). Argumento né o tamanho da matriz menos um.

MATLAB / Oitava , 19 17 12 bytes

@(A)eig(A)>0

Experimente online!

A função eig fornece os autovalores em ordem crescente, portanto, se o primeiro autovalor for maior que zero, os outros também.

Geléia , 11 10 bytes

ṖṖ€$ƬÆḊṂ>0

Usa o critério de Sylvester .

Experimente online!

Como funciona

ṖṖ€$ƬÆḊṂ>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 bytes

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

Experimente online!

---

Alternativa usando cholesky:

R , 34 33 bytes

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

Experimente online!

-1 byte graças a @ Giuseppe

Haskell , 56 bytes

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

Experimente online!

Basicamente, um porto de resposta do nwellnhof . Executa a eliminação gaussiana e verifica se os elementos na diagonal principal são positivos.

Falha na primeira saída falsey devido a erros de arredondamento, mas teoricamente funcionaria com precisão infinita. Graças à sugestão de Curtis Bechtel , agora os resultados estão todos corretos.

Wolfram Language (Mathematica) , 20 bytes

0<Min@Eigenvalues@#&

Experimente online!

MATL , 4 bytes

Yv0>

Experimente online!

Percebi que, para o [3 -2 2; -2 4 0; 2 0 2]caso de teste, o MATL calcula o 0autovalor com uma imprecisão muito pequena, calculando algo tão baixo quanto$10^{-18}$. Portanto, isso falha no primeiro caso de teste falso devido a problemas de precisão. Agradecemos a Luis Mendo por apontar que uma matriz não vazia é verdadeira se todas as suas entradas diferirem de 0, economizando 1 byte.

Mathematica, 29 28 bytes

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

Definição 2.

Julia 1.0 , 28 bytes

using LinearAlgebra
isposdef

Experimente online!

---

Julia 0,6 , 8 bytes

isposdef

Experimente online!

MATL , 6 bytes

É possível fazer isso usando ainda menos bytes, @Mr. O Xcoder conseguiu encontrar uma resposta MATL de 5 bytes !

YvX<0>

Explicação

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

Experimente online!

Bordo , 33 bytes

(ou seja, meus 2 centavos)

with(LinearAlgebra):
IsDefinite(A)

JavaScript (ES6),  99 95  88 bytes

O mesmo método da resposta de nwellnhof . Devoluções$0$ ou $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

Experimente online!