2
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Can you compute $\det A$ ? If $A$ is invertible, then your system has an unique solution. $\endgroup$ Commented Jun 22, 2016 at 14:11
  • $\begingroup$ math.stackexchange.com/questions/388829/… This question is not quite a duplicate but the desired result follows immediately from the result in this question. $\endgroup$ Commented Jun 22, 2016 at 14:23
  • $\begingroup$ This tridiagonal system has a unique solution according to the theorem here $\endgroup$ Commented Jun 22, 2016 at 14:27
  • $\begingroup$ Thanks guys, I see now. Could I also do it like this, since $A$ is tridiagonal, an $LU$ factorization exists which can be computed by Thomas algorithm. Since $A\mathbf{x}=\mathbf{b}$ iff $(LU)\mathbf{x}=\mathbf{b}$ We can solve the lower triangular system $L\mathbf{y} = \mathbf{b}$ which yields a unique solution and we can also solve the upper triangular system $U\mathbf{x} = \mathbf{y}$ resulting in $\mathbf{x}$ being unique. Also I cannot accept comment answers unfortunately! $\endgroup$ Commented Jun 22, 2016 at 14:27
  • $\begingroup$ No, because an LU factorization doesn't guarantee uniqueness. In particular, if $A$ is not invertible then neither is $U$. LU factorization only reduces us to showing that $U$ is invertible. But if, say, you replace the $2$s in the top left and bottom right corner with $1$s, the result is not invertible (constant vectors get mapped to zero; this is a feature shared by all graph Laplacians), yet your logic goes through the same way. $\endgroup$ Commented Jun 22, 2016 at 14:32

3 Answers 3

Reset to default
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Nice trick. You might briefly comment on why the solution to the recurrence has that form. $\endgroup$ Commented Jun 22, 2016 at 16:43
  • $\begingroup$ @Ian: suggestion accepted. $\endgroup$ Commented Jun 22, 2016 at 16:45
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ It's not quite a Laplacian, because of the first and last rows. The actual Laplacian of a circular graph would have a $-1$ in the top right and bottom left corners. This is important, because graph Laplacians are never invertible. $\endgroup$ Commented Jun 23, 2016 at 15:24
  • $\begingroup$ @Ian You're totally right, of course. I will delete that part. $\endgroup$ Commented Jun 23, 2016 at 15:36

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.