Consider the following matrix: $$A = \begin{pmatrix} 3 & -1 & 0 & 0 & 0 & -1 \\ -1 & 3 & -1 & 0 & -1 & 0 \\ 0 & -1 & 3 & -1 & 0 & 0 \\ 0 & 0 & -1 & 3 & -1 & 0 \\ 0 & -1 & 0 & -1 & 3 & -1 \\ -1 & 0 & 0 & 0 & -1 & 3 \end{pmatrix}$$
It was part of an exam question, where one needed to prove that it is symmetric positive definite in order to prove that both the Gauss-Seidel and Jacob method converge. I was not able to solve this by hand.
How can one approach this in the most efficient way in a time-sensitive setting? I personally tried to just calculate the eigenvalues, but failed because of the $6 \times 6$ determinant. Another approach would be to compute the determinants of the principal minors, but this also would be a lot of work for this small of a part of an exam.
Thanks!
To show that $A$ is positive semidefinite, it suffices to note that $A$ is symmetric and diagonally dominant with non-negative diagonal entries. From there, we could row-reduce to verify that $A$ is invertible.
Another approach: we can write $A$ as a sum $$ A = \begin{pmatrix} 2 & -1 & 0 & 0 & 0 & -1 \\ -1 & 2 & -1 & 0 & 0 & 0 \\ 0 & -1 & 2 & -1 & 0 & 0 \\ 0 & 0 & -1 & 2 & -1 & 0 \\ 0 & 0 & 0 & -1 & 2 & -1 \\ -1 & 0 & 0 & 0 & -1 & 2 \end{pmatrix} + \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & -1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & -1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}. $$ It is easy to compute the eigenvalues of both matrices to verify that they are positive semidefinite (the first matrix in particular is circulant). It follows that $A$ is the sum of positive semidefinite matrices and is therefore positive semidefinite.
In fact, we could also use this decomposition to see that $A$ is positive definite. For positive semidefinite matrices $B,C$, we have $$ \ker(B + C) \subset \ker(B) \cap \ker(C). $$ In this case, the two matrices being added have distinct $1$-dimensional kernels so that $\ker(B) \cap \ker(C) = \{0\}$.