Proving that a symmetric tridiagonal matrix is positive definite

linear algebramatricespositive definitesymmetric matricestridiagonal-matrices

How to prove that the square and symmetric matrix below is positive definite?

$$A = \begin{bmatrix}
81 & -40 & \\
-40 & 101 & -40 & \\
0 & -40 & 101 & -40 & \\
0 & 0 & -40 & 101 & -40 \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & 101& -40\\
\dots & \dots & \dots & \dots & \dots & \dots & -40 & 20
\end{bmatrix}$$

I am self-studying linear algebra, and I wonder if I could prove this to be positive definite without using advanced theorems like the Gershgorin and Sylvester's criterion. What I know is, for a matrix to be positive definite, all eigenvalues must be positive or there is a vector $x$ such that $x^T Ax > 0$, where $x^T$ refers to the transposition of $x$. If I replace $-40$ by $0$, then $A$ is indeed positive definite since the diagonal entries are all positive. How could I continue this?

Best Answer

Note that $100 = 80 + 20$ and $\sqrt{80} \cdot \sqrt{20} = 40$. We have

$$ \begin{aligned} x^{\mathsf{T}} A x &= 81 x_1^2 + 20 x_n^2 + 101 \sum_{1 < i < n} x_i^2 - 80 \sum x_i x_{i + 1} \\ &= \sum (\sqrt{80} x_i - \sqrt{20} x_{i + 1})^2 + \sum_{1 \le i < n} x_i^2 \\ &\ge 0 \text{.} \end{aligned} $$

And if the RHS $= 0$, then $x_i = 0$ for all $i \in [1, n - 1]$ and hence $x_n$, too.

Related Solutions

Positivity of eigenvalues of tridiagonal, almost-Toeplitz matrix

THREE:

$$ P^T H P = D $$ $$\left( \begin{array}{rrr} 1 & 0 & 0 \\ 3 & 1 & 0 \\ \frac{ 3 }{ 11 } & \frac{ 1 }{ 11 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} - 1 & 3 & 0 \\ 3 & 2 & - 1 \\ 0 & - 1 & 2 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & 3 & \frac{ 3 }{ 11 } \\ 0 & 1 & \frac{ 1 }{ 11 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} - 1 & 0 & 0 \\ 0 & 11 & 0 \\ 0 & 0 & \frac{ 21 }{ 11 } \\ \end{array} \right) $$ $$ Q^T D Q = H $$ $$\left( \begin{array}{rrr} 1 & 0 & 0 \\ - 3 & 1 & 0 \\ 0 & - \frac{ 1 }{ 11 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} - 1 & 0 & 0 \\ 0 & 11 & 0 \\ 0 & 0 & \frac{ 21 }{ 11 } \\ \end{array} \right) \left( \begin{array}{rrr} 1 & - 3 & 0 \\ 0 & 1 & - \frac{ 1 }{ 11 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} - 1 & 3 & 0 \\ 3 & 2 & - 1 \\ 0 & - 1 & 2 \\ \end{array} \right) $$

===========================================

FOUR:

$$ P^T H P = D $$ $$\left( \begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 \\ \frac{ 3 }{ 11 } & \frac{ 1 }{ 11 } & 1 & 0 \\ \frac{ 1 }{ 7 } & \frac{ 1 }{ 21 } & \frac{ 11 }{ 21 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrr} - 1 & 3 & 0 & 0 \\ 3 & 2 & - 1 & 0 \\ 0 & - 1 & 2 & - 1 \\ 0 & 0 & - 1 & 2 \\ \end{array} \right) \left( \begin{array}{rrrr} 1 & 3 & \frac{ 3 }{ 11 } & \frac{ 1 }{ 7 } \\ 0 & 1 & \frac{ 1 }{ 11 } & \frac{ 1 }{ 21 } \\ 0 & 0 & 1 & \frac{ 11 }{ 21 } \\ 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrr} - 1 & 0 & 0 & 0 \\ 0 & 11 & 0 & 0 \\ 0 & 0 & \frac{ 21 }{ 11 } & 0 \\ 0 & 0 & 0 & \frac{ 31 }{ 21 } \\ \end{array} \right) $$ $$ Q^T D Q = H $$ $$\left( \begin{array}{rrrr} 1 & 0 & 0 & 0 \\ - 3 & 1 & 0 & 0 \\ 0 & - \frac{ 1 }{ 11 } & 1 & 0 \\ 0 & 0 & - \frac{ 11 }{ 21 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrr} - 1 & 0 & 0 & 0 \\ 0 & 11 & 0 & 0 \\ 0 & 0 & \frac{ 21 }{ 11 } & 0 \\ 0 & 0 & 0 & \frac{ 31 }{ 21 } \\ \end{array} \right) \left( \begin{array}{rrrr} 1 & - 3 & 0 & 0 \\ 0 & 1 & - \frac{ 1 }{ 11 } & 0 \\ 0 & 0 & 1 & - \frac{ 11 }{ 21 } \\ 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrr} - 1 & 3 & 0 & 0 \\ 3 & 2 & - 1 & 0 \\ 0 & - 1 & 2 & - 1 \\ 0 & 0 & - 1 & 2 \\ \end{array} \right) $$

====================================

FIVE:

$$ P^T H P = D $$ $$\left( \begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 \\ \frac{ 3 }{ 11 } & \frac{ 1 }{ 11 } & 1 & 0 & 0 \\ \frac{ 1 }{ 7 } & \frac{ 1 }{ 21 } & \frac{ 11 }{ 21 } & 1 & 0 \\ \frac{ 3 }{ 31 } & \frac{ 1 }{ 31 } & \frac{ 11 }{ 31 } & \frac{ 21 }{ 31 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrr} - 1 & 3 & 0 & 0 & 0 \\ 3 & 2 & - 1 & 0 & 0 \\ 0 & - 1 & 2 & - 1 & 0 \\ 0 & 0 & - 1 & 2 & - 1 \\ 0 & 0 & 0 & - 1 & 2 \\ \end{array} \right) \left( \begin{array}{rrrrr} 1 & 3 & \frac{ 3 }{ 11 } & \frac{ 1 }{ 7 } & \frac{ 3 }{ 31 } \\ 0 & 1 & \frac{ 1 }{ 11 } & \frac{ 1 }{ 21 } & \frac{ 1 }{ 31 } \\ 0 & 0 & 1 & \frac{ 11 }{ 21 } & \frac{ 11 }{ 31 } \\ 0 & 0 & 0 & 1 & \frac{ 21 }{ 31 } \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrr} - 1 & 0 & 0 & 0 & 0 \\ 0 & 11 & 0 & 0 & 0 \\ 0 & 0 & \frac{ 21 }{ 11 } & 0 & 0 \\ 0 & 0 & 0 & \frac{ 31 }{ 21 } & 0 \\ 0 & 0 & 0 & 0 & \frac{ 41 }{ 31 } \\ \end{array} \right) $$ $$ Q^T D Q = H $$ $$\left( \begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ - 3 & 1 & 0 & 0 & 0 \\ 0 & - \frac{ 1 }{ 11 } & 1 & 0 & 0 \\ 0 & 0 & - \frac{ 11 }{ 21 } & 1 & 0 \\ 0 & 0 & 0 & - \frac{ 21 }{ 31 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrr} - 1 & 0 & 0 & 0 & 0 \\ 0 & 11 & 0 & 0 & 0 \\ 0 & 0 & \frac{ 21 }{ 11 } & 0 & 0 \\ 0 & 0 & 0 & \frac{ 31 }{ 21 } & 0 \\ 0 & 0 & 0 & 0 & \frac{ 41 }{ 31 } \\ \end{array} \right) \left( \begin{array}{rrrrr} 1 & - 3 & 0 & 0 & 0 \\ 0 & 1 & - \frac{ 1 }{ 11 } & 0 & 0 \\ 0 & 0 & 1 & - \frac{ 11 }{ 21 } & 0 \\ 0 & 0 & 0 & 1 & - \frac{ 21 }{ 31 } \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrr} - 1 & 3 & 0 & 0 & 0 \\ 3 & 2 & - 1 & 0 & 0 \\ 0 & - 1 & 2 & - 1 & 0 \\ 0 & 0 & - 1 & 2 & - 1 \\ 0 & 0 & 0 & - 1 & 2 \\ \end{array} \right) $$

=================================

SIX:

$$ P^T H P = D $$ $$\left( \begin{array}{rrrrrr} 1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 \\ \frac{ 3 }{ 11 } & \frac{ 1 }{ 11 } & 1 & 0 & 0 & 0 \\ \frac{ 1 }{ 7 } & \frac{ 1 }{ 21 } & \frac{ 11 }{ 21 } & 1 & 0 & 0 \\ \frac{ 3 }{ 31 } & \frac{ 1 }{ 31 } & \frac{ 11 }{ 31 } & \frac{ 21 }{ 31 } & 1 & 0 \\ \frac{ 3 }{ 41 } & \frac{ 1 }{ 41 } & \frac{ 11 }{ 41 } & \frac{ 21 }{ 41 } & \frac{ 31 }{ 41 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrrr} - 1 & 3 & 0 & 0 & 0 & 0 \\ 3 & 2 & - 1 & 0 & 0 & 0 \\ 0 & - 1 & 2 & - 1 & 0 & 0 \\ 0 & 0 & - 1 & 2 & - 1 & 0 \\ 0 & 0 & 0 & - 1 & 2 & - 1 \\ 0 & 0 & 0 & 0 & - 1 & 2 \\ \end{array} \right) \left( \begin{array}{rrrrrr} 1 & 3 & \frac{ 3 }{ 11 } & \frac{ 1 }{ 7 } & \frac{ 3 }{ 31 } & \frac{ 3 }{ 41 } \\ 0 & 1 & \frac{ 1 }{ 11 } & \frac{ 1 }{ 21 } & \frac{ 1 }{ 31 } & \frac{ 1 }{ 41 } \\ 0 & 0 & 1 & \frac{ 11 }{ 21 } & \frac{ 11 }{ 31 } & \frac{ 11 }{ 41 } \\ 0 & 0 & 0 & 1 & \frac{ 21 }{ 31 } & \frac{ 21 }{ 41 } \\ 0 & 0 & 0 & 0 & 1 & \frac{ 31 }{ 41 } \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrrr} - 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 11 & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{ 21 }{ 11 } & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{ 31 }{ 21 } & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{ 41 }{ 31 } & 0 \\ 0 & 0 & 0 & 0 & 0 & \frac{ 51 }{ 41 } \\ \end{array} \right) $$ $$ Q^T D Q = H $$ $$\left( \begin{array}{rrrrrr} 1 & 0 & 0 & 0 & 0 & 0 \\ - 3 & 1 & 0 & 0 & 0 & 0 \\ 0 & - \frac{ 1 }{ 11 } & 1 & 0 & 0 & 0 \\ 0 & 0 & - \frac{ 11 }{ 21 } & 1 & 0 & 0 \\ 0 & 0 & 0 & - \frac{ 21 }{ 31 } & 1 & 0 \\ 0 & 0 & 0 & 0 & - \frac{ 31 }{ 41 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrrr} - 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 11 & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{ 21 }{ 11 } & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{ 31 }{ 21 } & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{ 41 }{ 31 } & 0 \\ 0 & 0 & 0 & 0 & 0 & \frac{ 51 }{ 41 } \\ \end{array} \right) \left( \begin{array}{rrrrrr} 1 & - 3 & 0 & 0 & 0 & 0 \\ 0 & 1 & - \frac{ 1 }{ 11 } & 0 & 0 & 0 \\ 0 & 0 & 1 & - \frac{ 11 }{ 21 } & 0 & 0 \\ 0 & 0 & 0 & 1 & - \frac{ 21 }{ 31 } & 0 \\ 0 & 0 & 0 & 0 & 1 & - \frac{ 31 }{ 41 } \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrrr} - 1 & 3 & 0 & 0 & 0 & 0 \\ 3 & 2 & - 1 & 0 & 0 & 0 \\ 0 & - 1 & 2 & - 1 & 0 & 0 \\ 0 & 0 & - 1 & 2 & - 1 & 0 \\ 0 & 0 & 0 & - 1 & 2 & - 1 \\ 0 & 0 & 0 & 0 & - 1 & 2 \\ \end{array} \right) $$

=============================

Bound on eigenvalues of hollow, tridiagonal symmetric matrix

You can go through the proof of Gershgorin circle theorem to prove strict inequality.

Let $M_n$ denote the original matrix. Suppose there exists an eigenvalue $\lambda$ of $M_n$ with $|\lambda| \geq 1$. Let $v = (v_1, \dots, v_n)^T$ be an eigenvector for $\lambda$.

Since at least one of $v_i$ is nonzero, we may divide $v$ by the maximum of $|v_i|$ and assume that the maximum of $|v_i|$ is equal to $1$. Let $k \in \{1, \dots, n\}$ be the smallest index such that $|v_k| = 1$.

If $k = 1$, then from $M_nv = \lambda v$ we get $\frac 12 v_2 = \lambda v_1$. Taking absolute values, we have $|v_2| \geq 2$ which contradicts our assumption. The same argument shows that $k = n$ leads to contradiction.

Now assume that $1 < k < n$. Again from $M_nv = \lambda v$ we get $\frac 1 2(v_{k - 1} + v_{k + 1}) = \lambda v_k$. Taking absolute values, we have $|v_{k - 1} + v_{k + 1}| \geq 2$.

However both $v_{k - 1}$ and $v_{k + 1}$ have absolute value at most $1$, hence the above inequality implies that $|v_{k - 1}| = 1$. This contradicts the minimality of $k$.

The same technique can be applied to more general matrices.

By the way, if we denote by $P_n(t)$ the characteristic polynomial of the matrix $M_n$, then the polynomials $P_n(t)$ satisfy the recurrence relation $P_{n + 2} - tP_{n + 1} + \frac14P_n = 0$, together with initial conditions $P_0 = 1$ and $P_1 = t$.

Best Answer

Related Solutions

Positivity of eigenvalues of tridiagonal, almost-Toeplitz matrix

Bound on eigenvalues of hollow, tridiagonal symmetric matrix

Related Question