Solving system of linear equations with cyclic tridiagonal matrix

Question

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?

Answer 1

It is not difficult to determine the complexity of a straightforward elimination/reduction to upper triangular form. Note that the initial matrix:

$$ \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} $$

becomes after one step of elimination:

$$ \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.