Positive Definiteness

From bio-physics-wiki

Jump to: navigation, search

In this article we deal with Matrices $\mathbf{A}$ that are symmetric and have positive eigenvalues $\lambda_i>0$. This matrices are called positive definite and satisfy the equation \begin{equation} \mathbf{x}^T\mathbf{A}\mathbf{x} > 0 \end{equation} which is the case if $\lambda_i>0 \text{ for all } i$, beacause if we mulitply the eigenvalue equation with $\mathbf{x}^T$ we get \begin{equation} \mathbf{A}\mathbf{x} = \lambda_i \mathbf{x}\\ \mathbf{x}^T\mathbf{A}\mathbf{x} = \lambda_i \mathbf{x}^T\mathbf{x} = \lambda_i \left\Vert \mathbf{x} \right\Vert^2 > 0 \Leftrightarrow \lambda_i>0 \hspace{1cm} \text{ for all } i \end{equation}

A Matrix $\mathbf{A}$ is positive definite if

  • $\mathbf{A}$ is symmetric
  • all eigenvalues of $\mathbf{A}$ are positive
  • all minor determinants are positive



In single variable calculus the minimum of the single variable function $f(x)$ at $f'(x)=0$ satisfys \begin{equation} \frac{d^2 f}{dx^2}<0 \end{equation} What if we have more than one variable? Let's consider the equation \begin{equation} ax^2+2bxy+y^2 \end{equation} Is the point $(x,y)=(0,0)$ a minimum? To answer this question we can use the concept of positive definiteness, since the equation above can be brought in the form \begin{equation} \begin{pmatrix} x\\ y \end{pmatrix}^T \begin{pmatrix} a &b\\ b &c \end{pmatrix} \begin{pmatrix} x\\ y \end{pmatrix} \end{equation}

The elliptic case

We check if the function \begin{equation} e(x,y)=\begin{pmatrix} x\\ y \end{pmatrix} \begin{pmatrix} 2 &6\\ 6 &20 \end{pmatrix} \begin{pmatrix} x\\ y \end{pmatrix} \end{equation} or equivalently \begin{equation} e(x,y)=2x^2+12xy+20y^2 \end{equation} is positive for all $x$ and $y$

If we move along the $x$ direction leaving $y=0$, $f(x,0)=2x^2$ goes up and stays positive vor all values of $x$. If we keep $x=0$ and move in the $y$ direction we geht $f(0,y)=20y^2$, again $f$ increases for all $y$. What about the term $12xy$? It could become negative for certain values of $x$ and $y$.

We can solve this problem by completing the square \begin{equation} e(x,y)=2x^2+12xy+20y^2=2(x+3y)^2+2y^2 > 0 \end{equation} Since there only occur square terms after the right most equal sign the function $f(x,y)$ must be positive for all $x$ and $y$. Such a function is called elliptic, since the intersection of $h(x,y)$ with a horizontal plane describes an ellipse given by the equation \begin{equation} e(x,y)=2x^2+12xy+20y^2 =const. \end{equation}

The intersection of the graph $e(x,y)$ and the plane $150$ forms an ellips $e(x,y)=150$

There exists a beatiful connection between completing the square and gaußian elimination. The coefficients before the squares are the pivots of gaußian elimination. Let's check this \begin{align} \begin{pmatrix} 2 &6\\ 6 &20 \end{pmatrix} \rightarrow \begin{pmatrix} 2 &6\\ 0 &2 \end{pmatrix}\\ \begin{pmatrix} 2 &6\\ 6 &20 \end{pmatrix}=\mathbf{LU}=\begin{pmatrix} 1 &0\\ 3 &1 \end{pmatrix} \begin{pmatrix} 2 &6\\ 0 &2 \end{pmatrix} \end{align} The first pivot in the upper left corner $a_{11}=2$ after the first step of elimination by multiplying the first row by $3$ and subtracting from the second, we are left with the second pivot $a_{22}=2$. This are exactly the values $2,3,2$ that appear in completing the square. This principle generalises to $n \times n$ matrices. If the pivots in $U$ are all positive the matrix $\mathbf{A}$ is positive definit.

Besides calculating the eigenvalues this is another method to prove that an equation (or the associated matix) is positive definite and also gives a geometric interpretation of the function.

The parabolic case

In the marginal case, where completion of the square gives \begin{equation} p(x,y)=2x^2+12xy+18y^2=2(x+3y)^2 \geq 0 \end{equation} without additional pure quadradic terms. Such equations are called parabolic.

Notice, there is a special direction $x+3y=const.$ along which $p(x,y)$ is degenerate and does not depend on any variable. $p(x,y)$ is constant along those lines. After coordinate transformation $w=x+3y$, $p(x,y)$ becomes a function of $w$ only, namely $p(w)=w^2$, thus $p(w)$ is a simple parabola (this is why the equation is called parabolic).

Graphic shows $2(x+3y)^2$

Parabolic functions satisfy \begin{equation} det(\mathbf{A})=0 \end{equation} and have one eigenvalue $\lambda_1=0$ since the columns of $\mathbf{A}$ are already dependent. \begin{equation} \mathbf{A}=\begin{pmatrix} 2 &6\\ 6 &18 \end{pmatrix} \end{equation} The eigenvalues can be readily guessed by vieta's formulas $\lambda_1 \cdot \lambda_2=trace(\mathbf{A})=0$ and $\lambda_1 + \lambda_2=det(\mathbf{A})=20$, thus the eigenvalues are $\lambda_1=0,\lambda_2=20$. For $\lambda_1=0$ the equation \begin{equation} \mathbf{x}^T\mathbf{A}\mathbf{x} = \lambda_1 \mathbf{x}^T \mathbf{x} = \lambda_1 \left\Vert \mathbf{x} \right\Vert = 0 \end{equation} The eigenvalue is not positive, thus $\mathbf{A}$ is called semidefinite.

The hyperbolic case

The third case we want to study is when the mixed term $2bxy$ overcomes the quadradic terms. To this end, consider the equation \begin{equation} h(x,y)=2x^2+12xy+7y^2 \end{equation} with the corresponding Matrix \begin{equation} \mathbf{A}=\begin{pmatrix} 2 &6\\ 6 &7 \end{pmatrix} \end{equation} is this Matrix positiv definite? The minor determinant of a two by two matrix is simply $a$ and in this case, positive. But the determinant of $\mathbf{A}$ is negative. \begin{equation} det(\mathbf{A})=2 \cdot 7- 6^2=-22<0 \Rightarrow \text{not pos. definite} \end{equation} Similarly completing the square gives \begin{equation} h(x,y)=2x^2+12xy+7y^2=2(x+3y)^2-11y^2 \end{equation} The second pivot is negative, so the matrix is not positive definite. The function $h(x,y)$ goes up in one direction and down in another. So the function has no minimum at $(x,y)=(0,0)$ but a saddle point instead.

Graphic shows the function $2(x+3y)^2-11y^2$

The intersection of the sadle with a horizontal plane describes a hyperbola, hence we call the function hyperbolic. The function describing the hyperbola is \begin{equation} h(x,y)=2x^2+12xy+7y^2=2(x+3y)^2-11y^2=const. \end{equation} which can be written as \begin{equation} 2w^2-11y^2=const. \end{equation} after variable transformation $w=x+3y$. The prototype of a hyperbola is $x^2-y^2=1$


Video Lectures:

  • Mulitvariable Caluclus - Lecture 9 Max- Minproblems [1]
  • Mulitvariable Caluclus - Lecture 10 Second derivative test; boundaries and infinity [2]
  • Linear Algebra - Lecture 27 Positive Definite Matrices and Minima [3]