$LU$ Factorization Suppose the $A\in\mathbb{R}^{n\times n}$ is nonsingular and that $A = LU$ is its $LU$ factorization. Give an algorithm that can compute, $e_i^TA^{-1}e_j$,i.e., the $(i,j)$ element of $A^{-1}$ in approximately $(n-j)^2 + (n-i)^2$ operations.
Attempted solution: We have \begin{align*}
A &= LU\\
e_i^{T}A^{-1}e_j &= e_i^{T}(LU)^{-1}e_j\\
&= (e_i^{T}U^{-1})(L^{-1}e_j)
\end{align*}
So we can construct an algorithm as so:


*

*Solve the unit lower triangular system $Lv = e_j$

*Solve the lower triangular system $U^T w = e_i$

*Evaluate $w^T v$
Now what I am confused about is showing that we have $(n-j)^2 + (n- i)^2$ computations. Any comments or suggestions is greatly appreciated.
 A: Your reasoning is correct. The goal of the exercise is to exploit the structure of the right hand side in order to reduce the number of arithmetic operations. There are a few points which I would like to make. It would be to your advantage to write 
\begin{equation}
e_i^T A^{-1} e_j = e_i^T (LU)^{-1} e_j = e_i^T U^{-1} L^{-1} e_j = (U^{-T} e_i)^T (L^{-1}e_j)
\end{equation} 
and then define $r_i$, $s_j$ as the solution of the linear system
\begin{align}
U^T r_i &= e_i \\
L s_j &= e_j
\end{align}
so that you could write
\begin{equation}
e_i^T A^{-1} e_j = r_i^T s_j.
\end{equation}
This would stress the critical point that you are not explicitly inverting matrices, but are solving linear system, i.e. computing the action of the inverse matrices. It is both more accurate and faster to proceed in this manner. 
When counting the flops you could partition the matrices conformally with the given structure. For example, if you are faced with
\begin{equation}
\begin{pmatrix}
L_{11} &  \\
L_{21} & L_{22}
\end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} f_1 \\ f_2 \end{pmatrix}
\end{equation}
and have chosen the partitioning, such that $f_1 = 0$, then it follows that the computation of $x_1=0$ can be avoided and that it only remains to solve $L_{22} x_2 = f_2$.
EDIT: In particular if $f=e_j$, then we partition $f$ as $f=(x_1,x_2)^T$ were $f_1$ is the zero vector with $j-1$ components and $f_2$ is the first column vector of the identity matrix of dimension $n-(j-1)$. We partition $L$ and $x$ conformally. We have
\begin{equation}
L_{11} x_1 = f_1, \quad L_{21} x_1 + L_{22} x_2 = f_2
\end{equation}
Since $f_1 = 0$ we know that $x_1=0$ and it is wasteful to do arithmetic operations to find these zeros. Moreover, the second equation reduces to 
\begin{equation}
L_{22} x_2 = f_2
\end{equation}
The dimension of this unit lower triangular linear system is $n_j = n-(j-1) = n - j + 1$. In general, such linear systems can be solved using $n_j(n_j-1) = (n-j+1)(n-j)$ arithmetic operations. If we want to be fanatically about the flop count, then we can save $(n-j)$ subtractions, because the $x_2$ contains $n-j$ known zeros. This gets the flop count down to $(n-j)^2$.
Exploiting the structure of the right hand side is done in the truncated Spike algorithm for solving narrow banded linear system which are also diagonally dominant by rows. Here the right hand sides are almost entirely zero with the only nonzero elements concentrated at either the top or the bottom of the vector. Moreover, there are applications in quantum mechanics and photogrammetry which require the calculation of entries of the inverse matrix, so this is not an empty exercise. 
