Let $A$ be a large square $(n+1) \times (n+1)$ invertible matrix, where $n \approx 1000$.
$$A = \begin{bmatrix}
-1 & 0 & 0 &\cdots & 0 & a_0\\
1 & -1 & 0 &\cdots & 0 & a_1\\
0 & 1 & -1 &\cdots & 0 & a_2\\
\vdots & \vdots & \vdots &\ddots & \vdots & \vdots\\
0 & 0 & 0 &\cdots & -1 & a_{n-1}\\
0 & 0 & 0 &\cdots & 1 & a_n-1\\
\end{bmatrix}$$
What is the most efficient way to find its inverse or solve its linear equation?
Matrix $A$ is the result of a subtraction of a matrix with the identity matrix. I try to solve this to find the result of the series of a matrix and apparently Gaussian elimination method was not efficient enough.
Best Answer
Let's solve $Ax = b$. The first equation in this linear system tells us that $-x_0 + a_0 x_n = b_0$, or $$ x_0 = a_0 x_n - b_0. $$ The second equation tells us that \begin{align} & x_0 - x_1 + a_1 x_n = b_1 \\ \implies & x_1 = (a_0 + a_1) x_n - b_0 - b_1. \end{align} The third equation tells us that \begin{align} &x_1 - x_2 + a_2 x_n = b_2 \\ \implies & x_2 = (a_0 + a_1 + a_2) x_n - b_0 - b_1 - b_2. \end{align} Continuing like this, the second-to-last equation tells us that \begin{align} & x_{n-1} = (a_0 + \cdots + a_{n-1}) x_n - b_0 - \cdots - b_{n-1}. \end{align} The final equation tells us that \begin{align} &x_{n-1} + (a_n - 1) x_n = b_n \\ \implies& (a_0 + \cdots + a_{n-1}) x_n - b_0 - \cdots - b_{n-1} + (a_n - 1) x_n = b_n \\ \implies & (-1 + \sum_{i=0}^n a_i)x_n - \sum_{i=0}^n b_i = 0 \\ \implies & x_n = \frac{\sum_{i=0}^n b_i }{-1 + \sum_{i=0}^n a_i}. \end{align} We can now do back-substitution to get the values of $x_{n-1}, \ldots, x_0$.
So we can solve $Ax = b$ in linear time.