# Solving for a single element of a solution of a linear system

I wish to solve a linear system $$A x =b$$ in which $$A$$ is dense but not too large, say no larger than $$10\times10$$. However, I am not interested in the full solution vector $$x = [x_0, x_1, \dots]$$, rather I only care about accurately determining $$x_0$$. I know that Cramer's rule can compute $$x_0$$ directly, but this requires the evaluation of two determinants. It is my understanding that calculating these determinants is not typically faster than solving the full linear system, and is also more susceptible to catastrophic cancellation.

Are there algorithms for determining $$x_0$$ alone whose expected computational complexity beats Gaussian elimination or LU factorization? Does the answer change if I am willing to accept an approximation for $$x_0$$, say from an iterative approach?

Edit:

I'll provide some additional context, which might help stimulate some ideas. In my application, I have a sequence of linear systems $$A^{(n)} x^{(n)} = b^{(n)}$$, with $$n=1,2,\dots$$ being the dimension of the system. Concretely, $$A^{(1)} x^{(1)} = b^{(1)} \to a_{00} x^{(1)}_0 = b_0 \\ A^{(2)} x^{(2)} = b^{(2)} \to \begin{bmatrix} a_{00} & a_{01} \\ a_{10} & a_{11} \end{bmatrix} \begin{bmatrix} x^{(2)}_0 \\ x^{(2)}_1 \end{bmatrix} = \begin{bmatrix} b_0 \\ b_1 \end{bmatrix}$$ and so on, with each linear system in the sequence simply appending another row and column to $$A$$ and appending an element to $$b$$, leaving the lower-order elements intact. As this sequence progresses, the value of $$x_0^{(n)}$$ should converge toward some limiting value $$x^{(\infty)}_0$$. So if it is possible to use the results of lower-order calculations $$x^{(1)},\dots,x^{(n-1)}$$ to compute $$x_0^{(n)}$$ in better than $$O(n^3)$$ time, that would be a useful answer as well.

• I think if the matrix is sparse, there are some tricks that can be used to lower the computational cost, but not the complexity. But if it is dense, I don't know any methods which can achieve what you want. Sep 18, 2021 at 6:34
• There is an $O(n^3)$ implementation of Cramer's rule, although I don't know if it would work in your case:. Ken Habgood; Itamar Arel (2012). "A condensation-based application of Cramerʼs rule for solving large-scale linear systems". Journal of Discrete Algorithms. 10: 98–109. doi:10.1016/j.jda.2011.06.007. Sep 18, 2021 at 13:34
• Apparently we need to find $x_0$ for many different cases. Is there anything in common for matrices A and vectors b for those cases? Or those are completely unrelated? I am wondering if it is possible to find $x_0$ for one given A,b and then to use that information for updated A and/or b. Sep 18, 2021 at 14:07
• Is $A$ special in any way? Symmetric, positive, non-negative, Hermitian, &c? Sep 18, 2021 at 15:03
• @MaximUmansky Very sharp observation. I've expanded the question to include more context about the problem which may help stimulate ideas along the lines of what you're thinking. Sep 19, 2021 at 2:30

You can update most matrix factorizations in $$O(n^2)$$ after adding a column and/or a row to the matrix (or, in general, after a rank-1 update). In real life, this is usually done with QR and/or Cholesky rather than other factorizations, for stability reasons; look for qrinsert in your language of choice; e.g. Python Matlab.
So in your iteration when you enlarge the system at each step you can solve the full linear systems while paying $$O(n^2)$$ per step, by relying on factorization updates: at each step, you update the factorization by adding a row ($$O(n^2)$$), then adding a column ($$O(n^2)$$), then you use the factorization to solve the linear system ($$O(n^2)$$).