Principles of Mathematics in Operations Research

44 3 Orthogonality

3.3 Summary for Ax = b

Let us start with the simplest case which is illustrated in Figure 3.5. A G R"x"
is square, nonsingular (hence invertible), rank(yl) = n = r. Thus, A represents
a change-of-basis transformation from R" onto itself. Since n = r, we have
V6 G Ti{A) = R™. Therefore, there exists a unique solution x = A~lb. If we
have a decomposition of A (PA = LU, A = QR, A = QiEQ^), we follow an
easy way to obtain the solution:

(A = LU) => Lc = b, Ux = c using forward/backward substitutions as illus-

trated in the previous chapter;

{A = QR) => Rx = QTb using backward substitution after multiplying the

right hand side with QT;

(A = Q\EQT) => x = Q-2E~lQjb using matrix multiplication operations

after we take the inverse of the diagonal matrix E simply by inverting the

diagonal elements.

1-1

••r:-&::-<

-:••:'•.•'.•'.'.•'•'• •:;:-\;;':l

' GASE"'

n ...^2        1

v

Fig. 3.5. Unique solution: b £ 11(A), A : n x n, and r = n

If A £ Rmxn has full rank r = m < n, we choose any basis among the

columns of A = [B\N] to represent 11(A) = Rm that contains b. In this case,

we have a p = n — m dimensional kernel M(A) whose elements, being the

solutions to the homogeneous system Ax = 0, extend the solution. Thus, we

have infinitely many solutions XB = B~lb — B~^1 NXN, given any basis B.

One such solution is obtained by .z'/v = 0 =4> XB = B~lb is called a basic

solution. In this case, we may use decompositions of B (B = LU, B = QR,

B = Q1EQ2) to speed up the calculations.

If A G

dim(M(A))

!mx" has rank r < m < n as given in Figure 3.6, we have

= p = n-r, dim(Af(AT)) = q = m-r and 11(A) = K(AT) = W.

The elementary row operations yield A B N
O, qxn

. There exists solution(s)

only if b G 1Z(A). Assuming that we are lucky to have b G 1Z(A), and if x
is a solution to the first r equations of Ax = b (hence to [B\N]x = b), then
x + ax, V.x G N(A) \ {0} , VQ G R is also a solution. Among all solutions
XB = B~lb — B~XNXN, XJV = 9 => XB = B~lb is a basic solution. We may
use decompositions of B to obtain XB as well.