Determining by hand whether a big matrix is positive definite 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!
 A: 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\}$.
