Show that the matrix is positive definite

Question

We have the tridiagonal matrix $A=\begin{pmatrix}2 & 1 & \ldots & 0 \\ 1 & 2 & 1 & \ldots \\ \ldots & \ldots & \ldots & \ldots \\ 0 & \ldots & 1 & 2\end{pmatrix}$. I want to show that it is positive definite.

How can we do that? Do we use the fact that it the elements of the diagonal is greater than the sum of the other elements of a row? Or do we use here something else?

Answer 1

Try to verify that its leading principal minors are all positive.

Answer 2

This is using Sylvester's Law of Inertia

Care is needed, but it is not difficult to prove the pattern indicated works for any dimension, giving $Q^T D Q = H$ for $\det Q = 1$ and $D$ diagonal positive. Indeed, $DQ$ is upper triangular, for $i < n$ we find $(DQ)_{ii} = \frac{i+1}{i}, $ while $(DQ)_{i,i+1} = 1. $ Then $(DQ)_{nn} = \frac{n+1}{n} \; . \; $

$$\left( \begin{array}{rr} 1 & 0 \\ \frac{ 1 }{ 2 } & 1 \\ \end{array} \right) \left( \begin{array}{rr} 2 & 0 \\ 0 & \frac{ 3 }{ 2 } \\ \end{array} \right) \left( \begin{array}{rr} 1 & \frac{ 1 }{ 2 } \\ 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rr} 2 & 1 \\ 1 & 2 \\ \end{array} \right) $$

$$\left( \begin{array}{rrr} 1 & 0 & 0 \\ \frac{ 1 }{ 2 } & 1 & 0 \\ 0 & \frac{ 2 }{ 3 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 2 & 0 & 0 \\ 0 & \frac{ 3 }{ 2 } & 0 \\ 0 & 0 & \frac{ 4 }{ 3 } \\ \end{array} \right) \left( \begin{array}{rrr} 1 & \frac{ 1 }{ 2 } & 0 \\ 0 & 1 & \frac{ 2 }{ 3 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 2 & 1 & 0 \\ 1 & 2 & 1 \\ 0 & 1 & 2 \\ \end{array} \right) $$

$$\left( \begin{array}{rrrr} 1 & 0 & 0 & 0 \\ \frac{ 1 }{ 2 } & 1 & 0 & 0 \\ 0 & \frac{ 2 }{ 3 } & 1 & 0 \\ 0 & 0 & \frac{ 3 }{ 4 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrr} 2 & 0 & 0 & 0 \\ 0 & \frac{ 3 }{ 2 } & 0 & 0 \\ 0 & 0 & \frac{ 4 }{ 3 } & 0 \\ 0 & 0 & 0 & \frac{ 5 }{ 4 } \\ \end{array} \right) \left( \begin{array}{rrrr} 1 & \frac{ 1 }{ 2 } & 0 & 0 \\ 0 & 1 & \frac{ 2 }{ 3 } & 0 \\ 0 & 0 & 1 & \frac{ 3 }{ 4 } \\ 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrr} 2 & 1 & 0 & 0 \\ 1 & 2 & 1 & 0 \\ 0 & 1 & 2 & 1 \\ 0 & 0 & 1 & 2 \\ \end{array} \right) $$

$$\left( \begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ \frac{ 1 }{ 2 } & 1 & 0 & 0 & 0 \\ 0 & \frac{ 2 }{ 3 } & 1 & 0 & 0 \\ 0 & 0 & \frac{ 3 }{ 4 } & 1 & 0 \\ 0 & 0 & 0 & \frac{ 4 }{ 5 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrr} 2 & 0 & 0 & 0 & 0 \\ 0 & \frac{ 3 }{ 2 } & 0 & 0 & 0 \\ 0 & 0 & \frac{ 4 }{ 3 } & 0 & 0 \\ 0 & 0 & 0 & \frac{ 5 }{ 4 } & 0 \\ 0 & 0 & 0 & 0 & \frac{ 6 }{ 5 } \\ \end{array} \right) \left( \begin{array}{rrrrr} 1 & \frac{ 1 }{ 2 } & 0 & 0 & 0 \\ 0 & 1 & \frac{ 2 }{ 3 } & 0 & 0 \\ 0 & 0 & 1 & \frac{ 3 }{ 4 } & 0 \\ 0 & 0 & 0 & 1 & \frac{ 4 }{ 5 } \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrr} 2 & 1 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 \\ 0 & 1 & 2 & 1 & 0 \\ 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 1 & 2 \\ \end{array} \right) $$

Answer 3

This is a way to show the matrix at hand, let call it $A$, is positive definite in your head.

Let $e_k$ be the $n\times 1$ column matrix with entry at $k^{th}$ row $1$ and $0$ otherwise.
One can decompose $A$ as a sum of $n+1$ positive semi-definite matrices:

$$A = \sum_{k=0}^n A_k \quad\text{ where }\quad A_k = \begin{cases} e_1 e_1^T, & k = 0\\ (e_k + e_{k+1})(e_k+e_{k+1})^T, & 1 \le k \le n - 1\\ e_n e_n^T, & k = n \end{cases}$$

So $A$ is positive semi-definite. To prove $A$ is positive definite, take any column vector $u = (u_1,u_2,\ldots,u_n)^T$ such that $$u^T A u = \sum_{k=0}^n u^T A_k u = 0$$ Since these $A_k$ are positive semi-definite, all $u^T A_k u = 0$. Look at these conditions one by one, one find: $$ \begin{align} u^T A_0 u = 0 &\iff u_1^2 = 0 \implies u_1 = 0\\ u^T A_1 u = 0 &\iff (u_1+u_2)^2 = 0 \implies u_2 = -u_1 = 0\\ u^T A_2 u = 0 &\iff (u_2+u_3)^2 = 0 \implies u_3 = -u_2 = 0\\ & \quad\vdots \\ u^T A_{n-1} u = 0 & \iff (u_{n+1}+u_n)^2 = 0 \implies u_n = -u_{n-1} =0 \end{align} $$ This means $u^T A u = 0$ only when $u = 0$. Together with $A$ is positive semi-definite, we can deduce $A$ is positive definite.