19
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 code-golf, 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}
SEJPM
Posted 2018-09-23T11:47:44.397
Reputation: 3 203
This challenge was sandboxed. – SEJPM – 2018-09-23T11:48:06.563
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. – Shaggy – 2018-09-23T15:53:04.303
9@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. – Post Rock Garf Hunter – 2018-09-23T16:37:11.803
@Shaggy I won't add a self-contained description / introduction of eigenvalues because this is neither the right place for that nor am I probably qualified enough to do that in a sufficient manner. I will also not add a "worked example" because there is no single "superior" strategy to this problem, because right now answers are generally using three different approaches to this challenge (either finding the eigenvalues and then checking they're positive or checking whether the cholesky decomposition exists or Sylvester's criterion). – SEJPM – 2018-09-23T17:40:26.320
1The challenge would have been nicer hadn't you restrict the input to symmetric matrices. – polfosol ఠ_ఠ – 2018-09-24T15:55:00.007
@SEJPM yes I noticed it. That was the point of my comment – polfosol ఠ_ఠ – 2018-09-24T16:07:03.693
@polfosolఠ_ఠ oh, I misread your comment to be a complaint that symmetric matrices are not guaranteed. Also I found it to be a boring tag-on to also force people to check for symmetric-ness. – SEJPM – 2018-09-24T16:09:50.130
1I meant just checking for the sign of eigenvalues is also boring. Different tastes I know ;) – polfosol ఠ_ఠ – 2018-09-24T16:11:10.073