Solution of Linear Equations

For simplicity let us consider a system of three equations in three unknowns:

OiiXi + auX2 + . = bi 21 , + 0222 + 2 = bj OjiX, + 0322 + 6(33X3 = bj

We can write them compactly in matrix notation as Ax = b, where

If b = 0, the system of equations is said to be homogeneous. In this case we have Ax = 0. This says that the vector x is orthogonal to the row vectors of A. But since A is 3 X 3 and there can be at most three linearly independent vectors of order 3, a necessary and sufficient condition for the existence of a nonzero solution to the set of equations is rank A < 3. In the general case of n equations, the condition is rank A < . If rank A = r < n, there are {n - r) linearly independent solutions x that satisfy the equations Ax = 0.

Now consider the case of the nonhomogeneous equations: Ax = b. We can write these equations as follows:

What this says is that b is a linear combination of the columns of A. Hence a necessary and sufficient condition for the existence of a solution to this set is: Rank(A) = Rank (Ab).

Cramers Rule

There is one convenient rule for solving a system of non-homogeneous equations. This rule, known as Cramers rule is as follows. Consider the system of non-homogeneous equation Ax = b where x = (x,, Xj, . . . x„). Let us denote by A, the matrix A with the first column replaced by the vector b. Similarly, 2 denotes the matrix A with the second column replaced by the vector b. We define 3, 4 . . . A„ similarly. Then Cramers rule says:

X, = A, A, X2 = \A,\ A, = A

and so on. As an example, consider the system of equations:

4x, + 2 + X3 = 13 X, - X2 + X3 = 2 2x, - X2 + 3 = 9

Then

A = {A, = Aal =

= -10

= -20

= -30

Hence, :, = -10/-10 = 1, Jc = -20/-10 * 2, Xj = -30/-10 = 3.

Another example we shall consider is that of the existence of a solution for which we require Rank (A) = Rank (Ab). Consider the question: For what value of will the following equations admit a solution? (Note that this is a case where Cramers rule breaks down because A( = 0.)

2xi - X2 + 5Xi = 4 4 , + 6xj = 1 -2x2 + 4 = 1 +

Note that what we need to show is

Rank

2 -I 4 0 0 -2

= Rank

2-1 5 4 4 0 6 1

0 -2 4 7 +

Since rank is unaltered by taking linear combinations of rows (or columns), subtract 2 (row 1) from row 2. We get

2 -1 5 4 0 2-4-7 0 -2 4 7 +

Now add row 2 to row 3. We get

2 -1 0 2 0 0

Rank(A) = Rank

5 4

-4 -7 0

2-1 5 0 2-4

because the third row has all zeros.

Rank(Ab) = Rank Hence the required answer is = 0.

2-1 5 0 2-4

-7

= 2 only if =

Linear and Quadratic Forms

Suppose that we have the vectors a, x, and the matrix A defined as

«21 «22 «23 «31 «32 «33>

Then L = ax = a,x, + 022 + « is said to be a linear form in xs: Q = xAx = anx\ + 12.»; + oXiXj + «21>

+ «222 + «23-2-3 + «31- + «32-23 + « -

is called a quadratic form in xs. The generalization to the case of n xs is obvious. In subsequent chapters we shall need differentiation of the linear function L and the quadratic function Q with respect to the xs.

Note that aL/ , = a,, dLldXi = aj, and / = Gj. We shall denote the vector of partial derivatives

bL x

aL 2

L. -3 J

by . Thus we have dLldx SQ

a. Also,

= (g„x, + + «,3x3) 4- (a„x, + 2 + « )

with similar expressions for dQldx2 and dQldXj. Collecting these and writing in matrix notation, we get

= Ax -t- Ax = 2Ax if A is symmetric

Thus we get

-(ax) = a and -(xAx) = (A -1- A)x

We shall use this result in the Appendix to Chapter 4.