[Math] fast way to prove a tridiagonal matrix is positive definite

matricespositive definitetridiagonal-matrices

I' m trying to prove that

$$A=\begin{pmatrix}
4 & 2 & 0 & 0 & 0 \\
2 & 5 & 2 & 0 & 0 \\
0 & 2 & 5 & 2 & 0 \\
0 & 0 & 2 & 5 & 2 \\
0 & 0 & 0 & 2 & 5 \\
\end{pmatrix}$$

admits a Cholesky decomposition.

$A$ is symmetric, so it admits a Cholesky decomposition iff it is positive definite. The only methods I know for checking this are:

  1. $X^tAX > 0, \quad \forall X \in \mathbb{K}^n- \{0\}$.
  2. If $\lambda$ is an eigenvalue of $A$, then $\lambda>0.$

I have failed to prove it using 1 and 2 is taking me so much time. Is there any easier way to do this, given that $A$ is tridiagonal?

Best Answer

Notice $A$ can be rewritten as a sum of 5 matrices. $$A = \left[\begin{smallmatrix} 2 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 3 \end{smallmatrix}\right] + \left[\begin{smallmatrix} 2 & 2 & 0 & 0 & 0\\ 2 & 2 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 \end{smallmatrix}\right] + \left[\begin{smallmatrix} 0 & 0 & 0 & 0 & 0\\ 0 & 2 & 2 & 0 & 0\\ 0 & 2 & 2 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 \end{smallmatrix}\right] + \left[\begin{smallmatrix} 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 2 & 2 & 0\\ 0 & 0 & 2 & 2 & 0\\ 0 & 0 & 0 & 0 & 0 \end{smallmatrix}\right] + \left[\begin{smallmatrix} 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 2 & 2\\ 0 & 0 & 0 & 2 & 2 \end{smallmatrix}\right] $$ The first matrix is diagonal with positive entries on diagonals, so it is positive definite. The remaining four matrices are clearly positive semi-definite. Being a sum of a positive definite matrix with a bunch of positive semi-definite matrices, $A$ itself is positive definite.

Related Question