29
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I would think diagonal dominance or Gershgorin discs would be easiest. Looking at the answers it seems so. $\endgroup$ – mathreadler May 12 '18 at 15:11
  • $\begingroup$ I agree, and I upvoted it but the theorem and its proof are a little bit too much for my linear algebra background. Maybe I should have added "using elementary linear algebra techniques" to the title. $\endgroup$ – Yagger May 12 '18 at 15:25
  • $\begingroup$ Ah I see now. It was not meant as a critique to the choice of answer. The one you chose was also nice. $\endgroup$ – mathreadler May 12 '18 at 15:28
44
$\begingroup$

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.

$\endgroup$
28
$\begingroup$

From Gershgorin’s disc theorem and the matrix being symmetric (real eigenvalues) you get that the eigenvalues are in the interval [1,9] and thus positive. Apparently it’s commonly known as Gershgorin’s circle theorem.

$\endgroup$
17
$\begingroup$

This particular matrix is symmetric diagonally dominant (SDD), meaning that the absolute values of each row's off-diagonal entries do not exceed the absolute value of the diagonal, ie. $$ \sum_{\substack{j\in[1,n] \\ i \neq j}} \lvert a_{i,j} \rvert \leq \lvert a_{ii} \rvert$$ Since the diagonals are positive, it is positive semidefinite, but it is actually positive definite because the inequality above is strict. This can be seen by splitting $A$ into $A = A' + \varepsilon I$ such that $A'$ remains SDD (and therefore PSD) and $\varepsilon > 0$. Multiplying on both sides by the same vector is always positive, since $\varepsilon I$ is positive definite.

$\endgroup$
11
$\begingroup$

Another approach specific to symmetric tridiagonal matrices is to use the following recurrence. Let $a_i$ be the entries of the main diagonal, and let $b_j$ be the entries of the off-diagonal. Then the determinant is given by $$ \begin{align*} d_{-1} &= 0 \\ d_0 &= 1 \\ d_n &= a_n d_{n-1} - b_{n-1}^2 d_{n-2} \end{align*} $$ This gives the series of determinants of its leading principal minors. In your case, this is: $$\begin{align*} d_1 = 4\cdot 1 - 0^2 \cdot 0 = 4 \\ d_2 = 5\cdot 4 - 2^2 \cdot 1 = 16 \\ d_3 = 5\cdot 16 - 2^2 \cdot 1 = 76 \\ d_4 = 5\cdot 76- 2^2 \cdot 1 = 376 \\ d_5 = 5\cdot 376- 2^2 \cdot 1 = 1876 \\ \end{align*}$$ Since they're all positive, Sylvester's criterion shows that the matrix is positive-definite.

Since you asked for a "fast" way, I'll note that this takes linear time to execute on a computer. I'll also note that a faster way of doing this on paper (fewer operations) is to divide the recurrence by the previous term to get $s_n = a_n - b^2_{n-1} / s_{n-1}$ with $s_0=1$ and $b_0=0$. If $a_1$ is positive and $s_n$ remains positive throughout, then the recurrence never changes sign, so $d_n$ is positive as before.

$\endgroup$
9
$\begingroup$

It is well-known that the eigenvalues of
$$ S=\begin{bmatrix} 0&1&0&0&0\\ 1&0&1&0&0\\ 0&1&0&1&0\\ 0&0&1&0&1\\ 0&0&0&1&0 \end{bmatrix} $$ are $$ 2\cos\frac{k\pi}{n+1},\ \ \ k=1,\ldots,n. $$ So the eigenvalues of $4I+2S$ are $$ 4+4\cos\frac{k\pi}{6}>0,\ \ \ k=1,\ldots,5. $$ Being symmetric, this tells us that $$4I+4S=\begin{bmatrix} 4&2&0&0&0\\ 2&4&2&0&0\\ 0&2&4&2&0\\ 0&0&2&4&2\\ 0&0&0&2&4 \end{bmatrix}$$ is positive definite. Now $A$ is also positive definite, as $A=B+4I+2S$, where $$ B=\begin{bmatrix} 0&0&0&0&0\\ 0&1&0&0&0\\ 0&0&1&0&0\\ 0&0&0&1&0\\ 0&0&0&0&1\end{bmatrix} $$ is positive semi definite.

$\endgroup$
7
$\begingroup$

Algorithm discussed at http://math.stackexchange.com/questions/1388421/reference-for-linear-algebra-books-that-teach-reverse-hermite-method-for-symmetr

This illustrates Sylvester's Law of Inertia: your matrix is, indeed, positive definite. On the other hand, you actually get a free decomposition this way, so somebody was very careful about setting this one up. With the names I use below $(2Q)^T (2Q) = H$

https://en.wikipedia.org/wiki/Sylvester%27s_law_of_inertia

$$ P^T H P = D $$ $$\left( \begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ - \frac{ 1 }{ 2 } & 1 & 0 & 0 & 0 \\ \frac{ 1 }{ 4 } & - \frac{ 1 }{ 2 } & 1 & 0 & 0 \\ - \frac{ 1 }{ 8 } & \frac{ 1 }{ 4 } & - \frac{ 1 }{ 2 } & 1 & 0 \\ \frac{ 1 }{ 16 } & - \frac{ 1 }{ 8 } & \frac{ 1 }{ 4 } & - \frac{ 1 }{ 2 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrr} 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{array} \right) \left( \begin{array}{rrrrr} 1 & - \frac{ 1 }{ 2 } & \frac{ 1 }{ 4 } & - \frac{ 1 }{ 8 } & \frac{ 1 }{ 16 } \\ 0 & 1 & - \frac{ 1 }{ 2 } & \frac{ 1 }{ 4 } & - \frac{ 1 }{ 8 } \\ 0 & 0 & 1 & - \frac{ 1 }{ 2 } & \frac{ 1 }{ 4 } \\ 0 & 0 & 0 & 1 & - \frac{ 1 }{ 2 } \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrr} 4 & 0 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 & 0 \\ 0 & 0 & 4 & 0 & 0 \\ 0 & 0 & 0 & 4 & 0 \\ 0 & 0 & 0 & 0 & 4 \\ \end{array} \right) $$ $$ Q^T D Q = H $$ $$\left( \begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ \frac{ 1 }{ 2 } & 1 & 0 & 0 & 0 \\ 0 & \frac{ 1 }{ 2 } & 1 & 0 & 0 \\ 0 & 0 & \frac{ 1 }{ 2 } & 1 & 0 \\ 0 & 0 & 0 & \frac{ 1 }{ 2 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrr} 4 & 0 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 & 0 \\ 0 & 0 & 4 & 0 & 0 \\ 0 & 0 & 0 & 4 & 0 \\ 0 & 0 & 0 & 0 & 4 \\ \end{array} \right) \left( \begin{array}{rrrrr} 1 & \frac{ 1 }{ 2 } & 0 & 0 & 0 \\ 0 & 1 & \frac{ 1 }{ 2 } & 0 & 0 \\ 0 & 0 & 1 & \frac{ 1 }{ 2 } & 0 \\ 0 & 0 & 0 & 1 & \frac{ 1 }{ 2 } \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrr} 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{array} \right) $$


$\endgroup$
5
$\begingroup$

I have failed to prove it using 1

Note: $$\begin{pmatrix}a&b&c&d&e\end{pmatrix}\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}\begin{pmatrix}a\\b\\c\\d\\e\end{pmatrix}=\\ \begin{pmatrix}4a+2b&2a+5b+2c&2b+5c+2d&2c+5d+2t&2d+5e\end{pmatrix}\begin{pmatrix}a\\b\\c\\d\\e\end{pmatrix}=\\ 4a^2+4ab+5b^2+4bc+5c^2+4cd+5d^2+4de+5e^2=\\ (2a+b)^2+(2b+c)^2+(2c+d)^2+(2d+e)^2+4e^2.$$

$\endgroup$
4
$\begingroup$

Let $I_n$ be $n\times n$ identity matrix and $$ J_n=\begin{bmatrix}0 & I_{n-1}\\0 & 0\end{bmatrix} $$ be $n\times n$ Jordan block (with zero blocks being of suitable sizes). Then $$ J_n^TJ_n=\begin{bmatrix}0 & 0\\I_{n-1} & 0\end{bmatrix}\begin{bmatrix}0 & I_{n-1}\\0 & 0\end{bmatrix}=\begin{bmatrix}0 & 0\\0 & I_{n-1}\end{bmatrix} $$ and $$ (2I_n+J_n)^T(2I_n+J_n)=4I_n+2J_n+2J_n^T+J_n^TJ_n=A $$ is the Cholesky factorization of $A$.

$\endgroup$
3
$\begingroup$

Let use Sylvester's criterion which states that a symmetric matrix is positive-definite if and only if all leading principal minors are positive.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.