# Solving system of linear equations with cyclic tridiagonal matrix

I have this problem in my textbook:

Suggest efficient algorithm for solving system of linear equations with cyclic three-diagonal matrix, that is of the form: \begin{bmatrix} a_1&b_1&0&\cdots&0&d_1\\c_2&a_2&b_2&0&\vdots&0\\0&\ddots&\ddots&\ddots&0&\vdots\\\vdots&\vdots&c_{n-2}&a_{n-2}&b_{n-2}&0\\0&\cdots&\cdots&c_{n-1}&a_{n-1}&b_{n-1}\\d_2&0&\cdots&0&c_n&a_n\end{bmatrix} without swapping any rows and columns. Estimate complexity.

And I don't know how to approach this. Classic elimination would work in very efficient $O(n)$ time with this matrix, but the problem is when, let's say, I want to eliminate $c_{2}$ with $1$-st row that is add to second row $\frac{-c_{2}}{a_{1}}\cdot \begin{bmatrix} a_1&b_1&0&\cdots&0&d_1 \end{bmatrix}$ and when $a_1=0$. I can't do that, and even if $a_1\neq 0$ then the same problem can occur somewhere in the middle of this proccess. Moreover, as the problem text states, I am not allowed to swap any rows or columns, so I don't know if this approach can be somehow fixed. Can anybody help?

• The form of the matrix will not prevent you from running into a problem with the matrix (or a submatrix) being singular, but I don't read the problem as asking about what might go wrong. Instead by asking for an "efficient algorithm... without swapping any rows and columns", it seems that your "[c]lassic elimination" without pivoting would be a reasonable approach. Do you see how to estimate the complexity of this method? – hardmath Nov 24 '13 at 21:57

$$\begin{bmatrix} a_1&b_1&0&\cdots&0&d_1\\c_2&a_2&b_2&0&\vdots&0\\0&\ddots&\ddots&\ddots&0&\vdots\\\vdots&\vdots&c_{n-2}&a_{n-2}&b_{n-2}&0\\0&\cdots&\cdots&c_{n-1}&a_{n-1}&b_{n-1}\\d_2&0&\cdots&0&c_n&a_n\end{bmatrix}$$
$$\begin{bmatrix} a_1&b_1&0&\cdots&0&d_1\\ 0 &a_2 - \frac{b_1 c_2}{a_1}&b_2&0&\vdots&-\frac{d_1 c_2}{a_1}\\0&\ddots&\ddots&\ddots&0&\vdots\\\vdots&\vdots&c_{n-2}&a_{n-2}&b_{n-2}&0\\0&\cdots&\cdots&c_{n-1}&a_{n-1}&b_{n-1}\\0&-\frac{b_1 d_2}{a_1}&\cdots&0&c_n&a_n-\frac{d_1 d_2}{a_1}\end{bmatrix}$$
The cost of this step is constant $O(1)$, and it leaves a $(n-1)\times(n-1)$ cyclic three-diagonal submatrix in the lower right corner. Full reduction will thus entail $O(n)$ cost. To solve a linear system one might perform the same operations on the right-hand side, also an $O(n)$ cost. One also has then to perform a backsolve with an upper triangular matrix having at most three nonzero entries per row, another $O(n)$ task. So that represents the complexity of solving systems with such coefficient matrices.
• +1, thanks, but what if $a_1=0$? Then the first step will differ. And there can be complications further. Isn't that a problem? – xan Nov 25 '13 at 16:06