## Linear Algebra and Its Applications, Exercise 1.5.10

Exercise 1.5.10. (a) Both Lc = b and Ux = c take approximately $n^2/2$ multiplication-substraction steps to solve. Explain why.

(b) Assume A is a 60 by 60 coefficient matrix. How many steps are required to use elimination to solve ten systems involving A?

Answer: (a) L is lower triangular, so we have $b = Lc \Rightarrow \begin{bmatrix} 1&&& \\ l_{21}&1&& \\ \vdots&\vdots&\ddots& \\ l_{n1}&l_{n2}&\cdots&1 \end{bmatrix} \begin{bmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{bmatrix} = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{bmatrix}$

The first entry $c_1$ can be found in a single operation, while solving for $c_2$ takes two operations, solving for $c_3$ three operations, and so on until solving for $c_n$ takes n operations.

The total number of operations is then $1 + 2 + 3 + \cdots + n = n(n+1)/2 \approx n^2/2$

We have a similar situation with Ux = c, since U is upper triangular: $Ux = c \Rightarrow \begin{bmatrix} u_{11}&u_{12}&\cdots&u_{1n} \\ &u_{22}&\cdots&u_{2n} \\ &&\ddots&\vdots \\ &&&u_{nn} \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} = \begin{bmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{bmatrix}$

Here solving for $x_n$ takes one step, solving for $x_{n-1}$ two steps, and so on until solving for $x_1$ takes n steps. Again the total number of steps is $n(n+1)/2 \approx n^2/2$.

(b) As discussed on p. 15, doing elimination on an arbitrary n by n matrix takes approximately $n^3/3$ steps for large n. As a result of performing elimination on A we obtain its two factors L and U. Given the particular system Ax = b we can use Lc = b to solve for c in approximately $n^2/2$ steps, and can then use Ux = c to solve for x, also in approximately $n^2/2$ steps, for a total of $n^2$ steps in all.

For ten systems with the same 60 by 60 matrix the total number of steps is then approximately $n^3/3 + 10n^2 = 60^3/3 + 10 \cdot 60^2= (60 \cdot 60^2)/3 + 10 \cdot 60^2$ $= 20 \cdot 60^2 + 10 \cdot 60^2 = 30 \cdot 60^2 = 30 \cdot 3,600 = 108,000$

NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition , Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books .

This entry was posted in linear algebra. Bookmark the permalink.