TABLE OF CONTENTS I'm thinking of two numbers. Their average is 3. What are the numbers?
- CLEVE B. MOLER, The World's Simplest Impossible Problem (1990)
This problem arises in important algorithms used in mathematical programming ... In these cases, B is usually very large and sparse and, because of storage difficulties, it is often uneconomical to store and access Q 1 ... Sometimes it has been thought that [the seminormal equations method] could be disastrously worse than [the Q method] ... It is the purpose of this note to show that such algorithms are numerically quite satisfactory.
- C. C. PAIGE, An Error Analysis of a Method for Solving Matrix Equations (1973)
Having considered well-determined and overdetermined linear systems, we now turn to the remaining class of linear systems: those that are underdetermined.
Consider the underdetermined system Ax = b, where 
with m ? n. The system can be analysed using a QR factorization
where 
is orthogonal and 
is upper triangular. (We could, alternatively, use an LQ factorization of A, but we will keep to the standard notation.) We have
where
If A has full rank then y 1 = R ? T b is uniquely determined and all solutions of Ax = b are given by
The unique solution x LS that minimizes x 2 is obtained by setting y 2 = 0. We have
where A
