Uniqueness of solution for a tridiagonal system

Question

I have a claim I’ve been conjecturing. Not sure if it’s true or not. Context: I’m doing some calculations with finite difference schemes.

Say I have the following real $n \times n$ tridiagonal matrix $A$:

$$ \begin{bmatrix} \;\;\;2 & -1 & & &\\ -1 & \;\;\;2 & -1 & &\\ & \ddots & \ddots & \ddots\\ & & -1 & \;\;\;2 & -1 \\ & & & -1 & \;\;\;2 \end{bmatrix} $$

Does the following system have a unique solution?

$A\mathbf{U}=\mathbf{F}$ where $\mathbf{U} = \begin{bmatrix} U_{1}\\ U_{2}\\ \vdots\\ \\ U_{n} \end{bmatrix}$ and $\mathbf{F}$ is just a real vector of dimension $n$.

Observations:

Other than the fact it’s tridiagonal, I noticed that it is diagonally dominant. I also think I can compute an $LU$ factorization, but I’m not sure how that would help. Any directions?

Answer 1

Rodrigo is perfectly right, but we may prove that $A_n$ (the $n\times n$ matrix with such a structure) is invertible by simply computing its determinant through a recursive approach. An expansion along the last row gives: $$\det A_n = 2\cdot\det A_{n-1}-\det A_{n-2} \tag{1}$$ hence: $$ \det A_n = Cn +D \tag{2}$$ and since $\det A_1=2$ and $\det A_2=3$, $\color{red}{\det A_n = n+1\neq 0}$ and $A_n$ is invertible.

$(2)$ follows from the fact that the characteristic polynomial of the sequence $\{\det A_n\}_{n\geq 1}$ is $p(x)=(x-1)^2$ by $(1)$.

Answer 2

$\mathrm A$ is not merely tridiagonal, it is also Toeplitz. Hence, the $n$ real eigenvalues of $\mathrm A$ are given by [0]

$$\lambda_k (\mathrm A) = 2 + 2 \cos \left(\frac{k \pi}{n+1}\right)$$

for $k \in \{1,2,\dots,n\}$. Thus,

$$0 < 2 - 2 \cos \left(\frac{\pi}{n+1}\right) \leq \lambda_k (\mathrm A) \leq 2 + 2 \cos \left(\frac{\pi}{n+1}\right) < 4$$

and we conclude that $\mathrm A$ is invertible.

---

[0] Silvia Noschese, Lionello Pasquini, and Lothar Reichel, Tridiagonal Toeplitz Matrices: Properties and Novel Applications, 2006.

Answer 3

Note that

$$\mathrm x^T \mathrm A \mathrm x = x_1^2 + \underbrace{\left(\sum_{i=1}^{n-1} (x_{i+1} - x_i)^2\right)}_{=: f(x)} + x_n^2$$

where $f$ is positive semidefinite and vanishes on $\{\gamma 1_n \mid \gamma \in \mathbb R\}$. Fortunately, $x_1^2 + x_n^2$, which is also positive semidefinite, does not vanish on $\{\gamma 1_n \mid \gamma \in \mathbb R\}$, which allows us to conclude that $\mathrm A$ is positive definite and, thus, invertible.