# Compute $x = B^{-1}(2A+I)(C^{-1}+A)b$ without calculating matrix inverses

If $A, B, C$ are $n \times n$ matrices, where both $B$ and $C$ are nonsingular, and $b$ is a vector of length $n$, how would you compute the following without computing any inverses?

$$x = B^{-1}(2A+I)(C^{-1}+A)b$$

• This seems like a typical homework question in an introductory NA course. If you are having trouble with it, could you please expand on what you don't understand, instead of just posting the question statement? Feb 12 '17 at 19:37
• @Kirill I mainly don't understand where to start. Does the solution to this involve LU decomposition? The without computing any inverses part is just throwing me off completely. Feb 12 '17 at 19:41
• A hint: Calculating $x = M^{-1}y$ is equivalent to solving (for $x$) the linear system $Mx = y$ (using, for example, the LU decomposition of $M$). Feb 12 '17 at 19:51

As was mentioned in the comment, calculating $x=M^{-1}y$ is equivalent to solving $Mx=y$. Here is the full solution:

First, you can reformulate the equation to:

$Bx=(2A+I)(C^{-1}+A)b$, and by defining $\tilde{b}=C^{-1}b$, the equation can be rewritten as:

$Bx=(2A+I)(I+AC)\tilde{b}$.

First, compute $\tilde{b}$ by solving (using, for example, LU decomposition for $C$):

$C\tilde{b}=b$. Now, once $\tilde{b}$ is computed, you can define $h=(2A+I)(I+AC)\tilde{b}$ and solve, using LU decomposition,

$Bx=h$

$$\rm x = B^{-1} (2A + I) (C^{-1} + A) b$$

Left-multiplying both sides by $\rm B$,

$$\rm B x = (2A + I) (C^{-1} + A) b$$

Let $\rm y:= C^{-1} b$. Hence,

$$\rm B x = (2A + I) (C^{-1} b + A b) = (2A + I) (y + A b) = (2A + I) y + (2A + I) A b$$

and, thus, we obtain a linear system of $2n$ equations in $2n$ unknowns

$$\begin{bmatrix} \mathrm B & -(2 \mathrm A + \mathrm I)\\ \mathrm O& \mathrm C\end{bmatrix} \begin{bmatrix} \mathrm x\\ \mathrm y \end{bmatrix} = \begin{bmatrix} (2 \mathrm A + \mathrm I) \mathrm A \mathrm b\\ \mathrm b\end{bmatrix}$$

which can be solved using Gaussian elimination.