Apendice D_Taha_Operations_Research

Prévia do material em texto

A P P E N D I X D
Review of Vectors 
and Matrices
D.1 VECTORS
D.1.1 Definition of a Vector
Let be any n real numbers and P an ordered set of these real numbers—
that is,
Then P is an n-vector (or simply a vector). The ith component of P is given by For
example, is a two-dimensional vector.
D.1.2 Addition (Subtraction) of Vectors
Consider the n-vectors
For component i is computed as In general, given the vectors
P, Q, and S,
P + 1-P2 = 0 1zero or null vector21P ; Q2 ; S = P ; 1Q ; S2 1Associative law2
P + Q = Q + P 1Commutative law2
ri = pi ; qi.R = P ; Q,
 R = 1r1, r2, Á , rn2
 Q = 1q1, q2, Á , qn2
 P = 1p1, p2, Á , pn2
P = 11, 22 pi.
P = 1p1, p2, Á , pn2
p1, p2, Á , pn
CD-145
CD-146 Appendix D Review of Vectors and Matrices
D.1.3 Multiplication of Vectors by Scalars
Given a vector P and a scalar (constant) quantity the new vector
is the scalar product of P and In general, given the vectors P and S and the scalars 
and 
D.1.4 Linearly Independent Vectors
The vectors are linearly independent if, and only if
If
then the vectors are linearly dependent. For example, the vectors
are linearly dependent because for and 
D.2 MATRICES
D.2.1 Definition of a Matrix
A matrix is a rectangular array of elements. The element of the matrix A occupies
the ith row and jth column of the array. A matrix with m rows and n columns is said to
be of size (or order) For example, the following matrix is of size 
D.2.2 Types of Matrices
1. A square matrix has 
2. An identity matrix is a square matrix in which all the main diagonal elements
equal 1 and all the off-diagonal elements equal zero. For example, a 
identity matrix is given by
I3 = £1 0 00 1 0
0 0 1
≥
13 * 32
m = n.
A = §a11 a12 a13a21 a22 a23
a31 a32 a33
a41 a42 a43
¥ = 7aij 74 * 3
14 * 32.m * n.
aij
u1P1 + u2P2 = 0
u2 = -1,u1 = 2
P1 = 11, 22, P2 = 12, 42
a
n
j = 1
ujPj = 0, for some uj Z 0
a
n
j = 1
ujPj = 0 Q uj = 0, j = 1, 2, Á , n
P1, P2, Á , Pn
u1gP2 = 1ug2P 1Associative law2u1P + S2 = uP + uS 1Distributive law2
g,
uu.
Q = uP = 1up1, up2, Á , upn2
u,
D.2 Matrices CD-147
3. A row vector is a matrix with one row and n columns.
4. A column vector is a matrix with m rows and one column.
5. The matrix is the transpose of A if the element in A is equal to element 
in for all i and j. For example,
6. A matrix is a zero matrix if every element of B is zero.
7. Two matrices and are equal if, and only if, they have the same
size and for all i and j.
D.2.3 Matrix Arithmetic Operations
In matrices only addition (subtraction) and multiplication are defined. Division,
though not defined, is replaced by inversion (see Section D.2.6).
Addition (Subtraction) of Matrices. Two matrices and can be
added together if they are of the same size The sum is obtained
by adding the corresponding elements. Thus,
If the matrices A, B, and C have the same size, then
Product of Matrices. The product of two matrices, and is
defined if, and only if, the number of columns of A equals the number of rows of B. If A
is of size and B is of size then D must be of size where m and n
are arbitrary positive integer values. In this case, the elements of D are computed as
For example, given
we have
In general, even if BA is defined.AB Z BA
 = a23 31 9
34 46 18
b
 D = a1 3
2 4
b a5 7 9
6 8 0
b = a11 * 5 + 3 * 6211 * 7 + 3 * 8211 * 9 + 3 * 0212 * 5 + 4 * 6212 * 7 + 4 * 8212 * 9 + 4 * 02b
A = a1 3
2 4
b , B = a5 7 9
6 8 0
b
dij = a
r
k = 1
aikbkj, for all i and j
m * n,1r * n2,1m * r2
B = 7bij 7 ,A = 7aij 7D = AB
 1A ; B2T = AT ; BT
 A ; 1B ; C2 = 1A ; B2 ; C 1Associative law2 A + B = B + A 1Commutative law2
7dij 7m * n = 7aij + bij 7m * n
D = A + B1m * n2. B =
7bij 7A = 7aij 7
aij = bij
B = 7bij 7A = 7aij 7
B = 0
A = £1 42 5
3 6
≥ Q AT = a1 2 3
4 5 6
b
AT
ajiaijA
T
CD-148 Appendix D Review of Vectors and Matrices
Matrix multiplication follows these general properties:
Multiplication of Partitioned Matrices. Let A be an matrix and B an 
matrix. Assume that A and B are partitioned as follows:
The partitioning assumes that the number of columns of is equal to the number of
rows of for all i and j. Then
For example,
D.2.4 Determinant of a Square Matrix
Consider the n-square matrix
Next, define the product
such that each column and each row of A is represented exactly once among the sub-
scripts of and Next, define
H j1j2Ájn = e1, j1 j2 Á jn even permutation0, j1 j2 Á jn odd permutation
jn.j1, j2, Á ,
Pj1j2Ájn = a1j1a2j2 Á anjn
A = §a11 a12 Á a1na21 a22 Á a2n
o o o o
an1 an2 Á ann
¥
£11
2
 
2 3
0 5
5 6
≥ £41
8
≥ = § 112142 + 12 32a18b
a1
2
b142 + a0 5
5 0
b a1
8
b
¥ = §
 
4 + 2 + 24 
a4
8
b + a40
53
b
¥ = £3044
61
≥
A * B = aA11B11 + A12B21 + A13B31
A21B11 + A22B21 + A23B31
 
A11B12 + A12B22 + A13B32
A21B12 + A22B22 + A23B32
b
Bij
Aij
A = aA11
A21
 
A12
A22
 
A13
A23
b , B = £B11B21
B32
 
B12
B22
B32
≥
1r * n2-1m * r2
a1AB2 = 1aA2B = A1aB2, a is a scalar
1A ; B2C = AC ; BC
C1A ; B2 = CA ; CB
1AB2C = A1BC2
ImA = AIn = A, Im and In are identity matrices
D.2 Matrices CD-149
Let represents the summation over all n! permutations, then the determinant of
A, det A or is computed as
As an illustration, consider
Then
The properties of a determinant are:
1. The value of the determinant is zero if every element of a row or a column is zero.
2.
3. If B is obtained from A by interchanging any two rows or any two columns, then
4. If two rows (or two columns) of A are multiples of one another, then 
5. The value of remains the same if scalar times a column (row) vector is
added to another column (row) vector.
6. If every element of a column or a row of a determinant is multiplied by a scalar
the value of the determinant is multiplied by 
7. If A and B are two n-square matrices, then
Definition of the Minor of a Determinant. The minor of the element in the
determinant is obtained from the matrix A by striking out the ith row and jth
column of B. For example, for
Definition of the Adjoint Matrix. Let be defined as the cofactor of
the element of the square matrix B. Then, the adjoint matrix of A is the transpose of
and is defined as:
adj A = 7Aij 7T = §A11 A21 Á An1A12 A22 Á An2o o o o
A1n A2n Á Ann
¥
7Aij 7 ,
aij
Aij = 1-12i + jMij
M11 = ` a22 a23a32 a33 ` , M22 = `
a11 a13
a31 a33
` , Á
A = £a11 a12 a13a21 a22 a23
a31 a32 a33
≥
ƒ A ƒ
aijMij
ƒ AB ƒ = ƒ A ƒ ƒ B ƒ
a.a,
aƒ A ƒ
ƒ A ƒ = 0.
ƒ B ƒ = - ƒ A ƒ .
ƒ A ƒ = ƒ AT ƒ .
ƒ A ƒ = a111a22 a33 - a23 a322 - a121a21 a33 - a31 a232 + a131a21 a32 - a22 a312
A = £a11 a12 a13a21 a22 a23
a31 a32 a33
≥
a
r
H j1j2ÁjnPj1j2Ájn
ƒ A ƒ ,
r
CD-150 Appendix D Review of Vectors and Matrices
For example, if
then, or
D.2.5 Nonsingular Matrix
A matrix is of a rank r if the largest square array in the matrix having a non-zero de-
terminant is of size r. A square matrix with a non-zero determinant is called a full-rank
or nonsingular matrix. For example, consider
A is a singular matrix because
But A has a rank because
D.2.6 Inverse of a Nonsingular Matrix
If B and C are two n-square matrices such that then B is called the in-
verse of C and C the inverse of B.The common notation for the inverse is and 
Theorem. If and B is nonsingular, then which means that the inverse
is unique.
Proof. By assumption,
then
or
IC = B-1
B-1BC = B-1I
BC = I
C = B-1,BC = I
C-1.B-1
BC = CB = I,
a1 2
2 3
b = -1 Z 0
r = 2
ƒ A ƒ = 1 * 121 - 202 - 2 * 114 - 122 + 3 * 110 - 92 = 0
A = £1 2 32 3 4
3 5 7
≥
adj A = £ 6 1 -5-2 -5 4
-3 3 -1
≥
A11 = 1-12213 * 4 - 2 * 32 = 6, A12 = 1-12312 * 4 - 3 * 22 = -2, Á ,
A = £1 2 32 3 2
3 3 4
≥
D.2 Matrices CD-151
or
Two important results can be proved for nonsingular matrices.
1. If A and B are nonsingular n-squre matrices, then 
2. If A is nonsingular, then implies that 
Matrix inversion is used to solve n linearly independent equations. Consider
where represents the unknowns and and are constants. These n equationscan
be written in matrix form as
Because the equations are independent, A must be nonsingular. Thus
or
D.2.7 Methods of Computing the Inverse of a Matrix1
Adjoint Matrix Method. Given A, a nonsingular matrix of size n,
For example, for
adj A = £ 6 1 -5-2 -5 4
-3 3 -1
≥ , ƒ A ƒ = -7
A = £1 2 32 3 2
3 3 4
≥
A-1 =
1
ƒ A ƒ
 adj A =
1
ƒ A ƒ
 §A11 A21 Á An1A12 A22 Á An2
o o o o
A1n A2n Á Ann
¥
X = A-1b
A-1AX = A-1b
AX = b
biaijxi
§a11 a12 Á a1na21 a22 Á a2n
o o o o
an1 an2 Á ann
¥ §x1x2
o
xn
¥ = §b1b2
o
bn
¥
B = C.AB = AC
1AB2-1 = B-1A-1
C = B-1
1TORA’s inverse module is based on LU decomposition method. See Press and Associates (1986)
CD-152 Appendix D Review of Vectors and Matrices
Hence
Row Operations (Gauss-Jordan) Method. Consider the partitioned matrix 
where A is nonsingular. Premultiplying by we obtain
Thus, applying a specific sequence of row transformations, A is changed to I and I is
changed to To illustrate the procedure, consider the system of equations:
The solution of X and the inverse of the basis matrix can be obtained directly by
considering
The following iterations detail the transformation operation:
Iteration 0
Iteration 1
Iteration 2
Iteration 3
£1 0 00 1 0
0 0 1
3 -67 -17 572
7
5
7 -
4
7
3
7 -
3
7
1
7
3 3767
2
7
≥
£1 0 -50 1 4
0 0 7
3 -3 2 02 -1 0
3 -3 1
3 -12
2
≥
£1 2 30 -1 -4
0 -3 -5
3 1 0 0-2 1 0
-3 0 1
3 3-2
-4
≥
£1 2 32 3 2
3 3 4
3 1 0 00 1 0
0 0 1
3 34
5
≥
A-11A �I �b2 = 1I �A-1 �A-1b2
£1 2 32 3 2
3 3 4
≥ £x1x2
x3
≥ = £34
5
≥
A-1.
1A-1A �A-1I2 = 1I �A-12
A-1,
1A �I2,
A-1 =
1
-7
 £ 6 1 -5-2 -5 4
-3 3 -1
≥ = £ -67 -17 5727 57 -47
3
7 -
3
7
1
7
≥
D.2 Matrices CD-153
This gives and The inverse of A is given by the right-hand-side
matrix, which is the same as obtained by the method of adjoint matrix.
Product Form of the Inverse. Suppose that two nonsingular matrices, B and dif-
fer exactly in one column. Further, assume that is given. Then the inverse can
be computed using the formula
The matrix E is computed in the following manner. If the column vector in B is re-
placed with the column vector to produce then E is constructed as an m-iden-
tity matrix with its rth column replaced by
If then does not exist.
The validity of the formula is proved as follows. Define F as an m-identity
matrix whose rth column is replaced by —that is,
Because differs from B only in that its rth column is replaced with then
Thus,
The formula follows by setting 
The product form can be used to invert any nonsingular matrix, B, in the follow-
ing manner. Start with Next, construct as an identity matrix, except
that the first column is replaced with the first column in B. Then
In general, if we construct as an identity matrix with its first i columns replaced with
the first i columns of B, then
This means that for the original matrix B,
B-1 = EnEn - 1 Á E1
Bi
-1 = EiBi - 1-1 = EiEi - 1Bi - 2-1 = Á = EiEi - 1 Á E1
Bi
B1
-1 = E1B0-1 = E1I = E1
B1B0 = I = B0-1.
E = F-1.
Bnext
-1 = 1BF2-1 = F-1B-1
Bnext = BF
Pj,Bnext
F = 1e1, er - 1, B-1Pj, er + 1, Á , em2
B-1Pj
Bnext
-1
Bnext
-11B-1Pj2r = 0,
j =
1
1B-1Pj2r ¶
-1B-1Pj21
-1B-1Pj22
o
+1
o
-1B-1Pj2m
∂ ; rth place, 1B-1Pj2r Z 0
Bnext,Pr
Pj
Bnext
-1 = EB-1
Bnext
-1B-1
Bnext,
x3 =
2
7.x1 =
3
7, x2 =
6
7,
CD-154 Appendix D Review of Vectors and Matrices
The following example illustrates the application of the product form of the in-
verse. Consider
Iteration 0
Iteration 1
Iteration 2
 B-1 = B2-1 = E2B1-1 = £ 1 -14 00 1
2
0
0 1 1
≥ £ 12 0 00 1 0
-2 0 1
≥ = £ 12 -14 00 1
2
0
-2 1 1
≥
 E2 = §1 -
1
2
2
0
0 +12 0
0 - - 22 1
¥ = £1 -14 00 1
2
0
0 1 1
≥
 B1
-1P2 = £ 12 0 00 1 0
-2 0 1
≥ £12
0
≥ = £ 122
-2
≥ ; r = 2
 B2 = £2 1 00 2 0
4 0 1
≥ = B
B1
-1 = £ 12 0 00 1 0
-2 0 1
≥
E1 = £ +12 0 0-02 1 0
-42 0 1
≥
B0
-1P1 = P1 = £20
4
≥;r = 1
B1 = £2 0 00 1 0
4 0 1
≥
B0 = B0-1 = £1 0 00 1 0
0 0 1
≥
B = £2 1 00 2 0
4 0 1
≥
D.2 Matrices CD-155
Partitioned Matrix Method. Suppose that the two n-nonsingular matrices A and B be
partitioned as shown as follows:
If B is the inverse of A, then from we have
Also, from we get
Because is nonsingular, exists. Solving for and we get
where
To illustrate the use of these formulas, partition the matrix
such that
A11 = 112, A12 = 12, 32, A21 = a23b , A22 = a
3 2
3 4
b
A = £12
3
 
2 3
3 2
3 4
≥
D = A22 - A211A11-1 A122
 B22 = D-1
 B21 = -D-11A21 A11-12
 B12 = -1A11-1 A122D-1
 B11 = A11-1 + 1A11-1 A122D-11A21 A11-12
B22,B11, B12, B21,A11
-1A11
 B21A12 + B22A22 = Iq
 B21A11 + B22A21 = 0
BA = In,
 A11B12 + B12A22 = 0
 A11B11 + A12B21 = Ip
AB = In,
 B = §B11 B121p * p2 1p * q2
B21 B221q * p2 1q * q2
¥
 A = §A11 A121p * p2 1p * q2
A21 A221q * p2 1q * q2
¥ , A11 nonsingular
CD-156 Appendix D Review of Vectors and Matrices
In this case, and
Thus,
which directly give 
D.2.8 Matrix Manipulations Using Excel
Excel provides facilities for automatically performing the following matrix manipulations:
1. Transpose.
2. Multiplication.
3. Inverse of a nonsingular matrix.
4. Determinant value of a nonsingular matrix.
Figure D.1 provides illustrative examples (file excelMatManip.xls). In Example 1
(Transpose), A is a matrix whose elements are entered in the range A4:C5.
Transpose(A), or appears in the user-specified range E4:F6.The steps for obtaining
the output in the selected range are:
1. Enter the in cell E4.
2. Select (highlight) the output cells E4:F6.
3. Press F2.
4. Press 
In Example 2, the elements of the input matrices A and B are entered in the re-
spective ranges A10:C13 and A16:A18. The output matrix is in the (user-selected)
range E10:E13. Next enter the (A10:C13,A16:A18) in cell E10
and follow steps 2 through 4 exactly as in Example 1 (replacing E4:F6 with E10:E13).
Notice that MMULT(A16:A18,A10:C13) is undefined. In Example 3, the inverse of
the matrix in the range A22:C24 is assigned to the range E22:G24 by entering the
in cell E22, then following steps 2, 3, and 4 as in Ex-
ample 1. Finally, in Example 4, the determinant of the matrix in the range A28:C30 is ob-
tained by entering the in the user-selected cell E28.formula = MDETERM1A28 : C302
formula = MINVERSE1A22 : C242
formula = MMULT
CTRL + SHIFT + ENTER.
formula = TRANSPOSE1A4 : C52
AT,
2 * 3
B = A-1
 B12 = a
2
7
3
7
b , B22 = a
5
7 -
4
7
-37
1
7
b
 B11 = A -67 B , B12 = A -17 57 B
D-1 = -17a -5 43 -1b = a
5
7 -
4
7
-37
1
7
b
D = a3 2
3 4
b - a2
3
b11212, 32 = a -1 -4
-3 -5
b
A11
-1 = 1
D.3 Quadratic Forms CD-157
FIGURE D.1
Matrix manipulations using Excel (file excelMatManip.xls)
D.3 QUADRATIC FORMS
Given
and
the function
Q1X2 = XTAX = a
n
i = 1
a
n
j = 1
aijxixj
A = §a11 a12 Á a1na21 a22 Á a2n
o o o o
an1 an2 Á ann
¥
X = 1x1, x2, Á , xn2T
CD-158 Appendix D Review of Vectors and Matrices
is called a quadratic form. The matrix A can always be assumed symmetric because
each element of every pair of coefficients and can be replaced by 
without changing the value of Q(X).
As an illustration, the quadratic form
is the same as
Note that A is symmetric in the second case. We will assume henceforth that A is al-
ways symmetric.
The quadratic form is said to be
1. Positive-definite if for all 
2. Positive-semidefinite if for all X, and there exists such that
3. Negative-definite if is positive-definite.
4. Negative-semidefinite if is positive-semidefinite.
5. Indefinite in all other cases.
It can be proved that the necessary and sufficient conditions for the realization of
the preceding cases are
1. Q(X) is positive-definite (-semidefinite) if the values of the principal minor de-
terminants of A are positive (nonnegative).† In this case, A is said to be positive
definite (semidefinite).
2. Q(X) is negative-definite if the value of the kth principal minor determinant of A
has the sign of In this case, A is called negative-definite.
3. Q(X) is negative-semidefinite if the kth principal minor determinant of A either
is zero or has the sign of 1-12k, k = 1, 2, Á , n.
1-12k,k = 1, 2, Á , n.
-Q1X2
-Q1X2
Q1X2 = 0. X Z 0Q1X2 Ú 0
X Z 0.Q1X2 7 0
Q1X2 = 1x1, x2, x32£1 1 21 7 3
2 3 2
≥ £x1x2
x3
≥
Q1X2 = 1x1, x2, x32£1 0 12 7 6
3 0 2
≥ £x1x2
x3
≥
1a
ij
+ a
ji
2
2aij 1i Z j2aij
†The kth principal minor determinant of is defined by
4 a11 a12 Á a1ka21 a22 Á a2k
o o o o
ak1 ak2 Á akk
4 , k = 1, 2, Á , n
An * n
Problems CD-159
D.4 CONVEX AND CONCAVE FUNCTIONS
A function f(X) is said to be strictly convex if, for any two distinct points and 
where Conversely, a function f(X) is strictly concave if is strictly
convex.
A special case of the convex (concave) function is the quadratic form (see 
Section D.3)
where C is a constant vector and A is a symmetric matrix. It can be proved that f(X) is
strictly convex if A is positive-definite and f(X) is strictly concave if A is negative definite.
PROBLEMS
1. Show that the following vectors are linearly dependent.
(a)
(b)
2. Given
find
(a)
(b)
(c)
3. In Problem 2, show that 
4. Consider the partitioned matrices
Find AB using partitioned matrix manipulation.
5. In Problem 2, find and using the following:
(a) Adjoint matrix method
(b) Row operations method
(c) Product form of the inverse
(d) Partitioned matrix method
B-1A-1
A = §12
3
4
 
5 7
-6 9
7 2
9 1
¥ , B = £2 31 2
3 1
 
-4 5
6 7
0 9
≥
AB Z BA
1A + 7B2T
2A - 3B
A + 7B
A = £1 4 92 5 -8
3 7 2
≥ , B = £7 -1 29 4 8
3 6 10
≥
§ 2-3
4
5
¥ § 4-6
8
10
¥
£ 1-2
3
≥ £ -24
-2
≥ £ 1-2
-1
≥
f1X2 = CX + XT AX
-f1X20 6 l 6 1.
f1lX1 + 11 - l2X22 6 lf1X12 + 11 - l2f1X22
X2,X1
CD-160 Appendix D Review of Vectors and Matrices
6. Consider
Suppose that the third vector is replaced with the This means that the
resulting matrix is singular. Show how the product form of the inverse discovers the singu-
larity of the matrix.
7. Use the product form of the inverse to verify whether each of the following equations
has a unique solution, no solution, or an infinity of solutions.
(a)
(b)
(c)
8. Verify the formulas given in Section B.2.7 for obtaining the inverse of a partitioned matrix.
9. Find the inverse of
10. Show that the following quadratic form is negative definite.
11. Show that the following quadratic form is positive definite.
12. Show that the function is strictly convex over all real values of x.
13. Show that the quadratic function
is strictly convex.
14. In Problem 13, show that is strictly concave.
SELECTED REFERENCES
Hadley, G., Matrix Algebra, Addison-Wesley, Reading, MA, 1961.
Hohn, F., Elementary Matrix Algebra, 2nd ed., Macmillan, New York, 1964.
Press, W., B. Flannery, B. Teukolsky, and W. Vetterling, Numerical Recipes: The Art of Scientific
Computing, Cambridge University Press, Cambridge, England, 1986.
-f1x1, x2, x32
f1x1, x2, x32 = 5x1 2 + 5x2 2 + 4x3 2 + 4x1x2 + 2x2x3
f1x2 = ex
Q1x1, x2, x32 = 2x12 + 2x22 + 3x32 + 2x1x2 + 2x2x3
Q1x1, x22 = 6x1 + 3x2 - 4x1x2 - 2x12 - 3x22 - 274
A = a 1 G
H B
b , B nonsingular
x1 + 3x2 - 2x3 = 3
4x1 + x2 + 3x3 = 8
x1 + 7x2 + x3 = 5
 -x1 - 2x2 = -5
 x1 + 2x2 = 5
 x1 + 4x2 = 2
 x1 + 2x2 = 3
V3 = P1 + 2P2.P3
B = £2 1 20 2 1
4 0 5
≥ , B-1 = £ 54 -58 -3812 14 -14
-1 12
1
2
≥