Definiteness of matrices and principal minors

The notion of positive and negative (semi)definiteness of matrices can be used to help characterize certain naturally occuring matrices in economics. In this post, I will explain when we can say a matrix is positive/negative (semi)definite and more importantly how we can use this fact in economics.

The point of this post is not to present overly formal mathematics, there are plenty of books out there that will do that for you. For this reason I will forgo the proofs and will rather present the intuition behind the notions in question.

First, to motivate our inquiry into matrices and linear algebra consider a profit maximization problem

\pi(p, w) = max \; pf(x) - wx.

Here we only have one input. So it is quite straightforward what we must do to find the maximum. The first-order condition for a maximum is

\frac{\partial \pi}{\partial x} = p \frac{\partial f(x^*)}{\partial x} - w = 0.

Also recall that the second-order condition

\frac{\partial^2 \pi}{\partial x^2} = p \frac{\partial^2 f(x^*)}{\partial x^2} \le 0

must also be satisfied. The intuition behind this is simple: if the second derivative were positive at the optimum (x*), then that would mean that the first derivative of the profit function is increasing at x*. This would in turn mean that as we increase x even further from where the first derivative equals 0, we would get a positive first derivative. A positive first derivative would then imply that profits are increasing. But then surely our original point x* cannot be a maximum.

This is quite intuitive and simple. But what happens when the number of inputs (x’s) increases? I will use a two-input example to show you how linear algebra can be used to solve the problem for an arbitrary number of inputs. So now we have

\pi(p, \mathbf{w}) = max \; pf(\mathbf{x}) - \mathbf{wx},

where w and x are now vectors of factor/input prices and input quantities, respectively. The first-order condition is still

\frac{\partial \pi}{\partial x_i} = p \frac{\partial f(\mathbf{x^*})}{\partial x_i} - w_i = 0 \; for \; i = 1,2.

Or in matrix notation

p\mathbf{D}f(\mathbf{x^*}) - \mathbf{w} = 0,

where

\mathbf{D}f(\mathbf{x^*}) = \left(\begin{array}{cc} \frac{\partial f(\mathbf{x^*})}{\partial x_1} & \frac{\partial f(\mathbf{x^*})}{\partial x_2} \end{array}\right)

is just a vector of the first derivatives of f with respect to each of its arguments. This is also called the gradient of f. It’s easy to see how this can be extended to an arbitrary number of dimensions. This simply says that the value of the marginal product of each input (i.e. each partial of f times p) must equal its price (i.e. the corresponding w). Now consider the second-order condition

\frac{\partial^2 \pi}{\partial x_i^2} = p \frac{\partial^2 f(x^*)}{\partial x_i^2} \le 0\; for \; i = 1,2.

Or in matrix notation

p\mathbf{D}^2f(\mathbf{x^*}) \le 0,

where

\mathbf{D}^2f(\mathbf{x^*}) = \left(\begin{array}{cc}f_{11} & f_{12} \\ f_{21} & f_{22} \end{array}\right),

a matrix of the second derivatives of f. This matrix is also called the Hessian. Recall that the second-order conditions require that the second derivative of the production function with respect to each input (f_11 and f_22) be negative (since p is always positive). In other words, the diagonal entries (top left to bottom right) of the Hessian matrix must be negative. It turns out that if the Hessian is negative definite, then this property is guaranteed.

(Note: strictly speaking, the second derivatives must be non-positive. In order to check for non-positivity, one must check if the Hessian is negative semidefinite. But because it is a lot easier to check for negative definiteness and negative definiteness implies negative semidefiniteness, we’ll test for negative definiteness. In the end, I will show how semidefiniteness can be checked in case the definiteness test fails.)

A symmetric matrix A is said to be negative definite if

\mathbf{h^T A h} < 0

for all non-zero (column) vectors h. With a little (albeit somewhat tricky) algebra one can verify that this can only happen if both a_11 and a_22 (or in case of the Hessian f_11 and f_22) are negative (see Simon & Blume, pp.384-385). In general the diagonal terms when going from the top left element to the bottom right one will be all negative if the above condition is fulfilled. (Side note: to get the definition of a negative semidefinite matrix just replace the strict inequality with a weak one. Similarly, for positive (semi)definiteness just flip the inequality.)

Therefore, if a matrix is negative definite, all of its diagonal terms will be negative. This means that negative definiteness guarantees that the relevant second derivatives (f_11, f_22, f_33 all the way to f_nn) are negative. Note though that since the above expression has to hold for all non-zero vectors h, it is very hard to check directly. There is, however, a quite feasible test to check the definiteness of a matrix: the principal minor test.

I claim that if the leading principal minors of a matrix alternate in sign, then it is negative definite (and you must take my word for it because I’m not going to present the proof here). But what does this mean? The leading principal minors of a matrix are the determinants of its top-left submatrices. So for the Hessian above, the leading principal minors and the appropriate condition (alternating signs) are

|f_{11}| < 0 , \left| \begin{array}{cc}f_{11} & f_{12} \\ f_{21} & f_{22} \end{array}\right| > 0.

If you had a 4×4 matrix, you would also have to check the determinant of the top-left 3×3 submatrix, which would have to be negative, and the determinant of the 4×4 matrix itself, which would have to be positive. And like this you can generalize this method to any n-by-n matrix. Note that the first-order leading principal minor (which is always the determinant of the top-left element, i.e. |f_11| above) always has to be negative. Because the signs have to alternate, this implies that all leading principal minors of odd order have to be negative and those of even order have to be positive. The order of a minor is just the number of rows/columns it has.

We have seen above that negative definiteness implies that the diagonal terms in the matrix will be negative. To see this, recall that in order for the Hessian to be negative definite, its leading principal minors have to fulfill the conditions stated above. Those conditions imply that the diagonal terms are negative because

|f_{11}| = f_{11} < 0,

this means that f_11 has to be negative. The second-order leading principal minor is

f_{11} f_{22} - f_{12} f_{21} > 0.

We know from calculus that

f_{12} = f_{21} \implies f_{12} f_{21} = f_{12}^2 = f_{21}^2 >0.

As f_11 is negative, f_22 has to be negative as well. To see why, consider what would happen to the second-order leading principal minor if f_22 were positive. Then the first term, f_11 * f_22, would be negative. But then we would substract a positive number (f_12 * f_21) from a negative number. The second-order leading principal minor would then be a negative number. But it must be positive as it was shown above. So f_22 clearly cannot be positive. Therefore, we have verified that for the 2×2 Hessian the diagonal terms f_11 and f_22 have to be negative in order for the matrix to be negative definite.

But of course this can be generalized to any n-by-n symmetric matrix. So basically, the second-order condition in the n-dimensional case amounts to checking out whether the Hessian is negative (semi)definite. Please note, the above leading principal minor-test will establish that the Hessian is negative definite (that is equivalent to the second derivative of f being strictly less than zero in the one-input case). To check whether it is negative semidefinite, you’d have to work a little more. But negative definiteness obviously implies negative semidefiniteness. So if the above test checks out, you’re OK.

If it doesn’t, you’d have to check all principal minors of the Hessian. The matrix will be negative semidefinite if all principal minors of odd order are less than or equal to zero, and all principal minors of even order are greater than or equal to zero. What other principal minors are left besides the leading ones? Well, one can make a principal minor by removing the ith column and the ith row, and then taking the determinant. Thus by removing the first column and the first row from the Hessian above, we’d have a third principal minor |f_22|.

For a 3×3 matrix the leading principal minors would of course include the determinants of the top-left 1×1, 2×2 and 3×3 submatrices. But to get the remaining principal minors of order 2, you’d have to form a matrix without the second row/column and one without the first row/column. To get the remaining principal minors of order 1, you’d have form 1×1 matrices by removing the first and second rows/columns and the first and third rows/columns. Altogether, this is 7 principal minors you’d have to check.

Positive (semi)definiteness can be checked similarly. If the leading principal minors are all positive, then the matrix is positive definite. If all principal minors are non-negative, then it is positive semidefinite. Also not surprisingly, checking whether a matrix is positive (semi)definite has a similar role in minimization problems that negative (semi)definiteness has in maximization problems.

There are many applications of these notions in economics (perhaps I will write a post soon on some of them). You will tend to find it in micro. If you take any graduate level course in micro, it is certainly worth being familiar with this.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s