## 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.