We have an k n matrix A and a k-dimensional vector b . We want to solve the line

Question

We have an k n matrix A and a k-dimensional vector b. We want to solve the linear system:

Ax = b

where x = (x1, . . . , xn) T are variables. The catch is, the system need not have a solution. What we want then is to find a vector x so that the error, computed as the sum of absolute values of the components of the vector Ax - b, is minimal. Describe the algorithm that uses A, b to output a linear program whose optimal solution gives you x (possibly along with some extra values that you can discard). The linear program does not need to be in the equational form.

Explanation / Answer

First we show:
Ax = b has at most one solution for every m x 1 matrix b if and only if Ax = 0 has at most one solution.
(=>: Set b=0.)
(<=: Let x, y satisfy Ax = b = Ay for some b. Then A(x-y) = 0 = A*0, so by assumption x-y = 0. Then x=y.)

Then write out what it means for Ax = 0 for some nonzero x in terms of the column vectors of A. You'll see it's exactly the same statement as "The columns of A are linearly dependent".

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.