# How to find the definiteness of a matrix given a relation $Ax=b$

Assume we have a matrix $A$ that satisfies this relation $Ax=b$ $$A\begin{bmatrix} 1\\0\\1 \end{bmatrix}=\begin{bmatrix} 1\\3\\-2\end{bmatrix}$$ Is $A$ postive definite, positive semidefinite, negative definite, negative semidefinite, or indefinite? How would we find out this information given any $\vec x$ and $\vec b$?

• There are many equivalent definitions, but a useful one here is that a matrix $A$ is positive definite iff $|\vec x|>0\implies\vec x^tA\vec x>0\ \forall\ \vec x$. If you know $A\vec x = \vec b$, then $\vec x^tA\vec x = \vec x\cdot\vec b$. Checking a finite number of vectors won't necessarily suffice,though. – Kajelad Aug 11 '17 at 20:52
• Is there an algorithm we can use to determine the definiteness? What about a way to directly prove that it is indefinite? – D.R. Aug 11 '17 at 21:07
• Can you find an example of an $A$ that fits your criteria? What are its eigenvalues? – Doug M Aug 11 '17 at 21:57
• I think MathLover's answer is the only conclusion we can draw from a single equation. If we have 3 linearly independent values for $\vec x$ and corresponding values for $\vec b$, we can solve the matrix equation $AX=B$ for $A$ and determine the eigenvalues directly. – Kajelad Aug 11 '17 at 23:12

## 2 Answers

In general, you want to determine the definiteness of a $n\times n$ matrix $A$ given vectors $\vec x$, $\vec b$ such that $A\vec x=\vec b$. Just to clarify, I'll define definiteness as follows:

$A$ is positive definite $\implies \vec x^tA\vec x>0\ \forall \vec x\neq \vec 0$

$A$ is negative definite $\implies \vec x^tA\vec x<0\ \forall \vec x\neq \vec 0$

$A$ is positive semidefinite $\implies \vec x^tA\vec x\ge 0\ \forall \vec x\neq \vec 0$

$A$ is negative semidefinite $\implies \vec x^tA\vec x\le0\ \forall \vec x\neq \vec 0$

$A$ is indefinite if none of the above are true.

Since $\vec x^TA\vec x=\vec x\cdot \vec b$, we can evaluate the above inequality once for each value for $\vec x$ and $\vec b$, but only one set of values is insufficient to completely determine the definiteness of $A$ (except in the one dimensional case). However, if $\vec x\cdot\vec b$ is a counterexample to any of the above inequalities, we can of course conclude that $A$ does not have the corresponding definiteness.

If we want to check the inequalities above for all $\vec x$, it's sufficient (and, in fact, necessary) to have a set of vectors that form a basis for the entire space, since we can write any $\vec x^tA\vec x$ in terms of this basis. The simplest way to do this is to completely determine $A$.

Suppose we know a linearly independent set $\{\vec x_1,\vec x_2,...,\vec x_n\}\subset\mathbb R^n$, as well as another set $\{\vec b_1,\vec b_2,...,\vec b_n\}\subset\mathbb R^n$, such that $A\vec x_i=\vec b_i\ \forall\ i$. We can then let $X$ and $B$ be matrices whose columns are $\vec x_i$ and $\vec b_i$ respectively, giving us the following matrix relation.

$$AX=B$$

Since $X$ has linearly independent columns, we know its inverse must exist. Thus we can compute $A$.

$$A=BX^{-1}$$

Definiteness is typically only discussed for Symmetric matrices, so if $A$ is not symmetric, it may be preferred to consider its symmetric part $A_{sym}=\frac 12(A+A^T)$, which defines the same quadratic form.

Once we know $A$ we can determine its definiteness several ways. One is to find all of its eigenvalues. If $A$ is symmetric we can find the determinants of the principal minors and use Sylvester's Criterion.

This matrix is certainly not positive definite or positive semidefinite as $\begin{bmatrix}1&0& 1\end{bmatrix} A \begin{bmatrix}1\\0\\ 1\end{bmatrix}=-1 < 0$.