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}
