Section 6

This was installed 10.22.16, do not edit here! Section 6. Matrix proof of the Method of Lagrange Multipliers In Section 2 it was shown that the Method of Lagrange Multipliers (Theorem 2) follows directly from Theorem 1, and really is just a restatement of Theorem 1 which we quote: Theorem 1: A point r is a "stationary point for f(r) subject to constraints ai(r) = 0" (1.24) 1. ai(r) = 0 for i = 1,2...C (point r must satisfy all the constraints ) 2. There exist C constants λi such that f(r) + Σi=1C λi ai(r) = 0 . Our proof of Theorem 1 was entirely geometric in nature. We talked about surfaces, normals to surfaces, tangent spaces, perp spaces, the intersection constraint surface, and so on. In this section, we shall rederive Theorem 1 using a certain "R matrix", though some geometry still appears. The reader should regard this simply as an alternative derivation of Theorem 1. As in Section 1, a certain amount of background material is necessary to provide a framework for the proof. We define S = C+1 so the number of constraint functions is C = S-1, and we rename the constraint functions to be a,b,c....q instead of a1, a2, a3....aC. The purpose of this renaming is to avoid having double subscripts on a constraint function, one identifying it and one indicating a partial derivative. 6.1. The R matrix and its Rank We shall operate in N dimensional Euclidean space EN with coordinates r = (x1, x2 ... xN). We seek stationary points of a real function f(r) subject to S-1 constraints a(r) = 0, b(r) = 0, ... q(r) = 0 where we use q generically to represent the last constraint function. For example, if there are two constraints, then S = 3 and the two constraint equations are a(r) = 0 and b(r) = 0. So here is the problem: find the stationary points of f(r) subject to constraints a(r)=0, b(r)=0, c(r)=0, .... q(r)=0 . (6.1.1) 1 2 3 S-1 Construct the following matrix of partial derivatives, where fi(r) ≡ ∂if(r) = ∂f(r)/∂xi. That is, the subscript on f indicates which of the arguments x1,x2, x3....xN the partial is with respect to. So here is that matrix, which we shall call R : (6.1.2) For example, f2 ≡ ∂f(x1,x2, x3....xN)/∂x2. On the far right we abbreviate each row of functions in bold, indicating a row vector like f . The matrix has S rows and N columns. We shall only be interested in N ≥ S which is the same as saying N ≥ C+1 or N > C. Recall from the discussion below (2.8) that if N ≤ C, the problem is overconstrained and one cannot seek stationary points where df = 0. If N = S, the R matrix is square, otherwise for N > S it has more columns than rows, so it has a horizontal band shape. The maximum possible rank of the above matrix is S since this is the smaller of the number of rows and columns (see below). S would then be the "full rank" of R. Since all the functions are functions of r, we really have R(r). As the point r is varied, the elements of the matrix R(r) generally change. If S = N, the matrix is square and we can talk about the determinant det(R). In this case there is only one SxS "submatrix" and it is the entire matrix R. If S < N, the matrix is wider than it is tall. In this case, we can talk about square submatrices within R which are of shape SxS. For example, for N = 6 and S = 4 we have three constraints and the R matrix is this, (6.1.3) Here we have outlined two 4x4 submatrices in red and blue. The columns of a submatrix need not be contiguous, so the three green boxes indicate another 4x4 submatrix. In this example, the number of submatrices is given by the binomial factor (6,4) -- pick a committee of 4 columns from 6 candidates. So we have shown only 3 out of (6,4) = 6!/(4!2!) = 15 possible 4x4 submatrices. We can indicate a submatrix using this notation: red = (f1,f2,f3,f4) blue = (f2,f3,f4,f5) green = (f1,f2,f4,f6) . (6.1.4) That is to say, we abbreviate the submatrix by stating only the values in the first row of the submatrix. Since our main interest will be whether or not the determinants of these 4x4 submatrices vanish, the ordering of the columns within a submatrix is not important. For the general R matrix shown in (6.1.2) with N columns and S rows, there are (N,S) possible submatrices of size SxS. A particular submatrix is then indicated by a sequence of S subscripted f values. We now quote a few facts from linear algebra concerning the rank of a matrix: Definitions: A minor of matrix A is the determinant of any square submatrix of A obtained by crossing out some rows and columns The rank r of an m x n matrix A is the dimension of the largest non-vanishing minor within A. [Shilov 1.92 ] Thus, r ≤ min(m,n). (6.1.5) Definitions: [Shilov 2.21] Consider an m x n matrix A. Let r1, r2, ...rN be an arbitrary selection of N rows (row vectors) from the matrix A. This set of N rows is linearly dependent if one can find a set of constants ki at least one of which is non-zero such that k1 r1 + k2 r2 + .... + kN rN = 0 . (6.1.6) There could be several such equations, or there could be only one. This generally means that at least one row can be expressed as a linear combination of the other rows. A legal such equation would be r2 = 0 in which case k2 = 1. One could then say that r2 is a linear combination of the other rows with coefficients all zero. In any event, if one or more rows are all zeros, a set of N rows are linearly dependent. If no such equation (6.1.6) exists, then the set of N rows is linearly independent. For example, the set of vectors r1 = (1,0) and r2 = (0,1) is linearly independent. The above discussion also applies to columns. Take "row" → "column" and ri → ci . Facts: The rank r as defined in (6.1.5) has these properties for any m x n matrix A: (6.1.7) (a) the rank r equals the number of linearly independent columns of A [Shilov 3.12 ] (b) the rank r equals the number of linearly independent rows of A [Shilov 3.13 ] In Appendix A below we provide our own proof of the claims of (6.1.7). With the above as background, the following theorem is fundamental to our matrix proof of Theorem 1 : Theorem 3. Point r is a "stationary point of f(r) subject to the constraints a=0,b=0...q=0" rank[R(r)] < S. (6.1.8) But rank[R(r)] < S f(r) + λ1a(r) + λ2b(r) + ... + λS-1q(r) = 0 for some λi because the rows of R are the gradients of f,a,b...q and having rank(R) < S means these rows are linearly dependent by (6.1.7). Thus proving Theorem 3 proves Theorem 1. According to the rank definition (6.1.5), rank(R) < S all SxS submatrices must have zero determinant (6.1.9) If, for example, the red submatrix in Fig 1.3 had a non-zero determinant, then rank(R) = 4 = S. The point of Theorem 3 is that the solution point r of the constrained stationary point problem must be a point where the R(r) matrix drops below full rank. We shall prove Theorem 3 in the direction in Section 6.2 by showing that, if r is a stationary point, then all those SxS submatrices discussed above have zero determinant and thus rank(R) < S. If one is searching for candidate solutions r to the stationary point problem, one can restrict one's search to points r for which rank[R(r)] < S. The proof of Theorem 3 in the direction is fairly simple. If rank(R) < S, then the rows of R are linearly dependent by (6.1.7) and then f(r) + λ1a(r) + λ2b(r) + ... + λS-1q(r) = 0. This implies that df(r) = f(r) dr = – λ1[a(r) dr] – λ2 [b(r) dr] – ...... – λS-1 [q(r) dr] (6.1.10) for any dr. Restricting to dr which don't violate any of the constraints, we know that each term on the right vanishes. For example, a(r) dr = 0 because a(r) is normal to the surface a(r) = 0, see (1.2). Since all the terms on the right above then vanish, we get df(r) = 0 and r is a stationary point of f by our definition (1.18) of a constrained stationary point. Comment on the R matrix. Imagine a general transformation from x-space x = (x1, x2, ....xN) to u-space with coordinates u = (u1, u2, ... uS). One might write such a transformation as u = F(x) where F:EN→ ES. Although this transformation in general is non-linear, in a tiny neighborhood of point x in x-space (and the corresponding point u in u-space), the transformation will be linear if certain conditions are met. That local linear relation is then described by du = Rdx where R is a matrix (N columns, S rows) whose matrix elements are Rij = ∂ui/∂xj. If we think of f = u1(x1, x2, ....xN) R11 = ∂u1/∂x1 = ∂f/∂x1 = f1 R12 = f2 etc. a = u2(x1, x2, ....xN) R21 = ∂u2/∂x1 = ∂a/∂x1 = a1 R22 = a2 etc b = u3(x1, x2, ....xN) ... q = uS(x1, x2, ....xN) (6.1.11) then the matrix shown in (6.1.2) is exactly the R matrix for this general transformation u = F(x). If S < N, then the R matrix is not square, the relation du = Rdx is a "projection" of a larger space into a smaller one, and the equation therefore cannot be inverted. This notation "R" is used extensively in our Tensor Analysis document, see in particular Chapter 2, though only invertible transformations F:EN→ EN are considered there. Sometimes R is referred to as "the differential" of a transformation. 6.2. Proof of Theorem 3 Theorem 3. Point r is a "stationary point of f(r) subject to the constraints a=0,b=0...q=0" rank[R(r)] < S. (6.1.8) (a) Proof for N = 6 and S = 4 The more general the proof is made, the less clear it becomes due to the notational baggage that must be added. Therefore we shall prove Theorem 3 for the specific case shown above in Fig (6.1.3) where N = 6 and S = 4 (3 constraints). The reader should have no trouble following each step for this sample case. When we reach the proof conclusion for the sample case, we start over again doing the general case and compare each step to the steps of this sample case. Although a lot of equations appear below (and a lot of column inches are consumed), everything is really quite simple. So, for our sample case we start off with this R matrix, again with bolded row vectors on the right, f1 f2 f3 f4 f5 f6 f a1 a2 a3 a4 a5 a6 a R = b1 b2 b3 b4 b5 b6 = b (6.2.1) c1 c2 c3 c4 c5 c6 c We want then to find an stationary point of f(x1, x2, x3, x4, x5, x6) subject to these constraints: a(x1, x2, x3, x4, x5, x6) = 0 b(x1, x2, x3, x4, x5, x6) = 0 c(x1, x2, x3, x4, x5, x6) = 0 . (6.2.2) In practice, a person solving this problem might try to eliminate variables. For example, somehow with enough labor one should be able to "use up" the three constraint equations to eliminate three of the six variables xi. There are of course (6,3) ways to select three variables for elimination. For starters, imagine that we have used up the 3 constraints to eliminate variables x1, x2 and x3. Then we write a(x1, x2, x3, x4, x5, x6) = 0 x1 = X1(x4, x5, x6) b(x1, x2, x3, x4, x5, x6) = 0 x2 = X2(x4, x5, x6) c(x1, x2, x3, x4, x5, x6) = 0 x3 = X3(x4, x5, x6) (6.2.3) where X1, X2 and X3 are three resulting functions. This is a "theoretical" elimination, one does not actually have to do the process, one need only understand that in principle it could be done and the functions Xi could in principle be found. See Appendix C for an elaboration of this point. Now rewrite the function f and the three constraint functions in this manner, substituting for example the function X1 for x1 everywhere it appears, f(X1(x4, x5, x6), X2(x4, x5, x6), X3(x4, x5, x6), x4, x5, x6) ≡ F(x4, x5, x6) a(X1(x4, x5, x6), X2(x4, x5, x6), X3(x4, x5, x6), x4, x5, x6) ≡ A(x4, x5, x6) b(X1(x4, x5, x6), X2(x4, x5, x6), X3(x4, x5, x6), x4, x5, x6) ≡ B(x4, x5, x6) c(X1(x4, x5, x6), X2(x4, x5, x6), X3(x4, x5, x6), x4, x5, x6) ≡ C(x4, x5, x6) . (6.2.4) In this way we have defined four new functions F,A,B,C each of the 3 variables shown (those that were not eliminated). Next, compute the first partial derivatives of F using the chain rule. For example = + + + . (6.2.5a) In our compact notation where Fi means ∂F/∂xi this can be restated as F4 = f1X14 + f2X24 + f3X34 + f4 . (6.2.5b) Doing this for each of the non-eliminated variables one gets, F4 = f1X14 + f2X24 + f3X34 + f4 F5 = f1X15 + f2X25 + f3X35 + f5 F6 = f1X16 + f2X26 + f3X36 + f6 . (6.2.6) Notice that the subscripts on the leftmost three fi correspond to those of the eliminated variables i = 1,2,3. Now, since we are seeking an extremal point of F(x4, x5, x6) with no constraints at all (the three initial constraints have all been absorbed in the process of eliminating three variables), we require that (x4, x5, x6) be a "critical point" for the function F, which means we require that F4 = F5 = F6 = 0. Then the above equations become, f1X14 + f2X24 + f3X34 + f4 = 0 f1X15 + f2X25 + f3X35 + f5 = 0 f1X16 + f2X26 + f3X36 + f6 = 0 . (6.2.7) Now apply the same process to the three constraint functions A,B,C. First compute the derivatives, and then set the derivatives to zero. One does this for A(x4, x5, x6), for example, because the constraint condition a = 0 says that that A(x4, x5, x6) = 0 = a constant, for all values of x4, x5, x6 , so all first derivatives must vanish. Doing this for function A then gives these three equations, a1X14 + a2X24 + a3X34 + a4 = 0 a1X15 + a2X25 + a3X35 + a5 = 0 a1X16 + a2X26 + a3X36 + a6 = 0 . (6.2.8) We have just taken the previous equations and replaced f→ a everywhere. Then do this for B and C. One ends up then with this set of 12 equations: f1X14 + f2X24 + f3X34 + f4 = 0 f1X15 + f2X25 + f3X35 + f5 = 0 f1X16 + f2X26 + f3X36 + f6 = 0 a1X14 + a2X24 + a3X34 + a4 = 0 a1X15 + a2X25 + a3X35 + a5 = 0 a1X16 + a2X26 + a3X36 + a6 = 0 b1X14 + b2X24 + b3X34 + b4 = 0 b1X15 + b2X25 + b3X35 + b5 = 0 b1X16 + b2X26 + b3X36 + b6 = 0 c1X14 + c2X24 + c3X34 + c4 = 0 c1X15 + c2X25 + c3X35 + c5 = 0 c1X16 + c2X26 + c3X36 + c6 = 0 . (6.2.9) Here there are S = 4 equation groups, and each group has N-S+1 = 6-4+1 = 3 equations (this last 3 is the number of non-eliminated variables). Next reorder these equations into three groups of four, for example taking the first equation in each group above to make the first new group below, f1X14 + f2X24 + f3X34 + f4 = 0 a1X14 + a2X24 + a3X34 + a4 = 0 b1X14 + b2X24 + b3X34 + b4 = 0 c1X14 + c2X24 + c3X34 + c4 = 0 f1X15 + f2X25 + f3X35 + f5 = 0 a1X15 + a2X25 + a3X35 + a5 = 0 b1X15 + b2X25 + b3X35 + b5 = 0 c1X15 + c2X25 + c3X35 + c5 = 0 f1X16 + f2X26 + f3X36 + f6 = 0 a1X16 + a2X26 + a3X36 + a6 = 0 b1X16 + b2X26 + b3X36 + b6 = 0 c1X16 + c2X26 + c3X36 + c6 = 0 . (6.2.10) Now there are N-S+1 = 3 equation groups, and each group has S = 4 equations. Next, write each of these three equation sets as a matrix equation, = = (f1,f2, f3, f4) = = (f1,f2, f3, f5) = = (f1,f2, f3, f6) . (6.2.11) On the right we show our abbreviated notation for a matrix, just showing the first row. Now we claim that the three matrices shown must have zero determinant! Suppose the first matrix equation had a non-zero determinant. It could then be inverted (see (B.4.8)) to give = (f1,f2, f3, f4)-1 = . (6.2.12) But this produces a blatant contradiction that 1 = 0 (not to mention the other rows), and therefore we must have det (f1,f2, f3, f4) = 0 det (f1,f2, f3, f5) = 0 det (f1,f2, f3, f6) = 0 or det (f1,f2, f3, fm) = 0 m ≠ 1,2,3 . (6.2.13) Therefore, we have shown that three of the SxS = 4x4 submatrices of Fig (1.3) vanish. But there are (6,4) = 15 such submatrices, and in order to show that rank(R) < S, we have to show that all 15 SxS determinants vanish. But that can be demonstrated by starting over several times and each time choosing to eliminate three different variables. Notice in the det = 0 equations above that the first three fi values correspond to the three eliminated variables x1, x2 and x3, Had we instead chosen to eliminate x1, x2 and x4, we would have obtained, det (f1,f2, f4, f3) = 0 det (f1,f2, f4, f5) = 0 det (f1,f2, f4, f6) = 0 or det (f1,f2, f4, fm) = 0 m ≠ 1,2,4 . (6.2.14) More generally, had we chosen to eliminate variables xi, xj and xk ( i ≠ j ≠ k), we would have obtained det (fi,fj, fk, fm) = 0 m ≠ i,j,k . (6.2.15) As i,j,k range over all possible values 1,2,3,4,5,6, we clearly hit all possible 4x4 subdeterminants, and thus we have shown that they all vanish, and therefore rank(R) < S, QED. Lest it be overlooked, one must keep in mind that r = (x1, x2, x3, x4, x5, x6) must be a stationary point of f(r) subject to the constraints. And then the conclusion is that, for such a solution point r, one has rank[R(r)] < S. To summarize, one theoretically eliminates S-1 of the N variables to create the functions F,A,B,C of (6.2.4). One then looks for the normal (unconstrained) critical points of F where all partials vanish. Since the constraints all have the form A = 0, B = 0, C = 0, their partials vanish as well. Writing all these equations in matrix form (for various sets of eliminated variables) leads to the conclusion that all the SxS minors of matrix R vanish so that rank(R) < S. (b) Proof for general S ≤ N To generalize now to general N and S, we restate some of the previous equations (adding a prime to the equation number) using a more generalized notation. The reader will note how even our simple notation becomes rather unpleasant. We start off with this R matrix which has N columns and S ≤ N rows. The S-1 constraint functions are a,b,....q. Remember that f2 means ∂f/∂x2. f1 f2 f3 ... fN f a1 a2 a3 ... aN a R = b1 b2 b3 ... bN = b (6.2.1)' .... ... q1 q2 q3 ... qN q Here are the S-1 constraint equations, a(x1, x2, ...xN) = 0 // S-1 constraint equations b(x1, x2, ...xN) = 0 ... q(x1, x2, ...xN) = 0 . (6.2.2)' Eliminate (theoretically) the first S-1 variables x1,x2....xS-1 using the S-1 constraint equations: a(x1, x2, ...xN) = 0 x1 = X1(xS, xS+1 ... xN) b(x1, x2, ...xN) = 0 x2 = X2(xS, xS+1 ... xN) ... ... q(x1, x2, ...xN) = 0 xS-1 = XS-1(xS, xS+1 ... xN) . (6.2.3)' Substitute to get the F,A,B...Q equations (a set of S equations), f(X1(xS, xS+1 ... xN), X2(xS, xS+1 ... xN), .. XS-1(xS, xS+1 ... xN) , xS, xS+1 ... xN) ≡ F(xS, xS+1 ... xN) a(X1(xS, xS+1 ... xN), X2(xS, xS+1 ... xN), .. XS-1(xS, xS+1 ... xN) , xS, xS+1 ... xN) ≡ A(xS, xS+1 ... xN) b(X1(xS, xS+1 ... xN), X2(xS, xS+1 ... xN), .. XS-1(xS, xS+1 ... xN) , xS, xS+1 ... xN) ≡ B(xS, xS+1 ... xN) ... q(X1(xS, xS+1 ... xN), X2(xS, xS+1 ... xN), .. XS-1(xS, xS+1 ... xN) , xS, xS+1 ... xN) ≡ Q(xS, xS+1 ... xN) . (6.2.4)' Now take first derivatives as shown in (6.2.5) to get this generalized version of (6.2.6), FS = f1X1S + f2X2S + f3X3S + ... + fS-1XS-1S + fS FS+1 = f1X1S+1 + f2X2S+1 + f3X3S+1 + ... + fS-1XS-1S+1 + fS+1 FS+2 = f1X1S+2 + f2X2S+2 + f3X3S+2 + ... + fS-1XS-1S+2 + fS+2 ... FN = f1X1N + f2X2N + f3X3N + ... + fS-1XS-1N + fN . // N-S+1 equations (6.2.6)' Requiring (xS, xS+1 ... xN) to be a "critical point", we set all the these first derivatives to 0 to get, f1X1S + f2X2S + f3X3S + ... + fS-1XS-1S + fS = 0 f1X1S+1 + f2X2S+1 + f3X3S+1 + ... + fS-1XS-1S+1 + fS+1 = 0 f1X1S+2 + f2X2S+2 + f3X3S+2 + ... + fS-1XS-1S+2 + fS+2 = 0 ... f1X1N + f2X2N + f3X3N + ... + fS-1XS-1N + fN = 0 . // N-S+1 equations (6.2.7)' A similar set of equations is obtained for a,b,c...q. Just replace f→a, then f→b and so on. We shall not write out all these equations as we did in (6.2.9). We have then S sets of equations, each set containing N-S+1 equations. As in the sample case, we then reorder the equations to get first this group, f1X1S + f2X2S + f3X3S + ... + fS-1XS-1S + fS = 0 a1X1S + a2X2S + a3X3S + ... + aS-1XS-1S + aS = 0 b1X1S + b2X2S + b3X3S + ... + bS-1XS-1S + bS = 0 .... q1X1S + q2X2S + q3X3S + ... + qS-1XS-1S + qS = 0 . // S equations (6.2.10)'S The next group has S→S+1 in all subscript positions. The last group has S→N, and here is that last group, f1X1N + f2X2N + f3X3N + ... + fS-1XS-1N + fN = 0 a1X1N + a2X2N + a3X3N + ... + aS-1XS-1N + aN = 0 b1X1N + b2X2N + b3X3N + ... + bS-1XS-1N + bN = 0 .... q1X1N + q2X2N + q3X3N + ... + qS-1XS-1N + qN = 0 . // S equations (6.2.10)'N So there are now N-S+1 groups of equations and each group has S equations each having S terms. The next task is to write each set of S equations as a matrix equation. Here we do that just using the abbreviated notation for the matrix. There are then N-S+1 matrix equations, = (f1,f2, f3, ... fS-1, fS) = (f1,f2, f3, ... fS-1, fS+1) = (f1,f2, f3, ... fS-1, fN) . (6.2.11)' We then argue as before that, to avoid the contradiction 0 = 1, the determinants of these SxS submatrices must be zero, det(f1,f2, f3, ... fS-1, fS) = 0 det(f1,f2, f3, ... fS-1, fS+1) = 0 ... det(f1,f2, f3, ... fS-1, fN) = 0 or det(f1,f2, f3, ... fS-1, fm) = 0 m ≠ 1,2,3...S-1 . (6.2.13)' Finally, if we start off by eliminating the S-1 variables xi, xj, xk.... xr where i ≠ j ≠k....≠r, we would find that det(fi,fj, fk, ... fr, fm) = 0 m ≠ i,j,k...r . (6.2.15)' Since this includes any possible SxS subdeterminant of the R matrix, we have then shown that all (N,S) SxS subdeterminants vanish, and therefore rank[R(r)] < S when r is a stationary point of f(r) subject to the constraints.