# Is the Matrix Positive-Definite?

## Introduction

Today we're gonna take care of the bane of first-year linear algebra students: matrix definiteness! Apparently this doesn't yet have a challenge so here we go:

## Input

• A $$\n\times n\$$ symmetric Matrix $$\A\$$ in any convenient format (you may also of course only take the upper or the lower part of the matrix)
• Optionally: the size of the matrix $$\n\$$

## What to do?

The challenge is simple: Given a real-valued matrix $$\n\times n\$$ Matrix decide whether it is positive definite by outputting a truthy value if so and a falsey value if not.

You may assume your built-ins to actually work precisely and thus don't have to account for numerical issues which could lead to the wrong behaviour if the strategy / code "provably" should yield the correct result.

## Who wins?

This is , so the shortest code in bytes (per-language) wins!

## What is a positive-definite Matrix anyways?

There are apparently 6 equivalent formulations of when a symmetric matrix is positive-definite. I shall reproduce the three easier ones and reference you to Wikipedia for the more complex ones.

• If $$\\forall v\in\mathbb R^n\setminus \{0\}: v^T Av>0\$$ then $$\A\$$ is positive-definite.
This can be re-formulated as:
If for every non-zero vector $$\v\$$ the (standard) dot product of $$\v\$$ and $$\Av\$$ is positive then $$\A\$$ is positive-definite.
• Let $$\\lambda_i\quad i\in\{1,\ldots,n\}\$$ be the eigenvalues of $$\A\$$, if now $$\\forall i\in\{1,\ldots,n\}:\lambda_i>0\$$ (that is all eigenvalues are positive) then $$\A\$$ is positive-definite.
If you don't know what eigenvalues are I suggest you use your favourite search engine to find out, because the explanation (and the needed computation strategies) is too long to be contained in this post.
• If the Cholesky-Decomposition of $$\A\$$ exists, i.e. there exists a lower-triangular matrix $$\L\$$ such that $$\LL^T=A\$$ then $$\A\$$ is positive-definite. Note that this is equivalent to early-returning "false" if at any point the computation of the root during the algorithm fails due to a negative argument.

## Examples

### For truthy output

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

### For falsey output

(at least one eigenvalue is 0 / positive semi-definite) $$\begin{pmatrix}3&-2&2\\-2&4&0\\2&0&2\end{pmatrix}$$

(eigenvalues have different signs / indefinite) $$\begin{pmatrix}1&0&0\\0&-1&0\\0&0&1\end{pmatrix}$$

(all eigenvalues smaller than 0 / negative definite) $$\begin{pmatrix}-1&0&0\\0&-1&0\\0&0&-1\end{pmatrix}$$

(all eigenvalues smaller than 0 / negative definite) $$\begin{pmatrix}-2&3&0\\3&-5&0\\0&0&-1\end{pmatrix}$$

(all eigenvalues smaller than 0 / negative definite) $$\begin{pmatrix}-7.15&-2.45\\-2.45&-9.37\end{pmatrix}$$

(three positive, one negative eigenvalue / indefinite) $$\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}$$

• Commented Sep 23, 2018 at 11:48
• You need to provide a better definition of what we're supposed to be looking for rather than assuming we can all read mathematical notation (or all know what an "eigenvalue" is). A worked example would be useful too. Commented Sep 23, 2018 at 15:53
• @Shaggy I think the challenge is better without all the background to clog it up. There are many existing explanations of what an eigenvalue is elsewhere, and this post is already really large. Commented Sep 23, 2018 at 16:37
• The challenge would have been nicer hadn't you restrict the input to symmetric matrices. Commented Sep 24, 2018 at 15:55
• I meant just checking for the sign of eigenvalues is also boring. Different tastes I know ;) Commented Sep 24, 2018 at 16:11

# C, 108 bytes

-1 byte thanks to Logern
-3 bytes thanks to 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));}

Try it online!

Performs Gaussian elimination and checks whether all diagonal elements are positive (Sylvester's criterion). Argument n is the size of the matrix minus one.

• Perhaps save a character with float instead of double?
– Jens
Commented Sep 23, 2018 at 15:10
• 106 bytes - Try it online!
– user36046
Commented Sep 23, 2018 at 15:35
• You can shave another character if you drop i=0 in the for loop, make the recursive call f(M,n-1,0) and the initial call with 0 as the third arg.
– Jens
Commented Sep 23, 2018 at 19:36
• @Jens 1. Using floats instead of doubles can quickly lead to noticable rounding errors, so I don't think the one byte saved is worth it. 2. Initializing a variable via an additional argument looks like cheating to me. Commented Sep 24, 2018 at 17:42
• @Logern I refuse to use the "omit the return statement" trick in my C answers. But thanks for the other byte saved. Commented Sep 24, 2018 at 17:45

# MATLAB/Octave, 1917 12 bytes

@(A)eig(A)>0

Try it online!

The function eig provides the eigenvalues in ascending order, so if the first eigenvalue is greater than zero, the other ones are too.

• You can drop the f= at the beginning - anonymous functions are generally accepted as answers. Commented Sep 23, 2018 at 15:05
• Thanks for the tip! Commented Sep 23, 2018 at 15:11
• Even if its a vector? Interesting Commented Sep 23, 2018 at 15:17
• +1. I've added a link for trying it online. Hope you don't mind. Note that it is also proving that the output values despite being arrays do count as the correct "truthy" or "falsey" values as per the link @Delfad0r posted. Commented Sep 23, 2018 at 17:03
• Having said that, it fails for the first "falsey" test case on TIO. I'm guessing due to a precision issue - one of the Eigen values comes out as 8.9219e-17 rather than 0. Commented Sep 23, 2018 at 17:05

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

Try it online!

Alternative using cholesky :

# R, 34 33 bytes

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

Try it online!

-1 byte thanks to @Giuseppe

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

Try it online!

Basically a port of nwellnhof's answer. Performs gaussian elimination and checks whether the elements on the main diagonal are positive.

Fails the first falsey output because of rounding errors, but it would theoretically work with infinite precision. Thanks to Curtis Bechtel's suggestion, now the outputs are all correct.

• you can add inputs :: [[[Rational]]] to get correct answers Commented Sep 23, 2018 at 20:38

# Wolfram Language (Mathematica), 20 bytes

0<Min@Eigenvalues@#&

Try it online!

• Should 4th test case be False?
– tsh
Commented Sep 23, 2018 at 14:48
• @tsh Fixed, I am dumb! Commented Sep 23, 2018 at 14:57
• Funny how Mathematica has a builtin for this, but its name is longer than your solution. Commented Sep 23, 2018 at 15:04
• @FedericoPoloni: Wouldn't a solution using NullSpace or MatrixRank be even shorter? If Null space is zero then the matrix is positive definite. Commented Sep 24, 2018 at 15:41
• @PhilH No, I'm afraid that doesn't work by itself. For instance, the second falsey example (diagonal matrix with (1,-1,1)) has rank 3, but is not positive definite. Commented Sep 24, 2018 at 16:39

# MATL, 4 bytes

Yv0>

Try it online!

I've noticed that for the [3 -2 2; -2 4 0; 2 0 2] test case, MATL calculates the 0 eigenvalue with a very small inaccuracy, computing something as low as about $$\10^{-18}\$$. This therefore fails the first falsy test case due to precision issues. Thanks to Luis Mendo for pointing out that a non-empty array is truthy iff all its entries differ from 0, saving 1 byte.

• @LuisMendo Thanks, I learned something new about MATL today! Commented Sep 26, 2018 at 21:53
• My pleasure :-) Here's a better explanation by Suever. I forgot to say that for complex-valued arrays only the real part is compared against zero. So [1 2 3j] is falsey Commented Sep 26, 2018 at 22:04

# Mathematica, 29 28 bytes

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

Definition 2.

# Julia 1.0, 28 bytes

using LinearAlgebra
isposdef

Try it online!

isposdef

Try it online!

# MATL, 6 bytes

It is possible to do it using even less bytes, @Mr. Xcoder managed to find a 5 byte MATL answer!

YvX<0>

Explanation

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

Try it online!

• Fails on the first falsy test case. See my deleted answer. Commented Sep 25, 2018 at 6:59
• @Mr.Xcoder Oh, you even submitted an answer before me. I think you should undelete your answer as it just depends on rounding issues. (I think you can expect answers to use limited precision arithmetic - I think only the CAS languages here use exact computations.) Commented Sep 25, 2018 at 18:02
• Following your advice, I've undeleted it. Commented Sep 25, 2018 at 21:18

## Maple, 33 bytes

(i.e. my 2 cents)

with(LinearAlgebra):
IsDefinite(A)
• Hello and welcome to PPCG; I am unfamiliar with Maple, though is the newline necessary? Commented Sep 24, 2018 at 16:06
• @JonathanFrech Hello and thanks. No it's not. I didn't count it btw. Commented Sep 24, 2018 at 16:09
• To me your current byte count seems to reflect the newline character. Commented Sep 24, 2018 at 16:16
• @JonathanFrech Duh, my bad Commented Sep 24, 2018 at 16:18
• Well ... now your code and your byte count disagree. Commented Sep 24, 2018 at 17:07

# JavaScript (ES6),  99 95  88 bytes

Same method as nwellnhof's answer. Returns $$\0\$$ or $$\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

Try it online!